返回本章首页
下一页
上一页
为了解决比较复杂的问题, 本章介绍 C语言提供的
一种最简单的构造类型 ──数组及应用 。
5.1 1维数组的定义和引用
5.2 2维数组的定义和引用
5.3 字符数组与字符串
5.4 数组作为函数参数
5.5 线性表
5.6 栈
5.7 队列
第 5章 数据的顺序存储结构及应用
上一章
返回目录
下一章
返回本章首页
下一页
上一页
5.1 1维数组的定义和引用
5.1.1 1维数组的定义
5.1.2 1维数组元素的引用
5.1.3 1维数组元素的初始化
5.1.4 1维数组应用举例
返回本章首页
下一页
上一页
5.1.1 1维数组的定义
[案例 5.1] 从键盘上任意输入 10个整数, 要求按从小到大的顺序
在屏幕上显示出来 。
排序的方法有很多, 本题采用冒泡法 。
冒泡法的基本思想,通过相邻两个数之间的比较和交换, 使排序
码 （ 数值 ） 较小的数逐渐从底部移向顶部, 排序码较大的数逐渐从顶
部移向底部 。 就像水底的气泡一样逐渐向上冒, 故而得名 。
由 A[n]~A[1]组成的 n个数据, 进行冒泡排序的过程可以描述为：
（ 1） 首先将相邻的 A[n]与 A[n-1]进行比较, 如果 A[n]的值小于
A[n-1]的值, 则交换两者的位置, 使较小的上浮, 较大的下沉；接着
比较 A[n-1]与 A[n-2],同样使小的上浮, 大的下沉 。 依此类推, 直到
比较完 A[2]和 A[1]后, A[1]为具有最小排序码 （ 数值 ） 的元素, 称第
一趟排序结束 。
（ 2） 然后在 A[n]~A[2]区间内, 进行第二趟排序, 使剩余元素中
排序码最小的元素上浮到 A[2]；重复进行 n-1趟后, 整个排序过程结
束 。
返回本章首页
下一页
上一页
/*案例代码文件名,AL5_1.C*/
/*功能：从键盘上任意输入 n个整数, 用冒泡法按从小到大地排序,
并在屏幕上显示出来 。 */
#include "stdio.h"
#define NUM 10 /*定义符号常量 （ 数据个数 N） */
main()
{ int data[NUM]; /*定义 1个 1维整型数组 data*/
int i,j,temp; /*定义循环变量和临时变量 */
clrscr(); /*库函数 clrscr()：清屏 */
printf("Please input 10 numbers:\n");
for(i=0; i<NUM; i++)
scanf("%d",&data[i]);
返回本章首页
下一页
上一页
/*冒泡法排序 */
for(i=0; i<NUM-1; i++) /*外循环：控制比较趟数 */
for(j=NUM-1; j>i; j--) /*内循环：进行每趟比较 */
if(data[j]<data[j-1]) /*如果 data[j]大于 data[j-1],交换两者的位置 */
{temp=data[j];
data[j]=data[j-1];
data[j-1]=temp;
};
/*输出排序后的数据 */
printf("\nthe result of sort:\n");
for(i=0; i<NUM; i++)
printf("%d ",data[i]);
getch(); /*等待键盘输入任一字符, 目的使程序暂停 */
}
返回本章首页
下一页
上一页
数组同变量一样, 也必须先定义, 后使用 。
1维数组是只有 1个下标的数组, 定义形式如下：
数据类型 数组名 [常量表达式 ][,数组名 2[常量表达式
2]……] ；
（ 1）, 数据类型, 是指数组元素的数据类型 。
（ 2） 数组名, 与变量名一样, 必须遵循标识符命名规
则 。
（ 3）“常量表达式”必须用方括号括起来，指的是数
组的元素个数（又称数组长度），它是一个整型值，其中可
以包含常数和符号常量，但不能包含变量。
注意, C语言中不允许动态定义数组 。
返回本章首页
下一页
上一页
特别说明,在数组定义时,, 常量表达式, 外的方
括号；以及元素引用时,, 下标表达式, 外的方括号,
都是 C语言语法规则所要求的, 不是本书所约定的可选项
的描述符号 ！
（ 4） 数组元素的下标, 是元素相对于数组起始地址
的偏移量, 所以从 0开始顺序编号 。
（ 5） 数组名中存放的是一个地址常量, 它代表整个
数组的首地址 。 同一数组中的所有元素, 按其下标的顺
序占用一段连续的存储单元 。
返回本章首页
下一页
上一页
5.1.2 数组元素的引用
引用数组中的任意一个元素的形式：
数组名 [下标表达式 ]
1．, 下标表达式, 可以是任何非负整型数据, 取值
范围是 0~（ 元素个数 -1） 。
特别强调,在运行 C语言程序过程中, 系统并不自动
检验数组元素的下标是否越界 。 因此在编写程序时, 保
证数组下标不越界是十分重要的 。
2,1个数组元素, 实质上就是 1个变量, 它具有和相
同类型单个变量一样的属性, 可以对它进行赋值和参与
各种运算 。
3,在 C语言中, 数组作为 1个整体, 不能参加数据运
算, 只能对单个的元素进行处理 。
返回本章首页
下一页
上一页
5.1.3 1维数组元素的初始化
初始化格式,
数据类型 数组名 [常量表达式 ]＝ {初值表 }
（ 1） 如果对数组的全部元素赋以初值, 定义时可以
不指定数组长度 （ 系统根据初值个数自动确定 ） 。 如果
被定义数组的长度, 与初值个数不同, 则数组长度不能
省略 。
（ 2）, 初值表, 中的初值个数, 可以少于元素个数,
即允许只给部分元素赋初值 。
（ 3） 根据存储类型的不同, 数组有静态数组 （ static）
和动态数组 （ auto） 之分；根据定义的位置不同, 数组有
内部数组 （ 在函数内部定义的数组 ） 和外部数组 （ 在函
数外部定义的数组 ） 之分 。
返回本章首页
下一页
上一页
5.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 con_key=?\x20?; /* ?\x20? 空格键的 ASCII码 */
float score[5],ratio[4]={0.1,0.2,0.2,0.5}; /*定义成绩,比例系数数组 */
while(con_key=='\x20')
返回本章首页
下一页
上一页
while(con_key=='\x20')
{clrscr();
printf("输入第 %2d个学生的成绩 \n",i++);
printf("平时 实习 测验 期末成绩 \n");
score[4]=0; /* score[4]：存储总评成绩 */
for(j=0; j<4; j++)
{scanf("%f",&score[j]);
score[4] += score[j] * ratio[j];
}
printf("总评成绩为,%6.1f\n",score[4]);
printf("\n按空格键继续,其它键退出 ");
con_key=getch(); /*getch()函数等待从键盘上输入一个字符 */
}
}
返回本章首页
下一页
上一页
5.2 2维数组的定义和引用
5.2.1 2维数组的定义
5.2.2 2维数组元素的引用
5.2.3 2维数组元素的初始化
5.2.4 2维数组应用举例
返回本章首页
下一页
上一页
[案例 5.3] 给一个 2＊ 3的 2维数组各元素赋值, 并输出全部元素的值 。
/*案例代码文件名,AL5_3.C*/
/*功能：从键盘上给 2＊ 3数组赋值, 并在屏幕上显示出来 。 */
#define Row 2
#define Col 3
#include "stdio.h"
main()
{ int i,j,array[Row][Col]; /*定义 1个 2行 3列的 2维数组 array*/
for(i=0; i<Row; i++) /*外循环：控制 2维数组的行 */
for(j=0; j<Col; j++) /*内循环：控制 2维数组的列 */
{printf("please input array[%2d][%2d]:",i,j);
scanf("%d",&array[i][j]); /*从键盘输入 a[i][j]的值 */
}
printf("\n");
/*输出 2维数组 array*/
for(i=0;i<Row;i++)
5.2.1 2维数组的定义
返回本章首页
下一页
上一页
{ for(j=0;j<Col;j++)
printf("%d\t",array[i][j]); /*将 a[i][j]的值显示在屏幕上 */
printf("\n");
}
getch();
}
2维数组的定义方式如下：
数据类型 数组名 [行常量表达式 ][列常量表达式 ][,
数组名 2[行常量表达式 2][列常量表达式 2]……];
1．数组元素在内存中的排列顺序为“按行存放”，即
先顺序存放第一行的元素，再存放第二行，以此类推。
2,设有一个 m*n的数组 x，则第 i行第 j列的元素 x[i][j]在
数组中的位置为,i*n+j（ 注意,行号、列号均从 0开始计
数）。
返回本章首页
下一页
上一页
3,可以把 2维数组看作是一种特殊的 1维数组：它
的元素又是一个 1维数组 。
例如, 对 x[3][2],可以把 x看作是一个 1维数组, 它
有 3个元素,x[0],x[1],x[2],每个元素又是一个包含 2
个元素的 1维数组, 如图 6-4所示 。 即把 x[0],x[1],x[2]
看作是 3个 1维数组的名字 。
返回本章首页
下一页
上一页
5.2.2 2维数组元素的引用
引用 2维数组元素的形式为：
数组名 [行下标表达式 ][列下标表达式 ]
1．, 行下标表达式, 和, 列下标表达式,, 都应是
整型表达式或符号常量 。
2．, 行下标表达式, 和, 列下标表达式, 的值, 都
应在已定义数组大小的范围内 。 假设有数组 x[3][4],则可
用的行下标范围为 0~2,列下标范围为 0~3。
3,对基本数据类型的变量所能进行的操作, 也都适
合于相同数据类型的 2维数组元素 。
返回本章首页
下一页
上一页
5.2.3 2维数组元素的初始化
1,按行赋初值
数据类型 数组名 [行常量表达式 ][列常量表达式 ]＝ {{第 0行初值
表 },{第 1行初值表 },……, {最后 1行初值表 }}；
赋值规则：将, 第 0行初值表, 中的数据, 依次赋给第 0行中各元
素；将, 第 1行初值表, 中的数据, 依次赋给第 1行各元素；以此类
推 。
2,按 2维数组在内存中的排列顺序给各元素赋初值
数据类型 数组名 [行常量表达式 ][列常量表达式 ]＝ {初值表 }；
赋值规则：按 2维数组在内存中的排列顺序, 将初值表中的数据,
依次赋给各元素 。
如果对全部元素都赋初值，则“行数”可以省略。 注意,只能
省略“行数”。
返回本章首页
下一页
上一页
5.2.4 2维数组应用举例
[案例 5.4] 有 M个学生，学习 N门课程，已知所有学生的各科成绩，
编程：分别求每个学生的平均成绩和每门课程的平均成绩。
/*案例代码文件名,AL5_4.C*/
/*功能：计算个人平均成绩与各科平均成绩，并在屏幕上显示出来。 */
#define NUM_std 5 /*定义符号常量人数为 5*/
#define NUM_course 4 /*定义符号常量课程为 4*/
#include "stdio.h"
main()
{ int i,j;
static float score[NUM_std+1][NUM_course+1]={{78,85,83,65},
{88,91,89,93},{72,65,54,75},
{86,88,75,60},{69,60,50,72}};
返回本章首页
下一页
上一页
for(i=0;i<NUM_std;i++)
{for(j=0;j<NUM_course;j++)
{ score[i][NUM_course] += score[i][j];/*求第 i个人的总成绩 */
score[NUM_std][j] += score[i][j];/*求第 j门课的总成绩 */
}
score[i][NUM_course] /= NUM_course;/*求第 i个人的平均成绩 */
}
for(j=0;j<NUM_course;j++)
score[NUM_std][j] /= NUM_std; /*求第 j门课的平均成绩 */
clrscr();
/*输出表头 */
printf("学生编号 课程 1 课程 2 课程 3 课程 4 个人平均 \n");
/*输出每个学生的各科成绩和平均成绩 */
返回本章首页
下一页
上一页
for(i=0;i<NUM_std;i++)
{ printf("学生 %d\t",i+1);
for(j=0;j<NUM_course+1;j++)
printf("%6.1f\t",score[i][j]);
printf("\n");
}
/*输出 1条短划线 */
for(j=0;j<8*(NUM_course+2);j++)
printf("-");
printf("\n课程平均 ");
/*输出每门课程的平均成绩 */
for(j=0;j<NUM_course;j++)
printf("%6.1f\t",score[NUM_std][j]);
printf("\n");
getch();
}
返回本章首页
下一页
上一页
5.3 字符数组与字符串
5.3.1 字符数组的逐个字符操作
5.3.2 字符数组的整体操作
5.3.3 常用的字符串处理函数
返回本章首页
下一页
上一页
5.3.1 字符数组的逐个字符操作
[案例 5.5]从键盘输入一个字符串, 回车键结束, 并将字符串在屏幕上输出 。
/*案例代码文件名,AL5_5.C*/
main()
{int i;
static char str[80];
clrscr();
for(i=0;i<80;i++)
{ str[i]=getch(); /*逐次给数组元素 str[i]赋值, 但不回显在屏幕上 */
printf("*"); /*以星号代替输入字符的个数 */
if(str[i]=='\x0d') break;/*若输入回车则终止循环 */
}
i=0;
while(str[i]!='\x0d')
printf("%c",str[i++]); /*逐次输出字符数组的各个元素 */
printf("\n");
getch(); /*程序暂停 */
}
返回本章首页
下一页
上一页
1,字符数组的定义
1维字符数组, 用于存储和处理 1个字符串, 其定义格式
与 1维数值数组一样 。
2维字符数组, 用于同时存储和处理多个字符串, 其定义
格式与 2维数值数组一样 。
2,字符数组的初始化
字符数组的初始化, 可以通过为每个数组元素指定初值
字符来实现 。
3,字符数组的引用
字符数组的逐个字符引用, 与引用数值数组元素类似 。
返回本章首页
下一页
上一页
（ 1） 字符数组的输入
除了可以通过初始化使字符数组各元素得到初值外,
也可以使用 getchar()或 scanf()函数输入字符 。
例如：
char str[10]；
……
for(i=0; i<10; i++)
{ scanf("%c",&str[i])；
fflush(stdin); /*清除键盘输入缓冲区 */
}
……
返回本章首页
下一页
上一页
（ 2） 字符数组的输出
字符数组的输出, 可以用 putchar()或 printf()函数 。
例如：
char str[10]="c language";
……
for(i=0; i<10; i++) printf("%c",str[i])；
printf("\n");
……
注意,逐个字符输入, 输出时, 要指出元素的下标,
而且使用, %c”格式符 。 另外, 从键盘上输入字符时, 无
需输入字符的定界符 ──单引号；输出时, 系统也不输出
字符的定界符 。
返回本章首页
下一页
上一页
5.3.2 字符数组的整体操作
[案例 5.6] 字符数组的整体输入与输出 。
/*案例代码文件名,AL5_6.C*/
/*功能：将 2维字符数组进行初始化, 并在屏幕上输出 */
main()
{ int i;
char name[5][9]={"张三山 ","李四季 ","王五魁 ","刘六顺 ","赵七巧 "};
for(i=0;i<5;i++)
printf("\n%s\t",name[i]); /*name[i]代表该行数组元素的首地址 */
getch();
}
1．字符串及其结束标志
所谓字符串，是指若干有效字符的序列。 C语言中的字符串，可以包
括字母、数字、专用字符、转义字符等。
C语言规定：以‘ \0?作为字符串结束标志（‘ \0?代表 ASCII码为 0的字
符，表示一个“空操作”，只起一个标志作用）。因此可以对字符数组采
用另一种方式进行操作了 ──字符数组的整体操作 。
返回本章首页
下一页
上一页
注意,由于系统在存储字符串常量时, 会在串尾自动加上 1个结束
标志, 所以无需人为地再加 1个 。
另外, 由于结束标志也要在字符数组中占用一个元素的存储空间,
因此在说明字符数组长度时, 至少为字符串所需长度加 1。
2,字符数组的整体初始化
字符串设置了结束标志以后, 对字符数组的初始化, 就可以用字符
串常量来初始化字符数组 。
3,字符数组的整体引用
（ 1） 字符串的输入
除了可以通过初始化使字符数组各元素得到初值外, 也可以使用
scanf()函数输入字符串 。
（ 2） 字符串的输出
printf()函数, 不仅可以逐个输出字符数组元素, 还可以整体输出存
放在字符数组中的字符串 。
返回本章首页
下一页
上一页
5.3.3 常用的字符串处理函数
字符串标准函数的原型在头文件 string.h中 。
1,输入字符串 ──gets()函数
（ 1） 调用方式,gets(字符数组 )
（ 2） 函数功能：从标准输入设备 (stdin)──键盘上, 读取
1个字符串 （ 可以包含空格 ）, 并将其存储到字符数组中去 。
（ 3） 使用说明
1） gets()读取的字符串, 其长度没有限制, 编程者要保
证字符数组有足够大的空间, 存放输入的字符串 。
2） 该函数输入的字符串中允许包含空格, 而 scanf()函数
不允许 。
返回本章首页
下一页
上一页
2,输出字符串 ──puts()函数
（ 1） 调用方式,puts(字符数组 )
（ 2） 函数功能：把字符数组中所存放的字符串, 输出
到标准输出设备中去, 并用 ‘ \n?取代字符串的结束标志 ‘ \0?。
所以用 puts()函数输出字符串时, 不要求另加换行符 。
（ 3） 使用说明
1)字符串中允许包含转义字符, 输出时产生一个控制操
作 。
2)该函数一次只能输出一个字符串, 而 printf()函数也能
用来输出字符串, 且一次能输出多个 。
返回本章首页
下一页
上一页
3,字符串比较 ──strcmp()函数
（ 1） 调用方式,strcmp(字符串 1,字符串 2)
其中, 字符串, 可以是串常量, 也可以是 1维字符数组 。
（ 2） 函数功能：比较两个字符串的大小 。
如果,字符串 1=字符串 2,函数返回值等于 0；
字符串 1<字符串 2,函数返回值负整数；
字符串 1>字符串 2,函数返回值正整数 。
（ 3） 使用说明
1） 如果一个字符串是另一个字符串从头开始的子串, 则母串为大 。
2） 不能使用关系运算符, ＝＝, 来比较两个字符串, 只能用
strcmp() 函数来处理 。
返回本章首页
下一页
上一页
[案例 5.7] gets函数和 strcmp函数的应用 。
/*案例代码文件名,AL6_7.C*/
/*功能：简单密码检测程序 */
#include "stdio.h"
main()
{char pass_str[80]; /*定义字符数组 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); /*输入三次错误的密码, 退出程序 */
}
/*输入正确密码所进入的程序段 */
}
返回本章首页
下一页
上一页
4,拷贝字符串 ──strcpy()函数
（ 1） 调用方式,strcpy(字符数组,字符串 )
其中, 字符串, 可以是串常量, 也可以是字符数组 。
（ 2） 函数功能：将, 字符串, 完整地复制到, 字符数
组, 中, 字符数组中原有内容被覆盖 。
（ 3） 使用说明
1） 字符数组必须定义得足够大, 以便容纳复制过来的
字符串 。 复制时, 连同结束标志 '\0'一起复制 。
2） 不能用赋值运算符, ＝, 将一个字符串直接赋值给
一个字符数组, 只能用 strcpy()函数来处理 。
返回本章首页
下一页
上一页
5,连接字符串 ──strcat()函数
（ 1） 调用方式,strcat(字符数组,字符串 )
（ 2） 函数功能：把, 字符串, 连接到, 字符数组, 中
的字符串尾端, 并存储于, 字符数组, 中 。, 字符数组,
中原来的结束标志, 被, 字符串, 的第一个字符覆盖, 而
,字符串, 在操作中未被修改 。
（ 3） 使用说明
1） 由于没有边界检查, 编程者要注意保证, 字符数组,
定义得足够大, 以便容纳连接后的目标字符串；否则, 会
因长度不够而产生问题 。
2） 连接前两个字符串都有结束标志 '\0',连接后, 字
符数组, 中存储的字符串的结束标志 '\0'被舍弃, 只在目标
串的最后保留一个 '\0'。
返回本章首页
下一页
上一页
6,求字符串长度 ──strlen()函数 （ len是 length的缩写 ）
（ 1） 调用方式,strlen(字符串 )
（ 2） 函数功能：求字符串 （ 常量或字符数组 ） 的实际长度
（ 不包含结束标志 ） 。
7,将字符串中大写字母转换成小写 ──strlwr()函数
（ 1） 调用方式,strlwr(字符串 )
（ 2） 函数功能：将字符串中的大写字母转换成小写, 其它字
符 （ 包括小写字母和非字母字符 ） 不转换 。
8,将字符串中小写字母转换成大写 ──strupr()函数
（ 1） 调用方式,strupr(字符串 )
（ 2） 函数功能：将字符串中小写字母转换成大写, 其它字符
（ 包括大写字母和非字母字符 ） 不转换 。
返回本章首页
下一页
上一页
5.4 数组作为函数参数
? 数组用作函数参数有两种形式：一种是把数组元素
（又称下标变量）作为实参使用；另一种是把数组名作
为函数的形参和实参使用。
? 5.4.1 数组元素作为函数参数
? 5.4.2 数组名作为函数的形参和实参
返回本章首页
下一页
上一页
5.4.1 数组元素作为函数参数
? 数组元素就是下标变量，它与普通变量并无区别。数
组元素只能用作函数实参，其用法与普通变量完全相同：
在发生函数调用时，把数组元素的值传送给形参，实现单
向值传送。
? [案例 5.8] 写一函数, 统计字符串中字母的个数 。
? /*案例代码文件名,AL5_8.C*/
? /*功能：数组元素作为函数实参 */
? int isalp(char c)
? { if (c>='a'&&c<='z'||c>='A'&&c<='Z')
? return(1);
? else return(0);
? }
返回本章首页
下一页
上一页
? main()
? { int i,num=0;
? char str[255];
? printf("Input a string,");
? gets(str);
? for(i=0;str[i]!='\0';i++)
? if (isalp(str[i])) num++;
? puts(str);
? printf("num=%d\n",num);
? getch();
? }
返回本章首页
下一页
上一页
? 说明：
? （ 1） 用数组元素作实参时, 只要数组类型和函数的
形参类型一致即可, 并不要求函数的形参也是下标变量 。
换句话说, 对数组元素的处理是按普通变量对待的 。
? （ 2） 在普通变量或下标变量作函数参数时, 形参变
量和实参变量是由编译系统分配的两个不同的内存单元 。
在函数调用时发生的值传送, 是把实参变量的值赋予形
参变量 。
?
返回本章首页
下一页
上一页
5.4.2 数组名作为函数的形参和实参
? 数组名作函数参数时, 既可以作形参, 也可以作实参 。
? 数组名作函数参数时, 要求形参和相对应的实参都必
须是类型相同的数组 （ 或指向数组的指针变量 ）, 都必
须有明确的数组说明
? [案例 5.9] 已知某个学生 5门课程的成绩, 求平均成绩 。
? /*案例代码文件名,AL5_9.C*/
? float aver(float a[ ]) /*求平均值函数 */
? { int i；
? float av,s=a[0]；
? for(i=1； i<5； i++) s += a[i]；
? av=s/5；
? return av；
? }
返回本章首页
下一页
上一页
? void main()
? { float sco[5],av；
? int i；
? printf("\ninput 5 scores:\n")；
? for(i=0； i<5； i++) scanf("%f",&sco[i])；
? av=aver(sco)； /*调用函数, 实参为一数组名 */
? printf("average score is %5.2f\n",av)；
? getch();
? }
返回本章首页
下一页
上一页
说明,
（ 1） 用数组名作函数参数, 应该在调用函数和被调
用函数中分别定义数组, 且数据类型必须一致, 否则结
果将出错 。 例如, 在本案例中, 形参数组为 a[],实参数
组为 sco[],它们的数据类型相同 。
（ 2） C编译系统对形参数组大小不作检查, 所以形
参数组可以不指定大小 。 例如, 本案例中的形参数组 a[]。
如果指定形参数组的大小, 则实参数组的大小必须
大于等于形参数组, 否则因形参数组的部分元素没有确
定值而导致计算结果错误 。
返回本章首页
下一页
上一页
5.5线性表
一, 线性表的逻辑结构
? 线性表由一组具有相同属性的数据元素构成 。 数据元素的含义广泛, 在
不同的具体情况下, 可以有不同的含义 。 例如：英文字母表 （ A,B，
C,…, Z） 是一个长度为 26的线性表, 其中的每一个字母就是一个数据
元素；再如, 某公司 2000年每月产值表 （ 400,420,500,…, 600,650）
(单位：万元 )是一个长度为 12的线性表, 其中的每一个数值就是一个数
据元素 。 上述两例中的每一个数据元素都是不可分割的, 在一些复杂的
线性表中, 每一个数据元素又可以由若干个数据项组成, 在这种情况下,
通常将数据元素称为记录 （ record）, 例如, 图 5－ 1的某单位职工工资
表就是一个线性表, 表中每一个职工的工资就是一个记录, 每个记录包
含八个数据项：职工号, 姓名, 基本工资 …… 。
返回本章首页
下一页
上一页
职工
号 姓名
基本
工资
岗位
工资
奖
金
应发
工资
扣
款
实发
工资
1201 张强 540 300 200 1040 20 1020
1301 周敏 500 200 200 900 20 880
1202 徐黎 芬 550 300 200 1050 30 1020
1105 黄承 振 530 250 200 980 20 960
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
图 5－ 1 职工工资表
返回本章首页
下一页
上一页
? 矩阵也是一个线性表, 但它是一个比较复杂的线性表 。 在矩阵中, 我们可以
把每行看成是一个数据元素, 也可以把每列看成是一个数据元素, 而其中的
每一个数据元素又是一个线性表 。
? 综上所述, 一个线性表是 n≥0个数据元素 a0,a1,a2,…, an-1的有限序列 。
如果 n>0,则除 a0和 an-1外, 有且仅有一个直接前趋和一个直接后继数据元素,
ai（ 0≤i≤n-1） 为线性表的第 i个数据元素, 它在数据元素 ai-1之后, 在 ai+1之前 。
a0为线性表的第一个数据元素, 而 an-1是线性表的最后一个数据元素；若 n=0，
则为一个空表, 表示无数据元素 。 因此, 线性表或者是一个空表 （ n=0）,
或者可以写成,（ a0,a1,a2,…, ai-1,ai,ai+1,…, an-1） 。
? 抽象数据类型线性表的定义如下：
? LinearList=(D,R)
? 其中,D={ ai| ai∈ ElemSet,i=0,1,2,…, n-1 n≥1}
? R={<ai-1,ai>| ai-1,ai∈ D,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) 删除：在给定的线性表 L中，删除第 i个元素。线性表 L的
长度减 1。
4,Locate(L,x) 查找定位：对给定的值 x，若线性表 L中存在一个元素 ai
与之相等，则返回该元素在线性表中的位置的序号 i，否则返回 Null（空）
。
5,Length(L) 求长度：对给定的线性表 L，返回线性表 L的数据元素的
个数。
6,Get(L,i) 存取：对给定的线性表 L，返回第 i（ 0≤i≤Length(L)-1）个数
据元素，否则返回 Null。
7,Traverse(L) 遍历：对给定的线性表 L，依次输出 L的每一个数据元素
。
8,Copy(L,C) 复制：将给定的线性表 L复制到线性表 C中。
9,Merge(A,B,C) 合并：将给定的线性表 A和 B合并为线性表 C。
上面我们定义了线性表的逻辑结构和基本操作 。 在计算机内, 线性表有两
种基本的存储结构：顺序存储结构和链式存储结构 。 下面我们将讨论顺序
存储结构下实现各操作的算法 。
返回本章首页
下一页
上一页
二,线性表的顺序存储结构
? 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素, 称作线
性表的顺序存储结构 。
1 线性表的顺序存储结构
在线性表的顺序存储结构中, 其前后两个元素在存储空间
中是紧邻的, 且前驱元素一定存储在后继元素的前面 。 由于线性表的所有
数据元素属于同一数据类型, 所以每个元素在存储器中占用的空间大小相
同, 因此, 要在该线性表中查找某一个元素是很方便的 。 假设线性表中的
第一个数据元素的存储地址为 Loc(a0),每一个数据元素占 d字节, 则线性表
中第 i个元素 ai在计算机存储空间中的存储地址为：
Loc(ai)= Loc(a0)+id
在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是
因为数组具有如下特点：（ 1）数据中的元素间的地址是连续的；（ 2）
数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结
构是类似的。
返回本章首页
下一页
上一页
1,一维数组
若定义数组 A[n]={ a0,a1,a2,…, an-1}，假设每一个数组元素占用 d个字
节，则数组元素 A[0],A[1],A[2],…, A[n-1]的地址分别为 Loc(A[0])，
Loc(A[0])+d,Loc(A[0])+2d,…, Loc(A[0])+（ n-1） d 。其结构如图 5－ 2
所示。
返回本章首页
下一页
上一页
若定义数组 A[n][m],表示此数组有 n行 m列, 如下图 5－ 3所示 。
0 1 2 … j … m -1
0 a00 a01 a02 … a 0j … a 0 m-1
1 a10 a11 a12 … a 1j … a 1 m-1
2 a20 a21 a22 … a 2j … a 2 m-1
i ai0 ai1 ai2 … a ij … a i m-1
n-1 an-1,0 an-1,1 an-1,2 … a n-1,j … a n-1,m-1
图 5－ 3 二维
数组
２, 二维数组
返回本章首页
下一页
上一页
在 C语言中, 二维数组的保存是按照行方式存储的, 先将第一行元素
排好, 接着排第二行元素, 直至所有行的元素排完 。 如图 5-4所示 。
图 5-4 二维数组存
储示意图
返回本章首页
下一页
上一页
2 线性表在顺序存储结构下的运算
可用 C语言描述顺序存储结构下的线性表 （ 顺序表 ） 如下：
#define TRUE 1
#define FALSE 0
#define MAXNUM <顺序表最大元素个数 >
Elemtype List[MAXNUM] ; /*定义顺序表 List*/
int num=-1; /*定义当前数据元素下标, 并初始
化 */
我们还可将数组和表长封装在一个结构体中：
struct Linear_list {
Elemtype List[MAXNUM]; /*定义数组域 */
int length; /*定义表长域 */
}
返回本章首页
下一页
上一页
1,顺序表的插入操作
在 长 度 为 num(0≤num≤MAXNUM-2) 的 顺 序 表 List 的第
i(0≤i≤num+1)个数据元素之前插入一个新的数据元素 x时,
需将最后一个即第 num个至第 i个元素 （ 共 num-i+1个元素 ）
依次向后移动一个位置, 空出第 i个位置, 然后把 x插入到
第 i个存储位置, 插入结束后顺序表的长度增加 1,返回
TRUE值；若 i＜ 0或 i＞ num+1,则无法插入, 返回 FALSE。
如图 2-5 所示 。
在 长 度 为 num(0≤num≤MAXNUM-2) 的 顺 序 表 List 的第
i(0≤i≤num+1)个数据元素之前插入一个新的数据元素 x时,
需将最后一个即第 num个至第 i个元素 （ 共 num-i+1个元素 ）
依次向后移动一个位置, 空出第 i个位置, 然后把 x插入到
第 i个存储位置, 插入结束后顺序表的长度增加 1,返回
TRUE值；若 i＜ 0或 i＞ num+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+2 ai+1
┇ ┇
num anum
插入
x
图 5-5 在数组中插入元素
返回本章首页
下一页
上一页
其算法如下：
【 算法 5.1 顺序表的插入 】
int Insert(Elemtype List[],int *num,int i,Elemtype x)
{/*在顺序表 List[]中, *num为表尾元素下标位置, 在第 i个元素前
插入数据元素 x,若成功, 返回 TRUE,否则返回 FALSE。 */
int j;
if (i<0||i>*num+1)
{printf(“Error!”); /*插入位置出错 */
return FALSE;}
if (*num>=MAXNUM-1)
{printf(“overflow!”);
return FALSE; /*表已满 */｝
for (j=*num;j>=i;j--)
List[j+1]=List[j]; /*数据元素后移 */
List[i]=x; /*插入 x*/
(*num)++; /*长度加 1*/
return TRUE;}
注,顺序表 List的最大数据元素个数为 MAXNUM,num标识为顺
序表的当前表尾 （ num≤MAXNUM-1） 。
返回本章首页
下一页
上一页
２．顺序表的删除操作
0 a0
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+1 ai+1
┇ ┇
num anum
图 5-6 在数组
中删除元素
在长度为 num(0≤num≤MAXNUM-1)的顺序表 List,删除第 i(0≤i≤num)个数
据元素, 需将第 i至第 num个数据元素的存储位置 （ num-i+1） 依次前移,
并使顺序表的长度减 1,返回 TRUE值, 若 i＜ 0或 i＞ num,则无法删除,
返回 FALSE值, 如图 5-6所示 。
返回本章首页
下一页
上一页
其算法如下：
【 算法 5.2 顺序表的删除 】
int Delete(Elemtype List[],int *num,int i)
{/*在线性表 List[]中, *num为表尾元素下标位置, 删除第 i个元素, 线性
表的元素减 1,若成功, 则返回 TRUE；否则返回 FALSE。 */
int j;
if(i<0||i>*num)
{printf(“Error!”); return FALSE; /*删除位置出错 ！ */ }
for(j=i+1;j<=*num;j++)
List[j-1]=List[j]; /*数据元素前移 */
(*num)--; /*长度减 1*/
return TRUE; }
从上述两个算法来看, 很显然, 在线性表的顺序存储结构中插入或删除
一个数据元素时, 其时间主要耗费在移动数据元素上 。 而移动元素的次数
取决于插入或删除元素的位置 。
假设 Pi是在第 i个元素之前插入一个元素的概率, 则在长度为 n的线性表中
插入一个元素时所需移动元素次数的平均次数为
)(
0
inpE
n
i
iin s ?? ?
?
返回本章首页
下一页
上一页
假设 qi是删除第 i个元素的概率, 则在长度为 n的线性表中删除一个元素时
所需移动元素次数的平均次数为
如果在线性表的任何位置插入或删除元素的概率相等, 即
则
可见, 在顺序存储结构的线性表中插入或删除一个元素时, 平均要移动
表中大约一半的数据元素 。 若表长为 n,则插入和删除算法的时间复杂度都
为 O(n)。
在顺序存储结构的线性表中其他的操作也可直接实现, 在此不再讲述 。
)1(1
0
??? ??
?
inqE n
i
id e l
1
1
?? np inq i 1?
2)(1
1
0
nin
nE
n
i
in s ???? ?
?
2
1)1(1 1
0
????? ??
?
nin
nE
n
i
d e l
返回本章首页
下一页
上一页
例：将有序线性表 La={2,4,6,7,9},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_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(a<b) {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_length) { b=get(La,i);insert(Lc,++k,b); } }
返回本章首页
下一页
上一页
3,顺序表存储结构的特点
线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出,
因此顺序存储结构的线性表是可以随机存取其中的任意元素 。 也就是说
定位操作可以直接实现 。 高级程序设计语言提供的数组数据类型可以直
接定义顺序存储结构的线性表, 使其程序设计十分方便 。
但是, 顺序存储结构也有一些不方便之处, 主要表现在：
（ 1） 数据元素最大个数需预先确定, 使得高级程序设计语言编译系统需
预先分配相应的存储空间 。
（ 2） 插入与删除运算的效率很低 。 为了保持线性表中的数据元素的顺序
,在插入操作和删除操作时需移动大量数据 。 这对于插入和删除操作频
繁的线性表, 以及每个数据元素所占字节较大的问题将导致系统的运行
速度难以提高 。
（ 3） 顺序存储结构的线性表的存储空间不便于扩充 。 当一个线性表分配
顺序存储空间后, 如果线性表的存储空间已满, 但还需要插入新的元素
,则会发生, 上溢, 错误 。 在这种情况下, 如果在原线性表的存储空间
后找不到与之连续的可用空间, 则会导致运算的失败或中断 。
返回本章首页
下一页
上一页
5.6 栈
在各种程序设计语言中都有子程序 （ 或称函数, 过程 ） 调用功能 。 而
子程序也可以调用其它的子程序, 甚至可以直接或间接地调用自身,
这种调用关系就是递归 。 下面以求阶乘的递归方法为例, 来分析计算
机系统是如何处理这种递归调用关系的 。
求 n！ 的递归方法的思路是：
相应的 C语言函数是：
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!=%f\n”,fact(5)); }
)1(
)1,0(
)!1(*
1!
?
?
??
?
?? n
n
nnn
返回本章首页
下一页
上一页
图 5-7给出了递归调用执行过程 。 从图中可看到 fact函数共被调用 5次,
即 fact(5),fact(4),fact(3),fact(2),fact(1)。 其中, fact(5)为主函数调
用, 其它则为在 fact函数内的调用 。 每一次递归调用并未立即得到结
果, 而是进一步向深度递归调用, 直到 n=1或 n=0时, 函数 fact才有结
果为 1,然后再一一返回计算, 最终得到结果 。
主函数
mani()
printf(“fact(5)”) 第一层调
用
n=5
s=5*fact(4) 第二层调
用
n=4
s=4*fact(3) 第三层调
用
n=3
S=3*fact(2) 第四层调
用
n=2
S=2*fact(1)
第五层调
用
n=1
S=1
fact(1)
=1
fact(2)
=2
fact(3)
=6
fact(4)
=24
fact(5)=
120
输出
s=120.00
图 5-7 递归调用过程示意图
返回本章首页
下一页
上一页
计算机系统处理上述过程时, 其关键是要正确处理执行过程中的递归
调用层次和返回路径, 也就是要记住每一次递归调用时的返回地址 。 在
系统中是用一个线性表动态记忆调用过程中的路径, 其处理原则为：
（ 1） 在开始执行程序前, 建立一个线性表, 其初始状态为空 。
（ 2） 当发生调用 （ 递归 ） 时, 将当前的调用的返回点地址插入到线
性表的末尾；
（ 3） 当调用 （ 递归 ） 返回时, 其返回地址从线性表的末尾取出 。
根据以上的原则, 可以给出线性表中的元素变化状态如图 3-2所示 （
以递归调用时 n值的变化为例 ）,
5 45
45 3 45 3 2 45 3 2 1
图 5-8 递归调用时线性
表状态
返回本章首页
下一页
上一页
1 栈的定义及其运算
1,栈的定义
栈 （ stack） 是一种只允许在一端进行插入和删除的线性表, 它是一种操作
受限的线性表 。 在表中只允许进行插入和删除的一端称为栈顶 （ top）, 另
一端称为栈底 (bottom)。 栈的插入操作通常称为入栈或进栈 (push),而栈的
删除操作则称为出栈或退栈 (pop)。 当栈中无数据元素时, 称为空栈 。
根据栈的定义可知, 栈顶元素总是最后入栈的, 因而是最先出栈；栈底元
素总是最先入栈的, 因而也是最后出栈 。 这种表是按照后进先出 （ LIFO，
last in first out ） 的原则组织数据的, 因此, 栈也被称为, 后进先出, 的线
性表 。
a0
a1
an-1
入栈 出栈
栈顶 top
栈底
bottom 图 5-9栈的示意图
．
．
．
图 5-9是一个栈的示意图, 通常用指针 top指示栈顶的位置, 用指针 bottom
指向栈底 。 栈顶指针 top动态反映栈的当前位置 。
返回本章首页
下一页
上一页
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为空栈 。
栈是一种特殊的线性表, 因此栈可采用顺序存储结构存储, 也可以
使用链式存储结构存储 。
返回本章首页
下一页
上一页
2 栈的顺序存储结构
1,顺序栈的数组表示
与第二章讨论的一般的顺序存储结构的线性表一样, 利用一组地址连续的
存储单元依次存放自栈底到栈顶的数据元素, 这种形式的栈也称为顺序栈
。 因此, 我们可以使用一维数组来作为栈的顺序存储空间 。 设指针 top指向
栈顶元素的当前位置, 以数组小下标的一端作为栈底, 通常以 top=0时为空
栈, 在元素进栈时指针 top不断地加 1,当 top等于数组的最大下标值时则栈
满 。
top=0 top=1
A
top=5
A
C
D
B
E
top=3
A
BC
图 5-10 栈的存储结构
（ a）空栈；（ b）插入元素 A后；（ c
）插入元素 B,C,D,E后；（ d）删
除元素 E,D后
（ a） （ b） （ c） （ d）
图 5-10展示了顺序栈中数据元素与栈顶指针的变化 。
返回本章首页
下一页
上一页
用 C语言定义的顺序存储结构的栈如下：
# define MAXNUM <最大元素数 >
typedefstruct {
Elemtype stack[MAXNUM];
int top; } sqstack;
鉴于 C语言中数组的下标约定是从 0开始的, 因而使用 C语言的一维
数组作为栈时, 应设栈顶指针 top=-1时为空栈 。
2,顺序栈的基本运算算法
（ 1） 初始化栈
【 算法 5.4 栈的初始化 】
int initStack(sqstack *s)
{/*创建一个空栈由指针 S指出 */
if ((s=(sqstack*)malloc(sizeof(sqstack)))= =NULL) 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->stack[s->top]=x;
return TRUE;
}
（ 3） 出栈操作
【 算法 5.6 出栈操作 】
Elemtype pop(sqstack *s)
{/*若栈 s不为空, 则删除栈顶元素 */
Elemtype x;
if(s->top<0) return NULL; /*栈空 */
x=s->stack[s->top];
s->top--;
return x;
}
返回本章首页
下一页
上一页
（ 4） 取栈顶元素操作
【 算法 5.7 取栈顶元素 】
Elemtype gettop(sqstack *s)
{/*若栈 s不为空, 则返回栈顶元素 */
if(s->top<0) return NULL; /*栈空 */
return (s->stack[s->top]);
}
取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针 top的位置, 而取栈
顶元素操作不改变栈的栈顶指针 。
（ 5） 判栈空操作
【 算法 5.8 判栈空操作 】
int Empty(sqstack *s)
{/*栈 s为空时, 返回为 TRUE；非空时, 返回为 FALSE*/
if(s->top<0) return TRUE;
return FALSE;
}（ 6） 置空操作
【 算法 5.9 栈置空操作 】
void setEmpty(sqstack *s)
{/*将栈 s的栈顶指针 top,置为 -1*/
s->top= -1;
}
返回本章首页
下一页
上一页
5.7 队列
在日常生活中队列很常见, 如, 我们经常排队购物或购票, 排队是体
现了, 先来先服务, （ 即, 先进先出, ） 的原则 。
队列在计算机系统中的应用也非常广泛 。 例如：操作系统中的作业排
队 。 在多道程序运行的计算机系统中, 可以同时有多个作业运行, 它
们的运算结果都需要通过通道输出, 若通道尚未完成输出, 则后来的
作业应排队等待, 每当通道完成输出时, 则从队列的队头退出作业作
输出操作, 而凡是申请该通道输出的作业都从队尾进入该队列 。
计算机系统中输入输出缓冲区的结构也是队列的应用 。 在计算机系统
中经常会遇到两个设备之间的数据传输, 不同的设备通常处理数据的
速度是不同的, 当需要在它们之间连续处理一批数据时, 高速设备总
是要等待低速设备, 这就造成计算机处理效率的大大降低 。 为了解决
这一速度不匹配的矛盾, 通常就是在这两个设备之间设置一个缓冲区
。 这样, 高速设备就不必每次等待低速设备处理完一个数据, 而是把
要处理的数据依次从一端加入缓冲区, 而低速设备从另一端取走要处
理的数据 。
返回本章首页
下一页
上一页
1 队列的定义及其运算
1,队列的定义
队列 （ queue） 是一种只允许在一端进行插入, 而在另一端进行删除的线
性表, 它是一种操作受限的线性表 。 在表中只允许进行插入的一端称为队
尾 （ rear）, 只允许进行删除的一端称为队头 (front)。 队列的插入操作通常
称为入队列或进队列, 而队列的删除操作则称为出队列或退队列 。 当队列
中无数据元素时, 称为空队列 。
根据队列的定义可知, 队头元素总是最先进队列的, 也总是最先出队列；
队尾元素总是最后进队列, 因而也是最后出队列 。 这种表是按照先进先出
（ FIFO,first in first out ） 的原则组织数据的, 因此, 队列也被称为, 先
进先出, 表 。
假若队列 q={a0,a1,a2,…, an-1},进队列的顺序为 a0,a1,a2,…, an-1
,则队头元素为 a0,队尾元素为 an-1。
入列出列 a0 a1 a2 ai an-1
front rear
图 5-11 队列的示意
图
… …
图 5-11是一个队列的示意图，通常用指针 front指示队头的位置，用指针 rear指
向队尾。
返回本章首页
下一页
上一页
2,队列的基本运算
（ 1） initQueue(q) 初始化：初始化一个新的队列 。
（ 2） empty(q) 队列非空判断：若队列 q不空, 则返回 TRUE；否则, 返
回 FALSE。
（ 3） append(q,x) 入队列：在队列 q的尾部插入元素 x,使元素 x成为新的
队尾 。 若队列满, 则返回 FALSE；否则, 返回 TRUE。
（ 4） delete(s) 出队列：若队列 q不空, 则返回队头元素, 并从队头删除
该元素, 队头指针指向原队头的后继元素；否则, 返回空元素 NULL。
（ 5） getHead(q) 取队头元素：若队列 q不空, 则返回队头元素；否则返
回空元素 NULL。
（ 6） length(q) 求队列长度：返回队列的长度 。
队列是一种特殊的线性表, 因此队列可采用顺序存储结构存储, 也可以
使用链式存储结构存储 。
返回本章首页
下一页
上一页
2 队列的顺序存储结构
1,顺序队列的数组表示
队列的顺序存储结构可以简称为顺序队列, 也就是利用一组地址连续的
存储单元依次存放队列中的数据元素 。 一般情况下, 我们使用一维数组
来作为队列的顺序存储空间, 另外再设立两个指示器：一个为指向队头
元素位置的指示器 front,另一个为指向队尾的元素位置的指示器 rear。
C语言中, 数组的下标是从 0开始的, 因此为了算法设计的方便, 在此我
们约定：初始化队列时, 空队列时令 front=rear=-1,当插入新的数据元素
时, 尾指示器 rear加 1,而当队头元素出队列时, 队头指示器 front加 1。 另
外还约定, 在非空队列中, 头指示器 front总是指向队列中实际队头元素的
前面一个位置, 而尾指示器 rear总是指向队尾元素 。
图 5-12 队列的存储结构
（ a）空队列；（ b）元素 A入列后；（ c）元素 B,C
,D,E入列后；（ d）元素 E,D出队列后
front=-
10
front=-1
A
front=-1
A
C
D
B
E rear=4
D
（ a） （ b） （ c） （ d）rear=-1
rear=0
rear=4 E
front=2
图 5-12给出了队列中头尾指针的变化状态 。
返回本章首页
下一页
上一页
2,顺序队列的基本运算算法
（ 1） 初始化队列
【 算法 5.10 顺序队列的初始化 】
int initQueue(sqqueue *q)
{/*创建一个空队列由指针 q指出 */
if ((q=(sqqueue*)malloc(sizeof(sqqueue))= =NULL) return FALSE;
q->front= -1;
q->rear=-1;
return TRUE;
}
（ 2） 入队列操作
【 算法 5.11 顺序队列的入队列操作 】
int append(sqqueue *q,Elemtype x)
{/*将元素 x插入到队列 q中, 作为 q的新队尾 */
if(q->rear>=MAXNUM-1) return FALSE; /*队列满 */
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
返回本章首页
下一页
上一页
（ 3） 出队列操作
【 算法 5.12 顺序队列的出队列操作 】
Elemtype delete(sqqueue *q)
{/*若队列 q不为空, 则返回队头元素 */
Elemtype x;
if(q->rear= =q->front) return NULL; /*队列空 */
x=q->queue[++q->front];
return x;
}
（ 4） 取队头元素操作
【 算法 5.13 顺序队列的取头元素操作 】
Elemtype getHead(sqqueue *q)
{/*若队列 q不为空, 则返回队头元素 */
if(q->rear= =q->front) return NULL; /*队列空 */
return (q->queue[s->front+1]);
}
（ 5） 判队列非空操作
【 算法 5.14 顺序队列的非空判断操作 】
int Empty(sqqueue *q)
{/*队列 q为空时, 返回 TRUE；否则返回 FALSE*/ if (q->rear= =q-
>front) return TRUE;
return FALSE;
返回本章首页
下一页
上一页
（ 6） 求队列长度操作
【 算法 5.15 顺序队列的求长度操作 】
int length(sqqueue *q)
{/*返回队列 q的元素个数 */
return(q->rear-q->front);
3,循环队列
MAXNUM
-1 0
1
rear
front
图 5-13 循环队列
示意
在顺序队列中, 当队尾指针已经指向了队列的最后一个位置时, 此时若
有元素入列, 就会发生, 溢出, 。 在图 5-12（ c） 中队列空间已满, 若再
有元素入列, 则为溢出；在图 5-12（ d） 中, 虽然队尾指针已经指向最后
一个位置, 但事实上队列中还有 3个空位置 。 也就是说, 队列的存储空间
并没有满, 但队列却发生了溢出, 我们称这种现象为假溢出 。 解决这个
问题有两种可行的方法：
返回本章首页
下一页
上一页
（ 1） 采用平移元素的方法, 当发生假溢出时, 就把整个队列的元素平移
到存储区的首部, 然后再插入新元素 。 这种方法需移动大量的元素, 因而
效率是很低的 。
（ 2） 将顺序队列的存储区假想为一个环状的空间, 如图 5-13所示 。 我们
可假想 q->queue[0]接在 q->queue[MAXNUM-1]的后面 。 当发生假溢出时,
将新元素插入到第一个位置上, 这样做, 虽然物理上队尾在队首之前, 但
逻辑上队首仍然在前 。 入列和出列仍按, 先进先出, 的原则进行, 这就是
循环队列 。
很显然, 方法二中不需要移动元素, 操作效率高, 空间的利用率也很高
。
在循环队列中, 每插入一个新元素时, 就把队尾指针沿顺时针方向移动
一个位置 。 即：
q->rear=q->rear+1;
if(q->rear= =MAXNUM) q->rear=0;
在循环队列中, 每删除一个元素时, 就把队头指针沿顺时针方向移动一
个位置 。 即：
q->front=q->front+1;
if(q->front= =MAXNUM) q->front=0;
返回本章首页
下一页
上一页
0
1
23
4
5front
rear(b)
A
B
C
0
1
23
4
5front
rear
(a)
0
1
23
4
5
A
B
CD
E
F
front
rear
(c)
图 3-14 循环队列示意图
（ a）队列空；（ b）队列非空；
(c)队列满
图 5-14所示, 为循环队列的三种状态, 图 5-14（ a） 为队列空时, 有 q-
>front= =q->rear；图 5-14（ b） 为队列满时, 也有 q->front= =q->rear；因此
仅凭 q->front= =q->rear不能判定队列是空还是满 。
返回本章首页
下一页
上一页
为了区分循环队列是空还是满, 我们可以设定一个标志位 s：
s= 0时为空队列, s=1时队列非空 。
用 C语言定义循环队列结构如下：
typedefstruct
{Elemtype queue[MAXNUM];
int front; /*队头指示器 */
int rear; /*队尾指示器 */
int s; /*队列标志位 */
}qqueue;
下面给出循环队列的初始化, 入队列及出队列的算法 。
（ 1） 初始化队列
【 算法 5.16循环队列的初始化 】
int initQueue(qqueue*q)
{/*创建一个空队列由指针 q指出 */
if ((q=(qqueue*)malloc(sizeof(qqueue)))= =NULL) return FALSE;
q->front= MAXNUM;
q->rear=MAXNUM;
q->s=0;
return TRUE;
}
返回本章首页
下一页
上一页
（ 2） 入队列操作
【 算法 5.17 循环队列的入队列操作 】
int append(qqueue*q,Elemtype x)
{/*将元素 x插入到队列 q中, 作为 q的新队尾 */
if (( q->s= =1)&&(q->front= =q->rear)) return FALSE; /*队列满 */
q->rear++;
if (q->rear= =MAXNUM) q->rear=0;
q->queue[q->rear]=x;
q->s=1; /*置队列非空 */
return TRUE;
}
（ 3） 出队列操作
【 算法 5.18 循环队列的出队列操作 】
Elemtype delete(qqueue *q)
{/*若队列 q不为空, 则返回队头元素 */
Elemtype x;
if (q->s= =0) retrun NULL; /*队列为空 */
q->front++;
if (q->front= =MAXNUM) q->front=0;
x=q->queue[q->front];
if (q->front = =q->rear) q->s=0; /*置队列空 */
return x; }
下一页
上一页
为了解决比较复杂的问题, 本章介绍 C语言提供的
一种最简单的构造类型 ──数组及应用 。
5.1 1维数组的定义和引用
5.2 2维数组的定义和引用
5.3 字符数组与字符串
5.4 数组作为函数参数
5.5 线性表
5.6 栈
5.7 队列
第 5章 数据的顺序存储结构及应用
上一章
返回目录
下一章
返回本章首页
下一页
上一页
5.1 1维数组的定义和引用
5.1.1 1维数组的定义
5.1.2 1维数组元素的引用
5.1.3 1维数组元素的初始化
5.1.4 1维数组应用举例
返回本章首页
下一页
上一页
5.1.1 1维数组的定义
[案例 5.1] 从键盘上任意输入 10个整数, 要求按从小到大的顺序
在屏幕上显示出来 。
排序的方法有很多, 本题采用冒泡法 。
冒泡法的基本思想,通过相邻两个数之间的比较和交换, 使排序
码 （ 数值 ） 较小的数逐渐从底部移向顶部, 排序码较大的数逐渐从顶
部移向底部 。 就像水底的气泡一样逐渐向上冒, 故而得名 。
由 A[n]~A[1]组成的 n个数据, 进行冒泡排序的过程可以描述为：
（ 1） 首先将相邻的 A[n]与 A[n-1]进行比较, 如果 A[n]的值小于
A[n-1]的值, 则交换两者的位置, 使较小的上浮, 较大的下沉；接着
比较 A[n-1]与 A[n-2],同样使小的上浮, 大的下沉 。 依此类推, 直到
比较完 A[2]和 A[1]后, A[1]为具有最小排序码 （ 数值 ） 的元素, 称第
一趟排序结束 。
（ 2） 然后在 A[n]~A[2]区间内, 进行第二趟排序, 使剩余元素中
排序码最小的元素上浮到 A[2]；重复进行 n-1趟后, 整个排序过程结
束 。
返回本章首页
下一页
上一页
/*案例代码文件名,AL5_1.C*/
/*功能：从键盘上任意输入 n个整数, 用冒泡法按从小到大地排序,
并在屏幕上显示出来 。 */
#include "stdio.h"
#define NUM 10 /*定义符号常量 （ 数据个数 N） */
main()
{ int data[NUM]; /*定义 1个 1维整型数组 data*/
int i,j,temp; /*定义循环变量和临时变量 */
clrscr(); /*库函数 clrscr()：清屏 */
printf("Please input 10 numbers:\n");
for(i=0; i<NUM; i++)
scanf("%d",&data[i]);
返回本章首页
下一页
上一页
/*冒泡法排序 */
for(i=0; i<NUM-1; i++) /*外循环：控制比较趟数 */
for(j=NUM-1; j>i; j--) /*内循环：进行每趟比较 */
if(data[j]<data[j-1]) /*如果 data[j]大于 data[j-1],交换两者的位置 */
{temp=data[j];
data[j]=data[j-1];
data[j-1]=temp;
};
/*输出排序后的数据 */
printf("\nthe result of sort:\n");
for(i=0; i<NUM; i++)
printf("%d ",data[i]);
getch(); /*等待键盘输入任一字符, 目的使程序暂停 */
}
返回本章首页
下一页
上一页
数组同变量一样, 也必须先定义, 后使用 。
1维数组是只有 1个下标的数组, 定义形式如下：
数据类型 数组名 [常量表达式 ][,数组名 2[常量表达式
2]……] ；
（ 1）, 数据类型, 是指数组元素的数据类型 。
（ 2） 数组名, 与变量名一样, 必须遵循标识符命名规
则 。
（ 3）“常量表达式”必须用方括号括起来，指的是数
组的元素个数（又称数组长度），它是一个整型值，其中可
以包含常数和符号常量，但不能包含变量。
注意, C语言中不允许动态定义数组 。
返回本章首页
下一页
上一页
特别说明,在数组定义时,, 常量表达式, 外的方
括号；以及元素引用时,, 下标表达式, 外的方括号,
都是 C语言语法规则所要求的, 不是本书所约定的可选项
的描述符号 ！
（ 4） 数组元素的下标, 是元素相对于数组起始地址
的偏移量, 所以从 0开始顺序编号 。
（ 5） 数组名中存放的是一个地址常量, 它代表整个
数组的首地址 。 同一数组中的所有元素, 按其下标的顺
序占用一段连续的存储单元 。
返回本章首页
下一页
上一页
5.1.2 数组元素的引用
引用数组中的任意一个元素的形式：
数组名 [下标表达式 ]
1．, 下标表达式, 可以是任何非负整型数据, 取值
范围是 0~（ 元素个数 -1） 。
特别强调,在运行 C语言程序过程中, 系统并不自动
检验数组元素的下标是否越界 。 因此在编写程序时, 保
证数组下标不越界是十分重要的 。
2,1个数组元素, 实质上就是 1个变量, 它具有和相
同类型单个变量一样的属性, 可以对它进行赋值和参与
各种运算 。
3,在 C语言中, 数组作为 1个整体, 不能参加数据运
算, 只能对单个的元素进行处理 。
返回本章首页
下一页
上一页
5.1.3 1维数组元素的初始化
初始化格式,
数据类型 数组名 [常量表达式 ]＝ {初值表 }
（ 1） 如果对数组的全部元素赋以初值, 定义时可以
不指定数组长度 （ 系统根据初值个数自动确定 ） 。 如果
被定义数组的长度, 与初值个数不同, 则数组长度不能
省略 。
（ 2）, 初值表, 中的初值个数, 可以少于元素个数,
即允许只给部分元素赋初值 。
（ 3） 根据存储类型的不同, 数组有静态数组 （ static）
和动态数组 （ auto） 之分；根据定义的位置不同, 数组有
内部数组 （ 在函数内部定义的数组 ） 和外部数组 （ 在函
数外部定义的数组 ） 之分 。
返回本章首页
下一页
上一页
5.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 con_key=?\x20?; /* ?\x20? 空格键的 ASCII码 */
float score[5],ratio[4]={0.1,0.2,0.2,0.5}; /*定义成绩,比例系数数组 */
while(con_key=='\x20')
返回本章首页
下一页
上一页
while(con_key=='\x20')
{clrscr();
printf("输入第 %2d个学生的成绩 \n",i++);
printf("平时 实习 测验 期末成绩 \n");
score[4]=0; /* score[4]：存储总评成绩 */
for(j=0; j<4; j++)
{scanf("%f",&score[j]);
score[4] += score[j] * ratio[j];
}
printf("总评成绩为,%6.1f\n",score[4]);
printf("\n按空格键继续,其它键退出 ");
con_key=getch(); /*getch()函数等待从键盘上输入一个字符 */
}
}
返回本章首页
下一页
上一页
5.2 2维数组的定义和引用
5.2.1 2维数组的定义
5.2.2 2维数组元素的引用
5.2.3 2维数组元素的初始化
5.2.4 2维数组应用举例
返回本章首页
下一页
上一页
[案例 5.3] 给一个 2＊ 3的 2维数组各元素赋值, 并输出全部元素的值 。
/*案例代码文件名,AL5_3.C*/
/*功能：从键盘上给 2＊ 3数组赋值, 并在屏幕上显示出来 。 */
#define Row 2
#define Col 3
#include "stdio.h"
main()
{ int i,j,array[Row][Col]; /*定义 1个 2行 3列的 2维数组 array*/
for(i=0; i<Row; i++) /*外循环：控制 2维数组的行 */
for(j=0; j<Col; j++) /*内循环：控制 2维数组的列 */
{printf("please input array[%2d][%2d]:",i,j);
scanf("%d",&array[i][j]); /*从键盘输入 a[i][j]的值 */
}
printf("\n");
/*输出 2维数组 array*/
for(i=0;i<Row;i++)
5.2.1 2维数组的定义
返回本章首页
下一页
上一页
{ for(j=0;j<Col;j++)
printf("%d\t",array[i][j]); /*将 a[i][j]的值显示在屏幕上 */
printf("\n");
}
getch();
}
2维数组的定义方式如下：
数据类型 数组名 [行常量表达式 ][列常量表达式 ][,
数组名 2[行常量表达式 2][列常量表达式 2]……];
1．数组元素在内存中的排列顺序为“按行存放”，即
先顺序存放第一行的元素，再存放第二行，以此类推。
2,设有一个 m*n的数组 x，则第 i行第 j列的元素 x[i][j]在
数组中的位置为,i*n+j（ 注意,行号、列号均从 0开始计
数）。
返回本章首页
下一页
上一页
3,可以把 2维数组看作是一种特殊的 1维数组：它
的元素又是一个 1维数组 。
例如, 对 x[3][2],可以把 x看作是一个 1维数组, 它
有 3个元素,x[0],x[1],x[2],每个元素又是一个包含 2
个元素的 1维数组, 如图 6-4所示 。 即把 x[0],x[1],x[2]
看作是 3个 1维数组的名字 。
返回本章首页
下一页
上一页
5.2.2 2维数组元素的引用
引用 2维数组元素的形式为：
数组名 [行下标表达式 ][列下标表达式 ]
1．, 行下标表达式, 和, 列下标表达式,, 都应是
整型表达式或符号常量 。
2．, 行下标表达式, 和, 列下标表达式, 的值, 都
应在已定义数组大小的范围内 。 假设有数组 x[3][4],则可
用的行下标范围为 0~2,列下标范围为 0~3。
3,对基本数据类型的变量所能进行的操作, 也都适
合于相同数据类型的 2维数组元素 。
返回本章首页
下一页
上一页
5.2.3 2维数组元素的初始化
1,按行赋初值
数据类型 数组名 [行常量表达式 ][列常量表达式 ]＝ {{第 0行初值
表 },{第 1行初值表 },……, {最后 1行初值表 }}；
赋值规则：将, 第 0行初值表, 中的数据, 依次赋给第 0行中各元
素；将, 第 1行初值表, 中的数据, 依次赋给第 1行各元素；以此类
推 。
2,按 2维数组在内存中的排列顺序给各元素赋初值
数据类型 数组名 [行常量表达式 ][列常量表达式 ]＝ {初值表 }；
赋值规则：按 2维数组在内存中的排列顺序, 将初值表中的数据,
依次赋给各元素 。
如果对全部元素都赋初值，则“行数”可以省略。 注意,只能
省略“行数”。
返回本章首页
下一页
上一页
5.2.4 2维数组应用举例
[案例 5.4] 有 M个学生，学习 N门课程，已知所有学生的各科成绩，
编程：分别求每个学生的平均成绩和每门课程的平均成绩。
/*案例代码文件名,AL5_4.C*/
/*功能：计算个人平均成绩与各科平均成绩，并在屏幕上显示出来。 */
#define NUM_std 5 /*定义符号常量人数为 5*/
#define NUM_course 4 /*定义符号常量课程为 4*/
#include "stdio.h"
main()
{ int i,j;
static float score[NUM_std+1][NUM_course+1]={{78,85,83,65},
{88,91,89,93},{72,65,54,75},
{86,88,75,60},{69,60,50,72}};
返回本章首页
下一页
上一页
for(i=0;i<NUM_std;i++)
{for(j=0;j<NUM_course;j++)
{ score[i][NUM_course] += score[i][j];/*求第 i个人的总成绩 */
score[NUM_std][j] += score[i][j];/*求第 j门课的总成绩 */
}
score[i][NUM_course] /= NUM_course;/*求第 i个人的平均成绩 */
}
for(j=0;j<NUM_course;j++)
score[NUM_std][j] /= NUM_std; /*求第 j门课的平均成绩 */
clrscr();
/*输出表头 */
printf("学生编号 课程 1 课程 2 课程 3 课程 4 个人平均 \n");
/*输出每个学生的各科成绩和平均成绩 */
返回本章首页
下一页
上一页
for(i=0;i<NUM_std;i++)
{ printf("学生 %d\t",i+1);
for(j=0;j<NUM_course+1;j++)
printf("%6.1f\t",score[i][j]);
printf("\n");
}
/*输出 1条短划线 */
for(j=0;j<8*(NUM_course+2);j++)
printf("-");
printf("\n课程平均 ");
/*输出每门课程的平均成绩 */
for(j=0;j<NUM_course;j++)
printf("%6.1f\t",score[NUM_std][j]);
printf("\n");
getch();
}
返回本章首页
下一页
上一页
5.3 字符数组与字符串
5.3.1 字符数组的逐个字符操作
5.3.2 字符数组的整体操作
5.3.3 常用的字符串处理函数
返回本章首页
下一页
上一页
5.3.1 字符数组的逐个字符操作
[案例 5.5]从键盘输入一个字符串, 回车键结束, 并将字符串在屏幕上输出 。
/*案例代码文件名,AL5_5.C*/
main()
{int i;
static char str[80];
clrscr();
for(i=0;i<80;i++)
{ str[i]=getch(); /*逐次给数组元素 str[i]赋值, 但不回显在屏幕上 */
printf("*"); /*以星号代替输入字符的个数 */
if(str[i]=='\x0d') break;/*若输入回车则终止循环 */
}
i=0;
while(str[i]!='\x0d')
printf("%c",str[i++]); /*逐次输出字符数组的各个元素 */
printf("\n");
getch(); /*程序暂停 */
}
返回本章首页
下一页
上一页
1,字符数组的定义
1维字符数组, 用于存储和处理 1个字符串, 其定义格式
与 1维数值数组一样 。
2维字符数组, 用于同时存储和处理多个字符串, 其定义
格式与 2维数值数组一样 。
2,字符数组的初始化
字符数组的初始化, 可以通过为每个数组元素指定初值
字符来实现 。
3,字符数组的引用
字符数组的逐个字符引用, 与引用数值数组元素类似 。
返回本章首页
下一页
上一页
（ 1） 字符数组的输入
除了可以通过初始化使字符数组各元素得到初值外,
也可以使用 getchar()或 scanf()函数输入字符 。
例如：
char str[10]；
……
for(i=0; i<10; i++)
{ scanf("%c",&str[i])；
fflush(stdin); /*清除键盘输入缓冲区 */
}
……
返回本章首页
下一页
上一页
（ 2） 字符数组的输出
字符数组的输出, 可以用 putchar()或 printf()函数 。
例如：
char str[10]="c language";
……
for(i=0; i<10; i++) printf("%c",str[i])；
printf("\n");
……
注意,逐个字符输入, 输出时, 要指出元素的下标,
而且使用, %c”格式符 。 另外, 从键盘上输入字符时, 无
需输入字符的定界符 ──单引号；输出时, 系统也不输出
字符的定界符 。
返回本章首页
下一页
上一页
5.3.2 字符数组的整体操作
[案例 5.6] 字符数组的整体输入与输出 。
/*案例代码文件名,AL5_6.C*/
/*功能：将 2维字符数组进行初始化, 并在屏幕上输出 */
main()
{ int i;
char name[5][9]={"张三山 ","李四季 ","王五魁 ","刘六顺 ","赵七巧 "};
for(i=0;i<5;i++)
printf("\n%s\t",name[i]); /*name[i]代表该行数组元素的首地址 */
getch();
}
1．字符串及其结束标志
所谓字符串，是指若干有效字符的序列。 C语言中的字符串，可以包
括字母、数字、专用字符、转义字符等。
C语言规定：以‘ \0?作为字符串结束标志（‘ \0?代表 ASCII码为 0的字
符，表示一个“空操作”，只起一个标志作用）。因此可以对字符数组采
用另一种方式进行操作了 ──字符数组的整体操作 。
返回本章首页
下一页
上一页
注意,由于系统在存储字符串常量时, 会在串尾自动加上 1个结束
标志, 所以无需人为地再加 1个 。
另外, 由于结束标志也要在字符数组中占用一个元素的存储空间,
因此在说明字符数组长度时, 至少为字符串所需长度加 1。
2,字符数组的整体初始化
字符串设置了结束标志以后, 对字符数组的初始化, 就可以用字符
串常量来初始化字符数组 。
3,字符数组的整体引用
（ 1） 字符串的输入
除了可以通过初始化使字符数组各元素得到初值外, 也可以使用
scanf()函数输入字符串 。
（ 2） 字符串的输出
printf()函数, 不仅可以逐个输出字符数组元素, 还可以整体输出存
放在字符数组中的字符串 。
返回本章首页
下一页
上一页
5.3.3 常用的字符串处理函数
字符串标准函数的原型在头文件 string.h中 。
1,输入字符串 ──gets()函数
（ 1） 调用方式,gets(字符数组 )
（ 2） 函数功能：从标准输入设备 (stdin)──键盘上, 读取
1个字符串 （ 可以包含空格 ）, 并将其存储到字符数组中去 。
（ 3） 使用说明
1） gets()读取的字符串, 其长度没有限制, 编程者要保
证字符数组有足够大的空间, 存放输入的字符串 。
2） 该函数输入的字符串中允许包含空格, 而 scanf()函数
不允许 。
返回本章首页
下一页
上一页
2,输出字符串 ──puts()函数
（ 1） 调用方式,puts(字符数组 )
（ 2） 函数功能：把字符数组中所存放的字符串, 输出
到标准输出设备中去, 并用 ‘ \n?取代字符串的结束标志 ‘ \0?。
所以用 puts()函数输出字符串时, 不要求另加换行符 。
（ 3） 使用说明
1)字符串中允许包含转义字符, 输出时产生一个控制操
作 。
2)该函数一次只能输出一个字符串, 而 printf()函数也能
用来输出字符串, 且一次能输出多个 。
返回本章首页
下一页
上一页
3,字符串比较 ──strcmp()函数
（ 1） 调用方式,strcmp(字符串 1,字符串 2)
其中, 字符串, 可以是串常量, 也可以是 1维字符数组 。
（ 2） 函数功能：比较两个字符串的大小 。
如果,字符串 1=字符串 2,函数返回值等于 0；
字符串 1<字符串 2,函数返回值负整数；
字符串 1>字符串 2,函数返回值正整数 。
（ 3） 使用说明
1） 如果一个字符串是另一个字符串从头开始的子串, 则母串为大 。
2） 不能使用关系运算符, ＝＝, 来比较两个字符串, 只能用
strcmp() 函数来处理 。
返回本章首页
下一页
上一页
[案例 5.7] gets函数和 strcmp函数的应用 。
/*案例代码文件名,AL6_7.C*/
/*功能：简单密码检测程序 */
#include "stdio.h"
main()
{char pass_str[80]; /*定义字符数组 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); /*输入三次错误的密码, 退出程序 */
}
/*输入正确密码所进入的程序段 */
}
返回本章首页
下一页
上一页
4,拷贝字符串 ──strcpy()函数
（ 1） 调用方式,strcpy(字符数组,字符串 )
其中, 字符串, 可以是串常量, 也可以是字符数组 。
（ 2） 函数功能：将, 字符串, 完整地复制到, 字符数
组, 中, 字符数组中原有内容被覆盖 。
（ 3） 使用说明
1） 字符数组必须定义得足够大, 以便容纳复制过来的
字符串 。 复制时, 连同结束标志 '\0'一起复制 。
2） 不能用赋值运算符, ＝, 将一个字符串直接赋值给
一个字符数组, 只能用 strcpy()函数来处理 。
返回本章首页
下一页
上一页
5,连接字符串 ──strcat()函数
（ 1） 调用方式,strcat(字符数组,字符串 )
（ 2） 函数功能：把, 字符串, 连接到, 字符数组, 中
的字符串尾端, 并存储于, 字符数组, 中 。, 字符数组,
中原来的结束标志, 被, 字符串, 的第一个字符覆盖, 而
,字符串, 在操作中未被修改 。
（ 3） 使用说明
1） 由于没有边界检查, 编程者要注意保证, 字符数组,
定义得足够大, 以便容纳连接后的目标字符串；否则, 会
因长度不够而产生问题 。
2） 连接前两个字符串都有结束标志 '\0',连接后, 字
符数组, 中存储的字符串的结束标志 '\0'被舍弃, 只在目标
串的最后保留一个 '\0'。
返回本章首页
下一页
上一页
6,求字符串长度 ──strlen()函数 （ len是 length的缩写 ）
（ 1） 调用方式,strlen(字符串 )
（ 2） 函数功能：求字符串 （ 常量或字符数组 ） 的实际长度
（ 不包含结束标志 ） 。
7,将字符串中大写字母转换成小写 ──strlwr()函数
（ 1） 调用方式,strlwr(字符串 )
（ 2） 函数功能：将字符串中的大写字母转换成小写, 其它字
符 （ 包括小写字母和非字母字符 ） 不转换 。
8,将字符串中小写字母转换成大写 ──strupr()函数
（ 1） 调用方式,strupr(字符串 )
（ 2） 函数功能：将字符串中小写字母转换成大写, 其它字符
（ 包括大写字母和非字母字符 ） 不转换 。
返回本章首页
下一页
上一页
5.4 数组作为函数参数
? 数组用作函数参数有两种形式：一种是把数组元素
（又称下标变量）作为实参使用；另一种是把数组名作
为函数的形参和实参使用。
? 5.4.1 数组元素作为函数参数
? 5.4.2 数组名作为函数的形参和实参
返回本章首页
下一页
上一页
5.4.1 数组元素作为函数参数
? 数组元素就是下标变量，它与普通变量并无区别。数
组元素只能用作函数实参，其用法与普通变量完全相同：
在发生函数调用时，把数组元素的值传送给形参，实现单
向值传送。
? [案例 5.8] 写一函数, 统计字符串中字母的个数 。
? /*案例代码文件名,AL5_8.C*/
? /*功能：数组元素作为函数实参 */
? int isalp(char c)
? { if (c>='a'&&c<='z'||c>='A'&&c<='Z')
? return(1);
? else return(0);
? }
返回本章首页
下一页
上一页
? main()
? { int i,num=0;
? char str[255];
? printf("Input a string,");
? gets(str);
? for(i=0;str[i]!='\0';i++)
? if (isalp(str[i])) num++;
? puts(str);
? printf("num=%d\n",num);
? getch();
? }
返回本章首页
下一页
上一页
? 说明：
? （ 1） 用数组元素作实参时, 只要数组类型和函数的
形参类型一致即可, 并不要求函数的形参也是下标变量 。
换句话说, 对数组元素的处理是按普通变量对待的 。
? （ 2） 在普通变量或下标变量作函数参数时, 形参变
量和实参变量是由编译系统分配的两个不同的内存单元 。
在函数调用时发生的值传送, 是把实参变量的值赋予形
参变量 。
?
返回本章首页
下一页
上一页
5.4.2 数组名作为函数的形参和实参
? 数组名作函数参数时, 既可以作形参, 也可以作实参 。
? 数组名作函数参数时, 要求形参和相对应的实参都必
须是类型相同的数组 （ 或指向数组的指针变量 ）, 都必
须有明确的数组说明
? [案例 5.9] 已知某个学生 5门课程的成绩, 求平均成绩 。
? /*案例代码文件名,AL5_9.C*/
? float aver(float a[ ]) /*求平均值函数 */
? { int i；
? float av,s=a[0]；
? for(i=1； i<5； i++) s += a[i]；
? av=s/5；
? return av；
? }
返回本章首页
下一页
上一页
? void main()
? { float sco[5],av；
? int i；
? printf("\ninput 5 scores:\n")；
? for(i=0； i<5； i++) scanf("%f",&sco[i])；
? av=aver(sco)； /*调用函数, 实参为一数组名 */
? printf("average score is %5.2f\n",av)；
? getch();
? }
返回本章首页
下一页
上一页
说明,
（ 1） 用数组名作函数参数, 应该在调用函数和被调
用函数中分别定义数组, 且数据类型必须一致, 否则结
果将出错 。 例如, 在本案例中, 形参数组为 a[],实参数
组为 sco[],它们的数据类型相同 。
（ 2） C编译系统对形参数组大小不作检查, 所以形
参数组可以不指定大小 。 例如, 本案例中的形参数组 a[]。
如果指定形参数组的大小, 则实参数组的大小必须
大于等于形参数组, 否则因形参数组的部分元素没有确
定值而导致计算结果错误 。
返回本章首页
下一页
上一页
5.5线性表
一, 线性表的逻辑结构
? 线性表由一组具有相同属性的数据元素构成 。 数据元素的含义广泛, 在
不同的具体情况下, 可以有不同的含义 。 例如：英文字母表 （ A,B，
C,…, Z） 是一个长度为 26的线性表, 其中的每一个字母就是一个数据
元素；再如, 某公司 2000年每月产值表 （ 400,420,500,…, 600,650）
(单位：万元 )是一个长度为 12的线性表, 其中的每一个数值就是一个数
据元素 。 上述两例中的每一个数据元素都是不可分割的, 在一些复杂的
线性表中, 每一个数据元素又可以由若干个数据项组成, 在这种情况下,
通常将数据元素称为记录 （ record）, 例如, 图 5－ 1的某单位职工工资
表就是一个线性表, 表中每一个职工的工资就是一个记录, 每个记录包
含八个数据项：职工号, 姓名, 基本工资 …… 。
返回本章首页
下一页
上一页
职工
号 姓名
基本
工资
岗位
工资
奖
金
应发
工资
扣
款
实发
工资
1201 张强 540 300 200 1040 20 1020
1301 周敏 500 200 200 900 20 880
1202 徐黎 芬 550 300 200 1050 30 1020
1105 黄承 振 530 250 200 980 20 960
┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇
图 5－ 1 职工工资表
返回本章首页
下一页
上一页
? 矩阵也是一个线性表, 但它是一个比较复杂的线性表 。 在矩阵中, 我们可以
把每行看成是一个数据元素, 也可以把每列看成是一个数据元素, 而其中的
每一个数据元素又是一个线性表 。
? 综上所述, 一个线性表是 n≥0个数据元素 a0,a1,a2,…, an-1的有限序列 。
如果 n>0,则除 a0和 an-1外, 有且仅有一个直接前趋和一个直接后继数据元素,
ai（ 0≤i≤n-1） 为线性表的第 i个数据元素, 它在数据元素 ai-1之后, 在 ai+1之前 。
a0为线性表的第一个数据元素, 而 an-1是线性表的最后一个数据元素；若 n=0，
则为一个空表, 表示无数据元素 。 因此, 线性表或者是一个空表 （ n=0）,
或者可以写成,（ a0,a1,a2,…, ai-1,ai,ai+1,…, an-1） 。
? 抽象数据类型线性表的定义如下：
? LinearList=(D,R)
? 其中,D={ ai| ai∈ ElemSet,i=0,1,2,…, n-1 n≥1}
? R={<ai-1,ai>| ai-1,ai∈ D,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) 删除：在给定的线性表 L中，删除第 i个元素。线性表 L的
长度减 1。
4,Locate(L,x) 查找定位：对给定的值 x，若线性表 L中存在一个元素 ai
与之相等，则返回该元素在线性表中的位置的序号 i，否则返回 Null（空）
。
5,Length(L) 求长度：对给定的线性表 L，返回线性表 L的数据元素的
个数。
6,Get(L,i) 存取：对给定的线性表 L，返回第 i（ 0≤i≤Length(L)-1）个数
据元素，否则返回 Null。
7,Traverse(L) 遍历：对给定的线性表 L，依次输出 L的每一个数据元素
。
8,Copy(L,C) 复制：将给定的线性表 L复制到线性表 C中。
9,Merge(A,B,C) 合并：将给定的线性表 A和 B合并为线性表 C。
上面我们定义了线性表的逻辑结构和基本操作 。 在计算机内, 线性表有两
种基本的存储结构：顺序存储结构和链式存储结构 。 下面我们将讨论顺序
存储结构下实现各操作的算法 。
返回本章首页
下一页
上一页
二,线性表的顺序存储结构
? 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素, 称作线
性表的顺序存储结构 。
1 线性表的顺序存储结构
在线性表的顺序存储结构中, 其前后两个元素在存储空间
中是紧邻的, 且前驱元素一定存储在后继元素的前面 。 由于线性表的所有
数据元素属于同一数据类型, 所以每个元素在存储器中占用的空间大小相
同, 因此, 要在该线性表中查找某一个元素是很方便的 。 假设线性表中的
第一个数据元素的存储地址为 Loc(a0),每一个数据元素占 d字节, 则线性表
中第 i个元素 ai在计算机存储空间中的存储地址为：
Loc(ai)= Loc(a0)+id
在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是
因为数组具有如下特点：（ 1）数据中的元素间的地址是连续的；（ 2）
数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结
构是类似的。
返回本章首页
下一页
上一页
1,一维数组
若定义数组 A[n]={ a0,a1,a2,…, an-1}，假设每一个数组元素占用 d个字
节，则数组元素 A[0],A[1],A[2],…, A[n-1]的地址分别为 Loc(A[0])，
Loc(A[0])+d,Loc(A[0])+2d,…, Loc(A[0])+（ n-1） d 。其结构如图 5－ 2
所示。
返回本章首页
下一页
上一页
若定义数组 A[n][m],表示此数组有 n行 m列, 如下图 5－ 3所示 。
0 1 2 … j … m -1
0 a00 a01 a02 … a 0j … a 0 m-1
1 a10 a11 a12 … a 1j … a 1 m-1
2 a20 a21 a22 … a 2j … a 2 m-1
i ai0 ai1 ai2 … a ij … a i m-1
n-1 an-1,0 an-1,1 an-1,2 … a n-1,j … a n-1,m-1
图 5－ 3 二维
数组
２, 二维数组
返回本章首页
下一页
上一页
在 C语言中, 二维数组的保存是按照行方式存储的, 先将第一行元素
排好, 接着排第二行元素, 直至所有行的元素排完 。 如图 5-4所示 。
图 5-4 二维数组存
储示意图
返回本章首页
下一页
上一页
2 线性表在顺序存储结构下的运算
可用 C语言描述顺序存储结构下的线性表 （ 顺序表 ） 如下：
#define TRUE 1
#define FALSE 0
#define MAXNUM <顺序表最大元素个数 >
Elemtype List[MAXNUM] ; /*定义顺序表 List*/
int num=-1; /*定义当前数据元素下标, 并初始
化 */
我们还可将数组和表长封装在一个结构体中：
struct Linear_list {
Elemtype List[MAXNUM]; /*定义数组域 */
int length; /*定义表长域 */
}
返回本章首页
下一页
上一页
1,顺序表的插入操作
在 长 度 为 num(0≤num≤MAXNUM-2) 的 顺 序 表 List 的第
i(0≤i≤num+1)个数据元素之前插入一个新的数据元素 x时,
需将最后一个即第 num个至第 i个元素 （ 共 num-i+1个元素 ）
依次向后移动一个位置, 空出第 i个位置, 然后把 x插入到
第 i个存储位置, 插入结束后顺序表的长度增加 1,返回
TRUE值；若 i＜ 0或 i＞ num+1,则无法插入, 返回 FALSE。
如图 2-5 所示 。
在 长 度 为 num(0≤num≤MAXNUM-2) 的 顺 序 表 List 的第
i(0≤i≤num+1)个数据元素之前插入一个新的数据元素 x时,
需将最后一个即第 num个至第 i个元素 （ 共 num-i+1个元素 ）
依次向后移动一个位置, 空出第 i个位置, 然后把 x插入到
第 i个存储位置, 插入结束后顺序表的长度增加 1,返回
TRUE值；若 i＜ 0或 i＞ num+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+2 ai+1
┇ ┇
num anum
插入
x
图 5-5 在数组中插入元素
返回本章首页
下一页
上一页
其算法如下：
【 算法 5.1 顺序表的插入 】
int Insert(Elemtype List[],int *num,int i,Elemtype x)
{/*在顺序表 List[]中, *num为表尾元素下标位置, 在第 i个元素前
插入数据元素 x,若成功, 返回 TRUE,否则返回 FALSE。 */
int j;
if (i<0||i>*num+1)
{printf(“Error!”); /*插入位置出错 */
return FALSE;}
if (*num>=MAXNUM-1)
{printf(“overflow!”);
return FALSE; /*表已满 */｝
for (j=*num;j>=i;j--)
List[j+1]=List[j]; /*数据元素后移 */
List[i]=x; /*插入 x*/
(*num)++; /*长度加 1*/
return TRUE;}
注,顺序表 List的最大数据元素个数为 MAXNUM,num标识为顺
序表的当前表尾 （ num≤MAXNUM-1） 。
返回本章首页
下一页
上一页
２．顺序表的删除操作
0 a0
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+1 ai+1
┇ ┇
num anum
图 5-6 在数组
中删除元素
在长度为 num(0≤num≤MAXNUM-1)的顺序表 List,删除第 i(0≤i≤num)个数
据元素, 需将第 i至第 num个数据元素的存储位置 （ num-i+1） 依次前移,
并使顺序表的长度减 1,返回 TRUE值, 若 i＜ 0或 i＞ num,则无法删除,
返回 FALSE值, 如图 5-6所示 。
返回本章首页
下一页
上一页
其算法如下：
【 算法 5.2 顺序表的删除 】
int Delete(Elemtype List[],int *num,int i)
{/*在线性表 List[]中, *num为表尾元素下标位置, 删除第 i个元素, 线性
表的元素减 1,若成功, 则返回 TRUE；否则返回 FALSE。 */
int j;
if(i<0||i>*num)
{printf(“Error!”); return FALSE; /*删除位置出错 ！ */ }
for(j=i+1;j<=*num;j++)
List[j-1]=List[j]; /*数据元素前移 */
(*num)--; /*长度减 1*/
return TRUE; }
从上述两个算法来看, 很显然, 在线性表的顺序存储结构中插入或删除
一个数据元素时, 其时间主要耗费在移动数据元素上 。 而移动元素的次数
取决于插入或删除元素的位置 。
假设 Pi是在第 i个元素之前插入一个元素的概率, 则在长度为 n的线性表中
插入一个元素时所需移动元素次数的平均次数为
)(
0
inpE
n
i
iin s ?? ?
?
返回本章首页
下一页
上一页
假设 qi是删除第 i个元素的概率, 则在长度为 n的线性表中删除一个元素时
所需移动元素次数的平均次数为
如果在线性表的任何位置插入或删除元素的概率相等, 即
则
可见, 在顺序存储结构的线性表中插入或删除一个元素时, 平均要移动
表中大约一半的数据元素 。 若表长为 n,则插入和删除算法的时间复杂度都
为 O(n)。
在顺序存储结构的线性表中其他的操作也可直接实现, 在此不再讲述 。
)1(1
0
??? ??
?
inqE n
i
id e l
1
1
?? np inq i 1?
2)(1
1
0
nin
nE
n
i
in s ???? ?
?
2
1)1(1 1
0
????? ??
?
nin
nE
n
i
d e l
返回本章首页
下一页
上一页
例：将有序线性表 La={2,4,6,7,9},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_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(a<b) {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_length) { b=get(La,i);insert(Lc,++k,b); } }
返回本章首页
下一页
上一页
3,顺序表存储结构的特点
线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出,
因此顺序存储结构的线性表是可以随机存取其中的任意元素 。 也就是说
定位操作可以直接实现 。 高级程序设计语言提供的数组数据类型可以直
接定义顺序存储结构的线性表, 使其程序设计十分方便 。
但是, 顺序存储结构也有一些不方便之处, 主要表现在：
（ 1） 数据元素最大个数需预先确定, 使得高级程序设计语言编译系统需
预先分配相应的存储空间 。
（ 2） 插入与删除运算的效率很低 。 为了保持线性表中的数据元素的顺序
,在插入操作和删除操作时需移动大量数据 。 这对于插入和删除操作频
繁的线性表, 以及每个数据元素所占字节较大的问题将导致系统的运行
速度难以提高 。
（ 3） 顺序存储结构的线性表的存储空间不便于扩充 。 当一个线性表分配
顺序存储空间后, 如果线性表的存储空间已满, 但还需要插入新的元素
,则会发生, 上溢, 错误 。 在这种情况下, 如果在原线性表的存储空间
后找不到与之连续的可用空间, 则会导致运算的失败或中断 。
返回本章首页
下一页
上一页
5.6 栈
在各种程序设计语言中都有子程序 （ 或称函数, 过程 ） 调用功能 。 而
子程序也可以调用其它的子程序, 甚至可以直接或间接地调用自身,
这种调用关系就是递归 。 下面以求阶乘的递归方法为例, 来分析计算
机系统是如何处理这种递归调用关系的 。
求 n！ 的递归方法的思路是：
相应的 C语言函数是：
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!=%f\n”,fact(5)); }
)1(
)1,0(
)!1(*
1!
?
?
??
?
?? n
n
nnn
返回本章首页
下一页
上一页
图 5-7给出了递归调用执行过程 。 从图中可看到 fact函数共被调用 5次,
即 fact(5),fact(4),fact(3),fact(2),fact(1)。 其中, fact(5)为主函数调
用, 其它则为在 fact函数内的调用 。 每一次递归调用并未立即得到结
果, 而是进一步向深度递归调用, 直到 n=1或 n=0时, 函数 fact才有结
果为 1,然后再一一返回计算, 最终得到结果 。
主函数
mani()
printf(“fact(5)”) 第一层调
用
n=5
s=5*fact(4) 第二层调
用
n=4
s=4*fact(3) 第三层调
用
n=3
S=3*fact(2) 第四层调
用
n=2
S=2*fact(1)
第五层调
用
n=1
S=1
fact(1)
=1
fact(2)
=2
fact(3)
=6
fact(4)
=24
fact(5)=
120
输出
s=120.00
图 5-7 递归调用过程示意图
返回本章首页
下一页
上一页
计算机系统处理上述过程时, 其关键是要正确处理执行过程中的递归
调用层次和返回路径, 也就是要记住每一次递归调用时的返回地址 。 在
系统中是用一个线性表动态记忆调用过程中的路径, 其处理原则为：
（ 1） 在开始执行程序前, 建立一个线性表, 其初始状态为空 。
（ 2） 当发生调用 （ 递归 ） 时, 将当前的调用的返回点地址插入到线
性表的末尾；
（ 3） 当调用 （ 递归 ） 返回时, 其返回地址从线性表的末尾取出 。
根据以上的原则, 可以给出线性表中的元素变化状态如图 3-2所示 （
以递归调用时 n值的变化为例 ）,
5 45
45 3 45 3 2 45 3 2 1
图 5-8 递归调用时线性
表状态
返回本章首页
下一页
上一页
1 栈的定义及其运算
1,栈的定义
栈 （ stack） 是一种只允许在一端进行插入和删除的线性表, 它是一种操作
受限的线性表 。 在表中只允许进行插入和删除的一端称为栈顶 （ top）, 另
一端称为栈底 (bottom)。 栈的插入操作通常称为入栈或进栈 (push),而栈的
删除操作则称为出栈或退栈 (pop)。 当栈中无数据元素时, 称为空栈 。
根据栈的定义可知, 栈顶元素总是最后入栈的, 因而是最先出栈；栈底元
素总是最先入栈的, 因而也是最后出栈 。 这种表是按照后进先出 （ LIFO，
last in first out ） 的原则组织数据的, 因此, 栈也被称为, 后进先出, 的线
性表 。
a0
a1
an-1
入栈 出栈
栈顶 top
栈底
bottom 图 5-9栈的示意图
．
．
．
图 5-9是一个栈的示意图, 通常用指针 top指示栈顶的位置, 用指针 bottom
指向栈底 。 栈顶指针 top动态反映栈的当前位置 。
返回本章首页
下一页
上一页
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为空栈 。
栈是一种特殊的线性表, 因此栈可采用顺序存储结构存储, 也可以
使用链式存储结构存储 。
返回本章首页
下一页
上一页
2 栈的顺序存储结构
1,顺序栈的数组表示
与第二章讨论的一般的顺序存储结构的线性表一样, 利用一组地址连续的
存储单元依次存放自栈底到栈顶的数据元素, 这种形式的栈也称为顺序栈
。 因此, 我们可以使用一维数组来作为栈的顺序存储空间 。 设指针 top指向
栈顶元素的当前位置, 以数组小下标的一端作为栈底, 通常以 top=0时为空
栈, 在元素进栈时指针 top不断地加 1,当 top等于数组的最大下标值时则栈
满 。
top=0 top=1
A
top=5
A
C
D
B
E
top=3
A
BC
图 5-10 栈的存储结构
（ a）空栈；（ b）插入元素 A后；（ c
）插入元素 B,C,D,E后；（ d）删
除元素 E,D后
（ a） （ b） （ c） （ d）
图 5-10展示了顺序栈中数据元素与栈顶指针的变化 。
返回本章首页
下一页
上一页
用 C语言定义的顺序存储结构的栈如下：
# define MAXNUM <最大元素数 >
typedefstruct {
Elemtype stack[MAXNUM];
int top; } sqstack;
鉴于 C语言中数组的下标约定是从 0开始的, 因而使用 C语言的一维
数组作为栈时, 应设栈顶指针 top=-1时为空栈 。
2,顺序栈的基本运算算法
（ 1） 初始化栈
【 算法 5.4 栈的初始化 】
int initStack(sqstack *s)
{/*创建一个空栈由指针 S指出 */
if ((s=(sqstack*)malloc(sizeof(sqstack)))= =NULL) 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->stack[s->top]=x;
return TRUE;
}
（ 3） 出栈操作
【 算法 5.6 出栈操作 】
Elemtype pop(sqstack *s)
{/*若栈 s不为空, 则删除栈顶元素 */
Elemtype x;
if(s->top<0) return NULL; /*栈空 */
x=s->stack[s->top];
s->top--;
return x;
}
返回本章首页
下一页
上一页
（ 4） 取栈顶元素操作
【 算法 5.7 取栈顶元素 】
Elemtype gettop(sqstack *s)
{/*若栈 s不为空, 则返回栈顶元素 */
if(s->top<0) return NULL; /*栈空 */
return (s->stack[s->top]);
}
取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针 top的位置, 而取栈
顶元素操作不改变栈的栈顶指针 。
（ 5） 判栈空操作
【 算法 5.8 判栈空操作 】
int Empty(sqstack *s)
{/*栈 s为空时, 返回为 TRUE；非空时, 返回为 FALSE*/
if(s->top<0) return TRUE;
return FALSE;
}（ 6） 置空操作
【 算法 5.9 栈置空操作 】
void setEmpty(sqstack *s)
{/*将栈 s的栈顶指针 top,置为 -1*/
s->top= -1;
}
返回本章首页
下一页
上一页
5.7 队列
在日常生活中队列很常见, 如, 我们经常排队购物或购票, 排队是体
现了, 先来先服务, （ 即, 先进先出, ） 的原则 。
队列在计算机系统中的应用也非常广泛 。 例如：操作系统中的作业排
队 。 在多道程序运行的计算机系统中, 可以同时有多个作业运行, 它
们的运算结果都需要通过通道输出, 若通道尚未完成输出, 则后来的
作业应排队等待, 每当通道完成输出时, 则从队列的队头退出作业作
输出操作, 而凡是申请该通道输出的作业都从队尾进入该队列 。
计算机系统中输入输出缓冲区的结构也是队列的应用 。 在计算机系统
中经常会遇到两个设备之间的数据传输, 不同的设备通常处理数据的
速度是不同的, 当需要在它们之间连续处理一批数据时, 高速设备总
是要等待低速设备, 这就造成计算机处理效率的大大降低 。 为了解决
这一速度不匹配的矛盾, 通常就是在这两个设备之间设置一个缓冲区
。 这样, 高速设备就不必每次等待低速设备处理完一个数据, 而是把
要处理的数据依次从一端加入缓冲区, 而低速设备从另一端取走要处
理的数据 。
返回本章首页
下一页
上一页
1 队列的定义及其运算
1,队列的定义
队列 （ queue） 是一种只允许在一端进行插入, 而在另一端进行删除的线
性表, 它是一种操作受限的线性表 。 在表中只允许进行插入的一端称为队
尾 （ rear）, 只允许进行删除的一端称为队头 (front)。 队列的插入操作通常
称为入队列或进队列, 而队列的删除操作则称为出队列或退队列 。 当队列
中无数据元素时, 称为空队列 。
根据队列的定义可知, 队头元素总是最先进队列的, 也总是最先出队列；
队尾元素总是最后进队列, 因而也是最后出队列 。 这种表是按照先进先出
（ FIFO,first in first out ） 的原则组织数据的, 因此, 队列也被称为, 先
进先出, 表 。
假若队列 q={a0,a1,a2,…, an-1},进队列的顺序为 a0,a1,a2,…, an-1
,则队头元素为 a0,队尾元素为 an-1。
入列出列 a0 a1 a2 ai an-1
front rear
图 5-11 队列的示意
图
… …
图 5-11是一个队列的示意图，通常用指针 front指示队头的位置，用指针 rear指
向队尾。
返回本章首页
下一页
上一页
2,队列的基本运算
（ 1） initQueue(q) 初始化：初始化一个新的队列 。
（ 2） empty(q) 队列非空判断：若队列 q不空, 则返回 TRUE；否则, 返
回 FALSE。
（ 3） append(q,x) 入队列：在队列 q的尾部插入元素 x,使元素 x成为新的
队尾 。 若队列满, 则返回 FALSE；否则, 返回 TRUE。
（ 4） delete(s) 出队列：若队列 q不空, 则返回队头元素, 并从队头删除
该元素, 队头指针指向原队头的后继元素；否则, 返回空元素 NULL。
（ 5） getHead(q) 取队头元素：若队列 q不空, 则返回队头元素；否则返
回空元素 NULL。
（ 6） length(q) 求队列长度：返回队列的长度 。
队列是一种特殊的线性表, 因此队列可采用顺序存储结构存储, 也可以
使用链式存储结构存储 。
返回本章首页
下一页
上一页
2 队列的顺序存储结构
1,顺序队列的数组表示
队列的顺序存储结构可以简称为顺序队列, 也就是利用一组地址连续的
存储单元依次存放队列中的数据元素 。 一般情况下, 我们使用一维数组
来作为队列的顺序存储空间, 另外再设立两个指示器：一个为指向队头
元素位置的指示器 front,另一个为指向队尾的元素位置的指示器 rear。
C语言中, 数组的下标是从 0开始的, 因此为了算法设计的方便, 在此我
们约定：初始化队列时, 空队列时令 front=rear=-1,当插入新的数据元素
时, 尾指示器 rear加 1,而当队头元素出队列时, 队头指示器 front加 1。 另
外还约定, 在非空队列中, 头指示器 front总是指向队列中实际队头元素的
前面一个位置, 而尾指示器 rear总是指向队尾元素 。
图 5-12 队列的存储结构
（ a）空队列；（ b）元素 A入列后；（ c）元素 B,C
,D,E入列后；（ d）元素 E,D出队列后
front=-
10
front=-1
A
front=-1
A
C
D
B
E rear=4
D
（ a） （ b） （ c） （ d）rear=-1
rear=0
rear=4 E
front=2
图 5-12给出了队列中头尾指针的变化状态 。
返回本章首页
下一页
上一页
2,顺序队列的基本运算算法
（ 1） 初始化队列
【 算法 5.10 顺序队列的初始化 】
int initQueue(sqqueue *q)
{/*创建一个空队列由指针 q指出 */
if ((q=(sqqueue*)malloc(sizeof(sqqueue))= =NULL) return FALSE;
q->front= -1;
q->rear=-1;
return TRUE;
}
（ 2） 入队列操作
【 算法 5.11 顺序队列的入队列操作 】
int append(sqqueue *q,Elemtype x)
{/*将元素 x插入到队列 q中, 作为 q的新队尾 */
if(q->rear>=MAXNUM-1) return FALSE; /*队列满 */
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
返回本章首页
下一页
上一页
（ 3） 出队列操作
【 算法 5.12 顺序队列的出队列操作 】
Elemtype delete(sqqueue *q)
{/*若队列 q不为空, 则返回队头元素 */
Elemtype x;
if(q->rear= =q->front) return NULL; /*队列空 */
x=q->queue[++q->front];
return x;
}
（ 4） 取队头元素操作
【 算法 5.13 顺序队列的取头元素操作 】
Elemtype getHead(sqqueue *q)
{/*若队列 q不为空, 则返回队头元素 */
if(q->rear= =q->front) return NULL; /*队列空 */
return (q->queue[s->front+1]);
}
（ 5） 判队列非空操作
【 算法 5.14 顺序队列的非空判断操作 】
int Empty(sqqueue *q)
{/*队列 q为空时, 返回 TRUE；否则返回 FALSE*/ if (q->rear= =q-
>front) return TRUE;
return FALSE;
返回本章首页
下一页
上一页
（ 6） 求队列长度操作
【 算法 5.15 顺序队列的求长度操作 】
int length(sqqueue *q)
{/*返回队列 q的元素个数 */
return(q->rear-q->front);
3,循环队列
MAXNUM
-1 0
1
rear
front
图 5-13 循环队列
示意
在顺序队列中, 当队尾指针已经指向了队列的最后一个位置时, 此时若
有元素入列, 就会发生, 溢出, 。 在图 5-12（ c） 中队列空间已满, 若再
有元素入列, 则为溢出；在图 5-12（ d） 中, 虽然队尾指针已经指向最后
一个位置, 但事实上队列中还有 3个空位置 。 也就是说, 队列的存储空间
并没有满, 但队列却发生了溢出, 我们称这种现象为假溢出 。 解决这个
问题有两种可行的方法：
返回本章首页
下一页
上一页
（ 1） 采用平移元素的方法, 当发生假溢出时, 就把整个队列的元素平移
到存储区的首部, 然后再插入新元素 。 这种方法需移动大量的元素, 因而
效率是很低的 。
（ 2） 将顺序队列的存储区假想为一个环状的空间, 如图 5-13所示 。 我们
可假想 q->queue[0]接在 q->queue[MAXNUM-1]的后面 。 当发生假溢出时,
将新元素插入到第一个位置上, 这样做, 虽然物理上队尾在队首之前, 但
逻辑上队首仍然在前 。 入列和出列仍按, 先进先出, 的原则进行, 这就是
循环队列 。
很显然, 方法二中不需要移动元素, 操作效率高, 空间的利用率也很高
。
在循环队列中, 每插入一个新元素时, 就把队尾指针沿顺时针方向移动
一个位置 。 即：
q->rear=q->rear+1;
if(q->rear= =MAXNUM) q->rear=0;
在循环队列中, 每删除一个元素时, 就把队头指针沿顺时针方向移动一
个位置 。 即：
q->front=q->front+1;
if(q->front= =MAXNUM) q->front=0;
返回本章首页
下一页
上一页
0
1
23
4
5front
rear(b)
A
B
C
0
1
23
4
5front
rear
(a)
0
1
23
4
5
A
B
CD
E
F
front
rear
(c)
图 3-14 循环队列示意图
（ a）队列空；（ b）队列非空；
(c)队列满
图 5-14所示, 为循环队列的三种状态, 图 5-14（ a） 为队列空时, 有 q-
>front= =q->rear；图 5-14（ b） 为队列满时, 也有 q->front= =q->rear；因此
仅凭 q->front= =q->rear不能判定队列是空还是满 。
返回本章首页
下一页
上一页
为了区分循环队列是空还是满, 我们可以设定一个标志位 s：
s= 0时为空队列, s=1时队列非空 。
用 C语言定义循环队列结构如下：
typedefstruct
{Elemtype queue[MAXNUM];
int front; /*队头指示器 */
int rear; /*队尾指示器 */
int s; /*队列标志位 */
}qqueue;
下面给出循环队列的初始化, 入队列及出队列的算法 。
（ 1） 初始化队列
【 算法 5.16循环队列的初始化 】
int initQueue(qqueue*q)
{/*创建一个空队列由指针 q指出 */
if ((q=(qqueue*)malloc(sizeof(qqueue)))= =NULL) return FALSE;
q->front= MAXNUM;
q->rear=MAXNUM;
q->s=0;
return TRUE;
}
返回本章首页
下一页
上一页
（ 2） 入队列操作
【 算法 5.17 循环队列的入队列操作 】
int append(qqueue*q,Elemtype x)
{/*将元素 x插入到队列 q中, 作为 q的新队尾 */
if (( q->s= =1)&&(q->front= =q->rear)) return FALSE; /*队列满 */
q->rear++;
if (q->rear= =MAXNUM) q->rear=0;
q->queue[q->rear]=x;
q->s=1; /*置队列非空 */
return TRUE;
}
（ 3） 出队列操作
【 算法 5.18 循环队列的出队列操作 】
Elemtype delete(qqueue *q)
{/*若队列 q不为空, 则返回队头元素 */
Elemtype x;
if (q->s= =0) retrun NULL; /*队列为空 */
q->front++;
if (q->front= =MAXNUM) q->front=0;
x=q->queue[q->front];
if (q->front = =q->rear) q->s=0; /*置队列空 */
return x; }
