搜索
第4章构造数据类型第一部分数组通过本节实验作业应达目标1．学习并掌握一维数组与二维数组的定义、使用及初始化方法。2．熟练掌握字符数组和字符串的使用方法。3．掌握数组的一种排序算法。4．学会用数组保存多个相关的同类数据，并对这一组数据进行各类操作。本章必须上交作业第一部分数组作业要求：程序4_3.c、4_4_2.c、4_5.c、4_7.c、4_8.c上传至。源程序可以.cpp命名。第二部分结构体作业要求程序4_11.c、4_12.c上传至。源程序可以.cpp命名。实验一一维数组的定义和简单应用【实验目的】学会定义一维数组，掌握一维数组的遍历操作，掌握在一组数组中求最大值、最小值的方法。【实验内容】从键盘读入5个成绩到一个数组中，求其中的最大值，最小值和平均成绩。在屏幕上显示输入成绩的提示信息，用键盘输入一个成绩，接着提示输入下一个，直到结束。以4_1.c命名本程序。程序运行界面【实验提示】求最大（小）值通常用“打擂台”的方法。首先设计两个变量，如max和min分别用来存放最大值和最小值，并将数组的首元素赋给这两个变量，这就是到目前为止的最大（小）值，然后利用循环依次比较其他的元素，总是将当前最大（小）值赋给max和min，直至比较到最后，max和min中的数据就是最大值和最小值。求平均值还要设置一个变量sum，用来累加各元素的值。实验二一维数组的排序【实验目的】熟练掌握一维数组三种基本排序方法：选择法，冒泡法，比较法。【实验内容】从键盘上接收10个成绩，存放到一个一维数组score中，分别利用三种排序方法，将数组从小到大排序并在屏幕上显示排序结果。分别以4_2_1.c、4_2_2.c和4_2_3.c命名三个程序。【实验提示】所谓排序是指把一组杂乱无章的数据按照大小顺序排列。将被排序的n个数据存放在一个数组中,假如按升序排列。我们将数组定义为a[n]，数据存放在a[0]到a[n-1]中。1．比较排序法将a[0]与a[1]比较，若a[1]a[0]，则a[0]与a[1]交换，否则不变，再将a[0]与a[2]比较，同样小者交换到a[0]，……如此比较下去至到a[0]与a[n－1]比较，小者放到a[0]中，第一轮比较n-1次，a[0]中的值就是n个数中最小者。然后a[1]再与a[2]比较，方法同上，小者交换到a[1]，……第二轮比较n-2次，这样a[1]也就确定了，第三轮a[2]与其后面的数比较，……，共比较n-1轮以后，数组中各元素的值就按升序排列好。2．选择排序法选择排序法就是对比较法的改进。它的算法思想是：仍然是a[i]与其后的a[j]进行比较，但是当比较出a[j]小于a[i]时，先不急于交换（因为a[j]并不一定是这一轮中最小的，可能还有更小的），用一个变量p记下j的下标（即第几个数），继续比较下去，将最小数的下标j存放在p中，一轮比较完毕，a[p]便是最小的，这样只要a[i]与a[j]交换即可。一轮只交换一次，大大提高了程序的效率.其中，一维数组既是数据的存放位置，也是交换的场所，这样可以很好的利用数据的内存空间。3．冒泡排序法将要排序的数放在某一个数组中，如a[0]~a[n－1]，然后比较数组相邻两元素的值，即a[0]与a[1]比较，假如按升序排列，且a[0]a[1]，则二者交换，否则不变，a[1]再与a[2]比较，前者大就交换，…，依次两两比较至到a[n-2]与a[n-1]比较，经过一轮以后，最大者“沉”到了最后，小数往上“冒”，所以得名“冒泡法”。第二轮比较数组的前n-1个，即a[0]~a[n-2]。重复此过程，直到所有的元素比较完毕。实验三一维数组元素的调换【实验目的】进一步加强对数组的应用。【实验内容】找出数组中的最小数和次小数，并把最小数和a[0]中的数对调、次小数和a[1]中的数对调，其余数据位置不变。例如，程序运行时若输入：24611397058，则输出：02611397458。以4_3.c命名本程序并上交，部分程序如下。#defineN10voidmain(){inta[N],i;for(i=0;iN;i++)scanf(%d,__________);…………/*编写程序，实现功能*/for(i=0;iN;i++)printf(%d,a[i]);printf(\n);}【实验提示】本题既可以套用选择法排序，只排序两轮。也可以两次求最值再互换。实验四一维数组的查找【实验目的】掌握数组的基本查找方法：顺序法和折半查找法。【实验提示】查找是计算机中经常要遇到的一种操作，其含义是在一组数据中查找到所查数据的位置。比较简单的是顺序查找法，效率较高的是折半查找法。1．顺序查找法顺序查找也叫线性查找，当一组数据无序时，一般采用顺序查找。其基本思想是：从数据集的第一个元素开始，依次将关键字x与数据集中的每一个元素进行比较，直到找到要找的数据。或者数据集遍历完毕，没有找到匹配元素。2．折半查找法若是已经排好序的数据，最好采用折半查找法。折半查找法的基本思想是：首先取第一个元素a[low]和最后一个元素a[high]中间的那个元素a[mid]与x比较（其中mid=(low+high)/2），如果a[mid]==x则正好找到，否则要看x比a[mid]大还是小，因假设数组已按降序排好，则当xa[mid]时，则要查找的x在数组的前半部分，这样数组的后半部分就不用去查找了，查找范围缩小为一半。然后在前半部分再找一个中点，与x比较，如此一半一半缩小，如果x在数组当中，终能找到x==a[mid]。由于每次缩小近一半的范围，所以数组的上、下界是要变化的，不妨用变量low、high、mid分别表示数组当前的上界、下界和中点。问题：如果x不在数组当中，最终怎样知道？【实验内容】在一个已经排好序的数组（升序）中，从键盘上输入某数x，查找x是否在数组内，若在，则在屏幕上输出其下标值。若不存在，则在屏幕上显示“Notfound！”。假设数组a[10]的每个元素分别为{1,2,3,4,6,7,9,10,11,15}，若从键盘上读入数x为9，则在屏幕上输出“thenumber’spositionis7”，若读入数为8，则屏幕上输出“Notfound!”。1.顺序查找法编写的程序如下，请完善程序，并以4_4_1.c命名本程序。#includestdio.h#defineN10voidmain(){inta[N]={1,2,3,4,6,7,9,10,11,15};inti,x;scanf(%d,&x);for(i=0;iN;i++)if(_________){printf(thenumber'spositionis%d\n,i+1);_________;}if(i==N)printf(Notfound!\n);}2.折半查找法编写的程序如下，请完善程序，并以4_4_2.c命名本程序并上交。#includestdio.h#defineN10voidmain(){inta[N]={1,2,3,4,6,7,9,10,11,15};intlow,high,mid,i,x;scanf(%d,&x);for(low=0,high=N-1;;){mid=_________;if(a[mid]==x){printf(thenumber'spositionis%d\n,mid+1);break;}if(_________){printf(Notfound\n);_________;}if(a[mid]x)low=mid+1;if(a[mid]x)_________;}}【讨论与思考】比较一下两种两种查找方法的优缺点。实验五二维数组使用【实验目的】掌握二维数组的使用方法。【实验内容】一个小组五位同学，选修了相同的4门功课。请输入每位同学的成绩，计算每位同学的总分，找出总分最高的同学是第几号同学，最后按总分对二维数组排序，并输出排序后的每位学生信息。以4_5.cpp或4_5.c命名本程序并上交。每位同学的信息如下表：学号S1S2S3S4total100145687891100265788488100392866878100466747381100590706567示例的输入输出窗口如下：【实验提示】定义的二维数组需要保存学号与总分信息。学号可以初始化的方式记录在第0列中。本题涉及到求最大值与排序操作。注意，排序交换数据时需要一整行都交换。实验六统计指定字符个数【实验目的】熟悉字符串的存取和结束标记。【实验内容】编写程序从键盘上输入一个字符串和一个字符，统计所指定字符的个数。例如：从键盘输入字符串为abaaAAbcaaaca，指定字符为'a'，则在屏幕上输出结果是7。以4_6.c命名本程序。下面给出程序的部分代码。#includestdio.hvoidmain(){chara[200],b;intnum;puts(Pleaseinputastring：);gets(a);puts(Pleaseenteracharacter:);b=getchar();…………/*编写程序，实现功能*/pirntf(“Theresultis%d\n”,num);}实验七从字符串中删字符【实验目的】熟悉字符串的存取和结束标记。并掌握从一维数组中删除元素的方法。【实验内容】编写程序从键盘上输入一个字符串和一个字符，实现从字符串中删除该字符。例如：从键盘输入字符串为abaaAAbcaaaca，要删除的字符为'a'，则在屏幕上输出bAAbcc。下面给出程序的部分代码。请完善程序，并以4_7.c命名本程序并上交。voidmain(){chars[20],ch;inti,j;printf(Pleaseinputastring:\n);gets(s);printf(Pleaseinputacharacter:\n);ch=getchar();for(i=0;_________;i++){…………/*编写程序，实现功能*/}puts(s);}【实验提示】要考虑被删除的字符在字符串出现多次，而且连续排列的情况。实验八数据加密【实验目的】学习通过字符数据的ASCII值进行加密的方法。【实验内容】某个单位要传递机密数据，数据是一组的整数数字（从键盘输入，长度不大于30个字符）。在传递过程中是加密的，加密规则如下：每位数字都加上5，然后用该和除以10的余数代替该数字。在屏幕上显示加密后的数字。以4_8.c命名本程序并上交。例如：输入数据327895123，显示结果为：872340678。【实验提示】1．应用字符数组来解决该问题。2．主程序中将各位数字以字符的形式存放，在加密的过程中应该注意‘0’跟0的区别。实验九将数字字符串转换为相应实数【实验目的】学习数字字符串与数值之间的转换问题。【实验内容】将键盘上输入的一个数字字符串转换为相应的实数，在屏幕上输出。转换时遇到第一个非数字字符时停止（不包含第一个小数点和起始的负号-）。例如：若输入字符串“123a45”，得到实数x=123.0；若输入字符串“-123.45.765”，得到实数x=-123.45；若输入字符串“123-56.78”，得到实数x=123.0；若输入字符串“-.123”，得到实数x=-0.123。下面给出不考虑负数的程序，请在下述程序的基础上补充完善为也能考虑负数的程序，并以4_9.c命名本程序。#includestdio.hvoidmain(){charstr[100];inti,sign;doublex,k;gets(str);/*str中存放的是一个数字字符串*/sign=1;k=0.1;/*sign是一个标志，标识是否出现了第一个小数点*/x=0;for(i=0;str[i];i++){if(sign==1)if(str[i]='0'&&str[i]='9')x=x*10+（str[i]-48）;elseif(str[i]=='.')sign=0;elsebreak;elseif(str[i