第3章数据结构优秀PPT.ppt

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

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

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

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

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

5、清为空栈。StackEmpty(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 现在学习的是第6页，共24页3.1.2栈的表示和实现栈的表示和实现1顺序栈的数组表示顺序栈的数组表示与第二章讨论的一般的顺序存

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

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

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

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

10、栈序列打印输出的即为与输入对应的八进制数。数。现在学习的是第11页，共24页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页，共24页例二、例二、括号匹配的检验括号匹配的检验假设表达

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

13、，也没有到来所没有到来所“期待期待”的。的。现在学习的是第14页，共24页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)re

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

15、发现有误时可以及时更正。现在学习的是第16页，共24页例如，可用一个例如，可用一个退格符退格符“#”表示前一个字符无效；可用一个表示前一个字符无效；可用一个退行符退行符“”，表示当前行中的字符均无效。，表示当前行中的字符均无效。例如，假设从终端接受了这样两行字符：例如，假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行：while(*s)putchar(*s+);现在学习的是第17页，共24页voidLineEdit()/利用字符栈利用字符栈S，从终端接收一行并传送至调用过程，从终端接收一行并传

16、送至调用过程/的数据区。的数据区。InitStack(S);/构造空栈构造空栈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页，共24页例四、例四、迷宫求解迷宫求解求迷宫中从入口到出口的所有路径是一个经典的程序设求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是计问题。由于计算机解迷宫时，通常用的是“穷举求解穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方

18、向再走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然证在任何位置上都能沿原路退回，显然需要用一个后进先需要用一个后进先出的结构来保存从入口到当前位置的路径出的结构来保存从入口到当前位置的路径。因此，在求迷。因此，在求迷宫通路的算法中应用宫通路的算法中应用“栈栈”也就是自然而然的事了。也就是自然而然的事了。现在学习的是第19页，共24页假设迷宫如下图所示假设迷宫如下图所示:现在学习的是第20页，共24页假设“当前位置当前位置”指的是“在搜索过程中某一时刻所在图在搜索过

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

20、，则应从，则应从“当前路径当前路径”上删除上删除该通道块。所谓该通道块。所谓“下一位置下一位置”指的是指的是“当前位置当前位置”四周四四周四个方向（东、南、西、北）上相邻的方块。假设以栈个方向（东、南、西、北）上相邻的方块。假设以栈S记记录录“当前路径当前路径”，则栈顶中存放的是，则栈顶中存放的是“当前路径上最后当前路径上最后一个通道块一个通道块”。由此，。由此，“纳入路径纳入路径”的操作即为的操作即为“当前当前位置入栈位置入栈”；“从当前路径上删除前一通道块从当前路径上删除前一通道块”的操作的操作即为即为“出栈出栈”。现在学习的是第21页，共24页求迷宫中一条从入口到出口的路径的算法可简单描

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