数据结构第02章_线性表(I).ppt

《数据结构第02章_线性表(I).ppt》由会员分享，可在线阅读，更多相关《数据结构第02章_线性表(I).ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、李云清李云清 杨庆红杨庆红 揭安全揭安全高等学校精品课程高等学校精品课程人民邮电出版社人民邮电出版社（第（第2版）版）揭安全揭安全江西省高等学校精品课程江西省高等学校精品课程E_mailE_mail:江西师范大学计算机信息工程学院江西师范大学计算机信息工程学院退出第第2章章 线性表及其顺序存储线性表及其顺序存储线性表线性表顺序表顺序表栈栈队列队列退出 线性表是一种常用的数据结构，本章介绍线性表线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。了详细的设计描述。2.1线性表线性表 线性表是一个线

2、性结构，它是一个含有线性表是一个线性结构，它是一个含有n0个结个结点的有限序列，对于其中的结点，有且仅有一个开点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：个线性表可以表示成一个线性序列：k1,k2,kn，其中其中k1是开始结点，是开始结点，kn是终端结点。是终端结点。退出例例1、26个英文字母组成的字母

3、表个英文字母组成的字母表 （A，B，C、Z）例例2、某校从、某校从1978年到年到1983年各种型号的计年各种型号的计算机拥有量的变化情况。算机拥有量的变化情况。（6，17，28，50，92，188）退出姓姓 名名学学 号号 性性 别别年年 龄龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 贫血贫血.例例3 学生健康情况登记表如下：学生健康情况登记表如下：退出例例4、一副扑克的点数、一副扑克的点数 （2，3，4，J，Q，K，A）从以上例子可看出线性表

4、的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它它没有直接前趋，而仅有一个直接后继没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而它没有直接后继，而仅有一个直接前趋仅有一个直接前趋an-1；其余的内部结点其余的内部结点ai(2 i n-1)都有且仅有一个直都有且仅有一个直接前趋接前趋ai-1和一个直接后继和一个直接后继ai+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。退出2.2.1顺序表顺序表 线性表采用顺序存储的方式存储就称之为顺序表。线性表

5、采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。地址连续的存储单元中。如如顺顺序序表表的的每每个个结结点点占占用用len个个内内存存单单元元，用用location(ki)表表示示顺顺序序表表中中第第i个个结结点点ki所所占占内内存存空空间间的的第第1个单元的地址。则有如下的关系个单元的地址。则有如下的关系location(ki+1)=location(ki)+lenlocation(ki)=location(k1)+(i-1)len2.2顺序表顺序表退出顺序表的存储结构如下图所示：顺序表的存

6、储结构如下图所示：存储结构要体现数据的逻辑结构，顺序表的存储存储结构要体现数据的逻辑结构，顺序表的存储结构中，内存中物理地址相邻的结点一定具有顺序表结构中，内存中物理地址相邻的结点一定具有顺序表中的逻辑关系。中的逻辑关系。存储地址存储地址存储地址存储地址 location(klocation(k1 1)location(k)location(k1 1)+(i-1)l)+(i-1)l en en 结点序号结点序号结点序号结点序号 1 2 i 1 2 i n n len len len lenk1k2kikn内存状况内存状况内存状况内存状况退出2.2.2顺序表的实现顺序表的实现 用用C语语言言中中

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

8、构的顺序表的存储结构的C语言描述如下：语言描述如下：/*顺序表的头文件，文件名顺序表的头文件，文件名sequlist.h*/#define MAXSIZE 100 typedef int datatype;typedef struct datatype aMAXSIZE;int size;sequence_list;表长表长退出顺序表的几个基本操作的具体实现顺序表的几个基本操作的具体实现：/函数功能函数功能:顺序表的初始化顺序表的初始化置空表置空表/函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt/函数返回值函数返回值:空空/文件名文件名:sequli

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

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

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

12、查找顺序表中值为查找顺序表中值为x的结点位置的结点位置 /函数功能函数功能:查找顺序表中值为查找顺序表中值为x的结点位置的结点位置/函数参数函数参数:sequence_list型变量型变量slt,datatype型变量型变量x/函数返回值函数返回值:int类型。返回类型。返回x的位置值的位置值,-1表示没找到表示没找到 /文件名文件名:sequlist.c,函数名函数名:find()/intfind(sequence_listslt,datatypex)inti=0;while(islt.size&slt.ai!=x)i+;return(islt.size?i:1);算法算法2.5 查找顺序表

13、中值为查找顺序表中值为x的结点位置的结点位置退出 取得顺序表中第取得顺序表中第i个结点的值个结点的值/函数功能函数功能:取得顺序表中第取得顺序表中第i个结点的值个结点的值/函数参数函数参数:sequence_list型变量型变量slt,int型变量型变量i/函数返回值函数返回值:datatype类型。返回第类型。返回第i个结点的值个结点的值/文件名文件名:sequlist.c,函数名函数名:get()/datatypeget(sequence_listslt,inti)if(i=slt.size)printf(n指定位置的结点不存在指定位置的结点不存在!);exit(1);elsereturn

14、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,x,ki,kn-1 插入过程的图示见下图：插入过程的图示见下图：k ik0k1k i-1k n-1k0k1k i-1k n-1xk i后移开始位置后移开始位置后

15、移结束位置后移结束位置插入前插入前插入后插入后退出/函数功能函数功能:在顺序表的在顺序表的position位置插入值为位置插入值为x的结点的结点 /函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt/datatype型变量型变量x,int型变量型变量position/函数返回值函数返回值:空空文件名文件名:sequlist.c,函数名函数名:insert()/voidinsert(sequence_list slt,datatypex,intposition)inti;if(slt-size=MAXSIZE)printf(n顺序表是满的顺序表是满的!没法

16、插入没法插入!);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的结点的结点退出 算算法法2.7中中，所所花花费费的的时时间间主主要要是是元元素素后后移移操操作作，对对于于在在第第i个个位位置置上上插插入入一一个个新新的的元元素素，需需要要移移动动（n-i）个个元元素素，设设在在第第i个个位位置

17、置上上插插入入一一个个元元素素的的概概率率为为pi，且且在在 任任 意意 一一 个个 位位 置置 上上 插插 入入 元元 素素 的的 概概 率率 相相 等等，即即p0=p1=p2=pn=1/(n+1)，则则在在一一个个长长度度为为n的的顺顺序序表表中插入一个元素所需的平均移动次数为：中插入一个元素所需的平均移动次数为：即在长度为即在长度为n的顺序表中插入一个元素平均需要的顺序表中插入一个元素平均需要移动表中的一半元素。该算法的时间复杂度为移动表中的一半元素。该算法的时间复杂度为O（n）。）。退出 顺顺序序表表的的删删除除操操作作是是指指删删除除顺顺序序表表中中的的第第i个个结结点点，0in-1

18、，一般地可表示为：一般地可表示为：删除前：删除前：k0,k1,ki-1,ki,ki+1,kn-1 删除后：删除后：k0,k1,ki-1,ki+1,kn-1 删除过程的图示见下图删除过程的图示见下图：k ik0k1k i-1k n-1k0k1k i-1k n-1k i+1前移结束位置前移结束位置前移开始位置前移开始位置删除前删除前删除后删除后k i+1退出删除操作的具体实现见算法删除操作的具体实现见算法2.8/函数功能函数功能:删除顺序表中第删除顺序表中第position位置的结点位置的结点/函数参数函数参数:指向指向sequence_list型变量的指针变量型变量的指针变量slt/int型变量

19、型变量position /函数返回值函数返回值:空空文件名文件名:sequlist.c,函数名函数名:dele()/voiddele(sequence_list slt,intposition)inti;if(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位置的结点位置的结点

20、退出 要要删删除除顺顺序序表表中中的的第第i个个结结点点，则则需需要要称称动动（n-i-1）个个元元素素，设设删删除除表表中中第第i个个结结点点的的概概率率为为qi，且且在在表表中中每每一个位置删除的概率相等，即：一个位置删除的概率相等，即：q0=q1=qn-1=1/n 则则在在一一个个长长度度为为n的的顺顺序序表表中中删删除除一一个个结结点点的的平平均均移动次数为：移动次数为：这表明，在一个长为这表明，在一个长为n的顺序表中删除一个元素平的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂均需要移动表中大约一半的元素。该算法的时间复杂度为度为O（n）。）。退出（1）void

21、 verge(sequence_list l)将顺序表将顺序表L就地转置，即借助于就地转置，即借助于O（1）的辅助空间。的辅助空间。（2）void sprit(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)略略 将有序顺序表将有序顺序表L1分裂成两个线性表分裂成两个线性表L2与与L3，L2由表由表中所奇数组成，中所奇数组成，L3由所有偶数组成。由所有偶数组成。顺序表上的一些其它常见算法顺序表上的一些其它常见算法（3）void merge(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)

22、将有序顺序表将有序顺序表L1与与L2合并成有序顺序表合并成有序顺序表L3。退出2.3 栈栈 2.3.1栈栈 栈是一种特殊的线性表，对于这种线性表规定它栈是一种特殊的线性表，对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行，进的插入运算和删除运算均在线性表的同一端进行，进行插入和删除的那一端称为行插入和删除的那一端称为栈顶栈顶，另一端称为，另一端称为栈底栈底。栈的插入操作和删除操作也分别简称进栈和出栈。栈的插入操作和删除操作也分别简称进栈和出栈。如如果果栈栈中中有有n个个结结点点k0,k1,k2,kn-1，k0为为栈栈底底，kn-1是是栈栈顶顶，则则栈栈中中结结点点的的进进栈栈顺顺

23、序序为为k0,k1,k2,kn-1，而而出出栈栈的的顺顺序序为为kn-1,kn-2,k1,k0。如图所示。如图所示。栈栈 具具 有有 后后进进 先先 出出 或或先先 进进 后后 出出（FILO,First In Last Out）的的性性质质 k0k1k n-1栈顶栈顶栈底栈底 出栈出栈 进栈进栈退出2.3.2顺序栈及其实现顺序栈及其实现 栈的顺序存储方式就是在顺序表的基础上对插入栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。顺序表一样也可用一维数组表示。一般地，可以设定一个足

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

25、数组下标MAXSIZE-1 MAXSIZE-1 MAXSIZE-12 top 2 21 1 1 top 0 0 0top (a)空栈空栈 (b)有两个结点的栈有两个结点的栈 (c)栈已满栈已满退出栈的顺序存储结构的栈的顺序存储结构的C语言描述如下：语言描述如下：/栈（顺序存储）的头文件栈（顺序存储）的头文件/文件名文件名seqstack.h/#defineMAXSIZE100typedefintdatatype;typedefstructdatatypeaMAXSIZE;inttop;sequence_stack;退出下面是顺序存储栈的几个基本操作的具体实现下面是顺序存储栈的几个基本操作的具体

26、实现/函数功能函数功能:栈（顺序存储）初始化栈（顺序存储）初始化/函数参数函数参数:指向指向sequence_stack型变量的指针变量型变量的指针变量st/函数返回值函数返回值:空空/文件名文件名:seqstack.c,函数名函数名:init()/voidinit(sequence_stack st)st-top=0;算法算法2.9栈（顺序存储）初始化栈（顺序存储）初始化 说明说明:top=0:top=0表示栈表示栈空，这种情况下栈空，这种情况下栈顶指示位内容始终顶指示位内容始终为空。为空。退出/函数功能函数功能:判断栈（顺序存储）是否为空判断栈（顺序存储）是否为空 /函数参数函数参数:se

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

28、数名函数名:read()/datatyperead(sequence_stackst)if(empty(st)printf(n栈是空的栈是空的!);exit(1);elsereturnst.ast.top-1;算法算法2.11 取得栈顶（顺序存储）结点值取得栈顶（顺序存储）结点值退出顺序栈的进栈与出栈操作顺序栈的进栈与出栈操作下图表明进出栈情况。下图表明进出栈情况。5 54 43 32 21 10 0toptop（a）空栈空栈5 54 43 32 21 10 0toptopA（b）A进栈进栈5 54 43 32 21 10 0-1-1toptopA（c）B、C、D进栈进栈BCDtoptopto

29、ptoptoptop退出5 54 43 32 21 10 0A（d d）D,CD,C出栈出栈出栈出栈BCDtoptop5 54 43 32 21 10 0（e e）E E进栈进栈进栈进栈ABCDtoptopEtoptop5 54 43 32 21 10 0ABEDtoptop（f f）E E、B B、A A出栈出栈出栈出栈退出/函数功能函数功能:栈（顺序存储）的插入（进栈）操作栈（顺序存储）的插入（进栈）操作/函数参数函数参数:指向指向sequence_stack型变量的指针变量型变量的指针变量st/datatype型变量型变量x /函数返回值函数返回值:空空/文件名文件名:seqstack.

30、c,函数名函数名:push()/voidpush(sequence_stack st,datatypex)if(st-top=MAXSIZE)printf(nThesequencestackisfull!);exit(1);st-ast-top=x;st-top+;算法算法2.12 栈（顺序存储）的插入操作栈（顺序存储）的插入操作 退出/函数功能函数功能:栈（顺序存储）的删除（出栈）操作栈（顺序存储）的删除（出栈）操作/函数参数函数参数:指向指向sequence_stack型变量的指针变量型变量的指针变量st/函数返回值函数返回值:空空/文件名文件名:seqstack.c,函数名函数名pop(

31、)/voidpop(sequence_stack st)if(st-top=0)printf(nThesequencestackisempty!);exit(1);st-top-;算法算法2.13栈（顺序存储）的删除操作栈（顺序存储）的删除操作 思考思考:如果将栈空表如果将栈空表示为示为top=-1,则所有则所有栈的所有操作为何栈的所有操作为何变化呢变化呢?退出2.3.3栈的应用之一栈的应用之一-括号匹配括号匹配 设设一一个个表表达达式式中中可可以以包包含含三三种种括括号号：小小括括号号、中中括括号号和和大大括括号号，各各种种括括号号之之间间允允许许任任意意嵌嵌套套，如如小小括括号号内可以嵌套

32、中括号、大括号，但是不能交叉。举例如下：内可以嵌套中括号、大括号，但是不能交叉。举例如下：()正确的正确的()正确的正确的()正确的正确的()不正确的不正确的()不正确的不正确的 退出 如何去检验一个表达式的括号是否匹配呢？大家如何去检验一个表达式的括号是否匹配呢？大家知道当自左向右扫描一个表达式时，凡是遇到的开括号知道当自左向右扫描一个表达式时，凡是遇到的开括号（或称左括号）都期待有一个和它对应的闭括号（或称（或称左括号）都期待有一个和它对应的闭括号（或称右括号）与之匹配。右括号）与之匹配。按照括号正确匹配的规则，在自左向右扫描一个按照括号正确匹配的规则，在自左向右扫描一个表达式时，后遇到的

33、开括号比先遇到的开括号更加期待表达式时，后遇到的开括号比先遇到的开括号更加期待有一个闭括号与之匹配。有一个闭括号与之匹配。退出/函数功能函数功能:判断表达式括号是否匹配判断表达式括号是否匹配/函数参数函数参数:char类型数组类型数组c/函数返回值函数返回值:int类型。返回类型。返回1为匹配为匹配,返回返回0为不匹配为不匹配/文件名文件名:seqmatch.c,函数名函数名:match_kouhao()/intmatch_kuohao(charc)inti=0;sequence_stacks;init(&s);while(ci!=#)switch(ci)case:退出case:case(:p

34、ush(&s,ci);break;case:if(!empty(s)&read(s)=)pop(&s);break;elsereturn0;case:if(!empty(s)&read(s)=)pop(&s);break;elsereturn0;case):if(!empty(s)&read(s)=()pop(&s);break;elsereturn0;i+;return(empty(s);/栈为空则匹配栈为空则匹配,否则不匹配否则不匹配/算法算法2.14 判断表达式括号是否匹配判断表达式括号是否匹配退出 算术表达式通常是由操作数、算术运算符和一对圆算术表达式通常是由操作数、算术运算符和一对圆

35、括号括号“（”和和“）”组合而成。其中操作数允许是程组合而成。其中操作数允许是程序语言中任意合法的变量名或常数。序语言中任意合法的变量名或常数。以下我们讨论以下我们讨论+、-、*、/四种算术运算。四种算术运算。表达式求值中的首要问题：如何确定表达式中所含运表达式求值中的首要问题：如何确定表达式中所含运算的计算次序。算的计算次序。算术运算的规则：算术运算的规则：1）先乘除、后加减）先乘除、后加减2）从左算到右）从左算到右3）先括号内、后括号外）先括号内、后括号外2.3.4栈的应用之二栈的应用之二-算术表达式求值算术表达式求值 退出按此原则，算术表达式按此原则，算术表达式 A+B*（C+D）的运算

36、次序为：的运算次序为：A+B*（C+D）而不是而不是 A+B*（C+D）1 12 23 31 12 23 3问题：问题：如何让计算机也遵守算术运算规则，正确计算表如何让计算机也遵守算术运算规则，正确计算表达式的值？达式的值？退出方法方法方法方法1 1：加括号，即对每个一运算都用一对括号将与加括号，即对每个一运算都用一对括号将与其配对的左、右操作对象括在一起，由此上面算术表其配对的左、右操作对象括在一起，由此上面算术表达式将写成（达式将写成（A+（B*（C+D）利用栈求表达式的值：利用栈求表达式的值：1）自左至右的扫描加括号的算术表达式）自左至右的扫描加括号的算术表达式2）将非右括号）将非右括号

37、“）”的符号进栈的符号进栈3）每每当当遇遇见见右右括括号号“）”，从从栈栈顶顶向向下下扫扫描描至至第第一一个个左左括括号号“（”，这这就就是是和和遇遇见见的的右右括括号号“）”配配对对的的左左括括号号“（”，该该左左括括号号“（”上上面面的的表表达达式式就就是是现现在在应应该该计计算算的的表表达达式式，从从栈栈中中弹弹出出对对应应的的左左括括号号“（”以以上上的的所所有有符符号号（含含左左括括号号”（“），计计算算相相应应表达式，并将结果压入栈中。表达式，并将结果压入栈中。退出重复重复1）2）3）即可计算出表达式的值。）即可计算出表达式的值。特特点点：方方法法简简单单明明了了，但但要要求求人人

38、们们事事先先为为要要计计算算的表达式加好括号，这既繁琐，又易出错。的表达式加好括号，这既繁琐，又易出错。方法方法方法方法2 2：重新改写表达式为后缀表达式。重新改写表达式为后缀表达式。在计算机中，表达式可以有三种不同的标识方法在计算机中，表达式可以有三种不同的标识方法设设 Exp=S1+OP+S2则称则称 OP+S1+S2 为表达式的前缀表示法为表达式的前缀表示法 称称 S1+OP+S2 为表达式的中缀表示法为表达式的中缀表示法 称称 S1+S2+OP 为表达式的后缀表示法为表达式的后缀表示法 退出可见，它以运算符所在不同位置命名的。可见，它以运算符所在不同位置命名的。例：例：中缀表达式中缀表

39、达式 后缀表达式后缀表达式 （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-/+退出结论结论结论结论:操作数之间的相对次序不变操作数之间的相对次序不变;运算符的相对次序不同运算符的相对次序不同;后后缀缀表表达达式式中中没没有有括括号号，运运算算符符排排在在其其第第二二个个操操作作数之后数之后;前前缀缀式式的的运运算算规规则则为为:连连续续出出现现的的两两个个操操作作数数和和在在它它们之前且紧靠它们的运算符构成一个最小表达式们之前且紧靠它们的运算符构成一个最小表达式;退出后缀式的运算规则为后缀式的运算规则为:

40、运运算算符符在在式式中中出出现现的的顺顺序序恰恰为为表表达达式式的的运运算算顺序顺序;每每个个运运算算符符和和在在它它之之前前出出现现且且紧紧靠靠它它的的两两个个操作数构成一个最小表达式操作数构成一个最小表达式;+-*/四则运算的计算方法：四则运算的计算方法：第一步：将中缀表达式转换成等价的后缀表达式第一步：将中缀表达式转换成等价的后缀表达式第二步：使用后缀表达式进行计算。第二步：使用后缀表达式进行计算。退出算法：利用后缀表达式求值算法：利用后缀表达式求值基本思想：基本思想：1）从左到右扫描后缀表达式，遇到操作对象进栈。）从左到右扫描后缀表达式，遇到操作对象进栈。2）遇遇到到运运算算符符，弹弹

41、出出栈栈顶顶的的元元素素，其其中中栈栈顶顶为为第第二二操操作作对对象象，次次栈栈顶顶为为第第一一操操作作对对象象，对对其其按按遇遇到到的运算符进行运算，并将结果进栈。的运算符进行运算，并将结果进栈。重复上述动作最后即可求出表达式的值。重复上述动作最后即可求出表达式的值。退出例如有中缀表达式：例如有中缀表达式：A/B-（C+D）*E其对应的后缀表达式为：其对应的后缀表达式为：AB/CD+E*-利用后缀表达式求值过程如下所示：利用后缀表达式求值过程如下所示：步骤步骤 操作数栈操作数栈 后缀表达式后缀表达式 说明说明1 AB/CD+E*-#初始栈空，初始栈空，A进栈进栈2 A AB/CD+E*-#B

42、进栈进栈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=，并将其进栈并将其进栈7 AB/CD+E*-#E进栈进栈8 E AB/CD+E*-#遇遇*，弹出栈，弹出栈顶两元做顶两元做*E=，并将并将结果进栈结果进栈9 AB/CD+E*-#遇遇-，弹出栈顶，弹出栈顶二元做二元做-=，并将结，并将结果进栈果进栈10 AB/CD+E*-#遇遇#，结束，结

43、束，栈顶就是表达栈顶就是表达式的计算结果式的计算结果退出 在实际应用中，操作数可设为实数，且两个在实际应用中，操作数可设为实数，且两个实数间用空格隔开。实数间用空格隔开。问题：后缀表达式为字符串，如何从其中分离出问题：后缀表达式为字符串，如何从其中分离出每一个操作数。每一个操作数。解决办法：解决办法：用函数用函数Readnumber(),实现将扫描到的数字字符实现将扫描到的数字字符序列转换成相应实数：序列转换成相应实数：退出float readnumber(char f,int*i)float x=0.0;int k=0;while(f*i=0&f*i=0&f*i=0&fi=0&fi=0&ei

44、=priority(ei)fj+=pop(&opst);push(&opst,ei);/*当前元进栈当前元进栈*/i+;/*处理下一元处理下一元*/while(!stackempty(&opst)fj+=pop(&opst);fj=0;退出判断是否为运算符判断是否为运算符 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-:r

45、eturn 1;case*:case/:return 2;default:return-1;两个辅助函数：两个辅助函数：本题源程序本题源程序后缀式后缀式.c.c退出习题习题:数制转换问题数制转换问题 十进制十进制n和其它进制数的转换是计算机实现计和其它进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算算的基本问题，其解决方法很多，其中一个简单算法基于下列原理法基于下列原理:n=(n div d)*d+n mod d (其中其中:div为整除运算为整除运算,mod为求余运算为求余运算)例如例如(1348)10=(2504)8，其运算过程如下：其运算过程如下：退出 n n di

46、v 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2倒倒取取余余数数(1348)10=(2504)8例用栈例用栈的知识实现任意正的的知识实现任意正的10进制整数到其它进进制整数到其它进位制的转换程序。位制的转换程序。退出算法设计题算法设计题:2、回文是指正读和反读均相同的字符序列，如、回文是指正读和反读均相同的字符序列，如“abba”和和“abdba”均是回文，但均是回文，但“good”不是回文不是回文，试写一个算法判定给定的字符向量是否为回文。，试写一个算法判定给定的字符向量是否为回文。退出 void conversion()init(s);scanf(“

47、%d”,&n);while(n)/余数进栈余数进栈 push(&s,n%8);n=n/8;while(!Stackempty(s)e=pop(&s);/余数出栈余数出栈 printf(“%d”,e);习题一解答习题一解答:退出2.4队列队列 2.4.1 队列队列 队列是一种特殊的线性表，它的特殊性在于队列队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。插入的那一的插入和删除操作分别在表的两端进行。插入的那一端称为队尾，删除的那一端称为队首。队列的插入操端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。作和删除操作也分别简称进队和出队。

48、对于一个队列：对于一个队列：k0,k1,k2,kn-1则则k0是这些结点中最先插入的结点，若要做删除操作，是这些结点中最先插入的结点，若要做删除操作，k0将首先被删除，所以说，队列是具有将首先被删除，所以说，队列是具有“先进先出先进先出”（FIFO,First In First Out）特点的线性结构。特点的线性结构。退出队列类型的描述如下：队列类型的描述如下：ADTsequence_queue数据集合数据集合K:K=k1,k2,kn,n0,K中的元素是中的元素是datatype类型类型;数据关系数据关系R:R=rr=|i=1,2,n1。操作集合操作集合:（1）voidinit(sequenc

49、e_queue sq)队列（顺序存储）初始化队列（顺序存储）初始化;（2）intempty(sequence_queuesq)判断队列（顺序存储）是否为判断队列（顺序存储）是否为空空;（3）voiddisplay(sequence_queuesq)打印队列（顺序存储）的结打印队列（顺序存储）的结点值点值;（4）datatypeget(sequence_queuesq)取得队列（顺序存储）的队首取得队列（顺序存储）的队首结点值结点值;（5）voidinsert(sequence_queue sq,datatypex)队列（顺序存储）的插入操作队列（顺序存储）的插入操作;（6）voiddele(sequence_queue sq)队列（顺序存储）的删除操作。队列（顺序存储）的删除操作。ADTsequence_queue;退出2.4.2顺序队列及其实现顺序队列及其实现 队列的顺序存储在队列的顺序存储在C语言中可以用一维数组表示，语言中可以用一维数组表示，为了标识队首和队尾，需要附设两个指针为了标识队首和队尾，需要附设两个指针front和和rear，front指示的是队列中最前面，即队首结点在指示的是队列中最前面，即队首结点在数组中元素的下标，数组中元素的下标，rear指示的是队尾结点在数组指示的是队尾结点在数组中元素的下标的下一个位置，也就是说中元素的下标的下一个位置，也就是说rear