1、2023-8-2512023-8-2522023-8-2532023-8-2562023-8-2572023-8-2582023-8-2592023-8-25102023-8-25112023-8-25122023-8-2513春夏秋冬父亲儿子女儿2023-8-25142023-8-25152023-8-25162023-8-25172023-8-25182023-8-25192023-8-25202023-8-2521 入栈 退栈栈顶 top栈底 bottom在程序设计中,用一维数据组在程序设计中,用一维数据组S(1:m)作为栈的顺序作为栈的顺序存储空间,存储空间,m为栈的最大容量。为栈的最
2、大容量。top=0 表示栈空表示栈空 top=m 表示栈满表示栈满入栈运算:在栈顶插入一个新元素。入栈运算:在栈顶插入一个新元素。有两个基本操作:首先将栈顶指针进一(即有两个基本操作:首先将栈顶指针进一(即top加加1),然后将新元素插入到栈顶指针指向),然后将新元素插入到栈顶指针指向的位置。的位置。“上溢上溢”错误:当栈顶指针已指向存储空间的错误:当栈顶指针已指向存储空间的最后一个位置时,不可能再进行入栈操作。最后一个位置时,不可能再进行入栈操作。退栈运算:指取出栈顶元素并赋给一个指定的变量。退栈运算:指取出栈顶元素并赋给一个指定的变量。有两个基本操作:首先将栈顶元素赋给一个指有两个基本操作
3、:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针退一(即定的变量,然后将栈顶指针退一(即top减减1)“下溢下溢”错误:错误:top=0,栈空,不可能再进行退,栈空,不可能再进行退栈操作。栈操作。读栈顶元素:指将栈顶元素赋给一个指定的变量。读栈顶元素:指将栈顶元素赋给一个指定的变量。这个运算中栈顶指针不会改变。这个运算中栈顶指针不会改变。2023-8-25222023-8-2523Q(1:m)rear mfront122023-8-2524Q(1:8)Q(1:8)Q(1:8)876543218765432187654321rearfrontfrontrearfrontrear(a)具有6个元
4、素的循环队列(b)加入X、Y后的队列(c)退出一个元素后的循环队列2023-8-25252023-8-2526数据1数据2数据n NULLHEAD2023-8-25272023-8-25282023-8-25292023-8-25302023-8-2531书第一章第二章第三章第四章1.1节1.2节2.1节2.2节3.1节2023-8-25322023-8-25332023-8-25342023-8-25352023-8-25362023-8-25372023-8-25382023-8-25392023-8-2540FCEADBGHP2023-8-25412023-8-25422023-8-25
5、432023-8-2544二分查找又称折半查找,它是一种效率较高的查找方法。二分查找又称折半查找,它是一种效率较高的查找方法。【二分查找要求二分查找要求】:1.1.必须采用顺序存储结构。必须采用顺序存储结构。2.2.必须按关键字大小有序排列。必须按关键字大小有序排列。【优缺点优缺点】折半查找法的优点是比较次数少,查找速度折半查找法的优点是比较次数少,查找速度快,平均性能好快,平均性能好;其缺点是要求待查表为有序表,且插入删其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。的有序列表。【算法思想
6、算法思想】首先,将表中间位置记录的关键字与查找首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。或直到子表不存在为止,此时查找不成功。202
7、3-8-2545程序:程序:/找到时返回元素下标,否则返回找到时返回元素下标,否则返回0/前提:前提:a1.2.n是非递减有序的是非递减有序的#include#define N 10int binsearch(int a,int n,int x)/二分查找二分查找int mid,low=0,high=n-1;while(low=high)mid=(low+high)/2;if(x=amid)return mid+1;else if(xamid)high=mid-1;elselow=mid+1;return 0;2023-8-2546void main()int x,y,bN=7,9,12,46
8、,78,89,93,97,103,178;printf(请输入查询数据:请输入查询数据:n);scanf(%d,&x);y=binsearch(b,N,x);if(y)printf(数据已经找到,序号为:数据已经找到,序号为:%dn,y);elseprintf(数据不存在数据不存在n);2023-8-25472023-8-2548分析说明:1)相邻两数比较:ajaj+12)第一轮:6个数,j=15;循环5次,找出最大数,放在最后。3)第二轮:5个数,j=14;循环4次,找出次大数,放在最大数前。4)余此类推,经过5轮,将6个数排序输出。所以:外循环为 i=04,内循环为:j=04-i;即:fo
9、r(i=0;i5;i+)for(j=0;j5i;j+)if(ajaj+1)ajaj+1 2023-8-2549程序:程序:#include stdio.h#define N 10void popsort(int a,int n)int i,j,k;for(i=0;in;i+)for(j=0;jaj+1)k=aj;aj=aj+1;aj+1=k;2023-8-2550void main()int i,bN=123,7,9,12,7,89,93,97,103,18;popsort(b,N);printf(排序结果为:排序结果为:n);for(i=0;iN;i+)printf(%d,bi);2023-
10、8-25512023-8-2552插入排序算法思路插入排序算法思路假定这个数组的序是排好的假定这个数组的序是排好的,然后从头往后然后从头往后,如果有数比当前外如果有数比当前外层元素的值大层元素的值大,则将这个数的位置往后挪则将这个数的位置往后挪,直到当前外层元素的值大直到当前外层元素的值大于或等于它前面的位置为止于或等于它前面的位置为止.这具算法在排完前这具算法在排完前k个数之后个数之后,可以保可以保证证a1k是局部有序的是局部有序的,保证了插入过程的正确性保证了插入过程的正确性.编辑本段算法描述编辑本段算法描述一般来说,插入排序都采用一般来说,插入排序都采用in-place在数组上实现。具体
11、算法在数组上实现。具体算法描述如下:描述如下:1.从第一个元素开始,该元素可以认为已经被排序从第一个元素开始,该元素可以认为已经被排序2.取出下一个元素,在已经排序的元素序列中从后向前扫描取出下一个元素,在已经排序的元素序列中从后向前扫描3.如果该元素(已排序)大于新元素,将该元素移到下一位置如果该元素(已排序)大于新元素,将该元素移到下一位置4.重复步骤重复步骤3,直到找到已排序的元素小于或者等于新元素的位置,直到找到已排序的元素小于或者等于新元素的位置5.将新元素插入到下一位置中将新元素插入到下一位置中6.重复步骤重复步骤2 2023-8-2553#include stdio.h#defi
12、ne N 10void InsertSort(int array,unsigned int n)int i,j;int temp;for(i=1;i0&temp arrayj-1;j-)arrayj=arrayj-1;/原数组中满足条件的元素右移 arrayj=temp;/找到插入位置,插入数据 程序:程序:2023-8-2554void main()int i,bN=123,7,9,12,7,89,93,97,103,18;InsertSort(b,N);printf(排序结果为:排序结果为:n);for(i=0;iN;i+)printf(%d,bi);2023-8-25552023-8-2
13、5562023-8-25572023-8-2558程序:程序:2023-8-2559void main()int i,bN=123,7,9,12,7,89,93,97,103,18;selectionsort(b,N);printf(排序结果为:排序结果为:n);for(i=0;iN;i+)printf(%d,bi);2023-8-25602023-8-25612023-8-25622023-8-25632023-8-25642023-8-25652023-8-25662023-8-25672023-8-25682023-8-25692023-8-25702023-8-25712023-8-2
14、572加工(转换)数据流存储文件源(潭)2023-8-2573储户检验付款登录日历账卡存折检验出的问题取款单存折*取款付款信息现金年月日银行取款业务的数据流图2023-8-25742023-8-25752023-8-25762023-8-25772023-8-2578ABCDEFGH2023-8-25792023-8-2580传入数据变换数据输出数据变换型数据流结构2023-8-2581事务处理中心事务n事务2事务1输入流事务型数据流结构2023-8-25822023-8-25832023-8-25842023-8-25852023-8-25862023-8-25872023-8-258820
15、23-8-25892023-8-25902023-8-25912023-8-25922023-8-25932023-8-25942023-8-25952023-8-25962023-8-25972023-8-25982023-8-25992023-8-251002023-8-251012023-8-251022023-8-25103studentcourseSCS#SnSaGC#CnP#nm2023-8-25104学校领导领导领导院系研究所部处教研室班领导领导2023-8-251052023-8-251062023-8-25107学号学号姓名姓名语文语文数学数学物理物理化学化学2001001柳
16、迪柳迪91919393898998982001002李晓李晓89898585848489892001003石磊石磊87878181888871712001004杜鹏杜鹏71718989727285852023-8-251082023-8-251092023-8-251102023-8-251112023-8-25112A AB BC CD D1 12 23 34 47 78 85 56 67 78 83 34 41 12 25 56 61 12 24 42 2C CD D3 34 45 56 6C CD D3 34 4A AB B1 127 78 8A AB B1 12 27 78 8TRRS
17、S2023-8-25113ijij2023-8-251142023-8-251152023-8-251162023-8-251172023-8-25118S#S#SNAMESNAMECLASSCLASSC#C#TNAMETNAMETAGETAGEADDRESSADDRESSSCORESCORES1S1刘力刘力200101200101C1C1周文军周文军3838A1A17878S1S1刘力刘力200101200101C2C2曹立新曹立新2727A1A16464S2S2李军李军200101200101C1C1周文军周文军3838A1A18585S2S2李军李军200101200101C2C2曹立新
18、曹立新2727A1A16262S2S2李军李军200101200101C3C3罗晓罗晓5252A2A28585S3S3王林王林200102200102C1C1周文军周文军3838A1A17272S3S3王林王林200102200102C3C3罗晓罗晓5252A2A29393S4S4沈国立沈国立200102200102C2C2曹立新曹立新2727A1A17272S4S4沈国立沈国立200102200102C3C3罗晓罗晓5252A1A16666S4S4沈国立沈国立200102200102C4C4周文军周文军3838A1A173732023-8-251192023-8-251202023-8-251212023-8-251222023-8-25123