第7章_一维数组

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章,数 组,江苏大学计算机学院,7.1一维数组的定义和引用,例1：输入50个数，要求按输入时的逆序打印这50个数。,例2：输入100个学生某门功课的成绩，要求把高于平均分的那些成绩打印出来。,例1：输入50个数，要求按输入时的逆序打印这50个数。,main(),int,a1,a2a50;,scanf,(“%d”,scanf,(“%d”,printf,(“%d”,printf,(“%d”,例2：输入100个学生某门功课的成绩，把高于平均分的那些成绩打印出来。,main(),int,a1,a2a100，,ave,;,scanf,(“%d”,scanf,(“%d”,ave,=(a1+a100)/100;,if(a1,ave,),printf,(“%d”,if(a100,ave,),printf,(“%d”,7.1一维数组的定义和引用,数组的定义：,数组类型、数组名、维、维长,数组元素的表示：,数组下标从0开始,7.2一维数组应用举例,1.求,Fibonacci,数列前20项：,实例7_2_2,a,1,=1,a,2,=1,a,n,=a,n-1,+a,n-2,main(),int,i,a20;,a0=1;,a1=1;,for(i=2;i20;i+),ai=ai-1+ai-2;,for(i=0;i=0;j-),if(aj9),putchar,();,else,putchar,(aj+0);,aj-10+A,一维数组初始化(前几例均为在程序运行时数组得到值,),定义数组时实现,初始化,，方法如下：全体赋值：,int,a10=0,1,2,3,4,5,6,7,8,9；,部分赋值：,int,a10=0,1,2,3,4；,/*a5a9,均为0*/省略维长：,int,a=0,1,2,3,4；,/*,维长为5*，等同于,a5,/,清零赋值：,int,a10=0,0,0,0,0,0,0,0,0,0；,int,a10=0；,在运算过程中，,只能,对数组元素赋值，赋值方法同普通变量,7.1一维数组的使用,排序算法,实例7_2_3 起泡排序,：将由键盘输入的十个数由小到大排列。,实例7_2_4 插入法排序,：将,N,个数由大到小排列,实例7_2_5 两路合并：,将两个已按升序排列的数组合并成一个升序数组,实例7_2_6 选择排序：,将,N,个数由小到大排列,检索算法,实例7_2_7 顺序检索：,在一个数组中查找是否存在关键字,实例7_2_8 二分检索：,对已排序的序列检索是否存在关键字,7.1一维数组的使用,为了方便理解，数组下标一律从1开始,7.2 一维数组应用举例,例：输入4个整数，要求按由小到大的顺序输出,if(ab)t=a;a=b;b=t;,if(ac)t=a;a=c;c=t;,if(ad)t=a;a=d;d=t;,if(bc)t=b;b=c;c=t;,if(bd)t=b;b=d;d=t;,if(cd)t=c;c=d;d=t;,7.2 一维数组应用举例,3.排序算法冒泡排序：,实例7_2_3,冒泡,法,排序,15,8,4,13,6,10,17,1,8,15,4,13,6,10,17,1,8,4,15,13,6,10,17,1,8,4,13,15,6,10,17,1,8,4,13,6,15,10,17,1,8,4,13,6,10,15,17,1,8,4,13,6,10,15,17,1,8,4,13,6,10,15,1,17,例如，对,15,8,4,13,6,10,17,1,按由小到大顺序排序,第一轮（趟）,结果为,8,4,13,6,10,15,1,17,其中最后一个数17位置已经确定,两两比较，比较次数为7=8-1,冒泡,法,排序,8,4,13,6,10,15,1,17,4,8,13,6,10,15,1,17,4,8,13,6,10,15,1,17,4,8,6,13,10,15,1,17,4,8,6,10,13,15,1,17,4,8,6,10,13,15,1,17,4,8,6,10,13,1,15,17,第二轮（趟）,8,4,13,6,10,15,1 17,结果为,4,8,6,10,13,1,15,17,其中数15，17位置已经确定,比较次数为6=8-2,冒泡,法,排序,4,8,6,10,13,1,15,17,4,8,6,10,13,1,15,17,4,6,8,10,13,1,15,17,4,6,8,10,13,1,15,17,4,6,8,10,13,1,15,17,4,6,8,10,1,13,15,17,第三轮（趟）,4,8,6,10,13,1 15 17,结果为,4,6,8,10,1,13,15,17,其中数13，15，17位置已经确定,比较次数为5=8-3,冒泡,法,排序,4,6,8,10,1,13,15,17,4,6,8,10,1,13,15,17,4,6,8,10,1,13,15,17,4,6,8,10,1,13,15,17,4,6,8,1,10,13,15,17,第四轮（趟）,4,6,8,10,1 13 15 17,结果为,4,6,8,1,10,13,15,17,其中数10,13,15,17位置已经确定,比较次数为4=8-4,冒泡,法,排序,4,6,8,1,10,13,15,17,4,6,8,1,10,13,15,17,4,6,8,1,10,13,15,17,4,6,1,8,10,13,15,17,第五轮（趟）,4,6,8,1 10 13 15 17,结果为,4,6,1,8,10,13,15,17,其中数8,10,13,15,17位置已经确定,比较次数为3=8-5,冒泡,法,排序,4,6,1,8,10,13,15,17,4,6,1,8,10,13,15,17,4,1,6,8,10,13,15,17,第六轮（趟）,4,6,18 10 13 15 17,结果为,4,1,6,8,10,13,15,17,其中数6,8,10,13,15,17位置已经确定,比较次数为2=8-6,冒泡,法,排序,4,1,6,8,10,13,15,17,1,4,6,8,10,13,15,17,第七轮（趟）,4,16 8 10 13 15 17,结果为,1,4,6,8,10,13,15,17,所有数的位置均已经确定,比较次数为1=8-7,7.2一维数组应用举例,j=1;j=n-1;j+,i=1;iai+1（,从小到大排序）,Y,N,交换,t=ai;ai=ai+1;ai+1=t,n:,参与比较的数的个数,4.排序算法插入法排序：,实例7_2_4,while(j=1&maj),aj+1=aj；,i=2;i=n;i+,m=ai;j=i-1；,j-;,aj+1=m;,（,从小到大排序）,例，有整型数组,a4,未排序前各元素的值分别为：,10,8,3,9,插入法升序排序各遍执行的结果如下所示：,初 始,10,8 3 9,第一遍 8 10 3 9,第二遍 3 8 10 9,第三遍 3 8 9 10,5.排序算法两路合并排序：,实例7_2_5,while(i=n)&(j=m),while(i=n),ck+=ai+,while(jbj,y,n,ck+=bj+,ck+=ai+,从小到大排序,6.排序算法选择排序：,实例7_2_6,选择,法,排序,15,8,4,13,6,10,17,1,1,8,4,13,6,10,17,15,1,4,8,13,6,10,17,15,1,4,6,13,8,10,17,15,1,4,6,8,13,10,17,15,例如，对,15,8,4,13,6,10,17,1,按由小到大顺序排序,i,=,第一趟,第二趟,第三趟,第四趟,第五趟,第六趟,第七趟,1,4,6,8,10,13,17,15,1,4,6,8,10,13,17,15,1,4,6,8,10,13,15,17,i=1;i=n-1;i+,min=i;,j=i+1;jaj,Y,N,min=j,t=ai;ai=amin;amin=t,（,从小到大排序）,7.检索算法顺序查找：,实例7_2_7,(共有,n,条记录，查找是否有关键字为,x,的记录),for(i=1;in),printf,(Cant found!);,8.检索算法折半查找,：,实例7_2_8,适用于已排好序的数组,mid=(,bott,+top)/2;,if(num=amid),printf,(Found!The index is:%dn,mid);,break;,while(!(top,bott,),if(top,bott,),printf,(Cant found!n);,else if(num amid),bott,=mid-1;,else,top=mid+1;,9.,洗牌程序：将有序的13张牌,，,随机打乱,实例7_2_1,A,for(i=0;i13;i+),ai=i+1;,for(i=0;i13;i+),p=,rand,()%13;,t=ap;,ap=,;,=t;,a12-p,a12-p,10.,老鼠出列问题：有20个老鼠围成圈,，,每数到3时该老鼠出列，给出老鼠出列的顺序。,实例,K033005,int,aN,bN,i,j,n=0;/*i,是,a,数组下标；,n,是,b,数组下标*/,for(i=0;iN;i+)ai=i+1;/*,产生序列*/,i=0;j=0;,while,循环何时终止？,(nN),j+;/*,计数器增一*/,i+;/*,遍列数组*/,if(i=N-1)/*,数组越界*/,i=0;/*,回到数组开始位置*/,if(ai)/*,对未出列老鼠计数*/,if(j=M)/*,计数器到位*/,bn+=ai;/*,出列*/,ai=0;/*,打上出列标志*/,j=0;/*,计数器复位*/,作业,1.已知递推公式：,A1=0,A2=1,A3=2,An=An-1+2*An-2An-3,用数组求前20项的值。,2.编写程序，随机生成2组20个100以内的整数，第一组用插入排序，第二组用选择排序，最后用两路归并实现从小到大排序，要求输出原始数据和排序后的数据（输出时每行10个数）,3.用筛选法求1000以内的所有素数,每行输出10个,