数据的顺序存储结构及应用计算机专业

1、为了解决比较复杂的问题，本章介绍C语言提供的一种最简单的构造类型数组及应用。5.1 1维数组的定义和引用维数组的定义和引用5.2 2维数组的定义和引用维数组的定义和引用5.3 字符数组与字符串字符数组与字符串5.4 数组作为函数参数数组作为函数参数5.5 线性表线性表5.6 栈栈5.7 队列队列Return第第5章章 数据的顺序存储结构及应用数据的顺序存储结构及应用5.1 1维数组的定义和引用维数组的定义和引用5.1.1 1维数组的定义维数组的定义5.1.2 1维数组元素的引用维数组元素的引用5.1.3 1维数组元素的初始化维数组元素的初始化5.1.4 1 1维数组应用举例维数组应用举例 Re

2、turn5.1.1 1维数组的定义维数组的定义案例案例5.1 从键盘上任意输入10个整数，要求按从小到大的顺序在屏幕上显示出来。 排序的方法有很多，本题采用冒泡法。冒泡法的基本思想冒泡法的基本思想：通过相邻两个数之间的比较和交换，使排序码（数值）较小的数逐渐从底部移向顶部，排序码较大的数逐渐从顶部移向底部。就像水底的气泡一样逐渐向上冒，故而得名。由AnA1组成的n个数据，进行冒泡排序的过程可以描述为：（1）首先将相邻的An与An-1进行比较，如果An的值小于An-1的值，则交换两者的位置，使较小的上浮，较大的下沉；接着比较An-1与An-2，同样使小的上浮，大的下沉。依此类推，直到比较完A2和

3、A1后，A1为具有最小排序码（数值）的元素，称第一趟排序结束。（2）然后在AnA2区间内，进行第二趟排序，使剩余元素中排序码最小的元素上浮到A2；重复进行n-1趟后，整个排序过程结束。/*案例代码文件名：AL5_1.C*/*功能：从键盘上任意输入n个整数，用冒泡法按从小到大地排序，并在屏幕上显示出来。*/#include stdio.h#define NUM 10/*定义符号常量（数据个数N）*/main() int dataNUM;/*定义1个1维整型数组data*/ int i,j,temp;/*定义循环变量和临时变量*/ clrscr();/*库函数clrscr()：清屏*/ print

4、f(Please input 10 numbers:n); for(i=0; iNUM; i+) scanf(%d, &datai); /*冒泡法排序*/ for(i=0; ii; j-) /*内循环：进行每趟比较*/ if(datajdataj-1) /*如果dataj大于dataj-1,交换两者的位置*/ temp=dataj; dataj=dataj-1; dataj-1=temp; ; /*输出排序后的数据*/ printf(nthe result of sort:n); for(i=0; iNUM; i+) printf(%d ,datai); getch();/*等待键盘输

5、入任一字符，目的使程序暂停*/程序演示程序演示数组同变量一样，也必须先定义、后使用。1维数组是只有1个下标的数组，定义形式如下：数据类型数据类型 数组名数组名常量表达式常量表达式, 数组名数组名2常量表达式常量表达式2；（1）“数据类型”是指数组元素的数据类型。（2）数组名，与变量名一样，必须遵循标识符命名规则。（3）“常量表达式”必须用方括号括起来，指的是数组的元素个数（又称数组长度），它是一个整型值，其中可以包含常数和符号常量，但不能包含变量。注意注意：C语言中不允许动态定义数组语言中不允许动态定义数组。 特别说明特别说明：在数组定义时，“常量表达式”外的方括号；以及元素引用时，“下标表达

6、式”外的方括号，都是C语言语法规则所要求的，不是本书所约定的可选项的描述符号！（4）数组元素的下标，是元素相对于数组起始地址的偏移量，所以从0开始顺序编号。（5）数组名中存放的是一个地址常量，它代表整个数组的首地址。同一数组中的所有元素，按其下标的顺序占用一段连续的存储单元。Return 5.1.2 数组元素的引用数组元素的引用 引用数组中的任意一个元素的形式： 数组名数组名下标表达式下标表达式 1“下标表达式”可以是任何非负整型数据，取值范围是0（元素个数-1）。 特别强调特别强调：在运行C语言程序过程中，系统并不自动检验数组元素的下标是否越界。因此在编写程序时，保证数组下标不越界是十分重要

7、的。 21个数组元素，实质上就是1个变量，它具有和相同类型单个变量一样的属性，可以对它进行赋值和参与各种运算。 3在C语言中，数组作为1个整体，不能参加数据运算，只能对单个的元素进行处理。Return 5.1.3 1维数组元素的初始化维数组元素的初始化 初始化格式：数据类型数据类型 数组名数组名常量表达式常量表达式初值表初值表（1）如果对数组的全部元素赋以初值，定义时可以不指定数组长度（系统根据初值个数自动确定）。如果被定义数组的长度，与初值个数不同，则数组长度不能省略。（2）“初值表”中的初值个数，可以少于元素个数，即允许只给部分元素赋初值。（3）根据存储类型的不同，数组有静态数组（stat

8、ic）和动态数组（auto）之分；根据定义的位置不同，数组有内部数组（在函数内部定义的数组）和外部数组（在函数外部定义的数组）之分。Return5.1.4 1维数组应用举例维数组应用举例 案例案例5.2 已知某课程的平时、实习、测验和期末成绩，求该课程的总评成绩。其中平时、实习、测验和期末分别占10、20、20、50。/*案例代码文件名：AL5_2.C*/*功能：从键盘上循环输入某课程的平时、实习、测验和期末成绩，按10，20，20，50的比例计算总评成绩，并在屏幕上显示出来。按空格键继续循环，其他键终止循环。*/#include “stdio.h”main() int i=1,j; char

9、 con_key=x20; /* x20 空格键的ASCII码*/ float score5,ratio4=0.1,0.2,0.2,0.5; /*定义成绩、比例系数数组*/ while(con_key=x20) while(con_key=x20) clrscr(); printf(输入第%2d个学生的成绩n, i+); printf(平时 实习 测验 期末成绩n); score4=0;/* score4：存储总评成绩*/ for(j=0; j4; j+) scanf(%f,&scorej); score4 += scorej * ratioj; printf(总评成绩为:%6.1fn

10、, score4); printf(n按空格键继续,其它键退出); con_key=getch(); /*getch()函数等待从键盘上输入一个字符*/ 程序演示程序演示Return5.2 2维数组的定义和引用维数组的定义和引用5.2.1 2维数组的定义维数组的定义5.2.2 2维数组元素的引用维数组元素的引用5.2.3 2维数组元素的初始化维数组元素的初始化5.2.4 2维数组应用举例维数组应用举例 Return案例案例5.3 给一个23的2维数组各元素赋值，并输出全部元素的值。 /*案例代码文件名：AL5_3.C*/*功能：从键盘上给23数组赋值，并在屏幕上显示出来。*/#define R

11、ow 2#define Col 3#include stdio.hmain() int i, j, arrayRowCol;/*定义1个2行3列的2维数组array*/ for(i=0; iRow; i+)/*外循环：控制2维数组的行*/ for(j=0; jCol; j+)/*内循环：控制2维数组的列*/ printf(please input array%2d%2d:,i,j); scanf(%d,&arrayij); /*从键盘输入aij的值*/ printf(n); /*输出2维数组array*/ for(i=0;iRow;i+)5.2.1 2维数组的定义维数组的定义 for(

12、j=0;jCol;j+) printf(%dt,arrayij); /*将aij的值显示在屏幕上*/ printf(n); getch(); 程序演示程序演示2维数组的定义方式如下： 数据类型数据类型 数组名数组名行常量表达式行常量表达式列常量表达式列常量表达式, 数组名数组名2行常量表达式行常量表达式2列常量表达式列常量表达式2;1数组元素在内存中的排列顺序为“按行存放”，即先顺序存放第一行的元素，再存放第二行，以此类推。2. 设有一个m*n的数组x，则第i行第j列的元素xij在数组中的位置为：i*n+j（注意注意：行号、列号均从0开始计数）。 3可以把2维数组看作是一种特殊的1维数组：它的

13、元素又是一个1维数组。例如，对x32，可以把x看作是一个1维数组，它有3个元素：x0、x1、x2，每个元素又是一个包含2个元素的1维数组，如图6-4所示。即把x0、x1、x2看作是3个1维数组的名字。 Return5.2.2 2维数组元素的引用维数组元素的引用引用2维数组元素的形式为：数组名数组名行下标表达式行下标表达式列下标表达式列下标表达式1“行下标表达式”和“列下标表达式”，都应是整型表达式或符号常量。2“行下标表达式”和“列下标表达式”的值，都应在已定义数组大小的范围内。假设有数组x34，则可用的行下标范围为02，列下标范围为03。3对基本数据类型的变量所能进行的操作，也都适合于相同数

14、据类型的2维数组元素。Return5.2.3 2维数组元素的初始化维数组元素的初始化1按行赋初值数据类型数据类型 数组名数组名行常量表达式行常量表达式列常量表达式列常量表达式第第0行初值行初值表表，第第1行初值表行初值表，最后最后1行初值表行初值表；赋值规则：将“第0行初值表”中的数据，依次赋给第0行中各元素；将“第1行初值表”中的数据，依次赋给第1行各元素；以此类推。2按2维数组在内存中的排列顺序给各元素赋初值数据类型数据类型 数组名数组名行常量表达式行常量表达式列常量表达式列常量表达式初值表初值表；赋值规则：按2维数组在内存中的排列顺序，将初值表中的数据，依次赋给各元素。如果对全部元素都赋

15、初值，则“行数”可以省略。注意注意：只能省略“行数”。 Return5.2.4 2维数组应用举例维数组应用举例 案例案例5.4 有M个学生，学习N门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩。 /*案例代码文件名：AL5_4.C*/*功能：计算个人平均成绩与各科平均成绩，并在屏幕上显示出来。*/#define NUM_std 5/*定义符号常量人数为5*/#define NUM_course 4/*定义符号常量课程为4*/#include stdio.hmain() int i,j; static float scoreNUM_std+1NUM_cours

16、e+1=78,85,83,65, 88,91,89,93, 72,65,54,75,86,88,75,60, 69,60,50,72; for(i=0;iNUM_std;i+) for(j=0;jNUM_course;j+) scoreiNUM_course += scoreij;/*求第i个人的总成绩*/ scoreNUM_stdj += scoreij;/*求第j门课的总成绩*/ scoreiNUM_course /= NUM_course;/*求第i个人的平均成绩*/ for(j=0;jNUM_course;j+) scoreNUM_stdj /= NUM_std; /*求第j门课的平均

17、成绩*/ clrscr(); /*输出表头*/ printf(学生编号 课程1 课程2 课程3 课程4 个人平均n); /*输出每个学生的各科成绩和平均成绩*/ for(i=0;iNUM_std;i+) printf(学生%dt,i+1); for(j=0;jNUM_course+1;j+) printf(%6.1ft,scoreij); printf(n); /*输出1条短划线*/ for(j=0;j8*(NUM_course+2);j+) printf(-); printf(n课程平均); /*输出每门课程的平均成绩*/ for(j=0;jNUM_course;j+) printf(%6.

18、1ft,scoreNUM_stdj); printf(n); getch(); 程序演示程序演示Return5.3 字符数组与字符串字符数组与字符串5.3.1 字符数组的逐个字符操作字符数组的逐个字符操作 5.3.2 字符数组的整体操作字符数组的整体操作5.3.3 常用的字符串处理函数常用的字符串处理函数Return5.3.1 字符数组的逐个字符操作字符数组的逐个字符操作案例案例5.5从键盘输入一个字符串，回车键结束，并将字符串在屏幕上输出。 /*案例代码文件名：AL5_5.C*/main() int i; static char str80; clrscr(); for(i=0;i80;i+

19、) stri=getch(); /*逐次给数组元素stri赋值，但不回显在屏幕上*/ printf(*); /*以星号代替输入字符的个数*/ if(stri=x0d) break;/*若输入回车则终止循环*/ i=0; while(stri!=x0d) printf(%c,stri+); /*逐次输出字符数组的各个元素*/ printf(n); getch();/*程序暂停*/ 程序演示程序演示1字符数组的定义字符数组的定义1维字符数组，用于存储和处理1个字符串，其定义格式与1维数值数组一样。2维字符数组，用于同时存储和处理多个字符串，其定义格式与2维数值数组一样。2字符数组的初始化字符数组的

20、初始化字符数组的初始化，可以通过为每个数组元素指定初值字符来实现。 3字符数组的引用字符数组的引用 字符数组的逐个字符引用，与引用数值数组元素类似。 （1）字符数组的输入 除了可以通过初始化使字符数组各元素得到初值外，也可以使用getchar()或scanf()函数输入字符。 例如： char str10；for(i=0; i10; i+) scanf(%c, &stri)； fflush(stdin); /*清除键盘输入缓冲区*/ （2）字符数组的输出 字符数组的输出，可以用putchar()或printf()函数。 例如： char str10=c language;for(i=0

21、; i10; i+) printf(%c, stri)；printf(n); 注意：逐个字符输入、输出时，要指出元素的下标，而且使用“%c”格式符。另外，从键盘上输入字符时，无需输入字符的定界符单引号；输出时，系统也不输出字符的定界符。Return5.3.2 字符数组的整体操作字符数组的整体操作案例案例5.6 字符数组的整体输入与输出。 /*案例代码文件名：AL5_6.C*/*功能：将2维字符数组进行初始化，并在屏幕上输出*/main() int i; char name59=张三山, 李四季, 王五魁, 刘六顺, 赵七巧; for(i=0;i5;i+) printf(n%st,namei);

22、 /*namei代表该行数组元素的首地址*/ getch();程序演示 1字符串及其结束标志字符串及其结束标志 所谓字符串，是指若干有效字符的序列。C语言中的字符串，可以包括字母、数字、专用字符、转义字符等。C语言规定：以0作为字符串结束标志（0代表ASCII码为0的字符，表示一个“空操作”，只起一个标志作用）。因此可以对字符数组采用另一种方式进行操作了字符数组的整体操作字符数组的整体操作。 注意注意：由于系统在存储字符串常量时，会在串尾自动加上1个结束标志，所以无需人为地再加1个。另外，由于结束标志也要在字符数组中占用一个元素的存储空间，因此在说明字符数组长度时，至少为字符串所需长度加1。2

23、字符数组的整体初始化字符数组的整体初始化字符串设置了结束标志以后，对字符数组的初始化，就可以用字符串常量来初始化字符数组。3字符数组的整体引用字符数组的整体引用（1）字符串的输入除了可以通过初始化使字符数组各元素得到初值外，也可以使用scanf()函数输入字符串。（2）字符串的输出printf()函数，不仅可以逐个输出字符数组元素，还可以整体输出存放在字符数组中的字符串。Return5.3.3 常用的字符串处理函数常用的字符串处理函数字符串标准函数的原型在头文件string.h中。1输入字符串输入字符串gets()函数函数（1）调用方式：gets(字符数组)（2）函数功能：从标准输入设备(st

24、din)键盘上，读取1个字符串（可以包含空格），并将其存储到字符数组中去。（3）使用说明 1）gets()读取的字符串，其长度没有限制，编程者要保证字符数组有足够大的空间，存放输入的字符串。 2）该函数输入的字符串中允许包含空格，而scanf()函数不允许。2输出字符串输出字符串puts()函数函数（1）调用方式：puts(字符数组)（2）函数功能：把字符数组中所存放的字符串，输出到标准输出设备中去，并用n取代字符串的结束标志0。所以用puts()函数输出字符串时，不要求另加换行符。（ 3）使用说明1)字符串中允许包含转义字符，输出时产生一个控制操作。2)该函数一次只能输出一个字符串，而pri

25、ntf()函数也能用来输出字符串，且一次能输出多个。3字符串比较字符串比较strcmp()函数函数（1）调用方式：strcmp(字符串1 ,字符串2)其中“字符串”可以是串常量，也可以是1维字符数组。（2）函数功能：比较两个字符串的大小。如果：字符串字符串1=字符串字符串2，函数返回值等于0； 字符串字符串1字符串字符串2，函数返回值正整数。（3）使用说明1）如果一个字符串是另一个字符串从头开始的子串，则母串为大。2）不能使用关系运算符“”来比较两个字符串，只能用strcmp() 函数来处理。案例案例5.7 gets函数和strcmp函数的应用。 /*案例代码文件名：AL6_7.C*/*功能：

26、简单密码检测程序*/#include stdio.hmain() char pass_str80; /*定义字符数组passstr*/ int i=0; /*检验密码*/ while(1) clrscr(); printf(请输入密码n); gets(pass_str); /*输入密码*/ if(strcmp(pass_str,“password”)!=0) /*口令错*/ printf(口令错误，按任意键继续); else break; /*输入正确的密码，中止循环*/ getch(); i+; if(i=3) exit(0); /*输入三次错误的密码，退出程序*/ /*输入正确密码所进入的

27、程序段*/程序演示4拷贝字符串拷贝字符串strcpy()函数函数（1）调用方式：strcpy(字符数组, 字符串)其中“字符串”可以是串常量，也可以是字符数组。（2）函数功能：将“字符串”完整地复制到“字符数组”中，字符数组中原有内容被覆盖。（3）使用说明1）字符数组必须定义得足够大，以便容纳复制过来的字符串。复制时，连同结束标志0一起复制。2）不能用赋值运算符“”将一个字符串直接赋值给一个字符数组，只能用strcpy()函数来处理。 5连接字符串连接字符串strcat()函数函数（1）调用方式：strcat(字符数组, 字符串)（2）函数功能：把“字符串”连接到“字符数组”中的字符串尾端，并

28、存储于“字符数组”中。“字符数组”中原来的结束标志，被“字符串”的第一个字符覆盖，而“字符串”在操作中未被修改。（3）使用说明 1）由于没有边界检查，编程者要注意保证“字符数组”定义得足够大，以便容纳连接后的目标字符串；否则，会因长度不够而产生问题。 2）连接前两个字符串都有结束标志0，连接后“字符数组”中存储的字符串的结束标志0被舍弃，只在目标串的最后保留一个0。6求字符串长度求字符串长度strlen()函数（函数（len是是length的缩写）的缩写）（1）调用方式：strlen(字符串)（2）函数功能：求字符串（常量或字符数组）的实际长度（不包含结束标志）。7将字符串中大写字母转换成小写

29、将字符串中大写字母转换成小写strlwr()函数函数（1）调用方式：strlwr(字符串)（2）函数功能：将字符串中的大写字母转换成小写，其它字符（包括小写字母和非字母字符）不转换。8将字符串中小写字母转换成大写将字符串中小写字母转换成大写strupr()函数函数（1）调用方式：strupr(字符串)（2）函数功能：将字符串中小写字母转换成大写，其它字符（包括大写字母和非字母字符）不转换。Return5.4 数组作为函数参数数组作为函数参数数组用作函数参数有两种形式：一种是把数组元素（又称下标变量）作为实参使用；另一种是把数组名作为函数的形参和实参使用。 5.4.1 数组元素作为函数参数数组元

30、素作为函数参数 5.4.2 数组名作为函数的形参和实参数组名作为函数的形参和实参 Return5.4.1 数组元素作为函数参数数组元素作为函数参数 数组元素就是下标变量，它与普通变量并无区别。数组元素只能用作函数实参，其用法与普通变量完全相同：在发生函数调用时，把数组元素的值传送给形参，实现单向值传送。案例5.8 写一函数，统计字符串中字母的个数。/*案例代码文件名：AL5_8.C*/*功能：数组元素作为函数实参*/int isalp(char c) if (c=a&c=A&c=Z) return(1); else return(0); main() int i,num=0;

31、char str255; printf(Input a string: ); gets(str); for(i=0;stri!=0;i+) if (isalp(stri) num+; puts(str); printf(num=%dn,num); getch(); 程序演示说明：（1）用数组元素作实参时，只要数组类型和函数的形参类型一致即可，并不要求函数的形参也是下标变量。换句话说，对数组元素的处理是按普通变量对待的。（2）在普通变量或下标变量作函数参数时，形参变量和实参变量是由编译系统分配的两个不同的内存单元。在函数调用时发生的值传送，是把实参变量的值赋予形参变量。Return5.4.2 数

32、组名作为函数的形参和实参数组名作为函数的形参和实参数组名作函数参数时，既可以作形参，也可以作实参。数组名作函数参数时，要求形参和相对应的实参都必须是类型相同的数组（或指向数组的指针变量），都必须有明确的数组说明案例案例5.9 已知某个学生5门课程的成绩，求平均成绩。/*案例代码文件名：AL5_9.C*/float aver(float a ) /*求平均值函数*/ int i； float av,s=a0； for(i=1；i5；i+) s += ai； av=s/5； return av； void main() float sco5,av； int i； printf(ninput 5 s

33、cores:n)； for(i=0；i0，则除，则除a0和和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0in-1）为线性表的第）为线性表的第i个数据元素，它在数据元素个数据元素，它在数据元素ai-1之后，在之后，在ai+1之前。之前。a0为线性表的第一个数据元素，而为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），），或者可以写成：（或者可以写成：（

34、a0，a1，a2， ai-1，ai，ai+1，an-1）。）。抽象数据类型线性表的定义如下：抽象数据类型线性表的定义如下：LinearList=(D,R)其中，其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1 R=| ai-1，aiD, i=0,1,2, ，n-1 Elemset为某一数据对象集；为某一数据对象集；n为线性表的长度。为线性表的长度。线性表的主要操作有如下几种：1 Initiate(L) 初始化：构造一个空的线性表L。2 Insert(L,i,x) 插入：在给定的线性表L中，在第i个元素之前插入数据元素x。线性表L长度加1。3 Delete(L,i) 删除

35、：在给定的线性表L中，删除第i个元素。线性表L的长度减1。4 Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。5 Length(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。6 Get(L,i) 存取：对给定的线性表L，返回第i（0iLength(L)-1）个数据元素，否则返回Null。7 Traverse(L) 遍历：对给定的线性表L，依次输出L的每一个数据元素。8 Copy(L,C) 复制：将给定的线性表L复制到线性表C中。9 Merge(A,B,C) 合并：将给定的线性表A

36、和B合并为线性表C。上面我们定义了线性表的逻辑结构和基本操作。在计算机内，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。下面我们将讨论顺序存储结构下实现各操作的算法。二、 线性表的顺序存储结构在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。性表的顺序存储结构。1 线性表的顺序存储结构线性表的顺序存储结构在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间大

37、小相同，因此，要在该线性表中查找某一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)= Loc(a0)+id在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点：（1）数据中的元素间的地址是连续的；（2）数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结构是类似的。 1一维数组一维数组若定义数组An= a0，a1，a2，an-1，假设每一个数组元素占用d个字节，则数组元素A0，A1，A2，An-1的地址分别为Loc(A0)，Loc(A

38、0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。其结构如图52所示。 若定义数组Anm，表示此数组有n行m列，如下图53所示。 0 1 2 j m-10 a00 a01 a02 a0j a0 m-11a10 a11 a12 a1j a1 m-12a20 a21 a22 a2j a2 m-1i ai0 ai1 ai2 aij ai m-1 n-1 an-1 ,0 an-1,1 an-1,2 an-1,j an-1,m-1 图53 二维数组二维数组二维数组在C语言中，二维数组的保存是按照行方式存储的，先将第一行元素排好，接着排第二行元素，直至所有行的元素排完。如图5-4所示。图5-

39、4 二维数组存储示意图 2 线性表在顺序存储结构下的运算线性表在顺序存储结构下的运算可用C语言描述顺序存储结构下的线性表（顺序表）如下：#define TRUE 1 #define FALSE 0#define MAXNUM Elemtype ListMAXNUM ; /*定义顺序表List*/int num=-1; /*定义当前数据元素下标，并初始化*/我们还可将数组和表长封装在一个结构体中：struct Linear_list Elemtype ListMAXNUM; /*定义数组域*/ int length; /*定义表长域*/1. 顺序表的插入操作在长度为num(0numMAXNUM-

40、2)的顺序表List的第i(0inum+1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第num个至第i个元素（共num-i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，插入结束后顺序表的长度增加1，返回TRUE值；若i0或inum+1，则无法插入，返回FALSE。如图2-5所示。在长度为num(0numMAXNUM-2)的顺序表List的第i(0inum+1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第num个至第i个元素（共num-i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，插入结束后顺序表的长度

41、增加1，返回TRUE值；若i0或inum+1，则无法插入，返回FALSE。如图2-5所示。 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum 插入x图5-5 在数组中插入元素 其算法如下：【算法5.1 顺序表的插入】int Insert(Elemtype List,int *num,int i,Elemtype x)/*在顺序表List中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回TRUE，否则返回FAL

42、SE。*/ int j; if (i*num+1) printf(“Error!”); /*插入位置出错*/ return FALSE; if (*num=MAXNUM-1) printf(“overflow!”); return FALSE; /*表已满*/for (j=*num;j=i;j-)Listj+1=Listj; /*数据元素后移*/Listi=x; /*插入x*/(*num)+; /*长度加1*/return TRUE;注：顺序表List的最大数据元素个数为MAXNUM，num标识为顺序表的当前表尾（numMAXNUM-1）。顺序表的删除操作顺序表的删除操作 序号 元素 0 a0

43、 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numanum 图5-6 在数组中删除元素在长度为num(0numMAXNUM-1)的顺序表List，删除第i(0inum)个数据元素，需将第i至第num个数据元素的存储位置（num-i+1）依次前移，并使顺序表的长度减1，返回TRUE值，若i0或inum，则无法删除，返回FALSE值，如图5-6所示。其算法如下：【算法5.2 顺序表的删除】int Delete(Elemtype List,int *num,int i)/*在线性表

44、List中，*num为表尾元素下标位置，删除第i个元素，线性表的元素减1，若成功，则返回TRUE；否则返回FALSE。*/int j;if(i*num) printf(“Error!”); return FALSE; /*删除位置出错！*/ for(j=i+1;j=*num;j+) Listj-1=Listj; /*数据元素前移*/ (*num)-; /*长度减1*/return TRUE; 从上述两个算法来看，很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。而移动元素的次数取决于插入或删除元素的位置。假设Pi是在第i个元素之前插入一个元素的概率，则在

45、长度为n的线性表中插入一个元素时所需移动元素次数的平均次数为)(0inpEniiins假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的平均次数为如果在线性表的任何位置插入或删除元素的概率相等，即 则 可见，在顺序存储结构的线性表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。若表长为n，则插入和删除算法的时间复杂度都为O(n)。在顺序存储结构的线性表中其他的操作也可直接实现，在此不再讲述。) 1(10inqEniidel11npinqi12)(110ninnEniins21) 1(110ninnEnidel例：将有序线性表La=2,4,6,7,9

46、，Lb=1,5,7,8，合并为Lc=1,2,4,5,6,7,7,8,9。分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要先将Lc置为空表，然后将La或Lb中的元素逐个插入到Lc中即可。设两个指针i和j分别指向La和Lb中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到Lc中的元素c为c=当时当时 ，很显然，指针i和j的初值均为1，在所指元素插入Lc后，i，j在La或Lb中顺序后移。算法如下：void merge(Elemtype La,Elemtype Lb,Elemtype *Lc) int i,j,k; int La_length,Lb

47、_length; i=j=0;k=0; La_length=Length(La);Lb_length(Lb)=Length(Lb);/*取表La,Lb的长度*/ Initiate(Lc); /*初始化表Lc*/ While (i=La_length&j=Lb_length) a=get(La,i);b=get(Lb,j); if(ab) insert(Lc,+k,a);+i; else insert(Lc,+k,b);+j; /*将La和Lb的元素插入到Lc中*/while (i=La_length) a=get(La,i);insert(Lc,+k,a);while (j=lb_le

48、ngth) b=get(La,i);insert(Lc,+k,b); 3顺序表存储结构的特点顺序表存储结构的特点线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。也就是说定位操作可以直接实现。高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。但是，顺序存储结构也有一些不方便之处，主要表现在：（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间。（2）插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需移动大量数据。这对于插入

49、和删除操作频繁的线性表、以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高。（3）顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。5.6 栈栈 在各种程序设计语言中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序，甚至可以直接或间接地调用自身，这种调用关系就是递归。下面以求阶乘的递归方法为例，来分析计算机系统是如何处理这种递归调用关系的。求n！的递归方法的思路是：相应的C语言函

50、数是：float fact(int n)float s; if (n= =0|n= =1) s=1; else s=n*fact(n-1); return (s); 在该函数中可以理解为求n！用fact(n)来表示，则求(n-1)！就用fact(n-1)来表示。若求5!，则有main() printf(“5!=%fn”,fact(5); )1()1 ,0()!1(*1!nnnnn图5-7给出了递归调用执行过程。从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内的调用。

51、每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact才有结果为1，然后再一一返回计算，最终得到结果。 主函数mani()printf(“fact(5)”)第 一 层 调用n=5s=5*fact(4)第 二 层 调用n=4s=4*fact(3)第 三 层 调用n=3S=3*fact(2)第 四 层 调用n=2S=2*fact(1)第 五 层 调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00图5-7 递归调用过程示意图 计算机系统处理上述过程时，其关键是要正确处理执行过程中的

52、递归调用层次和返回路径，也就是要记住每一次递归调用时的返回地址。在系统中是用一个线性表动态记忆调用过程中的路径，其处理原则为：（1）在开始执行程序前，建立一个线性表，其初始状态为空。（2）当发生调用（递归）时，将当前的调用的返回点地址插入到线性表的末尾；（3）当调用（递归）返回时，其返回地址从线性表的末尾取出。根据以上的原则，可以给出线性表中的元素变化状态如图3-2所示（以递归调用时n值的变化为例）：545453453245321图5-8 递归调用时线性表状态1 栈的定义及其运算1栈的定义栈的定义栈（stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进

53、行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO，last in first out ）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。a0a1an-1入栈出栈栈顶 top栈底 bottom图5-9栈的示意图图5-9是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前

54、位置。2栈的基本运算栈的基本运算（1）initStack(s) 初始化：初始化一个新的栈。（2）empty(s) 栈的非空判断：若栈s不空，则返回TRUE；否则，返回FALSE。（3）push(s,x) 入栈：在栈s的顶部插入元素x，若栈满，则返回FALSE；否则，返回TRUE。（4）pop(s) 出栈：若栈s不空，则返回栈顶元素，并从栈顶中删除该元素；否则，返回空元素NULL。（5）getTop(s) 取栈元素：若栈s不空，则返回栈顶元素；否则返回空元素NULL。（6）setEmpty(s) 置栈空操作：置栈s为空栈。栈是一种特殊的线性表，因此栈可采用顺序存储结构存储，也可以使用链式存储结构

55、存储。2 栈的顺序存储结构栈的顺序存储结构1顺序栈的数组表示顺序栈的数组表示与第二章讨论的一般的顺序存储结构的线性表一样，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也称为顺序栈。因此，我们可以使用一维数组来作为栈的顺序存储空间。设指针top指向栈顶元素的当前位置，以数组小下标的一端作为栈底，通常以top=0时为空栈，在元素进栈时指针top不断地加1，当top等于数组的最大下标值时则栈满。top=0top=1Atop=5ACDBEtop=3ABC图5-10 栈的存储结构（a）空栈；（b）插入元素A后；（c）插入元素B、C、D、E后；（d）删除元素E、D后（a）（b）（

56、c）（d）图5-10展示了顺序栈中数据元素与栈顶指针的变化。用C语言定义的顺序存储结构的栈如下：# define MAXNUM typedef struct Elemtype stackMAXNUM;int top; sqstack;鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈时，应设栈顶指针top=-1时为空栈。2顺序栈的基本运算算法顺序栈的基本运算算法（1）初始化栈【算法5.4 栈的初始化】int initStack(sqstack *s)/*创建一个空栈由指针S指出*/ if (s=(sqstack*)malloc(sizeof(sqstack)= =NULL)

57、 return FALSE; s-top= -1;return TRUE;（2）入栈操作【算法5.5 入栈操作】int push(sqstack *s, Elemtype x)/*将元素x插入到栈s中，作为s的新栈顶*/ if(s-top=MAXNUM-1) return FALSE; /*栈满*/ s-top+; s-stacks-top=x;return TRUE;（3）出栈操作【算法5.6 出栈操作】Elemtype pop(sqstack *s)/*若栈s不为空，则删除栈顶元素*/Elemtype x; if(s-topstacks-top; s-top-;return x;（4）取栈

58、顶元素操作【算法5.7 取栈顶元素】Elemtype gettop(sqstack *s)/*若栈s不为空，则返回栈顶元素*/ if(s-topstacks-top); 取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针top的位置，而取栈顶元素操作不改变栈的栈顶指针。（5）判栈空操作【算法5.8 判栈空操作】int Empty(sqstack *s)/*栈s为空时，返回为TRUE；非空时，返回为FALSE*/ if(s-toptop= -1;5.7 队列在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体现了“先来先服务”（即“先进先出”）的原则。队列在计算机系统中的应用也非常广泛。例

59、如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业作输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常会遇到两个设备之间的数据传输，不同的设备通常处理数据的速度是不同的，当需要在它们之间连续处理一批数据时，高速设备总是要等待低速设备，这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾，通常就是在这两个设备之间设置一个缓冲区。这样，高速设备就不必每次等待低速设备处理

60、完一个数据，而是把要处理的数据依次从一端加入缓冲区，而低速设备从另一端取走要处理的数据。1 队列的定义及其运算1队列的定义队列的定义队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。根据队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，first in first out ）的原则组织数据的，因此，队列也被称为“