1、第5章 数组数据类型及其应用第五章 数组数据类型及其应用上面几章所介绍的变量都是相互独立的，变量与变量之间没有相互依存的关系，如int x, char c等，这种变量称为简单变量或离散型变量，它们都属于基本类型数据。若要处理100个学生的某门课程的成绩，就要声明100个简单变量，显然这是不可取的。可以按一定的结构将类型相同的变量组织在一起，成为一个有序数据的集合，这就是数组。在语言中， 数组属于构造数据类型，一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型也可以是构造数据类型。数组在各种程序设计中广泛使用，并通常使用数组来描述顺序存储结构的线性表、栈和队列。.一维数组 .一维数组
2、的定义数组的定义包括数组类型、维数、下标的范围等内容。其定义形式如下：类型说明符 数组名常量表达式;其中类型说明符是任一种基本数据类型或构造数据类型，数组名是用户自定义的数组标识符，常量表达式表示数据元素的个数，也称为数组的长度。例如：int a5;它表示定义了一个整数数组，数组名为a，数组有5个元素。说明：（）数组名的命名规则与变量的命名规则相同，书写规则应符合标识符的书写规定。（）在定义数组时，需要指定维数及下标的大小。方括号中常量表达式指定数组的元素个数，既数组长度。注意，C语言中数组的下标是从0开始的。因此，上例的数组的长度为5，这5个元素分别为a0、a1、a2、a3、a4。（）常量表
3、达式中可以包括常量和符号常量，不能包含变量。也就是说不能根据用户的需要来确定数组的长度。例如下面程序是错误的：int n ;scanf(“%d”,&n); /* 在程序中临时输入数组的长度*/intan ;（）数组下标的范围：一个数组所占的字节数最多为65535个字节，若超过，则编译出错，例如，下面的定义是不允许的：int a32768;定义了一个有32768个元素的数组a，由于一个元素占2个字节，共需65536个字节，超过所允许的范围，所以编译时出错。.数组的初始化数组的初始化可以包括以下几种方法：（）在定义数组时对数组的全部元素赋初值。例如： int a5=0,1,2,3,4;将数组元素的
4、初值依次放在一对花括号内，使数组中的元素全部被赋值。经过定义和初始化后，a0=0，a1=1，a2=2，a3=3，a4=4。（）可以只给数组的一部分元素赋值。例如：int a5=0,1,2;只给前3个元素赋初值，而后面的2个元素自动赋值为0。因此，a0=0，a1=1，a2=2，a3=0，a4=0。（）如不对数组赋初值，则数组的元素均为0值。（）在对全部数组元素赋初值时，可以省略常量表达式，即不指定数组的长度。例如：int a5=0,1,2,3,4;等价于：int a=0,1,2,3,4;.数组元素的访问数组必需先定义后使用，而且C语言只能逐个访问数组元素而不能一次访问整个数组。 数组元素的一般表
5、示形式为： 数组名下标其中，下标为整型常量或整型表达式。例如： int a5; /*定义数组长度为5*/ i=a2; /*访问第3个元素并将其赋值给变量i*/例5.1 数组元素的访问。# includestdio.hvoid main()int i,a10=0,1,2,3,4,5,6,7,8,9;for(i=0;i=9;i+) printf(“%d ,“,ai);printf(“n “);for(i=0;i=9;i+)ai=0;/*把数组的10个元素均赋值为0*/for(i=0;i=9;i+) printf(“%d ,“,ai);程序执行结果如下：01234567890000000000.数组
6、作函数参数在上一章中已经介绍了使用变量作函数的参数，其实，数组元素和数组名也可以用做函数参数。.数组元素作函数的参数数组元素作函数的实参时与变量做实参一样，是单向的值传递方式。用数组元素作参数时，要求数组类型和函数的形参变量的类型一致。例5.2数组元素作函数参数举例，比较两个数的大小。#includevoid main()int a2=42,50,n;int max(int x,int y); /*声明函数max()*/n=max(a0,a1); /*数组的元素作函数的实参*/printf(“max=%d”,n); /*输出大数*/int max(int x,int y)if(xy) x=y;
7、 /*比较大小,将大的数放入x中*/return x; /*返回x值为函数值*/程序的执行结果为：max=50.数组名作函数的参数在普通变量作函数参数时，形参变量和实参变量由编译系统分配两个不同的内存单元，在函数调用时采取的是“值传递”方式，即把实参变量的值赋予形参变量。而在用数组名作函数参数时，不是进行值的传递，即不是把实参数组的每一个元素的值都赋予形参数组的各个元素。因为实际上形参数组并不存在，编译系统不为形参数组分配内存。那么，数据的传送是如何实现的呢?数组名就是数组的首地址，因此在数组名作函数参数时所进行的传送只是地址的传送， 也就是说把实参数组的首地址赋予形参数组，形参数组取得该首地
8、址之后，也就等于有了实参数组。实际上，形参数组和实参数组为同一数组，共同拥有一段内存空间。这种参数的传递方式称为“地址传递”方式。例如5.3数组名作参数举例。# include stdio .hvoid main( )int a10=0,1,2,3,4,5,6,7,8,9; /*定义数组*/void proc(int b10 );proc(a);/*数组名a作为函数参数*/void proc(int b10 )for(i=0;i=9;i+ )printf(“%d “ ,bi” );程序的执行结果为：0123456789以数组名作参数时，实参数组必须定义为具有确定长度的数组，而形参数组可以不指定
9、大小，只在定义数组时在数组后面跟一个空的方括号，如上例中的int b10可以写成intb 。这是因为C语言编译系统不对形参数组的大小作检查。.二维数组.二维数组和多维数组的定义. 二维数组的定义二维数组的一般定义形式为：类型说明符 数组名常量表达式1 常量表达式2例如：int a23,b34;定义a为2*3（2行3列）的数组，b为3*4（3行4列）的数组。二维数组可被看作是一种特殊的一维数组，即把二维数组的元素看作是一维数组。例如上述定义的a数组，可看作它有2个元素即a0和a1，每个元素又包含3个元素。如图5.1所示。a0a00 a01 a02a1a10 a11 a12 图5.1二维数组元素示
10、意图. 二维数组的存储二维数组在存储时是按一维形式存放的，这是因为实际的硬件存储器是连续编址的，也就是说存储器单元是按一维线性排列的。在C语言中，二维数组的存储是按行存放的，即在内存中先存放第一行元素，再顺序存放第二行、第三行的元素。图5.2说明了数组a的存储情况。a00 a01 a0,2 a10 a11 a12图5.2二维数组a的各元素的存储顺序.二维数组的引用及举例 二维数组元素的引用形式为：数组名下标下标例5.4 通过键盘给2*3的二维数组赋值并输出。# include.void main()int a23,i,j;printf(“input a arry:n”);for (i=0;i2
11、;i+)for (j=0;j3;j+)scanf(“%d”,&aij);/*键盘输入*/printf(“output a array:n”);for(i=0;i2;i+)for(j=0;j字符串2，那么函数值为正数；如果字符串1字符串2，那么函数值为负数。.求长度字符串的长度就是字符串所包含的字符数，不包括结束标志符(0)。例如：char a10= “China” ;字符数组a的长度为5。求字符串长度strlen()函数的一般形式为：strlen(字符串)例如:char str=“chinese”;printf(“%d”,strlen(str);输出结果为7，而不是8，也可以直接测试字符串常量
12、的长度，例如：strlen(“chinese”); .线性表 线性表（Linear List）是一种最基本的数据结构，它不仅应用广泛，而且也是本书后续章节中的其他几种复杂的数据结构（如栈、队列等等）的基础。在这一节，将介绍线性表的逻辑结构、存储结构及基本算法。.线性表的定义和基本运算线性表是数据元素的一个有限序列，在这个序列中，每个元素有且只有一个（直接）前驱和一个（直接）后继，而第一个元素无前驱，最后一个元素无后继。例如一个字母表（a，b，c，f，g），或者是一个数字表（1，2，3，8，9，10），这些都是线性表。线性表可以表示为： L=（a1,a2,a3,an）;其中，ai是数据元素，n0
13、是整数，而ai-1是ai的前驱（i2），ai+1（in，其中i=1，2，n是ai的后继。线性表中元素的个数称为线性表的长度，没有元素的表被称为空表，它的长度为0。线性表L的逻辑结构如图5.6所示。 图5.6 线性表的逻辑结构示意图 线性表的基本算法主要有如下几种：（）InitList(L) 构造一个空的线性表L，即表的初始化。（）ListLength(L) 求线性表L中的结点个数，即求表长。（）GetNode(L,i) 取线性表L中的第i个结点，这里要求1iListLength(L)。（）LocateNode(L,x) 在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和
14、x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。 （）InsertList(L,x,i) 在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，n的结点变为编号为i+1，i+2，n+1的结点。这里1in+1，而n是原表L的长度。插入后，表L的长度加1。 （）DeleteList(L,i) 删除线性表L的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点。这里1in，而n是原表L的长度。删除后表L的长度减1。以上就是一些基本的对于线性表的操作。读者需要在了解线性表的存储结构后才能理解它的实现细节。.线
15、性表的存储结构 线性表的逻辑结构是线性结构，表中每个元素（除第一个和最后一个外）只有一个直接前驱和一个直接后继。根据其逻辑结构的特点，线性表的存储结构可以有两种方式，即顺序存储和链式存储，这两种方式各有优缺点，本章只介绍顺序存储的线性表即顺序表。线性表的这种顺序存储结构的主要特点是，按线性表中元素的逻辑顺序把所有的元素依次存放到一块连续的存储空间中，并且任意两个相邻元素之间的存储单元的个数是相等的。例如，假设每个元素占用b个存储单元，那么这个线性表中第i个元 素在这个存储空间的相对地址就是（i-1）*b。例如线性表L= a1,a2,a3,an 的存储结构如图5.7所示。 a1 a2A3 图5.
16、7 线性表的顺序存储假设这个表中每个元素占用n个存储单元，如果a1的地址为m，那么a2的地址就是m+（2-1）*n，a3的地址就是m+（3-1）*n，。所以，当知道了表中一个元素的相对地址和表中第一个元素的地址时，就能够对表中的任一元素进行随机的访问，因此通常把线性表的顺序存储称为随机存取存储结构，这是顺序存储最主要的优点。其主要的缺点是，一个连续的固定的存储空间很难预先分配，也很难扩展。在下一小节的运算中，读者将会发现，顺序存储进行插入和删除操作时，也非常麻烦。由于一维数组也是采用顺序存储表示的，所以可以定义一个数组来存储线性表中的所有的元素。可用Max来表示数组的最大允许长度，用lengt
17、h定义一个整型变量来表示数组的实际长度，数组中元素的类型是ElemType。线性表的顺序存储结构可描述如下：#define Max 100/*定义数组的最大长度*/typedef int Datatype ;/*定义数组元素的数据类型*/typedef struct Datetype dataMax;/*data数组用于开辟一段连续的存储空间*/int length; /*当前长度*/ SqList;.线性表的运算 .线性表的插入操作设长度为n的线性表（a1,a2,an），若要在第i-1与i个元素之间插入一个新的元素x，则必须将第n至第i个元素依次向后移动一位置，然后进行插入，插入后得到长度为
18、n+1的线性表(a1,a2,ai-1,x,ai,an+1)。插入过程如图5.8所示。插入前a1a2ai-1aian移动后a1a2ai-1aian插入后a1a2ai-1xaian图5.8顺序存储线性表的插入过程顺序表的插入算法如下所示：Void InsertList (SqList L, Datetype x ,int i) int j; if (i L.length+1) Error(“position error”); /*插入位置不合法，退出*/ if (L.length = Max) Error (“overflow ”) ; /*存储空间已满，退出*/ for (j=L.Length;
19、 j=i ; j-) /本算法没有考虑/言数组下标从0开始c语 L.dataj+1=L.dataj ; /*结点后移*/ L.datai=x ; /*插入*/ L.length+ ; /*表长加1*/算法5.1顺序表的插入算法时间复杂度分析：以顺序结构存储的线性表，插入元素的运算时间主要消耗在移动元素上，所需移动元素的个数与线性表的长度n和插入元素的位置i有关。在长度为n的线性表中，插入一个结点，在表中第i的位置上插入一个结点的移动次数为n-i+1，如果用Ein（n）表示移动的结点的平均次数，那么 Ein（n）= 设pi是在i个位置上插入一个结点的概率（假设概率相等），则p1=p2=pn+1
20、=1/(n+1),因此(n)= =n/2其平均时间复杂是O (n)。举例：线性表的插入操作#define Max 100 /*定义数组的最大长度*/typedef int Datatype; /*定义数组元素的数据类型*/typedef structDatatype dataMax; /*data数组用于开辟一段连续的存储空间*/int length; /*当前长度*/SqList;void InsertList(SqList *L,Datatype x,int i)int j;if (i L-length+1)printf(position error);exit(); /*Error(“p
21、osition error”); */else if (L-length = Max) printf(overflow!); exit(); /*Error (“overflow ”) ;*/ else for (j=L-length-1; j=i-1;j-) L-dataj+1=L-dataj; /*结点后移*/ L-datai-1=x; /*插入*/ L-length+; void main()SqList *L; Datatype x; int i;/* 下面三行代码的作用是：为线性表L赋初值。值为0、1、2、3、4、5、6、7、8、9，长度为10。*/for (i=0;idatai=
22、i; L-length=i; printf(n输入插入位置 i和数据x:); scanf(%d%d,&i,&x); InsertList(L,x,i); printf(n插入后的线性表值为:); for(i=0;ilength-1;i+) printf(n%d,L-datai);printf(n插入后的线性表长度为:);printf(n%d,L-length);.线性表的删除操作若要在长度为n的线性表中删除第i个元素（1in），即将线性表中（a1,a2,ai-1,ai ,ai+1,an）中的ai删除，需将ai以后的元素ai+1 ，an依次向前移动一位置，则线性表变成（a1,a2,ai-1,ai+1,an），长度变为n-1。其删除过程如图5.9所示。删除前a1a2ai-1aiai+1an删除后a1a2ai-1ai+1an图5.9顺序存储线性表的删除过程顺序表的删除算法如下所示：Void DeleteList ( SqList L, int i) /*从线性表L 中删除第i个结点*/int j ;if (iL. Length)return ERROR ; /*i的位置不合法*/for (j=i+1; j=L.length; j+) /本算法没有考虑c语/言数组下标从0开始L.dataj-1=L.dataj;L.Length-; /*表长减1*/
