数据结构ppt课件C++版=.ppt

《数据结构ppt课件C++版=.ppt》由会员分享，可在线阅读，更多相关《数据结构ppt课件C++版=.ppt（93页珍藏版）》请在三一办公上搜索。

1、2022/12/26,mayan,第三章 栈和队列,栈栈的应用队列队列的应用优先级队列,定义：,栈,限定只能在表的一端进行插入和删除运算的线性表。,递归函数的实现 在递归函数的执行中， 需多次自己调用自己，递归函数是如何执行的？先看一般函数的调用机制如何实现的。,A( )B( );,C( ),B( )C( );,函数调用顺序 A B C,函数返回顺序 C B A,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用和返回的,n=3 阶乘函数fact(n)的执行过程,Main( ) int n=3,y;L y= fact(n);,L 3,L1 1,L1 2,1,n*f

2、act (n-1),n*fact (n-1),fact(n),返回地址 实参,递归调用中 栈的变化,将十进制整数转换成二至九之间的任一进制数输出,将一个十进制数4327转换成八进制数(10347)8：,Y,X,Z,2022/12/26,mayan,第三章 栈和队列 -栈的定义,栈和队列称为运算受限的线性表。栈（stack）是指只允许在表的末端进行插入和删除的线性表。栈又叫做后进先出（LIFO）的线性表。,栈的基本概念,栈是一种“特殊”的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。栈顶：允许进行插入和删除的这一端。栈底：反之为栈底。栈顶元素：处于栈顶位置的数据元素称为。栈顶元素的位

3、置由栈顶指针变量记录；空栈:当栈中不含任何数据元素时称为,2022/12/26,mayan,第三章 栈和队列 -顺序栈,基于数组的存储表示实现的栈称为顺序栈。当前栈顶位置由数组下标指针top指示，即top指示最后加入的元素的存储位置，当top=-1时栈空，当top=maxSize-1时栈满。顺序栈的类定义,2022/12/26,mayan,第三章 栈和队列 -顺序栈的类定义,template class SeqStack /顺序栈类定义private: T *elements;/栈元素存放数组 int top;/栈顶指针 int maxSize; /栈最大容量public: SeqStack(

4、int sz =50);/构造函数 SeqStack() delete elements; /析构函数,2022/12/26,mayan,第三章 栈和队列 -顺序栈的类定义,void Push(const T,2022/12/26,mayan,第三章 栈和队列 -顺序栈的函数实现,/顺序栈的构造函数template SeqStack:SeqStack(int sz):top(-1),maxSize(sz) elements=new TmaxSize;,2022/12/26,mayan,第三章 栈和队列 -顺序栈的函数实现,/若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理template v

5、oid SeqStack:Push(const T /栈顶指针先加1, 再进栈,2022/12/26,mayan,第三章 栈和队列 -顺序栈的函数实现,/函数退出栈顶元素并返回栈顶元素的值template bool SeqStack:Pop(T /退栈成功,2022/12/26,mayan,第三章 栈和队列 -顺序栈的函数实现,/若栈不空则函数返回该栈栈顶元素template bool Seqstack:getTop(T,2022/12/26,mayan,第三章 栈和队列 -双栈共享一个栈空间,为了既能减少由于栈满而引起的溢出，又能有效的利用存储空间，提出一种双栈共享一个栈空间的策略。,202

6、2/12/26,mayan,第三章 栈和队列 -双栈共享一个栈空间,两个栈共享一个数组空间VmaxSize设立栈顶指针数组t2和栈底指针数组b2ti和bi分别指示第i个栈的栈顶与栈底初始 t0 = b0 = -1, t1 = b1 = maxSize 满条件：t0+1 = t1 /栈顶指针相遇栈空条件：t0 = b0或t1 = b1 /退到栈底,2022/12/26,mayan,第三章 栈和队列 -双栈共享一个栈空间,/双栈的插入算法bool push(DualStack,2022/12/26,mayan,第三章 栈和队列 -双栈共享一个栈空间,/双栈的删除算法bool Pop(DualSta

7、ck,2022/12/26,mayan,第三章 栈和队列 -链式栈,链式栈是栈的链接存储表示。链式栈的栈顶在链表的表头。因此，新结点的插入和栈顶结点的删除都在链表的表头，即栈顶进行。,2022/12/26,mayan,第三章 栈和队列 -链式栈的类定义,template class LinkedStack : public Stack /链式栈类定义 private: LinkNode *top;/栈顶指针public: LinkedStack() : top(NULL) /构造函数,2022/12/26,mayan,第三章 栈和队列 -链式栈的类定义,LinkedStack() makeEm

8、pty(); /析构函数 void Push(const T,2022/12/26,mayan,第三章 栈和队列 -链式栈的函数实现,/逐次删去链式栈中的元素直至栈顶指针为空。template LinkedStack:makeEmpty() LinkNode *p;while (top != NULL)/逐个结点释放 p = top; top = top-link; delete p; ,2022/12/26,mayan,第三章 栈和队列 -链式栈的函数实现,/将元素值x插入到链式栈的栈顶,即链头。template void LinkedStack:Push(const T/创建失败退出,20

9、22/12/26,mayan,第三章 栈和队列 -链式栈的函数实现,/删除栈顶结点, 返回被删栈顶元素的值。template bool LinkedStack:Pop(T,2022/12/26,mayan,第三章 栈和队列 -链式栈的函数实现,/返回栈顶元素的值template bool LinkedStack:getTop(T,2022/12/26,mayan,第三章 栈和队列 -链式栈的函数实现,/返回栈中元素个数template int LinkedStack:getSize const LinkNode *p=top; int k=0; while(top!=NULL)top=top-

10、link; k+; return k;,2022/12/26,mayan,第三章 栈和队列 -链式栈的函数实现,/输出栈中元素template ostream,2022/12/26,mayan,第三章 栈和队列,例1：一个栈的入栈序列是a、b、c、d、e，则栈的不可能的输出序列是（C）。Aedcba Bdecba Cdceab Dabcde例2：对于一个栈，给出输入项a、b、c。如果输入序列由a、b、c组成，试给出全部可能的输出序列。abc acb bac bca cba,2022/12/26,mayan,第三章 栈和队列 -栈的应用之括号匹配,观察：每个右括号将与最近遇到的那个未匹配的左括号

11、相匹配。(a (b+c)-d) (a+b) )(,(,(,(,没有与右括号匹配的左括号,没有与左括号匹配的右括号,(,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,一个表达式由操作数（亦称运算对象）、操作符（亦称运算符）和分界符组成。算术表达式有三种表示：中缀(infix)表示 ，如 A+B；前缀(prefix)表示 ，如 +AB；后缀(postfix)表示 ，如 AB+；,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,表达式示例中缀表达式 A+B*(C-D)-E/F后缀表达式 ABCD-*+EF/-前缀表达式 -+A*B-CD/EF

12、表达式中相邻两个操作符的计算次序为：优先级高的先计算；优先级相同的自左向右计算；当使用括号时从最内层括号开始计算。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,应用后缀表示计算表达式的值说明：这里只考虑双目运算的情形。从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。计算例 A B C D + E F /,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,通过后缀表示计算表达式值的过程：顺序扫描表达式的每一项，如果该项是操作数，则将其入栈；如果该

13、项是操作符，则连续从栈中退出两个操作数X和Y，形成运算指令XY，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,A B C D + E F /,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,A B C D + E F /,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,中缀表示转后缀表示先对中缀表达式按运算优先次序加上括号；再把操作符后移到右括号的后面并以就近移动为原则；最后将所有括号消去。例：中缀表示(A+B)*D-

14、E/(F+A*D)+C，转换为后缀表示,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,中缀表示转前缀表示先对中缀表达式按运算优先次序通统加上括号再把操作符前移到左括号前并以就近移动为原则最后将所有括号消去。 例：中缀表示 (A+B)*D-E/(F+A*D)+C，转换为前缀表示,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,利用栈将中缀表示转换为后缀表示使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。操作符优先级为了实现这种转换，需要考虑各操作符的优先级。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求

15、值,各个算术操作符的优先级isp叫做栈内(in stack priority)优先数icp叫做栈外(in coming priority)优先数。操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,中缀表达式转换为后缀表达式的算法操作符栈初始化，将结束符#进栈。然后读入中缀表达式字符流的首字符ch。重复执行以下步骤，直到ch = #，同时栈顶的操作符也是#，停止循环。若ch是操作数直接输出，读入下一个字符ch。若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：

16、,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,若 icp(ch) isp(op)，令ch进栈，读入下一个字符ch。若 icp(ch) isp(op)，退栈并输出。若 icp(ch) = isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。算法结束，输出序列即为所需的后缀表达式。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,例：给定中缀表达式A+B*(C-D)-E/F，按上述算法转换为后缀表达式。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之表达式求值,A+B*(C-D)-E/F,2022/12/

17、26,mayan,第三章 栈和队列 -栈的应用之表达式求值,A+B*(C-D)-E/F,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,递归的定义 若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,定义是递归的例如：求解阶乘函数的递归算法long Factorial(long n) if (n = 0) return 1; el

18、se return n*Factorial(n-1);,分解过程,求值过程,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,数据结构是递归的例如，单链表结构一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,搜索链表最后一个结点并打印其数值template void Print(ListNode *f) if (f -link = NULL) cout data link);,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,问

19、题的解法是递归的例如汉诺塔(Tower of Hanoi)问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,解决方法：如果 n = 1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步：用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上：将 A 柱上最后一个盘子直接移到 C 柱上；用

20、 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 C 柱上。,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,解决汉诺塔问题的算法#include void Hanoi (int n, char A, char B, char C) if (n = 1) cout move A to C endl; else Hanoi(n-1, A, C, B); cout move A to C endl; Hanoi(n-1, B, A, C); ,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,递归过程改为非递归过程递归过程简洁、易编、易懂递归

21、过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,Ackerman函数定义如下：学生课下学习部分,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,递归算法：unsigned akm(unsigned m, unsigned n)if(m=0) return n+1; /m=0else if(n=0) return akm(m-1,1); /m0,n=0else return akm(m-1,akm(m,n-1);/m

22、0,n0,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,非递归算法：#include#include ”stack.h”#define maxSize 3500;unsigned akm(unsigned m,unsigned n)struct nodeunsigned vm,vn;stack st(maxSize);node w;unsigned v;w.vm=m;w.vn=n;st.Push(w);,2022/12/26,mayan,第三章 栈和队列 -栈的应用之栈与递归,dowhile(st.GetTop().vm0)while(st.GetTop().vn0

23、)w.vn-;st.Push(w);w=st.GetTop();st.Pop(); w.vm-;w.vn=1;st.Push(w); w=st.GetTop(); st.Pop();v=w.vn+;if(st.IsEmpty()=0) w=st.GetTop();st.Pop();w.vm-;w.vn=v;st.Push(w);while(st.IsEmpty()=0);return v;,2022/12/26,mayan,第三章 栈和队列 -队列的定义,队列（Queue）是只允许在表的一端插入，在另一端删除的线性表。队列又叫先进先出（FIFO）的线性表。,2022/12/26,mayan,第

24、三章 栈和队列 -队列的类定义,template class Queue public: Queue() ; /构造函数 Queue() ; /析构函数void EnQueue(T,2022/12/26,mayan,第三章 栈和队列 -循环队列,顺序队列的概念 队列的基于数组的存储表示称为顺序队列。利用一个一维数组elementsmaxSize作为队列元素的存储结构。设置两个指针(下标变量)front和rear，分别指示对头和队尾位置。初始化时令front=rear=0。队尾指针rear指示了实际队尾位置的后一位置，队头指针front则指示真正队头元素所在位置。当front=rear，队列为空

25、；当rear=maxSize，队列满。,2022/12/26,mayan,第三章 栈和队列 -循环队列,循环队列的概念解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1: front = (front+1) % maxSize;队尾指针进1: rear = (rear+1) % maxSize;,2022/12/26,mayan,第三章 栈和队列 -循环队列,队列初始化：front = rear = 0;队空条件：front = rear;队

26、满条件：(rear+1) % maxSize = front;注意，在循环队列中，最多只能存放maxSize-1个元素。,2022/12/26,mayan,第三章 栈和队列 -循环队列的类定义,template class SeqQueue /队列类定义protected: int rear, front; /队尾与队头指针 T *elements; /队列存放数组 int maxSize; /队列最大容量,2022/12/26,mayan,第三章 栈和队列 -循环队列的类定义,ublic: SeqQueue(int sz = 10); /构造函数 SeqQueue() delete elem

27、ents; /析构函数 bool EnQueue(const T /队列做空,2022/12/26,mayan,第三章 栈和队列 -循环队列的类定义,bool IsEmpty() const return front = rear; /判断队空 bool IsFull() const /判断队满 return (rear+1)% maxSize = front); int getSize() const /队中元素个数 return (rear-front+maxSize) % maxSize; void display() const;/输出队中元素;,2022/12/26,mayan,第三

28、章 栈和队列 -循环队列的函数实现,/构造函数template SeqQueue:SeqQueue(int sz) : front(0), rear(0), maxSize(sz) elements = new TmaxSize; ,2022/12/26,mayan,第三章 栈和队列 -循环队列的函数实现,/若队列不满, 则将x插入到该队列队尾, 否则返回 template bool SeqQueue:EnQueue(const T,2022/12/26,mayan,第三章 栈和队列 -循环队列的函数实现,/若队列不空则函数退队头元素并返回其值template bool SeqQueue:De

29、Queue() int x; if (IsEmpty() = true) return false; x = elementsfront; /先取队头 front = (front+1) % maxSize; /再队头指针加一 return true;,2022/12/26,mayan,第三章 栈和队列 -循环队列的函数实现,/若队列不空则函数返回该队列队头元素的值template bool SeqQueue:getFront() const int x; if (IsEmpty() = true) return false; /队列空 x = elementsfront; /返回队头元素 r

30、eturn true;,2022/12/26,mayan,第三章 栈和队列 -循环队列的函数实现,/输出队列中的元素template void SeqQueue:display() constint i;if (IsEmpty() = true) return ; /队列空cout 队列中的元素为： endl;for(i = front;i!= rear;i = (i+1) % maxSize)cout elementsi ;cout endl;,2022/12/26,mayan,第三章 栈和队列 -链式队列,链式队列是基于单链表的一种存储表示。队列的队头指针指向单链表的第一个结点，队尾指针指

31、向单链表的最后一个结点。队空条件为 front = NULL;,2022/12/26,mayan,第三章 栈和队列 -链式队列的类定义,#include #include “LinkedList.h”#include “Queue.h”template class LinkedQueue :public Queueprivate: LinkNode *front, *rear; /队头、队尾指针public: LinkedQueue() : rear(NULL), front(NULL) LinkedQueue()makeEmpty();,2022/12/26,mayan,第三章 栈和队列 -

32、链式队列的类定义,bool EnQueue(const T,2022/12/26,mayan,第三章 栈和队列 -链式队列的函数实现,/置空队列template bool LinkedQueue:makeEmpty () LinkNode *p;while(front!=NULL)p=front;front=front-link;delete p;,2022/12/26,mayan,第三章 栈和队列 -链式队列的函数实现,template /将新元素x插入到队列的队尾bool LinkedQueue:EnQueue(const T,2022/12/26,mayan,第三章 栈和队列 -链式队列

33、的函数实现,/如果队列不空，将队头结点从链式队列中删去 template bool LinkedQueue:DeQueue(T,2022/12/26,mayan,第三章 栈和队列 -链式队列的函数实现,/若队列不空，则函数返回队头元素的值 template bool LinkedQueue:GetFront(T,2022/12/26,mayan,第三章 栈和队列 -链式队列的函数实现,/求队列元素个数template int LinkedQueue:getSize() constLinkNode *p=front;int k=0;while(p!=NULL)p=p-link;k+;return

34、 k;,2022/12/26,mayan,第三章 栈和队列 -链式队列的函数实现,/输出队列中的元素template ostream,2022/12/26,mayan,第三章 栈和队列 -队列的应用之打印杨辉三角形,将二项式 展开，其系数构成杨辉三角形。,2022/12/26,mayan,第三章 栈和队列 -队列的应用之打印杨辉三角形,2022/12/26,mayan,第三章 栈和队列 -队列的应用之打印杨辉三角形,#include #include #include queue.hvoid YANGVI(int n) Queue q(n+2); /队列初始化int i=1,j,s=k=0,t

35、,u;q.EnQueue(i); q.EnQueue(i);,2022/12/26,mayan,第三章 栈和队列 -队列的应用之打印杨辉三角形,for (int i = 1; i = n; i+) /逐行计算 cout endl; q.EnQueue(k); for (int j = 1; j = i+2; j+) /下一行 q.DeQueue(t); u=s+t; q.EnQueue(u); s = t; if (j!= i+2) cout s ; /第j+2个是0 ,2022/12/26,mayan,第三章 栈和队列 -优先级队列的概念,每次从队列中取出的是具有最高优先权的元素，这种队列就

36、是优先级队列（Priority Queue）。最小优先级队列（min Priority Queue）：数字越小优先权越高最大优先级队列（max Priority Queue）：数字越大优先权越高优先权相同时先来先服务。,2022/12/26,mayan,第三章 栈和队列 -优先级队列的存储表示与实现,优先级队列的数组存储表示#include #include #include template class PQueue private: T *pqelements;/存放数组 int count; /队列元素计数 int maxSize; /最大元素个数 void adjust(); /调整,

37、2022/12/26,mayan,第三章 栈和队列 -优先级队列的存储表示与实现,public: PQueue(int sz = 50); PQueue() delete pqelements; bool Insert(const T,2022/12/26,mayan,第三章 栈和队列 -优先级队列的存储表示与实现,template /构造函数PQueue:PQueue(int sz) :maxSize(sz),count(0) pqelements = new TmaxSize; assert (pqelements != NULL); template /插入bool PQueue:Ins

38、ert(const T,2022/12/26,mayan,第三章 栈和队列 -优先级队列的存储表示与实现,/将队尾元素按其优先权大小调整到适当位置，/保持所有元素按优先权从小到大有序template void PQueue:adjust() T temp = pqelementscount-1; for (int j = count-2; j = 0; j-) if (pqelementsj = temp) break; else pqelementsj+1 = pqelementsj; pqelementsj+1 = temp;,2022/12/26,mayan,第三章 栈和队列 -优先级队

39、列的存储表示与实现,/若优先级队列不空则函数返回队列具最大优先权/（值最小）元素的值，同时将该元素删除。template bool PQueue:RemoveMin(T,2022/12/26,mayan,第三章 栈和队列 -优先级队列的存储表示与实现,template bool PQueue:GetFront (T,2022/12/26,mayan,第三章 栈和队列,习题1试编写一个算法，以判断一个字符串是否是回文。所谓回文，是指从前向后顺序读都一样的不含空白字符的串。例如did，pop，abcba。2编写一个算法，将一个非负的十进制整数N转换为另一个基为B的B进制数。,2022/12/26,mayan,第三章 栈和队列,实验实验目的：掌握栈的基本操作算法实现及栈的应用方法。实验内容：问题描述：编写一个程序，检查某个程序中的花括号、方括号和圆括号是否配对（利用栈实现）。,