C语言程序设计与数据结构

1、要求： 掌握一维数组的定义及应用； 掌握二维数组的的定义及应用应用； 掌握字符数组及字符串处理函数的应用； 掌握数组在函数中的应用及常用的查找、排序方法。 重点： 一维数组及二维数组的应用； 数组在函数中的应用及常用的排序方法。 主要内容 7.1 一维数组 7.2 二维数组 7.3 字符数组 7.4 数组在函数中的应用 7.5 折半查找 7.6 数组元素排序 7.7 典型习题分析解答 7.1 一维数组 7.1.1 一维数组的定义与初始化 一维数组的定义 一维数组的定义格式为： 类型说明符 数组名 常量表达式； 说明： (1) 数组的类型指数组元素的取值类型。对于上例，即说明该数

2、组a中的10个元素都是整型。 (2) 数组名必须是合法标识符，也就是说必须符合标识符的命名规则； (3) 数组名不能与同一程序中的其它变量同名； (4) 若用方括号中的整数n来表示数组元素的总数，则数组的第一个元素的下标为0（称为数组 下标的下界），最后一个为n-1（称为数组下标的上界）。对于上例，数组中含有10个元素，分 别是：a0,a1,a2,a9。 (5) 不能在方括号中用变量来表示元素的个数。 (6) 允许在同一个说明中，说明相同类型的多个数组和多个变量。 (7) 可以使用在编译预处理#define中定义的符号常量。 一维数组的初始化 初始化赋值的一般形式为： 类型说明

3、符 数组名常量表达式=值，值值； 其中在 中的各数据值即为各元素的初值，各值之间用逗号间隔。 例如： int a10= 0,1,2,3,4,5,6,7,8,9 ; 说明： （1）可以只给部分元素赋初值。 当 中值的个数少于元素个数时，只给前面部分元素赋值。 例如： int a10=0,1,2,3,4; 表示只给a0a4这5个元素赋值，而后5个元素自动赋0值。 （2）能给元素逐个赋值，但不能给数组整体赋值。 例如给十个元素全部赋1值，只能写为： int a10=1,1,1,1,1,1,1,1,1,1; 而不能写为： int a10=1; （3）如给全部元素赋值，则在数组说明中， 可以不给出数组元

4、素的个数。 例如： int a5=1,2,3,4,5; 可写为： int a=1,2,3,4,5; 7.1.2 一维数组元素的引用 数组元素引用的一般形式为： 数组名下标 其中的下标只能为整型常量或整型表达式。如果为小数时，C编译将自动取整。例如， a6,bi+j,bi+都是合法的数组元素。 数组元素通常也称为下标变量。必须先定义数组，才能使用下标变量。在语言中只能逐个地使用 下标变量，而不能一次引用整个数组。例如，单独使用一个下标变量： int a10; a7=6; 7.1.3 一维数组元素的赋值 数组定义之后，如果不对其进行初始化，则其值可通过赋值语句获 或者可从键盘、文件等读取获得。现以

5、从键盘接收数据为例： 【例7.1】从键盘输入十个数据给数组a赋值，然后把数组a的值复制到数组b中。 main( ) int a10,b10,i; for(i=0;i10;i+) scanf( %d, for(i=0;i10;i+) bi=ai; for(i=0;i10;i+) printf(%d,bi); 7.1.4 顺序查找 顺序查找即为从数组的一端开始，逐个进行数组元素的值和给定值x 的比较，若某个元素的值和给定值x相等，则查找成功；反之，若 直至最后一个数组元素，其值和给定值x都不相等，则表明数组中 没有所查的数据，查找不成功。 【例7.2】已知存放在a数组中的数据两两不相同，在a数组中

6、查找和 x值相同的元素的位置。若找到，输出该值和其在a数组中的位置； 若没找到，输出相应的提示信息。 #define N 100 main() int aN,x,n,i,flag=-1; printf(Input n:n); scanf(%d, for(i=0;in;i+) scanf(%d, printf(Input x:n); scanf(%d, for(i=0;in;i+) if(ai=x) flag=i; break; if(flag!=-1) printf(%d index is %d,x,flag+1); else printf(%d donnt be founded!n,x);

7、对于上例，也可以通过设监视哨的方法对数组倒着查找，代码见课本。 7.2 二维数组 二维数组：数组元素是双下标变量的数组。二维数组的数组 素可以看作是排列为行列的形式（矩阵）。二维数组也用统一的数组名 标识，第一个下标表示行，第二个下标表示列。下标从0开始。 7.2.1 二维数组的定义与初始化 二维数组的定义 二维数组定义的一般形式是： 类型说明符 数组名常量表达式1常量表达式2； 其中常量表达式1表示第一维下标的长度，常量表达式2 表示第二维下标的长度。 例如： int a34; 说明了一个三行四列的数组，数组名为a，其下标变量的类型为整型。 该数组的下标变量共有34个，即：

8、a00,a01,a02,a03 a10,a11,a12,a13 a20,a21,a22,a23 如何在一维存储器中存放二维数组，可有两种方式：一种是按行排列， 即放完一行之后顺次放入第二行。另一种是按列排列， 即放完一列之后 顺次放入第二列。在语言中，二维数组是按行排列的。 二维数组的初始化 二维数组可按行分段赋值，也可按行连续赋值。 二维数组的初始化的几种常见形式： （1）分行给二维数组所有元素赋初值 例如：int a24=1,2,3,4,5,6,7,8; （2）不分行给二维数组所有元素赋初值 例如：int a24=1,2,3,4,5,6,7,8; （3）给二维数组所有元素赋

9、初值，二维数组第一维的长度可 以省略 （编译程序可计算出长度） 例如：int a4=1,2,3,4,5,6,7,8; 或：int a4=1,2,3,4,5,6,7,8; （4）对部分元素赋初值 例如：int a24=1,2,5; 7.2.2 二维数组元素的引用 定义了二维数组后，就可以引用该数组的所有元素。引用形式： 数组名下标1下标2 例如：a12 表示a数组第二行第三列的元素。 下标变量和数组说明在形式中有些相似，但这两者具有完全不同的含义。数组说明的方括号中给出的是某一维 的长度，即可取下标的最大值；而数组元素中的下标是该元素在数组中的位置标识。 7.2.3 二维数组元素的赋值 同一维数

10、组一样，若二维数组定义之后，不对其进行初始化，则其值可通过赋值语句获得，或者可 从键盘、文件等读取获得。现以从键盘接收数据为例： 【例7.3】通过键盘给33的二维数组输入数据，第一行赋1，2，3，第二行赋10，20，30，第 三行输入100，200，300，然后输出此二维数组。 main( ) int a33,i,j; for(i=0;i3;i+) for( j=0;j3;j+) scanf(%d, for(i=0;i3;i+) for( j=0;j3;j+) printf(%4d,ai j); printf(n); 7.3 字符数组 用来存放字符型数据的数组称为字符数组。字符数组中的一个元素

11、存放一个字符。 7.3.1 字符数组的定义、初始化 字符数组的定义与前面介绍的数值数组定义相同。其定义格式为： char 数组名下标总数; 例如： char c10=c, ,p,r,o,g,r,a,m; 赋值后各元素的值为：c0的值为c，c1的值为 ，c2的值为p， ，c8的 值为m，其中c9未赋值，系统自动赋予0值。 当对全体元素赋初值时也可以省去长度说明。 例如：char c=c, , p, r, o, g, r, a,m; 这时C数组的长度自动定为9。 另外，我们还可以将一个字符串赋给一个字符数组。 字符串，是指若干有效字符的序列。如：”a”,”abc”。 注意：由于系统在存储字符串常量

12、时，会在串尾自动加上1个结束标志，所以无需人为地再加1个。 7.3.2 7.3.2 字符串处理函数 字符串标准函数的原型在头文件string.h中。 1.输出字符串puts()函数 （1）调用方式：puts(字符数组) （2）函数功能：把字符数组中所存放的字符串，输出到标准输出设备中去，并用n取代字符 串的结束标志0。所以用puts()函数输出字符串时，不要求另加换行符。 （3）使用说明: 字符串中允许包含转义字符，输出时产生一个控制操作。 该函数一次只能输出一个字符串，而printf()函数也能用来输出字符串，且一次能输出多个。 【例7.5】下列程序的输出结果是: #include main

13、( ) char c =BASICndBASE; puts(c); 运行结果为：BASIC dBASE 2输入字符串gets()函数 （1）调用方式：gets(字符数组) （2）函数功能：从标准输入设备(stdin)键盘上，读取1个字符串（可以包含空格），并将其存储到字符 数组中去。 （3）使用说明 1）gets()读取的字符串，其长度没有限制，编程者要保证字符数组有足够大的空间，存放输入的字符串。 2）该函数输入的字符串中允许包含空格，而在scanf()函数中使用%s接收字符串时，空格做为字符串的结束 标志。 【例7.6】 #include main( ) char st15; printf

14、(input string:n); gets(st); puts(st); 输入：c program 显示：c program 3字符串比较strcmp()函数 （1）调用方式：strcmp(字符串1 ,字符串2) 其中“字符串”可以是串常量，也可以是1维字符数组。 （2）函数功能：比较两个字符串的大小。 如果：字符串1=字符串2，函数返回值等于0； 字符串1字符串2，函数返回值正整数。 （3）使用说明 如果一个字符串是另一个字符串从头开始的子串，则母串为大。 不能使用关系运算符“”来比较两个字符串，只能用strcmp() 函数来处理。 【例7.7】 #include main( ) int

15、k; char st115,st2=C Language; printf(input a string:n); gets(st1); k=strcmp(st1,st2); if(k=0) printf(st1=st2n); if(k0) printf(st1st2n); if(k0) printf(st1st2n); 4.拷贝字符串strcpy()函数 （1）调用方式：strcpy(字符数组1, 字符数组2) （2）函数功能：将“字符数组2”完整地复制到“字符数组1”中，字符数组中原有内容被覆盖。 （3）使用说明: 字符数组必须定义得足够大，以便容纳复制过来的字符串。复制时，连同结束标志0一起

16、复制。 不能用赋值运算符“”将一个字符串直接赋值给一个字符数组，只能用strcpy()函数来处理。 【例7.8】 #include main( ) char st115,st2=C Language; strcpy(st1,st2); puts(st1);printf(n); 运行结果为：C Language 5连接字符串strcat()函数 （1）调用方式：strcat(字符数组, 字符串) （2）函数功能：把“字符串”连接到“字符数组”中的字符串尾端，并存储于“字符数组”中。“字符数组” 中原来的结束标志，被“字符串”的第一个字符覆盖，而“字符串”在操作中未被修改。 （3）使用说明 由于没

17、有边界检查，编程者要注意保证“字符数组”定义得足够大，以便容纳连接后的目标字符串；否则， 会因长度不够而产生问题。 连接前两个字符串都有结束标志0，连接后“字符数组”中存储的字符串的结束标志0被舍弃，只在目 标串的最后保留一个0。 【例7.9】把初始化赋值的字符数组与动态赋值的字符串连接起来。 #include main( ) char st130=My name is ; /*注意长度为30*/ char st210; printf(Input your name:); gets(st2); strcat(st1,st2); puts(st1); 6求字符串长度strlen()函数（len是

18、length的缩写） （1）调用方式：strlen(字符串) （2）函数功能：求字符串（常量或字符数组）的实际长度（不包含结束标 志）。 【例7.10】 #include main( ) int k; char st=C language; k=strlen(st); printf(The lenth of the string is %dn,k); 运行结果为：The lenth of the string is 10 7.4 数组在函数中的应用 数组可以作为函数的参数使用，进行数据传送。数组用作函数参数有两种形式:一种是把数组元素(下标变量) 作为实参使用；另一种是把数组名作为函数的形参和

19、实参使用。 数组元素作函数实参 数组元素就是下标变量，它与普通变量并无区别。 因此它作为函数实参使用与普通变量是完全相同的，在发 生函数调用时，把作为实参的数组元素的值传送给形参，实现单向的值传送。 【例7.11】编程实现对一数组中所有元素取绝对值. #include main() int a5=1,-5,4,-7,-4,i; for(i=0;i5;i+) ai=f (ai); for(i=0;i5;i+) printf(%4d,ai); int f( int x ) if(x0) return -x; else return x; 2、数组名作为函数参数 数组名就是数组的首地址，因此在数组名

20、作函数参数时所进行的传送是地址的传送，所以要求形参 必须是和实参类型相同的数组名，对于形参必须有明确的数组说明。在实参与形参进行“值 传递”时，是把实参数组的首地址赋予形参数组名。形参数组名取得该首地址之后，也就等 于有了实在的数组。实际上是形参数组和实参数组为同一数组，共同拥有一段内存空间。 【例7.12】数组a中存放了一个学生5门课程的成绩，求平均成绩。 float aver(float a5) int i; float av,s=a0; for(i=1;i5;i+) s=s+ai; av=s/5; return av; void main() float sco5,av; int i;

21、printf(ninput 5 scores:n); for(i=0;ikey，说明待查元素若存在，必在区间low，mid-1 的范围内，则令指针high指向第mid-1个元素，重新求得mid=(1+5)2=3 仍以amid和key相比，因为amid key，说明待查元素若存在，必在mid+1，high范 围内，则令指针low指向第mid+1个元素，求得mid的新值为4，比较amid和key，因为相等， 则查找成功，所查元素在表中序号等于指针mid的值。 源程序： #define N 50 int binsrch(int r ,int n,int k) int mid,low,high,fin

22、d; low=1; high=n;find=0; /*置区间初值*/ while (lowrmid ) low=mid+1; /*在后半区间查找*/ else high=mid-1; /*在前半区间查找*/ if (find) return (mid); /*查找成功，返回找到元素的位置*/ else return (0); /*查找不成功，返回0标记*/ main() int aN,n,i,k,f; printf(请输入数据元素的个数:n); scanf(%d, printf(请输入数据元素 :n); for(i=1;i=n;i+) scanf(%d, printf(请输入要查找的数据:n)

23、; scanf(%d, f=binsrch(a,n,k); if(f=0) printf(值为%d 的元素不存在。n,k); else printf(%d在数组中的位置为%d,k,f); 7.6 数组元素排序 排序(Sorting)是计算机程序设计中的一种重要操作，它的功能是将一个数 据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列. 7.6.1 插入排序 线性插入排序的基本思想是：第1遍，将初始文件中的第1个记录看作有序 的序列，然后从第2个记录开始逐个插入前边的有序序列，并使插入后， 前边仍有序。第i趟直接插入排序的操作为：在含有i-1个记录的有序子序 列r1.i-1中插入一个

24、记录ri后，变成含有i个记录有序子序列r1.i。为 了在查找插入位置的过程中避免数组下标出界，在r0处设置监视哨，将 ri拷贝到r0处，当从i-1起往前搜索的过程中，可以同时后移记录。直 至整个数组变成有序为止。整个排序过程共进行n-1趟插入。 【例7.17】将数组（43，21，89，15，43，28）中的元素进行升序排列。 其源程序为： #define N 50 void insertsort(int r ,int n) int i,j; for(i=2;ir0) rj+1=rj; j-; rj+1=r0; main( ) int aN,n,i; printf(请输入数据元素的个数:n);

25、scanf(%d, printf(请输入数据元素 :n); for(i=1;i=n;i+) scanf(%d, insertsort(a,n); printf(升序排列的结果为 :n); for(i=1;i=n;i+) printf(%5d,ai); 7.6.2 折半插入排序 在线性插入排序中，我们采用顺序查找法来确定记录的插入位置。如果（R1，R2，Ri-1）是有序子文件，我们可以采 用折半查找法来确定R1的插入位置，这种排序称为折半插入排序。 【例7.18】将数组（43，21，89，15，43，28）中的元素进行升序排列。 #define N 50 void binarysort(int

26、r,int n) /*按关键字递增次序对r1,r2,rn进行折半插入排序 */ int i,j,l,h,mid; for(i=2;i=n;i+) r0=ri; l=1; h=i-1; while(l=h) mid=(l+h)/2; if(r0=l;j-) r j+1=r j; rl=r0; main( ) int aN,n,i; printf(请输入数据元素的个数:n); scanf(%d, printf(请输入数据元素 :n); for(i=1;i=n;i+) scanf(%d, binarysort(a,n); printf(升序排列的结果为 :n); for(i=1;i=n;i+) pr

27、intf(%5d,ai); 7.7 典型习题分析解答 【例7.19】若有说明：int a34，则对数组a元素非法引用的是。 A）a02*1 B）a13 C）a4-20 D）a04 分析：本题考察对于二维数组元素引用的原则。对以上述定义的二维数组，其最大下标的元素对应： a23. 答案：D 【例7.20】若二维数组有m列，则在ai j之前的元素的个数为 A.j*m+i B.i*m+j C.i*m+j-1 D.j*m+i-1 分析：在C语言中，由于二维数组在内存中是按照行优先的顺序存储的，且下标的起始值为0，因 此在ai j之前有i*m+j个。 答案：B 【例7.21】以下选项中合法的数组说明语句

28、是 A. in a =”string” B.int a5=0,1,2,3,4,5 C.char a=”string” D.char a5=0,1,2,3,4,5 分析：在C语言中，字符变量中存放的是与字符对应的ASCII码值，数值0，1，2，3，4，5对应 的字符虽然是不可显示的字符，但是这些都可以作为控制字符。此时，数组的大小有后面的初始 化数据的数量决定。 答案：D 【例7.22】以下程序的输出结果是： void reverse（int a,int n） int i,t; for（i=0;in/2;i+） t=ai; ai=an-1-i;an-1-i=t; main（） int b10=1

29、,2,3,4,5,6,7,8,9,10; int i,s=0; reverse（b,8）; for（i=6;i10;i+）s+=bi; printf（ %dn ,s）; A）22 B）10 C）34 D) 分析： 在main函数中，调用reverse函数将b数组中的前8个成员进行互置，执行完毕后，b数组中的成 员为8,7,6,5,4,3,2,1,9,10，然后再执行for循环结构，将b6，b7.b9的值相加， 结果为22。 答案：A 【例7.23】当运行以下程序时，从键盘输入；AhaMA(空格)Aha，则下面程序的运行结果是 #include main() char s80,c=a; int

30、i=0; scanf(%s,s); while(si!=n) if(si=c)si=si-32; else if(si=c-32)si=si+32; i+; puts(s); A）ahaMa B）AhAMa C）ahAMa空格ahA D）ahAMa 分析： 本题主要考查的知识点是大写字母比它对应的小写字母ASCII码值小32，并且字符可以看作整数进行算术 运算等操作。 答案：D 【例7.24】有以下程序: #include #include main() char a =a,b,c,d, e, f, g,h,0; int i,j; i=sizeof(a); j=strlen(a); print

31、f(%d,%dn,i,j); 程序运行后的输出结果是。 A)9，9 B)8，9 C)1，8 D)9，8 分析： 本题考查了求数据类型长度的运算符sizeof和求字符串长度的函数strlen的区别。 strlen计算的是一个字符串的实际字符个数，如果字符串放在字符数组中，则函数 strlen的值为0之前的全部字符个数。而sizeof求出的是数据占据存储空间的字节数， 当然也要包括字符串的结束。 答案：D 【例7.25】下面程序的运行结果是 #include main() char a=morning,t; int i,j=0; for(i=1;i7;i+)if(ajai)j=i; t=aj;aj

32、=a7; a7=aj;putsa; A）mrgninr B）mo C）moring D）morning 分析： 本题考查了一维数组元素的引用方法。题中数组a为一字符串数组，通过数组首地址和 下标可以引用数组中的每个元素。因为字符数组相当于字符串，所以可以用字符串输出 函数puts（）来输出字符数组中的各个字符。 答案: B 【例7.26】当执行以下程序时，如果输入ABC，则输出结果是。 #include #include main() char ss10=1,2,3,4,5; gets(ss); strcat(ss, 6789); printf(%sn,ss); A) ABC6789 B) A

33、BC67 C) 12345ABC6 D)ABC456789 分析： 本题考查了字符串处理函数的应用。gets( )函数调用后，从键盘接受的新 值”ABC”将初始化得到的值覆盖掉。然后调用字符串连接函数strcat( ) 将字符串”6789”连接在”ABC”的后面。 答案：A 一维数组的初始化 初始化赋值的一般形式为： 类型说明符 数组名常量表达式=值，值值； 其中在 中的各数据值即为各元素的初值，各值之间用逗号间隔。 例如： int a10= 0,1,2,3,4,5,6,7,8,9 ; 说明： （1）可以只给部分元素赋初值。 当 中值的个数少于元素个数时，只给前面部分元素赋值。

34、 例如： int a10=0,1,2,3,4; 表示只给a0a4这5个元素赋值，而后5个元素自动赋0值。 （2）能给元素逐个赋值，但不能给数组整体赋值。 例如给十个元素全部赋1值，只能写为： int a10=1,1,1,1,1,1,1,1,1,1; 而不能写为： int a10=1; （3）如给全部元素赋值，则在数组说明中， 可以不给出数组元素的个数。 例如： int a5=1,2,3,4,5; 可写为： int a=1,2,3,4,5; 7.1.2 一维数组元素的引用 数组元素引用的一般形式为： 数组名下标 其中的下标只能为整型常量或整型表达式。如果为小数时，C编译将自动取整。例如， a6,bi+j,bi+都是合法的数组元素。 数组元素通常也称