第四节 数组的查找-【单招零距离】计算机专业综合（下）

scanf(“％d％d”,&m,&n); for(i＝m－１;i＜n－１;i＋＋) 　　for(j＝i＋１;j＜＝n－１;j＋＋) if(a[i]＜a[j]) t＝a[i],a[i]＝a[j],a[j]＝t; printf(“ SORTEDAFTER: ”); for(i＝０;i＜１０;i＋＋) 　　printf(＂％４d＂,a[i]); 【技能实践】 　１．(１)strlen(s)　(２)i＋＋　(３)t[i＋d] 　２．(１)j＋１　 (２)i％２　 (３)t＝a[i][j] 　(４)printf(“ ”) 　３．j＜N改为j＜N－１－i 　a[j]＜a[j＋１]改为strcmp(a[j],a[j＋１])＜０ 　b＝a[j],a[j]＝a[j＋１],a[j＋１]＝b改为:strcpy(b, a[j]),strcpy(a[j],a[j＋１]),strcpy(a[j＋１],b); 　４．(１)for(i＝j＋１;i＜n－１;i＋＋ )改为for(i＝ j＋１;i＜n;i＋＋ ) 　(２)if(a[p]＞a[i])t＝i;改为if(a[p]＞a[i])p＝i; 　(３)printf(“％d“,&a[j]);改为printf(“％d“,&a[j]); 　５．charx[５];floatc; for(i＝０;i＜n－１;i＋＋) 　　for(j＝i＋１;j＜n;j＋＋) if(b[i]＞b[j]) {　c＝b[i];b[i]＝b[j];b[j]＝c; strcpy(x,a[i]);strcpy(a[i],a[j]); strcpy(a[j],x); } for(i＝０;i＜n;i＋＋) 　　printf(＂％s,％．２f ＂,a[i],b[i]); 第四节　数组的查找 【知识梳理】 　２．有序 (l＋h)/２　mid＋１ 【巩固练习】 　１．(１)left＜＝right&&flag＝＝０ 　(２)(left＋right)/２ 　(３)flag＝１ 　(４)flag 【拓展练习】 　１．(１)if(a[i]＝＝a[j])i－－ 　(２)j＝０;j＜２０－i;j＋＋ 　(３)l＜＝r&&f＝＝０ 　(４)p＝m 【技能实践】 　１．(１)left＝mid＋１; 　(２)elseif(m＜a[mid]) 　(３)right＝mid－１; 　２．srand((unsigned)time(NULL)); for(i＝０;i＜１０;i＋＋) {　a[i]＝rand()％９１＋１０; b[i]＝i; } for(i＝０;i＜１０;i＋＋) 　　printf(＂％d\t＂,a[i]); for(i＝０;i＜９;i＋＋) 　　for(j＝０;j＜９－i;j＋＋) 　　　if(a[j]＞a[j＋１]) {　k＝a[j];a[j]＝a[j＋１];a[j＋１]＝k; t＝b[j];b[j]＝b[j＋１];b[j＋１]＝t; } scanf(＂％d＂,&x); l＝０;r＝９;f＝０; while(l＜＝r&&f＝＝０) {　m＝(l＋r)/２; if(x＝＝a[m]){f＝１;p＝m;} if(x＞a[m])l＝m＋１; if(x＜a[m])r＝m－１; } if(f＝＝１) 　　printf(＂值为％d,是原数组中的第％d个.＂, x,p＋１); else 　　printf(＂NotFound!＂); 第五节　数组元素的复制、移动、插入、删除 【巩固练习】 　１．S＝１２３ 　２．１０　１１　１２　１３　１４　１５　１６　１７　１８　１９ １０　１１　１６　１７　１８　１９　１２　１３　１４　１５ 　３．１２　４５　６８　７８　６７　２３　７７　８８ 【拓展练习】 　１．２３　４５　６７　１２　３３　７８　９　９０　７７ １３　４５　３３　９０　６６　９９　１００　－６０ ４５　３　９０ k＝３ 　２．(１)i＋＋　(２)while(a[j]％２＝＝０) 　３．/∗从前往后找插入位置∗/ for(i＝０;i＜n;i＋＋) 􀅰４２􀅰 单招零距离􀅰计算机专业综合􀅰下册 单招零距离·计算机专业综合·下册 第四节 数组的查找 知识体系 顺序查找法（对数据是否有序无要求） 数组的查找 折半查找法（又称二分查找法，数据必须有序） 知识梳理 C⊙ 查找：可以分为顺序查找和折半查找法。 1.顺序查找法：按顺序由前往后依次找 printf("请输入要查找的数：n"); scanf("%d",&x); for(i=0;i<n;i++) if(a[i]==x) {printf("找到了，在%d位置处"，i);break;》 if(i==n)printf("没有该数在数组中")； 2.折半查找法：首先要求数据必须 ,然后用折半法进行查找。 下列假设数据为升序： printf("请输入要查找的数：n"); scanf("%d",&.x); f=0;l=0;h=n-1; while(f==0&.&l<h) mid= if(x==a[mid])f=1; else if (x<a[mid])h=mid-1; else 1= if(f==0) ·154· 总复习方案·第六章数组 printf("Not found! "); else printf("a%d=%d",mid,a[mid ) 典例精析 ©Y⊙ 【例1】请编程实现如下功能：输入5个整数，将他们存入数组a中，再输入1个数x,然 后在数组中查找x,如果找到，输出相应的最小下标，否则，输出“Not Found'”。 【分析】本程序从键盘输入的数应该是无序的，对于无序数据，最简捷的查找方法就是采 用顺序查找法。 【答案】 #include <stdio.h int main(void) { int i,flag,x; int a[5]; printf("Enter 5 integers:"); for(i=0;i<5;i++) scanf("%d",&ali]); printf("Enter x:") scanf("%d",&x); /*在数组中查找x*/ flag=0;/先假设x不在数组中，置flag为0 for(i=0;i<5:i++) if(a[==x) printf("Index is %d ",i); flag=1;/置flag为1，说明x在数组a中 break; } if(flag==0); printf("Not Found "); } 【例2】已知inta[30]={1,2,3,4,…,30}为升序，从键盘输入一个数x,在数组a中查 找看是否存在数x,若存在，则输出对应的位置。 #include <stdio.h> int main() int a[30],i,x; int left,right,mid,flag=-1; for(i=0;i<30;i++) ati]=i+1; printf("请输入要查找的数x=?"); ·155· 单招零距离·计算机专业综合·下册 scanf("%d",&x); left=0;right=29; while(left<=right&.&.flag==-1) { (1) ； if(a[mid]==x) //若中间数恰好等于x,则修改标志，退出循环 (2) else if(a[mid]<x) /若中间数小于x,则在右半部分去找，应修改左下标变量 left=mid+1; else /若中间数大于x,则在左半部分去找，应修改右下标变量 (3) if( (4) printf("找到，a[%d]=%dn",flag,x); else printf("查无此数！ "); } 【分析】本题重点考查的知识点是二分查找，对于升序数组，每次将待查找的数和中间数 进行学校比较，若中间数恰好等于x,则修改标志并退出循环；若中间数小于×，则在右半部分 去找，应修改左下标变量；若中间数大于x,则在左半部分去找，应修改右下标变量。 【答案】(1)mid=(left+right)/2(2)flag=mid (3)right=mid-1(4)flag！=-1或left<=right 巩固练习 ⊙S 1.下列程序的功能是从一个有序序列中采用对半查找的方法查找一个数是否存在，请在 空白处填写合适的内容。 #include <stdio.h> int main() {inta[10]={1,4,6,10,20,22,33,37,41,50}; int left,right,middle,x,flag=0; scanf(“%d”,&.x): left=0; right=9; while((1) ) middle=(2) if(a[middle]==x) { (3) break;} else if(a[middle]<x) left=middle+1; else ·156· 总复习方案·第六章数组 right=middle-1; if( (4) printf(“%d在数组a中”，x); else printf(“%d不在数组a中”，x); 拓展练习 2 C 1.程序填空题：随机产生20个[10,100]互不相同的整数，放在数组a中，再从键盘上输入 一个x整数，用二分法查找是否存在该数，若存在则输出该数及其原始位置，其中b数组是用 来记录原始数组位置的。请填写合适的内容。 #include <stdio.h> #include <stdlib.h include <time.h> int main() int x,a[20],i,j,k,t,1,r,m,p,f; intb[20]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}; srand((unsigned)time(NULL)); /产生互不相同的随机数并输出/ for(i=0;i<20;i++) {a[i]=rand()%91+10; for(j=i-1;j>=0;j--） (1)； } for(i=0;i<20;i++) printf("%d ",ai]); /排序并输出*/ for(i=1;i<=19;i++) {for((2)) if (a[j]>a[j+1]) {k=a[j];a[j]=a[j+l];a[j+1]=k; t=b[j];b[G]=bG+1];bG+1]=t: for(i=0;i<20;i++) printf("%d,%dt",a[i],b[i门+1)； /*二分法查找*/ scanf("%d",&.x); ·157· 单招零距离·计算机专业综合·下册 1=0;r=19;f=0; while (3)) {m=(1+r)/2; if(x==a[m]){f=1;(4);} if(x>a[m])1=m+1; if(x<a[m])r=m; } if(f==1) printf("值为%d,是原数组中的第%d个."，x,p十l); else printf("no found!"); 技能实践 ⑤ 1.程序改错题：N个已按升序排序好的整数数列放在一堆数组a中，下列给定程序中，函 数fu的功能是：利用折半查找算法查找整数m在数组中的位置。若找到，则返回其下标值； 反之，则返回一1。 #include <stdio.h define N 10 int fun(int a[],int m) intleft=0,right=N-1,mid; while(left<=right) { mid=(left+right)/2; if(m>a[mid]) right =mid-1; /*米0米米米**米米兴米米米FOUND0米米米*米米米￥并米米米米关/ else if (m<=a[mid]) /米*米并米米米***米*米米F○UND00关米关米*著关关米兴米关关*/ left mid +1; else return (mid); } return(-1); } 2.程序设计题：随机产生10个两位数存入数组intx[10]中，从键盘输入一个数x,采用二 分查找法查找该数在数组x是否存在，若存在则输出该数处于数据序列中的位置；若不存在， 则输出信息“Not Found!”。 #include <stdio.h ·158· 总复习方案·第六章数组 #include <stdlib.h #include <time.h #define N 10 int main() { int x,a[20],i,j,k,t,l,r,m,p,f; /关并关养茶茶茶关关关0米米米米米米BEGIN米关米米米米举米*举养养0**米 第五节 数组元素的复制、移动、插人、删除 知识体系 ⊙⊙ 数组元素的复制 数组元素的移动 基本算法（一） 数组元素的插入 数组元素的删除 知识梳理 一、数组元素的复制 数组元素的复制是采用赋值语句来实现的，其中包括将一维数组或二维数组的元素全部 (或指定的要求的数据)复制到另一个一维或二维数组中。 通常采用if语句来选择所要求的数据。 二、数组元素的移动 数组元素的移动，主要指数组中元素的位置发生变化。通常是指不改变相邻元素的位置。 分为（循环左移和循环右移）。有时也有特定的移位。 请注意第一个要移动的数据必须先保存到另一个变量中。 三、数组元素的插入 数组元素在数组中插入后，其后的数组元素均要向后（向右）移动一位，此时要注意先移动 那一个是特别要注意的。插入分为：指定位置的插入和有序的插入两种情况 四、数组元素的删除 数组元素在数组中删除之后，其后的数组元素要向前（向左）移动一位进行覆盖原数据。 同时数组元素的个数应少一个。删除分为：指定位置的删除和特定条件的删除。 ·159·