数据结构-第三章栈和队列.ppt

第三章栈和队列教学目的通过本章的学习，要求掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现，了解栈和队的各种应用。本章主要介绍以下内容：栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例重点：栈和队列的定义、特征；顺序栈、链栈的描述及基本操作实现算法；循环队列和链队列的基本操作实现算法。难点：栈满、栈空的条件及描述方法；队满和队空的描述方法；循环队列上的插入、删除操作。栈（stack）栈的定义栈的类型定义栈的存储方式栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。a1ana2……栈的示意图栈顶栈底进栈出栈进行插入和删除的一端是浮动端，被称为栈顶固定端一端被称为栈底假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）LastInFirstOut。栈的类型定义ADTStack{数据对象：D={ai|aiElemSeti=1,2,..,nn≥0}数据关系：R1={ai,ai+1|ai,ai+1ElemSet,i=1,2,..,n-1≥0}{约定an端为栈顶，a1端为栈底}基本操作：{结构初始化}InitStack(&S)操作结果：构造一个空栈S{销毁结构}DetroyStack(&S)初始条件：栈S已经存在操作结果：销毁栈S{引用型操作}StackEmpty(S)//判断S是否为空栈，若为空返回True，否则返回FalseStackLength(S)//得到栈S的元素个数，即栈的长度GetTop(S，&e)//得到S的栈顶元素，并将之放入变量e中StackTraverse(S,visit())//从栈底到栈顶遍历栈S，对每个元素调用visit(){加工型操作}ClearStack(&S)//清空栈SPush(&S,e)//向栈中插入元素e为新的栈顶元素Pop(&S,&e)//删除栈S的栈顶元素，并用e返回值栈的存储方法栈有两种存储表示方法:顺序存储和链式存储由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。通常由一个一维数组和一个记录栈顶元素位置的变量组成。当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值top=-1。在刚才基础上执行Push(S,‘A’)后得到这种状态又有三个元素B、C、D先后入栈，此时栈顶元素的下标值top=3。栈已满。在刚才状态下，执行两次Pop(S,x)运算后得到Top--1D01230123Top-A0123Top-ABC0123Top-AB顺序存储结构顺序栈的C#语言描述如下：publicclassSeqStack{privateintmaxSize;//顺序栈的容量privatechar[]data;//数组，用于存储顺序栈的数据元素，这里存储的只有字符型privateinttop;//指示顺序栈的栈顶}maxSize为栈中元素的最大容量。data域:为一个一维数组，用于存储栈中元素。top域:栈顶指针。取值范围为0～MaxSize-1。top=-1表示栈空，top=MaxSize-1表示栈满。类的实现publicclassSeqStack{privateintmaxSize;//顺序栈的容量privatechar[]data;//数组，用于存储顺序栈的数据元素，这里存储的只有字符型privateinttop;//指示顺序栈的栈顶publicintMaxSize//最大容量属性{get{returnmaxSize;}set{maxSize=value;}}publicintTop//栈顶属性{get{returntop;}}}使用SeqLists=newSeqList()生成一个SeqList类的对象实例栈底元素为栈顶指针为进栈时需将s.top加1，退栈时需将s.top减1s.top0表示空栈，s.top=MaxSize-1表示栈满s.data[0]s.top基本操作1.初始化栈S//构造函数publicSeqStack(intsize){data=newchar[size];maxSize=size;top=-1;}2.求栈的长度publicintGetLength(){returntop+1;}3.清空顺序栈publicvoidClear(){top=-1;}4、判栈空publicboolIsEmpty(){if(top==-1)returntrue;elsereturnfalse;}5、入栈publicvoidPush(charitem){if(top==maxSize-1)//若栈已满，则不能再做入栈操作{Console.WriteLine(TheStackisfull!);return;}top++;data[top]=item;}6、出栈publiccharPop(){if(IsEmpty())//若栈为空栈，无法做出栈操作{Console.WriteLine(TheStackisempty!);return'';}charitem=data[top];top--;returnitem;}7、取栈顶元素publiccharGetTop(){if(IsEmpty()){Console.WriteLine(TheStackisemptye!);return'';}returndata[top];}链式存储结构栈的链式存储结构称为链栈，它是运算是受限的单链表，可插入和删除操作仅限制在表头位置上进行.链栈的类型说明如下：publicclassStackNode{privateintdata;//数据域privateStackNodenext;//指针域}topABC栈顶栈底^datanext^(a)top-next=NULL表示空栈(b)A，B两个元素顺序入栈(c)B元素出栈topA^top^topAB链栈的几种状态栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。数值转换括号匹配检验数值转换十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。5822920214170231212101十进制58的二进制表示为：111010publicvoidDToB(intdecVal){SeqStacks=newSeqStack(50);while(decVal!=0){s.Push(decVal%2);decVal/=2;}while(!s.IsEmpty()){Console.Write(s.Pop().ToString());}Console.WriteLine();Console.ReadLine();}检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。检验括号是否匹配的方法可以用“期待的急迫程度”这个概念来描述。{[()()]},[()([])]是正确的格式，而[(]),{([]})是错误的格式{([][])}12345678{([[[(])([])){([])检验出错的情况（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。算法基本思想凡出现左括号，进栈凡出现右括号，首先检查栈是否是空若栈空，表明右括号多了否则和栈顶元素比较，若相等，则左括号出栈否则不匹配表达式检查结束时，若栈空，则匹配正确否则表明左括号多了迷宫求解.算法思想若当前位置“可通”，则纳入“路径”，继续前进若当前位置“不可通”，则后退，换向探索若四周皆“不可通”，则从路径中删除汉诺塔问题：有三根柱子分别叫A柱、B柱、C柱。现假设有N个圆盘（都是按从大到小依次放入柱中的）已经放在了A柱上，我们的任务就是把这N个圆盘移动到C柱。但移动的过程，必须遵守大盘永远在小盘的下面这一个原则。栈与递归递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多问题的算法设计。在计算机内部，通过栈来实现递归算法。所以递归是栈的一个实际应用。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需要完成三件事：将所有的实在参数、返回地址等信息传递给被调用函数保存为被调用函数的局部变量分配存储存储区将控制转移到被调用函数的入口从被调用函数返回调用函数之前，应完成：保存被调用函数的计算结果释放被调用函数的数据区依照被调用函数保存的返回地址将控制转移到调用函数多个函数嵌套调用的规则是：后调用先返回内存管理实行“栈式管理”递归函数斐波纳茨函数：1，1，2，3，5，8，13……求n的阶乘的递归函数算法:1n=1fib(n)=1n=2fib(n-1)+fib(n-2)n2longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}……if(n==0)f=1;elsef=n*fact(n-1);returnf;……函数fact(4)……if(n==0)f=1;elsef=n*fact(n-1);returnf;……调用fact(3)……if(n==0)f=1;elsef=n*fact(n-1);returnf;……调用fact(2)……if(n==0)f=1;elsef=n*fact(n-1);returnf;……调用fact(1)……if(n==0)f=1;elsef=n*fact(n-1);returnf;……调用fact(0)函数fact(3)函数fact(2)函数fact(1)函数fact(0)函数fact(0)的调用返回一个1值返回1函数fact(1)中f=1*1返回值1返回1函数fact(2)中f=2*1返回值2返回2函数fact(3)中f=3*2返回值6返回6递归函数：直接调用自身或通过一系列的调用语句间接地调用自己的函数调用fact(3)调用fact(4)longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}调用fact(4)fact(4)调用fact(3)fact(3)调用fact(2)fact(2)调用fact(1)fact(1)调用fact(0)调用fact(2)调用fact(1)调用fact(0)4r13r22r31r40r5汉诺塔问题如果汉诺塔问题中盘子的个数为64，而64个盘的移动次数是：18，446，744，073，709，551，615这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但