第9章 数组的应用(09_09_NIT_L)

第第9章章 数数组的的应用用(09_09_NIT_L)第1页，共59页。数组元素的查找数组元素的查找数组元素的排序数组元素的排序数组元素的插入数组元素的插入数组元素的删除数组元素的删除9.1 9.1 数组元素的查找数组元素的查找第2页，共59页。9.1.1 9.1.1 无序数组元素的查找无序数组元素的查找例例 已有宏定义已有宏定义SIZE为为100，对数组，对数组a中查找是否存在值为中查找是否存在值为20的元素的元素.数组数组:aSIZE=10,12,14,16,18,20,13,14,.134,59;找到找到,那么输出其元素所在的下标值那么输出其元素所在的下标值,并统计次数的个数并统计次数的个数.如找不到如找不到,那么输出那么输出“此数组中没有此数此数组中没有此数.第3页，共59页。#include#define SIZE 100void main()int aSIZE,i,n,m,k=0;printf(请输入数组元素的个数请输入数组元素的个数:n);scanf(%d,&n);printf(请输入数组元素请输入数组元素n);for(i=0;in;i+)scanf(%d,&ai);printf(输入查找的数输入查找的数:);scanf(%d,&m);.宏定义宏定义输入方法输入方法:1.连续输入连续输入,空格分开空格分开.或或2.输入一个数后回车输入一个数后回车.是否找到的是否找到的标志标志.第4页，共59页。for(i=0;in;i+)if(ai=m)printf(此数位于数组中的序号此数位于数组中的序号:%dn,i);k+;if(k=0)printf(此数组中没有此数组中没有%d这个数这个数n,m);else printf(此数组中有此数组中有%d个个%dn,k,m);每个元素与要找每个元素与要找的数比较的数比较.元素找到的标志元素找到的标志.第5页，共59页。例例 在数组中元素互异数据的查找在数组中元素互异数据的查找.由于各元素互异由于各元素互异,采用遍历查找，数组采用遍历查找，数组:aSIZE=10,12,14,16,18,20,13,14,.134,59,查找数组查找数组a中是否含元素值为中是否含元素值为12的元素。的元素。第6页，共59页。#include#define SIZE 10void main()int aSIZE=10,12,14,16,18,20,13,14,134,59;int x,i=0;printf(输入查找的数输入查找的数:);scanf(%d,&x);while(ai!=x)i+;if(i3,显然显然3在在a1 a5之间之间,这样就可甩掉这样就可甩掉a6 a9这一局部这一局部.假设已有按小到大排好的假设已有按小到大排好的9个数个数,a1a9:a1 a2 a3 a4 a5 a6a7a8a9 1 3 5 7 9 11 13 15 17 .其值如下其值如下:第9页，共59页。再将再将3与与a1 a3之间的居中数之间的居中数a2比较比较,这时这时数数3刚好等于刚好等于a2,查找到此完毕查找到此完毕.再找再找a1 a5之间的居中数之间的居中数,即即a3,将要找的数将要找的数3与与a3比较比较.发现发现 a33,显然显然3在在a1 a3之间之间,这样又可甩掉这样又可甩掉一半一半.a1 a2 a3 a4 a5 a6a7a8a9 1 3 5 7 9 11 13 15 17 .第10页，共59页。例例 现有降序排列的数组现有降序排列的数组:aSIZE=200,153,120,115,100,98,76,70,68,60,-90,-312；要查找值为要查找值为68的元素，如果找到，输出其下标，否那么输出无此的元素，如果找到，输出其下标，否那么输出无此数数.共共12个数据个数据.第11页，共59页。#include#define SIZE 12void main()int aSIZE=200,153,120,115,100,98,76,70,68,60,-90,-312;int m,found=0;int low=0,high=SIZE-1,mid;printf(输入查找的数输入查找的数:);scanf(%d,&m);.highlow现设输入现设输入:68Found是否查找到的标记是否查找到的标记.第12页，共59页。while(low=high)&(found=0)mid=(low+high)/2;/*确定中间位置确定中间位置*/if(mamid)high=mid-1;else found=1;if(found=1)printf(此数组中已找到数此数组中已找到数%d,它的下标为它的下标为%dn,m,mid);else printf(此数组中没有所查找的数此数组中没有所查找的数);200,153,120,115,100,98,76,70,68,60,-90,-312;High=11Low=0Mid=5在右端在右端.调整调整low.否那么否那么,调整调整high.第13页，共59页。9.2 数组的排序数组的排序9.2.1 冒泡法排序冒泡法排序 用于排序的方法有很多用于排序的方法有很多,如对于数组的排序的方法有如对于数组的排序的方法有起泡法起泡法和和选择法选择法.起泡法排序的思路是：起泡法排序的思路是：设设:对输入的元素从大到小进展排序对输入的元素从大到小进展排序.将相邻两个数比较，将大的调到上面，而小的数换到下将相邻两个数比较，将大的调到上面，而小的数换到下面。面。第14页，共59页。例例已有宏定义已有宏定义SIZESIZE为为100100，定义一个整型数组，定义一个整型数组a,a,数组元素个数数组元素个数n n与数组元素从键盘输入，对与数组元素从键盘输入，对输入的元素从大到小进展排序，最后输出排序输入的元素从大到小进展排序，最后输出排序后的数组。后的数组。假假设有一整型假假设有一整型 数组的初始元素的排列为数组的初始元素的排列为:900 2 3 58 34 76第一轮排序第一轮排序:第15页，共59页。900 900 900 900 900 900 2 2 3 3 3 3 3 3 2 58 58 58 58 58 58 2 34 34 34 34 34 34 2 76 76 76 76 76 76 2 第一次第一次第二次第二次第五次第五次结果结果 现有现有6个数，彼此两两进展比较，要进展个数，彼此两两进展比较，要进展5次次(6-1次次)比较比较.最小的最小的数数 2调到最下面。调到最下面。经过第一轮经过第一轮(5次比较次比较)后后,已得到最小数。已得到最小数。a1a2 a3 a4a5a0900 3 58 34 76 2 第一轮比较第一轮比较第16页，共59页。其实现的程序段如下其实现的程序段如下:for(j=0;j6-1;j+)if(ajaj+1)temp=aj;aj=aj+1;aj+1=temp;a1a2 a3 a4a5a0900 2 3 58 34 76 原数组原数组:如果前如果前(左左)面的数小面的数小,两两进展交换两两进展交换.第17页，共59页。然后进展第二轮比较，即对余下的然后进展第二轮比较，即对余下的5个数除最小者个数除最小者2外进展外进展 比比较。较。第二轮要比较第二轮要比较4次次5-1。900 900 900 900 900 3 3 58 58 58 58 58 3 34 34 34 34 34 3 76 76 76 76 76 3 2 2 2 2 2 第二轮比较第二轮比较第18页，共59页。如此下去，六个元素要比较如此下去，六个元素要比较 5 轮轮(6-1。第一轮中，要两两比较第一轮中，要两两比较5次，次，第二轮比较第二轮比较4次次6-2；第三轮比较第三轮比较3次次6-3;第四轮比较第四轮比较2次次6-4;第五轮比较第五轮比较1次次6-5。第19页，共59页。#include#define SIZE 100void main()int aSIZE,i,j,n,temp;printf(请输入数组元素的个数请输入数组元素的个数:);scanf(%d,&n);printf(请输入数组元素请输入数组元素:);for(i=0;in;i+)scanf(%d,&ai);.第20页，共59页。for(i=0;in-1;i+)for(j=0;jn-i-1;j+)if(ajaj+1)temp=aj;aj=aj+1;aj+1=temp;printf(从大到小排序后的数组为：从大到小排序后的数组为：n);for(i=0;in;i+)printf(%6d,ai);printf(n);外循环外循环,进展进展n-1轮的轮的控制控制.内循环内循环,每轮又进展每轮又进展(n-i-1)次比较次比较.如前如前(左左)面的数小面的数小,那么那么把小数换到后面去把小数换到后面去.第21页，共59页。9.2.2 选择排序选择排序 下面介绍下面介绍选择排序选择排序(从小到大从小到大)的算法步骤的算法步骤:(1).在未排序的在未排序的n个元素中个元素中(a0 a1 an-1)中中找到找到 最小的最小的 数数,将它与将它与a0交换交换.(2).在在剩下的剩下的末排序末排序n-1个数个数(a0 a1 an-1)中再找中再找 到最到最 小的数小的数,将它与将它与a1交换交换.a0 a1 a2 a3 a4 a5 a6 2 6 1 8 7 4 5第22页，共59页。排序是程序中常用的算法排序是程序中常用的算法,现以现以7个元素的数组为例个元素的数组为例,用用选择选择法法排序排序.a0 a1 a2 a3 a4 a5 a6 2 6 1 8 7 4 5 设排序前设排序前a数组中的数组中的7个数依次为个数依次为(无序无序):第23页，共59页。第一次选择第一次选择:在在a0a6中找最小的值中找最小的值ak,比较后确定比较后确定 k为为2:交换交换a0,ak中的值中的值,第一次排序后第一次排序后,各元素当前的值依次为各元素当前的值依次为:数组的第一数组的第一个元素有序个元素有序.原数组原数组为无为无序排列序排列.a0 a1 a2 a3 a4 a5 a6 2 6 1 8 7 4 5 a0 a1 a2 a3 a4 a5 a6 1 6 2 8 7 4 5第24页，共59页。第二次选择第二次选择:在省下的在省下的a1a6中找最小的值中找最小的值ak,比较后确定比较后确定 k为为2:交换交换a1,ak中的值中的值,第二次排序后第二次排序后,各元素当前的值依次各元素当前的值依次为为:数组的前二数组的前二个元素有序个元素有序.a0 a1 a2 a3 a4 a5 a6 1 6 2 8 7 4 5 a0 a1 a2 a3 a4 a5 a6 1 2 6 8 7 4 5第25页，共59页。第三次选择第三次选择:在省下的在省下的a2a6中找最小的值中找最小的值ak,比较后确定比较后确定 k为为5:交换交换a2,ak中的值中的值,第三次排序后第三次排序后,各元素当前的值依次为各元素当前的值依次为:数组的前三数组的前三个元素有序个元素有序.a0 a1 a2 a3 a4 a5 a6 1 2 6 8 7 4 5 a0 a1 a2 a3 a4 a5 a6 1 2 4 8 7 6 5所以所以n个数据个数据,只要进展只要进展n-1次选择次选择,即排好序即排好序.非常重要的结非常重要的结论论第26页，共59页。例例9.5 用选择法从小到大排序用选择法从小到大排序,并输出并输出.#include#define SIZE 100void main()int aSIZE,i,j,n,k,temp;printf(请输入数组元素的个数请输入数组元素的个数:);scanf(%d,&n);printf(请输入数组元素请输入数组元素:n);for(i=0;in;i+)scanf(%d,&ai);.输入要排序输入要排序的个数的个数.输入输入 n个具体数据个具体数据并赋予并赋予a数组数组.第27页，共59页。for(i=0;in-1;i+)k=i;for(j=i+1;j=n-1;j+)if(ajak)k=j;if(k!=i)temp=ai;ai=ak;ak=temp;printf(从小到大排序后的数组为：从小到大排序后的数组为：n);for(i=0;in;i+)printf(%6d,ai);printf(n);每次选择后每次选择后.交换交换 a(i)与与a(k)中的数据中的数据.a0 a1 a2 a3 a4 6 2 1 8 7 外循环控制选择外循环控制选择的次数的次数(n-1)次次.在余下的元素中选择在余下的元素中选择最小值的下标最小值的下标.用用k记录最小值记录最小值的下标的下标.开场假设开场假设i号元素最小号元素最小.第28页，共59页。第29页，共59页。9.3 数组元素的插入数组元素的插入 数组元素的插入有多种插法数组元素的插入有多种插法:1.一种是把数据插入到某个位置一种是把数据插入到某个位置,这时只要把此位置这时只要把此位置 后的元素依次后的元素依次向后向后(右右)移移,空出一位置空出一位置,然后插入此数然后插入此数.9.3.1 绝对位置的插入绝对位置的插入例例 定义一个数组定义一个数组aSIZE，数组元素无序，要求在数组中插入一，数组元素无序，要求在数组中插入一个数个数num.数组的个数数组的个数n与数组的元素、要插入的数据与数组的元素、要插入的数据num与插入的位与插入的位置置x都从键盘输入，最后输出数组。都从键盘输入，最后输出数组。第30页，共59页。第31页，共59页。#include#define SIZE 100void main()int aSIZE,num,x,n,i;printf(请输入数组元素的请输入数组元素的个数个数:n);scanf(%d,&n);printf(“请输入各数组元素请输入各数组元素:n);for(i=0;i=x;i-)ai+1=ai;ax=num;n+;printf(数组元素有数组元素有n=%dn,n);printf(插入后新数组为：插入后新数组为：n);for(i=0;in;i+)printf(%5d,ai);printf(n);把把X位置后的元素依次位置后的元素依次向后向后(右右)移移,空空出一位置出一位置,然后插入此数然后插入此数.a1a2 a3 a4a5a066 2 3 58 34 76 第33页，共59页。例例:定义一个数组定义一个数组aSIZE，假设数组元素为，假设数组元素为有序有序，从小到大，从小到大排序，要求在数组中插入一个数排序，要求在数组中插入一个数num.数组的元素个数数组的元素个数n与数组的元素、插入的数据与数组的元素、插入的数据num都从键盘都从键盘输入，要求插入数据后仍然有序，最后输出数组。输入，要求插入数据后仍然有序，最后输出数组。根据要插入的数的大小根据要插入的数的大小,通过通过查找定位查找定位,然后把此位置然后把此位置 后的后的元素依次向后元素依次向后(右右)移移,空出一位置空出一位置,然后插入此数然后插入此数.9.3.2 有序数据的插入有序数据的插入第34页，共59页。第35页，共59页。#include#define SIZE 100void main()int aSIZE,num,n,i,j;printf(请输入数组元素的请输入数组元素的个数个数:n);scanf(%d,&n);printf(“请从小到大输入数组的请从小到大输入数组的%d 元素，元素间用空格分隔元素，元素间用空格分隔.n);for(i=0;in;i+)scanf(%d,&ai);printf(请输入要插入的数据请输入要插入的数据num:n);scanf(%d,&num);.a1a2a3a4a5a0 2 3 34 58 76 90 设设num输入为输入为:55第36页，共59页。.for(i=0;inum)break;for(j=n;j=i;j-)aj=aj-1;ai=num;n+;printf(“数组共有数组共有n=%d个元素个元素.n,n);printf(插入插入%d 后新数组为：后新数组为：n,num);for(j=0;jn;j+)printf(%5d,aj);printf(n);a1a2a3a4a5a0 2 3 34 58 76 90 确定要插入的确定要插入的位置位置i.i右边的元素右边的元素依次右移依次右移.第37页，共59页。9.4 数组元素的删除数组元素的删除 例例 已定义数组已定义数组:aSIZE；数组的个数数组的个数n,各元素的数据从键盘输入各元素的数据从键盘输入(无序无序).现要删除某位置上的数值，其中删除的位置从现要删除某位置上的数值，其中删除的位置从键盘输入。键盘输入。第38页，共59页。第39页，共59页。#include#define SIZE 100void main()int aSIZE,x,n,i;printf(请输入数组元素的个数、请输入数组元素的个数、n);scanf(%d,&n);printf(请输入数组的请输入数组的%d 元素，元素间用空格元素，元素间用空格n,n);for(i=0;in|x0)printf(输入删除的位置有错输入删除的位置有错n);else break;while(1);for(i=x-1;in-1;i+)ai=ai+1;printf(删除第删除第%d 元素后的新数组为元素后的新数组为n,x);for(i=0;in-1;i+)printf(%-5d,ai);printf(n);循环保证输入的数有效循环保证输入的数有效.a1a2a3a4a5a09 7 34 5 76 11 “位置应理解为在数位置应理解为在数例中的位置值例中的位置值.把把x-1号后的元素依次前移号后的元素依次前移.第41页，共59页。第第 9 章章 数数 组组 的的 应应 用用 完毕完毕第42页，共59页。第第9章章 上机作业上机作业:第43页，共59页。P146:6.查找一字符串中是否含有单词查找一字符串中是否含有单词is.解解1:#include#define SIZE 100int main()char strSIZE,m;int i=0;printf(请输入字符串，以回车键完毕输入请输入字符串，以回车键完毕输入:n);while(stri=getchar()!=n)i+;stri=0;m=i;i=0;.第44页，共59页。while(stri!=0)if(!(striA&stria&striA&stri+3a&stri+3=m)printf(non);return 0;I am teacher.He is a student!i号元素不是字母号元素不是字母,下二个字母分下二个字母分别是别是i和和s.同时接下来的元素不是字母同时接下来的元素不是字母(应是应是空格空格).第45页，共59页。解解2:#include#define SIZE 100int main()char strSIZE,m;int i=0;printf(请输入字符串，以回车键完毕输入请输入字符串，以回车键完毕输入:n);while(stri=getchar()!=n)i+;stri=0;m=i;i=0;.第46页，共59页。while(stri!=0)if(stri=)&(stri+1=i)&(stri+2=s)&(stri+3=)printf(yesn);break;else i+;if(i=m)printf(non);return 0;He is a student!第47页，共59页。解解3:#include#include#define SIZE 100 void main()char stringSIZE;int i,word=0;char c;gets(string);.Word为为新单词出现的标志新单词出现的标志.未出现新单词未出现新单词,word=0.第48页，共59页。for(i=0;(c=stringi)!=0;i+)if(c=)word=0;else word=1;if(stringi=i&stringi+1=s&stringi+2=)printf(Yes!n);exit(0);printf(No!n);当前字符为空格当前字符为空格:未出现新单词未出现新单词,word=0,He is a student.第49页，共59页。第50页，共59页。计算字符串的有效长度，并输出该字符串。计算字符串的有效长度，并输出该字符串。字符串的字符串的有效长度有效长度:有效字符的个数有效字符的个数,即数组中第一个即数组中第一个 0 前面的字符个数前面的字符个数.例例:计算字符串的有效长度计算字符串的有效长度 str0 str1 str5 H a p p y 0?#include void main()int i=0,len;char str80=“Happy;/*初初 始始 化化 */.第51页，共59页。for(i=0;stri!=0;i+);len=i;printf(len=%dn,len);for(i=0;stri!=0;i+)/*输出字符串输出字符串*/putchar(stri);len=5Happy str0 str1 str5 H a p p y 0?i在计数在计数.第52页，共59页。补充题补充题 1:从键盘输入从键盘输入5个字符组成的单词个字符组成的单词,判断此单词是不是判断此单词是不是hello,并显示结果并显示结果.第53页，共59页。#include main()static char str=h,e,l,l,o;char str15;int i,flag;for(i=0;i=5;i+)str1i=getchar();flag=0;for(i=0;i5;i+)if(str1i!=stri)flag=1;break;if(flag)printf(This word is not hello);else printf(This word is hello);第54页，共59页。例例:输入一行字符输入一行字符,统计其中有多少单词统计其中有多少单词,单词用空格隔开单词用空格隔开.#include main()char string81;int i,num=0,word=0;char c;gets(string);num 统计单词个数统计单词个数,word用用来判断是否单词来判断是否单词的标志的标志.You are students.第55页，共59页。for(i=0;(c=stringi)!=0;i+)if(c=)word=0;else if(word=0)word=1;num+;printf(These are%d words in the line.n,num);(1).当前字符为空格当前字符为空格:未出现新单词未出现新单词,word=0,num 不不累加。累加。(2).当前字符为非空格当前字符为非空格(分两种情况分两种情况):a.前一字符为空格前一字符为空格(word=0),新词出新词出 现现,word=1,num 加加1.b.前一字符为非空格前一字符为非空格(word=1),未出未出 现新单词现新单词,num 不不加加1.You are students.第56页，共59页。从本质上来看从本质上来看,二维数组也可看作一种特殊的一维数组数组的二维数组也可看作一种特殊的一维数组数组的数组。数组。例如：例如：a34 数组可看作一个一维数组，这个一维数组有数组可看作一个一维数组，这个一维数组有 3个元素个元素,而每个元素又是有而每个元素又是有4个元素的一维数组。个元素的一维数组。a0 a00 a01 a02 a03a a1 a10 a11 a12 a13 a2 a20 a21 a22 a23 在在C语言中，二维数组中元素的语言中，二维数组中元素的排列顺序排列顺序先放第一先放第一行元素，后放第二行的元素行元素，后放第二行的元素。第57页，共59页。4.数组根本算法语句的实现数组根本算法语句的实现:(1).求数组的最小元素与下标求数组的最小元素与下标:int a710 ;int min ,p;min=a70;p=1;for(i=1;i10;i+)if(a7imin)min=ai;p=i;next i 假设第一个元素就假设第一个元素就是最小的元素是最小的元素第58页，共59页。谢谢观赏！2020/11/559第59页，共59页。