第2章-线性表及其顺序存储

1、线性表顺序表栈队列线性表是一种常用的数据结构，本章介绍线性表线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。了详细的设计描述。 线性表是一个线性结构，它是一个含有线性表是一个线性结构，它是一个含有n0个个结点的有限序列，对于其中的结点，有且仅有一个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后

2、继结点。一般地，点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：一个线性表可以表示成一个线性序列：k1,k2,kn，其中其中k1是开始结点，是开始结点，kn是终端结点。是终端结点。 例例1、26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z）例例2、某校从、某校从1978年到年到1983年各种型号的计年各种型号的计算机拥有量的变化情况。算机拥有量的变化情况。 （6，17，28，50，92，188）姓姓 名名学学 号号 性性 别别年年 龄龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建

3、平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 贫血贫血 . . .例例3 学生健康情况登记表如下：学生健康情况登记表如下：例例4、一副扑克的点数、一副扑克的点数 （2，3，4，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它，它没有直接前趋，而仅有一个直接后继没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而，它没有直接后继，而仅有一个直接前趋仅有一个直接前趋an-1；其余的内部结点其余的内

4、部结点ai(2in-1)都有且仅有一个直都有且仅有一个直接前趋接前趋ai-1和一个直接后继和一个直接后继ai+1。 线性表是一种典型的线性结构。线性表是一种典型的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。地址连续的存储单元中。 如顺序表的每个结点占用如顺序表的每个结点占用len个内存单元，用个内存单元，用location (ki)表示顺序表中第表示顺序表中第i个结点个结点ki所占内存空间的所占内存空间的第第1个单元的地址。则有

5、如下的关系个单元的地址。则有如下的关系location (ki+1) = location (ki) +lenlocation (ki) = location(k1) + (i-1)len顺序表的存储结构如下图所示：顺序表的存储结构如下图所示：存储结构要体现数据的逻辑结构，顺序表的存储存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。中的逻辑关系。 len len len lenk1k2k ik n用用C语言中的数组存储顺序表。语言中的数组存储顺序表。C语言中数组的下语言中数组的下标是从标是从0开

6、始的，即数组中下标为开始的，即数组中下标为0的元素对应的是顺的元素对应的是顺序表中的第序表中的第1个结点，数组中下标为个结点，数组中下标为i的元素对应的是的元素对应的是顺序表中的第顺序表中的第i+1个结点。为了方便，将顺序表中各结个结点。为了方便，将顺序表中各结点的序号改为和对应数组元素的下标序号一致，即将点的序号改为和对应数组元素的下标序号一致，即将顺序表中各结点的序号从顺序表中各结点的序号从0开始编号。这样，一个长度开始编号。这样，一个长度为为n的顺序表可以表示为的顺序表可以表示为k0, k1, k2, , kn-1顺序表的存储结构的顺序表的存储结构的C语言描述如下：语言描述如下：/*顺序

7、表的头文件，文件名顺序表的头文件，文件名sequlist.h */ #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int size; sequence_list;顺序表的几个基本操作的具体实现顺序表的几个基本操作的具体实现 ：/ 函数功能函数功能:顺序表的初始化顺序表的初始化置空表置空表 / 函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt / 函数返回值函数返回值:空空 / 文件名文件名:sequlist.c, 函数名函数名:init() / v

8、oid init(sequence_list slt) slt-size=0; 算法算法2.1顺序表的初始化顺序表的初始化-置空表置空表/ 函数功能函数功能:在顺序表后部进行插入操作在顺序表后部进行插入操作 / 函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt / datatype类型的变量类型的变量x / 函数返回值函数返回值:空空 / 文件名文件名:sequlist.c, 函数名函数名:append() / void append(sequence_list slt,datatype x) if(slt-size=MAXSIZE) printf(顺

9、序表是满的顺序表是满的!);exit(1); slt-aslt-size=x; slt-size=slt-size+1; 算法算法2.2 在顺序表后部进行插入操作在顺序表后部进行插入操作打印顺序表的各结点值打印顺序表的各结点值/ 函数功能函数功能:打印顺序表的各结点值打印顺序表的各结点值 / 函数参数函数参数:sequence_list型变量型变量slt / 函数返回值函数返回值:空空 / 文件名文件名:sequlist.c, 函数名函数名:display() / void display(sequence_list slt) int i; if(!slt.size) printf(n顺序表是

10、空的顺序表是空的!); else for(i=0;islt.size;i+) printf(%5d,slt.ai); 算法算法2.3 打印顺序表的各结点值打印顺序表的各结点值判断顺序表是否为空判断顺序表是否为空 / 函数功能函数功能:判断顺序表是否为空判断顺序表是否为空 / 函数参数函数参数:sequence_list型变量型变量slt / 函数返回值函数返回值:int类型。类型。1表示空表示空,0表示非空表示非空 / 文件名文件名:sequlist.c,函数名函数名:empty() / int empty(sequence_list slt) return (slt.size=0 ? 1:0

11、); 算法算法2.4 判断顺序表是否为空判断顺序表是否为空查找顺序表中值为查找顺序表中值为x的结点位置的结点位置/ 函数功能函数功能:查找顺序表中值为查找顺序表中值为x的结点位置的结点位置 / 函数参数函数参数:sequence_list型变量型变量slt,datatype型变量型变量x / 函数返回值函数返回值:int类型。返回类型。返回x的位置值的位置值,-1表示没找到表示没找到 / 文件名文件名:sequlist.c,函数名函数名:find() / int find(sequence_list slt,datatype x) int i=0; while( islt.size&s

12、lt.ai!=x ) i+; return(islt.size? i:1); 算法算法2.5 查找顺序表中值为查找顺序表中值为x的结点位置的结点位置 取得顺序表中第取得顺序表中第i个结点的值个结点的值 / 函数功能函数功能:取得顺序表中第取得顺序表中第i个结点的值个结点的值 / 函数参数函数参数:sequence_list型变量型变量slt,int型变量型变量i / 函数返回值函数返回值:datatype类型。返回第类型。返回第i个结点的值个结点的值 / 文件名文件名:sequlist.c,函数名函数名:get() / datatype get(sequence_list slt,int i)

13、 if(i=slt.size) printf(n指定位置的结点不存在指定位置的结点不存在!);exit(1); else return slt.ai; 算法算法2.6 取得顺序表中第取得顺序表中第i个结点的值个结点的值顺序表的插入运算是将一个值为顺序表的插入运算是将一个值为x的结点插入到顺的结点插入到顺序表的第序表的第i个位置个位置0in，即将，即将x插入到插入到ki-1和和ki之间，如之间，如果果i=n，则表示插入到表的最后，一般地可表示为：，则表示插入到表的最后，一般地可表示为：插入前：插入前：k0, k1, , ki-1, ki, , kn-1插入后：插入后：k0, k1, , ki-1

14、,x, ki, , kn-1 插入过程的图示见下图：插入过程的图示见下图：k ik0k1k i-1k n-1k0k1k i-1k n-1xk i后移开始位置后移开始位置后移结束位置后移结束位置插入前插入前插入后插入后/ 函数功能函数功能:在顺序表的在顺序表的position位置插入值为位置插入值为x的结点的结点 / 函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt / datatype型变量型变量x,int型变量型变量 position / 函数返回值函数返回值:空空 文件名文件名:sequlist.c,函数名函数名:insert() / void i

15、nsert(sequence_list slt,datatype x,int position) int i; if(slt-size=MAXSIZE) printf(n顺序表是满的顺序表是满的!没法插入没法插入!);exit(1); if(positionslt-size) printf(n指定的插入位置不存在指定的插入位置不存在!);exit(1); for(i=slt-size;iposition;i-) slt-ai=slt-ai1; slt-aposition=x; slt-size+; 算法算法2.7 在顺序表的在顺序表的position位置插入值为位置插入值为x的结点的结点算法算

16、法2.7中，所花费的时间主要是元素后移操作，中，所花费的时间主要是元素后移操作，对于在第对于在第i个位置上插入一个新的元素，需要移动（个位置上插入一个新的元素，需要移动（n-i）个元素，设在第个元素，设在第i个位置上插入一个元素的概率为个位置上插入一个元素的概率为pi，且，且在 任 意 一 个 位 置 上 插 入 元 素 的 概 率 相 等 ， 即在 任 意 一 个 位 置 上 插 入 元 素 的 概 率 相 等 ， 即p0=p1=p2=pn=1/(n+1)，则在一个长度为，则在一个长度为n的顺序表的顺序表中插入一个元素所需的平均移动次数为：中插入一个元素所需的平均移动次数为：22) 1(11

17、)(11)(00nnnninninpninii即在长度为即在长度为n的顺序表中插入一个元素平均需要的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为移动表中的一半元素。该算法的时间复杂度为O（n）。）。 顺序表的删除操作是指删除顺序表中的第顺序表的删除操作是指删除顺序表中的第i个结点，个结点，0in-1，一般地可表示为：，一般地可表示为： 删除前：删除前：k0, k1, , ki-1, ki, ki+1, , kn-1 删除后：删除后：k0, k1, , ki-1, ki+1, , kn-1 删除过程的图示见下图删除过程的图示见下图 ：k ik0k1k i-1k n-1k0

18、k1k i-1k n-1k i+1前移结束位置前移结束位置前移开始位置前移开始位置删除前删除前删除后删除后k i+1删除操作的具体实现见算法删除操作的具体实现见算法2.8 / 函数功能函数功能:删除顺序表中第删除顺序表中第position位置的结点位置的结点 / 函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt / int型变量型变量 position / 函数返回值函数返回值:空空 文件名文件名:sequlist.c,函数名函数名:dele() / void dele(sequence_list slt,int position) int i; if

19、(slt-size=0) printf(n顺序表是空的顺序表是空的!);exit(1); if(position=slt-size) printf(n指定的删除位置不存在指定的删除位置不存在!);exit(1); for(i=position;isize-1;i+) slt-ai=slt-ai+1; slt-size-; 算法算法2.8 删除顺序表中第删除顺序表中第position位置的结点位置的结点 要删除顺序表中的第要删除顺序表中的第i个结点，则需要称动（个结点，则需要称动（n-i-1）个元素，设删除表中第个元素，设删除表中第i个结点的概率为个结点的概率为qi，且在表中每，且在表中每一个位

20、置删除的概率相等，即：一个位置删除的概率相等，即：q0=q1=qn-1=1/n 则在一个长度为则在一个长度为n的顺序表中删除一个结点的平均的顺序表中删除一个结点的平均移动次数为：移动次数为： 212) 1(1) 1(1) 1(1010nnnninninqninii这表明，在一个长为这表明，在一个长为n的顺序表中删除一个元素平的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂均需要移动表中大约一半的元素。该算法的时间复杂度为度为O（n）。）。 #include #define listsize 100 /*表的最大空间大小表的最大空间大小*/typedef int datat

21、ype;typedef struct list datatype datalistsize ; /*向量向量data用于用于*/ int length; /*当前的表长度当前的表长度*/ seqlist;实验：自定义一个线性表实验：自定义一个线性表 seqlist.h（1）void verge(seqlist *L) 将顺序表将顺序表L就地转置，即借助于就地转置，即借助于O（1）的辅助空间。）的辅助空间。（2）void sprit(seqlist *l1,seqlist *l2, seqlist *l3) 将有序顺序表将有序顺序表l1分裂成两个线性表分裂成两个线性表l2与与l3，l2由表中所奇

22、由表中所奇数组成，数组成，l3由所有偶数组成。由所有偶数组成。顺序表上的一些常见算法顺序表上的一些常见算法（3）void merge(seqlist *l1,seqlist *l2, seqlist *l3) 将有序顺序表将有序顺序表L1与与L2合并成有序顺序表合并成有序顺序表L3。30151102163743258362375482999610i(1)算法演示：算法演示：j96015110216374325836237548299310i算法演示：算法演示：jvoid merge(seqlist *l1,seqlist *l2,seqlist *l3) int i=0,j=0,k=0; wh

23、ile (ilength-1) & (jlength-1) if (l1-dataidataj) l3-datak+=l1-datai+; else l3-datak+=l2-dataj+; while (ilength-1) /*处理处理l1中剩余元素中剩余元素*/ l3-datak+=l1-datai+; while (jlength-1) /*处理处理l2中剩余元素中剩余元素*/ l3-datak+=l2-dataj+; l3-length=k; /*置线性表置线性表l3长度长度*/ 算法设计题：算法设计题：1、设计一个算法将一个顺序线性表中的所有奇、设计一个算法将一个顺序线性表

24、中的所有奇数集中到数组的左边，所有的偶数集中到数组的数集中到数组的左边，所有的偶数集中到数组的右边，要求算法的时间复杂度为右边，要求算法的时间复杂度为O(n)。 栈是一种特殊的线性表，对于这种线性表规定它栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为行插入和删除的那一端称为栈顶栈顶，另一端称为，另一端称为栈底栈底。栈的插入操作和删除操作也分别简称进栈和出栈。栈的插入操作和删除操作也分别简称进栈和出栈。如果栈中有如果栈中有n个结点个结点k0, k1, k2, , kn-1，k0为栈为栈

25、底，底，kn-1是栈顶，则栈中是栈顶，则栈中结点的进栈顺序为结点的进栈顺序为k0, k1, k2, , kn-1，而出栈的顺，而出栈的顺序为序为kn-1, kn-2, , k1, k0。如图所示。如图所示。 栈 具 有 后栈 具 有 后进 先 出 或进 先 出 或先 进 后 出先 进 后 出（FILO,First In Last Out）的性）的性质质 k0k1k n-1栈顶栈顶栈底栈底 出栈出栈 进栈进栈栈的顺序存储方式就是在顺序表的基础上对插入栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可

26、用一维数组表示。顺序表一样也可用一维数组表示。 一般地，可以设定一个足够大的一维数组存储栈，一般地，可以设定一个足够大的一维数组存储栈，数组中下标为数组中下标为0的元素就是栈底，对于栈顶，可以设一的元素就是栈底，对于栈顶，可以设一个指针个指针top指示它。指示它。 为了方便，设定为了方便，设定top所指的位置是下一个将要插入所指的位置是下一个将要插入的结点的存储位置，这样，当的结点的存储位置，这样，当top=0时就表示是一个空时就表示是一个空的栈。一个栈的几种状态以及在这些状态下栈顶指针的栈。一个栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系如下图所示。和栈中结点的关系如下图所示。

27、 k0k1k0k2k1k 数组下标数组下标 数组下标数组下标 数组下标数组下标MAXSIZE-1 MAXSIZE-1 MAXSIZE-12 top 2 21 1 1 top 0 0 0top (a)空栈空栈 (b)有两个结点的栈有两个结点的栈 (c)栈已满栈已满栈的顺序存储结构的栈的顺序存储结构的C语言描述如下：语言描述如下：/ 栈（顺序存储）的头文件栈（顺序存储）的头文件 / 文件名文件名seqstack.h / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int top; seque

28、nce_stack;下面是顺序存储栈的几个基本操作的具体实现下面是顺序存储栈的几个基本操作的具体实现 / 函数功能函数功能:栈（顺序存储）初始化栈（顺序存储）初始化 / 函数参数函数参数:指向指向sequence_stack型变量的指针变量型变量的指针变量st / 函数返回值函数返回值:空空 / 文件名文件名:seqstack.c,函数名函数名:init() / void init(sequence_stack st) st-top=0; 算法算法2.9栈（顺序存储）初始化栈（顺序存储）初始化 / 函数功能函数功能:判断栈（顺序存储）是否为空判断栈（顺序存储）是否为空 / 函数参数函数参数:s

29、equence_stack型变量型变量st / 函数返回值函数返回值:int类型。类型。1表示空表示空,0表示非空表示非空 / 文件名文件名:seqstack.c,函数名函数名:empty() / int empty(sequence_stack st) return(st.top? 0:1); 算法算法2.10判断栈（顺序存储）是否为空判断栈（顺序存储）是否为空 / 函数功能函数功能:读栈顶（顺序存储）结点值读栈顶（顺序存储）结点值 / 函数参数函数参数:sequence_stack型变量型变量st / 函数返回值函数返回值:datatype类型。返回栈顶结点值类型。返回栈顶结点值 / 文件

30、名文件名:seqstack.c,函数名函数名:read() / datatype read(sequence_stack st) if (empty(st) printf(n栈是空的栈是空的!);exit(1); else return st.ast.top-1; 算法算法2.11 取得栈顶（顺序存储）结点值取得栈顶（顺序存储）结点值顺序栈的进栈与出栈操作顺序栈的进栈与出栈操作下图表明进出栈情况。下图表明进出栈情况。（a）空栈）空栈A（b）A进栈进栈A（c）B、C、D进栈进栈BCDABCDABCDEABED/ 函数功能函数功能:栈（顺序存储）的插入（进栈）操作栈（顺序存储）的插入（进栈）操作

31、/ 函数参数函数参数:指向指向sequence_stack型变量的指针变量型变量的指针变量st / datatype型变量型变量x / 函数返回值函数返回值:空空 / 文件名文件名:seqstack.c,函数名函数名:push() / void push(sequence_stack st,datatype x) if(st-top=MAXSIZE) printf(nThe sequence stack is full!);exit(1); st-ast-top=x; st-top+; 算法算法2.12 栈（顺序存储）的插入操作栈（顺序存储）的插入操作 / 函数功能函数功能:栈（顺序存储）的删

32、除（出栈）操作栈（顺序存储）的删除（出栈）操作 / 函数参数函数参数:指向指向sequence_stack型变量的指针变量型变量的指针变量st / 函数返回值函数返回值:空空 / 文件名文件名:seqstack.c,函数名函数名pop() / void pop(sequence_stack st) if(st-top=0) printf(nThe sequence stack is empty!);exit(1); st-top-; 算法算法2.13栈（顺序存储）的删除操作栈（顺序存储）的删除操作 思考思考:如果将栈空表如果将栈空表示为示为top=-1,则所有则所有栈的所有操作为何栈的所有操作

33、为何变化呢变化呢?设一个表达式中可以包含三种括号：小括号、中设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下：内可以嵌套中括号、大括号，但是不能交叉。举例如下：()正确的正确的() 正确的正确的()正确的正确的()不正确的不正确的() 不正确的不正确的 如何去检验一个表达式的括号是否匹配呢？大家如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号知道当自左向右扫描一个表达式时，凡是遇到的开括号（或称左括号）都期待有一个和

34、它对应的闭括号（或称（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。右括号）与之匹配。 按照括号正确匹配的规则，在自左向右扫描一个按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的开括号比先遇到的开括号更加期待表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。有一个闭括号与之匹配。 / 函数功能函数功能:判断表达式括号是否匹配判断表达式括号是否匹配 / 函数参数函数参数:char类型数组类型数组c / 函数返回值函数返回值:int类型。返回类型。返回1为匹配为匹配,返回返回0为不匹配为不匹配 / 文件名文件名:seqmatch.c,函数名函数名:

35、match_kouhao() /int match_kuohao(char c) int i=0; sequence_stack s; init(&s); while(ci!=#) switch(ci) case : case : case (:push(&s,ci);break; case :if(!empty(s)&read(s)= ) pop(&s);break; else return 0; case :if(!empty(s)&read(s)= ) pop(&s);break; else return 0; case ):if(!emp

36、ty(s)&read(s)=( ) pop(&s);break; else return 0; i+; return (empty(s); / 栈为空则匹配栈为空则匹配,否则不匹配否则不匹配 / 算法算法2.14 判断表达式括号是否匹配判断表达式括号是否匹配算术表达式通常是由操作数、算术运算符和一对圆算术表达式通常是由操作数、算术运算符和一对圆括号括号“（”和和“）”组合而成。其中操作数允许是程组合而成。其中操作数允许是程序语言中任意合法的变量名或常数。序语言中任意合法的变量名或常数。 以下我们讨论以下我们讨论+、-、*、/四种算术运算。四种算术运算。表达式求值中的首要问题：如

37、何确定表达式中所含运表达式求值中的首要问题：如何确定表达式中所含运算的计算次序。算的计算次序。算术运算的规则：算术运算的规则：1）先乘除、后加减）先乘除、后加减2）从左算到右）从左算到右3）先括号内、后括号外）先括号内、后括号外按此原则，算术表达式按此原则，算术表达式 A+B*（C+D）的运算次序为：的运算次序为： A+B*（C+D） 而不是而不是 A+B*（C+D）问题：问题：如何让计算机也遵守算术运算规则，正确计算如何让计算机也遵守算术运算规则，正确计算表达式的值？表达式的值？加括号，即对每个一运算都用一对括号将与加括号，即对每个一运算都用一对括号将与其配对的左、右操作对象括在一起，由此上

38、面算术表其配对的左、右操作对象括在一起，由此上面算术表达式将写成（达式将写成（A+（B*（C+D）利用栈求表达式的值：利用栈求表达式的值：1）自左至右的扫描加括号的算术表达式）自左至右的扫描加括号的算术表达式2）将非右括号）将非右括号“）”的符号进栈的符号进栈3）每当遇见右括号）每当遇见右括号“）”，从栈顶向下扫描至第一，从栈顶向下扫描至第一个左括号个左括号“（”，这就是和遇见的右括号，这就是和遇见的右括号“）”配对配对的左括号的左括号“（”，该左括号，该左括号“（”上面的表达式就是上面的表达式就是现在应该计算的表达式，从栈中弹出对应的左括号现在应该计算的表达式，从栈中弹出对应的左括号“（”以

39、上的所有符号（含左括号以上的所有符号（含左括号”（“），计算相），计算相应表达式，并将结果压入栈中。应表达式，并将结果压入栈中。重复重复1）2）3）即可计算出表达式的值。）即可计算出表达式的值。特点：方法简单明了，但要求人们事先为要计算特点：方法简单明了，但要求人们事先为要计算的表达式加好括号，这既繁琐，又易出错。的表达式加好括号，这既繁琐，又易出错。重新改写表达式为后缀表达式。重新改写表达式为后缀表达式。在计算机中，表达式可以有三种不同的标识方法在计算机中，表达式可以有三种不同的标识方法设设 Exp = S1 + OP + S2则称则称 OP + S1 + S2 为表达式的前缀表示法为表达式

40、的前缀表示法 称称 S1 + OP + S2 为表达式的中缀表示法为表达式的中缀表示法 称称 S1 + S2 + OP 为表达式的后缀表示法为表达式的后缀表示法可见，它以运算符所在不同位置命名的。可见，它以运算符所在不同位置命名的。例：例： 中缀表达式中缀表达式 后缀表达式后缀表达式 （1） A A （2） A+B AB+ （3） A+B*C ABC*+ （4） A*（B-C）+D ABC-*D+ （5） D+A/（B-C） DABC-/+操作数之间的相对次序不变操作数之间的相对次序不变; 运算符的相对次序不同运算符的相对次序不同; 后缀表达式中没有括号，运算符排在其第二个操作后缀表达式中没有

41、括号，运算符排在其第二个操作数之后数之后; 前缀式的运算规则为前缀式的运算规则为:连续出现的两个操作数和在它连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式们之前且紧靠它们的运算符构成一个最小表达式; 后缀式的运算规则为后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算运算符在式中出现的顺序恰为表达式的运算顺序顺序; 每个运算符和在它之前出现且紧靠它的两个每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式操作数构成一个最小表达式;+-*/四则运算的计算方法：四则运算的计算方法：第一步：将中缀表达式转换成等价的后缀表达式第一步：将中缀表达式转换成等价的后

42、缀表达式第二步：使用后缀表达式进行计算。第二步：使用后缀表达式进行计算。算法：利用后缀表达式求值算法：利用后缀表达式求值基本思想：基本思想：1）从左到右扫描后缀表达式，遇到操作对象进栈。）从左到右扫描后缀表达式，遇到操作对象进栈。2）遇到运算符，弹出栈顶的元素，其中栈顶为第）遇到运算符，弹出栈顶的元素，其中栈顶为第二操作对象，次栈顶为第一操作对象，对其按遇到二操作对象，次栈顶为第一操作对象，对其按遇到的运算符进行运算，并将结果进栈。的运算符进行运算，并将结果进栈。重复上述动作最后即可求出表达式的值。重复上述动作最后即可求出表达式的值。例如有中缀表达式：例如有中缀表达式：A/B-（C+D）*E其

43、对应的后缀表达式为：其对应的后缀表达式为：AB/CD+E*-利用后缀表达式求值过程如下所示：利用后缀表达式求值过程如下所示：步骤步骤 操作数栈操作数栈 后缀表达式后缀表达式 说明说明1 AB/CD+E*-# 初始栈空初始栈空，A进栈进栈2 A AB/CD+E*-#B进栈进栈3 AB AB/CD+E*-#遇遇/，弹出栈，弹出栈顶两元素做顶两元素做A/B= ，并，并将其进栈将其进栈4 AB/CD+E*-# C进栈进栈5 C AB/CD+E*-# D进栈进栈步骤步骤 操作数栈操作数栈 后缀表达式后缀表达式 说明说明6 CD AB/CD+E*-# 遇遇+，弹出，弹出CD做做 C+D= ，并将其，并将其

44、进栈进栈7 AB/CD+E*-# E进栈进栈8 E AB/CD+E*-# 遇遇*，弹出栈，弹出栈顶两元做顶两元做 *E= ，并，并将结果进栈将结果进栈9 AB/CD+E*-# 遇遇-，弹出栈顶，弹出栈顶二元做二元做 - = ，并将结，并将结果进栈果进栈10 AB/CD+E*-# 遇遇#，结束，结束，栈顶就是表达栈顶就是表达式的计算结果式的计算结果 在实际应用中，操作数可设为实数，且两个在实际应用中，操作数可设为实数，且两个实数间用空格隔开。实数间用空格隔开。问题：后缀表达式为字符串，如何从其中分离出问题：后缀表达式为字符串，如何从其中分离出每一个操作数。每一个操作数。解决办法：解决办法：用函数

45、用函数Readnumber(),实现将扫描到的数字字符实现将扫描到的数字字符序列转换成相应实数：序列转换成相应实数：float readnumber(char f,int *i) float x=0.0; int k=0; while(f*i=0&f*i=0& f*i=0 & ei=priority(ei) fj+=pop(&opst); push(&opst,ei); /*当前元进栈当前元进栈*/ i+; /*处理下一元处理下一元*/ while (!stackempty(&opst) fj+=pop(&opst); fj=0; 判断是

46、否为运算符判断是否为运算符 int is_operation(char op) switch(op) case +: case -: case : case /:return 1; default:return 0; 返回运算符的优先级返回运算符的优先级 int priority(char op) switch(op) case (:return 0; case +: case -:return 1; case *: case /:return 2; default: return -1; 两个辅助函数：两个辅助函数：习题习题:数制转换问题数制转换问题十进制十进制n和其它进制数的转换是计算机实

47、现计和其它进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算算的基本问题，其解决方法很多，其中一个简单算法基于下列原理法基于下列原理: n=(n div d)*d+n mod d( 其中其中:div为整除运算为整除运算,mod为求余运算为求余运算) 例如例如 (1348)10=(2504)8，其运算过程如下：其运算过程如下：n n div 8 n mod 8 1348 168 416821 0212 5 2 0 2倒倒取取余余数数1348)10=(2504)8例用栈的知识实现任意正的例用栈的知识实现任意正的10进制整数到其它进进制整数到其它进位制的转换程序。位制的转换程序。

48、算法设计题算法设计题:2、回文是指正读和反读均相同的字符序列，如、回文是指正读和反读均相同的字符序列，如“abba”和和“abdba”均是回文，但均是回文，但“good”不是回文不是回文，试写一个算法判定给定的字符向量是否为回文。，试写一个算法判定给定的字符向量是否为回文。void conversion( ) init(s); scanf (“%d”,&n); while(n) /余数进栈余数进栈 push(&s,n%8); n=n/8; while(! Stackempty(s) e=pop(&s); /余数出栈余数出栈 printf(“%d”,e); 习题一解答习题

49、一解答:2.4 队列队列 队列是一种特殊的线性表，它的特殊性在于队列队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。作和删除操作也分别简称进队和出队。 对于一个队列：对于一个队列：k0, k1, k2, , kn-1则则k0是这些结点中最先插入的结点，若要做删除操作，是这些结点中最先插入的结点，若要做删除操作，k0将首先被删除，所以说，队列是具有将首先被删除，所以说，队列是具有“先进先

50、出先进先出”（FIFO,First In First Out）特点的线性结构。）特点的线性结构。 队列类型的描述如下：队列类型的描述如下：ADT sequence_queue 数据集合数据集合K:K=k1,k2,kn,n0,K中的元素是中的元素是datatype类型类型; 数据关系数据关系R:R=r r= | i=1,2,n1。 操作集合操作集合: （1）void init (sequence_queue sq) 队列（顺序存储）初始化队列（顺序存储）初始化; （2）int empty (sequence_queue sq) 判断队列（顺序存储）是否为判断队列（顺序存储）是否为空空; （3）v

51、oid display (sequence_queue sq) 打印队列（顺序存储）的结打印队列（顺序存储）的结点值点值; （4）datatype get(sequence_queue sq) 取得队列（顺序存储）的队取得队列（顺序存储）的队首结点值首结点值; （5）void insert(sequence_queue sq,datatype x) 队列（顺序存储）的插入操作队列（顺序存储）的插入操作; （6）void dele(sequence_queue sq) 队列（顺序存储）的删除操作。队列（顺序存储）的删除操作。 ADT sequence_queue;队列的顺序存储在队列的顺序存储在

52、C语言中可以用一维数组表示，语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针为了标识队首和队尾，需要附设两个指针front和和rear，front指示的是队列中最前面，即队首结点在指示的是队列中最前面，即队首结点在数组中元素的下标，数组中元素的下标，rear指示的是队尾结点在数组指示的是队尾结点在数组中元素的下标的下一个位置，也就是说中元素的下标的下一个位置，也就是说rear指示的指示的是即将插入的结点在数组中的下标。是即将插入的结点在数组中的下标。 队首、队尾指针队首、队尾指针 front rear 数组下标数组下标 0 1 MAXSIZE-1 (a)初始状态初始状态-空队列空

53、队列AB队首、队尾指针队首、队尾指针 front rear 数组下标数组下标 0 1 MAXSIZE-1 (b)连续插入几个结点后的状态连续插入几个结点后的状态DC队首、队尾指针队首、队尾指针 front rear 数组下标数组下标 0 1 2 3 MAXSIZE-1 (c)连续删除几个结点后的状态连续删除几个结点后的状态-此时队列中只有一个结点此时队列中只有一个结点D队首、队尾指针队首、队尾指针 front rear 数组下标数组下标 0 1 MAXSIZE-1 (d) 在在(c)状态下再删除一个结点后的状态状态下再删除一个结点后的状态-空队列空队列X队首、队尾指针队首、队尾指针 front

54、 rear 数组下标数组下标 0 1 2 3 MAXSIZE-1 (e)连续插入若干结点后的状态连续插入若干结点后的状态-此时队列呈现满的状态，此时队列呈现满的状态，但数组前部有空位子但数组前部有空位子DE队列的顺序存储结构的队列的顺序存储结构的C语言描述如下：语言描述如下：/ 队列（顺序存储）的头文件队列（顺序存储）的头文件 / 文件名文件名seqqueue.h / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int front; int rear; sequence_queue;顺序

55、存储队列的几个基本操作的具体实现顺序存储队列的几个基本操作的具体实现 :/ 函数功能函数功能:队列（顺序存储）初始化队列（顺序存储）初始化 / 函数参数函数参数:指向指向sequence_queue类型变量的指针变量类型变量的指针变量sq / 函数返回值函数返回值:空空 / 文件名文件名:seqqueue.c,函数名函数名:init() / void init(sequence_queue sq) sq-front=sq-rear=0; 算法算法2.20 队列（顺序存储）初始化队列（顺序存储）初始化 / 函数功能函数功能:判断队列（顺序存储）是否为空判断队列（顺序存储）是否为空 / 函数参数函

56、数参数:sequence_queue类型变量类型变量sq / 函数返回值函数返回值:int类型。返回类型。返回1表示空表示空,0表示非空表示非空 / 文件名文件名:seqqueue.c,函数名函数名:empty() / int empty(sequence_queue sq) return (sq.front=sq.rear? 1:0); 算法算法2.21判断队列（顺序存储）是否为空判断队列（顺序存储）是否为空 / 函数功能函数功能:打印队列（顺序存储）的结点值打印队列（顺序存储）的结点值 / 函数参数函数参数:sequence_queue类型变量类型变量sq / 函数返回值函数返回值:空空

57、/ 文件名文件名:seqqueue.c,函数名函数名:display() /void display(sequence_queue sq) int i; if(empty(sq) printf(n顺序队列是空的顺序队列是空的!); else for(i=sq.front;irear=MAXSIZE) printf(n顺序队列是满的顺序队列是满的!);exit(1); sq-asq-rear=x; sq-rear=sq-rear+1; 算法算法2.24 队列（顺序存储）的插入操作队列（顺序存储）的插入操作/ 函数功能函数功能:队列（顺序存储）的删除（出队）操作队列（顺序存储）的删除（出队）操作

58、/ 函数参数函数参数:指向指向sequence_queue类型变量的指针变量类型变量的指针变量sq / 函数返回值函数返回值:空空 / 文件名文件名:seqqueue.c,函数名函数名:dele() / void dele(sequence_queue sq) if(sq-front=sq-rear) printf(n顺序队列是空的！不能做删除操作！顺序队列是空的！不能做删除操作！); exit(1); sq-front+; 算法算法2.25 队列（顺序存储）的删除操作队列（顺序存储）的删除操作 在队列的几种状态图的（在队列的几种状态图的（e）状态中，队列是一种）状态中，队列是一种队满状态，将

59、不能再插入新的结点，而实际上数组的队满状态，将不能再插入新的结点，而实际上数组的前部还有许多空的位置。为了充分地利用空间，可以前部还有许多空的位置。为了充分地利用空间，可以将队列看作一个循环队列，在数组的前部继续作插入将队列看作一个循环队列，在数组的前部继续作插入运算，这就是循环队列。运算，这就是循环队列。 X队首、队尾指针队首、队尾指针 front rear 数组下标数组下标 0 1 2 3 MAXSIZE-1 (e)连续插入若干结点后的状态连续插入若干结点后的状态-此时队列呈现满的状此时队列呈现满的状态，但数组前部有空位子态，但数组前部有空位子DE给定一个大小为给定一个大小为MAXSIZE

60、的数组存储一个队列的数组存储一个队列时，经过若干次插入和删除操作后，当队尾指示时，经过若干次插入和删除操作后，当队尾指示rear=MAXSIZE时，呈现队列满的状态，而事实上时，呈现队列满的状态，而事实上数组的前部可能还有空闲的位置。为了有效利用空间，数组的前部可能还有空闲的位置。为了有效利用空间，将顺序存储的队列想象为一个环状，把数组中的最前将顺序存储的队列想象为一个环状，把数组中的最前和最后两个元素看作是相邻的，这就是循环队列。和最后两个元素看作是相邻的，这就是循环队列。 在循环队列中进行出队、入队操作时，头尾在循环队列中进行出队、入队操作时，头尾指针仍要加指针仍要加1，朝前移动。只不过当头尾指针指，朝前移动。只不过当头尾指针指向向量上界（向向量上界（MaxSize-1）时，其加）时，其加1操作的结操作的结果是指向向量的下界果是指