第3章数据结构精选文档.ppt

《第3章数据结构精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章数据结构精选文档.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章数据结构本讲稿第一页，共二十四页从数据结构上看，栈和队列也是线性表，不过是从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。通过本队列也可以被称作为操作受限的线性表。通过本章的学习，应能掌握栈和队列的逻辑结构和存储章的学习，应能掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。结构，以及栈和队

2、列的基本运算以及实现算法。本讲稿第二页，共二十四页3.1.1 抽象数据类型栈的定义抽象数据类型栈的定义1栈的定义栈的定义栈栈（stack）是是一一种种只只允允许许在在一一端端进进行行插插入入和和删删除除的的线线性性表表，它它是是一一种种操操作作受受限限的的线线性性表表。在在表表中中只只允允许许进进行行插插入入和和删删除除的的一一端端称称为为栈栈顶顶（top），另另一一端端称称为为栈栈底底(bottom)。栈栈的的插插入入操操作作通通常常称称为为入入栈栈或或进进栈栈(push)，而而栈栈的的删删除除操操作作则则称称为为出出栈栈或或退退栈栈(pop)。当当栈栈中中无无数数据据元元素素时时，称称为空

3、栈。为空栈。根根据据栈栈的的定定义义可可知知，栈栈顶顶元元素素总总是是最最后后入入栈栈的的，因因而而是是最最先先出出栈栈；栈栈底底元元素素总总是是最最先先入入栈栈的的，因因而而也也是是最最后后出出栈栈。这这种种表表是是按按照照后后进进先先出出（LIFO，lastinfirstout）的的原原则则组组织织数数据据的的，因因此此，栈栈也也被被称称为为“后后进进先先出出”的的线性表。线性表。3.1 栈栈本讲稿第三页，共二十四页a0a1an-1入栈出栈栈顶 top栈底 bottom图3-3栈的示意图下下图图是是一一个个栈栈的的示示意意图图，通通常常用用指指针针top指指示示栈栈顶顶的的位位置置，用用指

4、指针针bottom指向栈底。栈顶指针指向栈底。栈顶指针top动态反映栈的当前位置。动态反映栈的当前位置。本讲稿第四页，共二十四页2、栈的类型定义栈的类型定义ADTStack 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈顶，a1 端为栈底。本讲稿第五页，共二十四页基本操作基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackE

5、mpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。ADTStack 本讲稿第六页，共二十四页3.1.2栈的表示和实现栈的表示和实现1顺序栈的数组表示顺序栈的数组表示与第二章讨论的一般的顺序存储结构的线性表一样，利用一

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

7、讲稿第八页，共二十四页二、二、栈的链式存储结构栈的链式存储结构栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top唯一确定，当top为NULL时，是一个空栈。下图给出了链栈中数据元素与栈顶指针top的关系。链栈的C语言定义为：typedef struct Stacknode Elemtype data;Struct Stacknode*next;slStacktype;本讲稿第九页，共二十四页BAtopBAto

8、pCAtop图3-6 链栈的存储结构图（a）含有两个元素A、B的栈；（b）插入元素C后的栈；（c）删除元素C、B后的栈（a）（b）（c）本讲稿第十页，共二十四页3.2栈的应用举例栈的应用举例例一、例一、数制转换数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)d+Nmodd(其中：其中：div为整除运算，为整除运算，mod为求余运算）为求余运算）例如：（例如：（1348)10=(2504)8，其运算过程如下：，其运算过程如下：NNdiv8Nmod8134816841682102125202假设现要编制一个满足下列要

9、求的程序：对于输入的任意一个非负十进制整数，打假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。即为与输入对应的八进制数

10、。本讲稿第十一页，共二十四页voidconversion()/对于输入的任意一个非负十进制整数，打印输出对于输入的任意一个非负十进制整数，打印输出/与其等值的八进制数与其等值的八进制数InitStack(S);/构造空栈构造空栈scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列这是利用栈的后进先出特性的最简单的例子。在这个例子中，栈操作的序列是直线式的，即先一味地入栈，然后一味地出栈。也许，有的同学

11、会提出疑是直线式的，即先一味地入栈，然后一味地出栈。也许，有的同学会提出疑问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入问：用数组直接实现不也很简单吗？仔细分析上述算法不难看出，栈的引入简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用简化了程序设计的问题，划分了不同的关注层次，使思考范围缩小了。而用数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。数组不仅掩盖了问题的本质，还要分散精力去考虑数组下标增减等细节问题。本讲稿第十二页，共二十四页例二、例二、括号匹配的检验括号匹配的检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺假设

12、表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即（）或（序随意，即（）或（）等为正确的格式，）等为正确的格式，（）或（）或（）或）或()均为不正确的格式。均为不正确的格式。检验括号是否匹配的方法可用检验括号是否匹配的方法可用“期待的急迫程度期待的急迫程度”这个概念来描这个概念来描述。述。例如考虑下列括号序列：例如考虑下列括号序列：()12345678本讲稿第十三页，共二十四页分析可能出现的不匹配的情况:1.到来的右括弧到来的右括弧非是所非是所“期待期待”的的;2.到来的是到来的是“不速之客不速之客”;3.直到结束，也直到结束，也没有到来所没有到来所“期待期待”的。的。本讲稿第十四

13、页，共二十四页statusmatching(string&exp)/检验表达式中所含括弧是否正确嵌套，若是，则返回检验表达式中所含括弧是否正确嵌套，若是，则返回/OK，否则返回，否则返回ERRORintstate=1;while(i=length(exp)&state)swithofexpicase左括弧左括弧:Push(S,expi);i+;break;case):if(NOTStackEmpty(S)&GetTop(S)=()Pop(S,e);i+;elsestate=0break;if(state&StackEmpty(S)returnOKelsereturnERROR;本讲稿第十五页，

14、共二十四页例三、行编辑程序问题例三、行编辑程序问题一个简单的行编辑程序的功能是：接受用户从终端输入一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。的程序或数据，并存入用户的数据区。每接受一个字符即存入用户数据区每接受一个字符即存入用户数据区”不恰当。不恰当。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。现有误时可以及时更正。本讲稿第十六页，共二十四页例如，可用一个

15、例如，可用一个退格符退格符“#”表示前一个字符无效；可用一个表示前一个字符无效；可用一个退行符退行符“”，表示当前行中的字符均无效。，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：例如，假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);本讲稿第十七页，共二十四页voidLineEdit()/利用字符栈利用字符栈S，从终端接收一行并传送至调用过程，从终端接收一行并传送至调用过程/的数据区。的数据区。InitStack(S);/构造空栈构

16、造空栈Sch=getchar();/从终端接收第一个字符从终端接收第一个字符while(ch!=EOF)/EOF为全文结束符为全文结束符while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c);break;/仅当栈非空时退栈仅当栈非空时退栈case:ClearStack(S);break;/重置重置S为空栈为空栈default:Push(S,ch);break;/有效字符进栈，未考虑栈满情形有效字符进栈，未考虑栈满情形ch=getchar();/从终端接收下一个字符从终端接收下一个字符将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程

17、的数据区；ClearStack(S);/重置重置S为空栈为空栈if(ch!=EOF)ch=getchar();DestroyStack(S);本讲稿第十八页，共二十四页例四、例四、迷宫求解迷宫求解求迷宫中从入口到出口的所有路径是一个经典的程序设计问求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是题。由于计算机解迷宫时，通常用的是“穷举求解穷举求解”的方法，的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有前走；否则沿原路退回，换一个方向再继续探

18、索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然路退回，显然需要用一个后进先出的结构来保存从入口到当需要用一个后进先出的结构来保存从入口到当前位置的路径前位置的路径。因此，在求迷宫通路的算法中应用。因此，在求迷宫通路的算法中应用“栈栈”也也就是自然而然的事了。就是自然而然的事了。本讲稿第十九页，共二十四页假设迷宫如下图所示假设迷宫如下图所示:本讲稿第二十页，共二十四页假设“当前位置当前位置”指的是“在搜索过程中某一时刻所在图中某在搜索过程中某一时刻所在图中某个方块位置个方块位置”，则求迷宫中一条路径的算法的基本思想

19、是：若当，则求迷宫中一条路径的算法的基本思想是：若当前位置前位置可通可通，则纳入，则纳入当前路径当前路径，并继续朝，并继续朝“下一位置下一位置”探探索，即切换索，即切换“下一位置下一位置”为为“当前位置当前位置”，如此重复直至到达出，如此重复直至到达出口；若当前位置口；若当前位置“不可通不可通”，则应顺着，则应顺着“来向来向”退回到退回到“前一通前一通道块道块”，然后朝着除，然后朝着除“来向来向”之外的其他方向继续探索；若该通之外的其他方向继续探索；若该通道块的四周四个方块均道块的四周四个方块均“不可通不可通”，则应从，则应从“当前路径当前路径”上删除上删除该通道块。所谓该通道块。所谓“下一位

20、置下一位置”指的是指的是“当前位置当前位置”四周四四周四个方向（东、南、西、北）上相邻的方块。假设以栈个方向（东、南、西、北）上相邻的方块。假设以栈S记记录录“当前路径当前路径”，则栈顶中存放的是，则栈顶中存放的是“当前路径上最后一个通当前路径上最后一个通道块道块”。由此，。由此，“纳入路径纳入路径”的操作即为的操作即为“当前位置入栈当前位置入栈”；“从当前路径上删除前一通道块从当前路径上删除前一通道块”的操作即为的操作即为“出栈出栈”。本讲稿第二十一页，共二十四页求迷宫中一条从入口到出口的路径的算法可简单描述如下：设定当前位置的初值为入口位置；do若若当前位置可通，则则将当前位置插入栈顶；/

21、纳入路径若若该位置是出口位置，则则结束；/求得路径存放在栈中否则否则切换当前位置的东邻方块为新的当前位置；否则否则若若栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通，则则 删去栈顶位置；/从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置，直至直至找到一个可通的相邻块或出栈至栈空；while(栈不空）；栈不空）；本讲稿第二十二页，共二十四页在此，尚需说明一点的是，所谓当前位置可通可通，指的是未曾走未曾走到过的通道块到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。本讲稿第二十三页，共二十四页本讲稿第二十四页，共二十四页