第栈和队列ppt课件

1、 Department of Computer Science & Technology, Nanjing University fall 2009DATA STRUCTURES第第3 3章章 栈和队列栈和队列 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES构造构造 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES3.1 栈栈 ( St

2、ack )a0an-1an-2topbottom Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Stack public: Stack ( int sz = 10 ); /构造函数构造函数 void Push (Type x); /进栈进栈 int Pop (Type& x); /出栈出栈 int GetTop (Type& x); /取栈顶元素取栈顶元素 void MakeEmpty ( ); /置空栈置空栈 int I

3、sEmpty ( ) const; /判栈空否判栈空否 int IsFull ( ) const; /判栈满否判栈满否 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES栈的两种物理存储方式栈的两种物理存储方式n栈的数组存储表示栈的数组存储表示 顺序栈顺序栈n栈的链接存储表示栈的链接存储表示 链式栈链式栈 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTU

4、REStemplate class Stack private: int top; /栈顶指针栈顶指针 Type *elements; /栈元素数组栈元素数组 int maxSize; /栈最大容量栈最大容量 void overflowProcess( ); /栈的溢出处置栈的溢出处置0 1 2 3 4 5 6 7 8 9 maxSize-1top (栈空栈空) 即即top=-1elements栈的数组存储表示栈的数组存储表示 顺序栈顺序栈top (栈满栈满) Department of Computer Science & Technology, Nanjing University

5、 fallDATA STRUCTURES public: Stack (int sz = 10); /构造函数构造函数 Stack ( ) delete elements; void Push (Type x); /进栈进栈 int Pop (Type& x); /出栈出栈 Type GetTop ( ); /取栈顶取栈顶 void MakeEmpty ( ) top = -1; /置空栈置空栈 int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = maxSize-1; Department o

6、f Computer Science & Technology, Nanjing University fallDATA STRUCTUREStop空栈toptoptoptoptopa 进栈进栈b 进栈进栈aababcdee 进栈进栈abcdef 进栈溢出进栈溢出abdee 退栈退栈c Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStopc 退栈退栈b 退栈退栈abaa 退栈退栈空栈空栈topabdd 退栈退栈ctopabctoptop Department

7、of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate void SeqStack:overflowProcess( ) /私有函数：当栈满那么执行扩展栈存储空间处置 T *newArray = new E2*maxSize;/创建更大的存储数组 for (int i = 0; i = top; i+) newArrayi = elementsi; maxSize += maxSize; delete elements; elements = newArray; /改动elemen

8、ts指针; template void SeqStack:Push(T x) /假设栈不满假设栈不满, 那么将元素那么将元素x插入该栈栈顶插入该栈栈顶, 否那么溢否那么溢出处置出处置 if (IsFull() = true) overflowProcess; /栈满栈满 elements+top = x; 留意 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate bool SeqStack:Pop(T& x) /函数退出栈顶元素并前往栈顶元素的值函

9、数退出栈顶元素并前往栈顶元素的值 if (IsEmpty() = true) return false; x = elementstop-; return true; /退栈胜利退栈胜利; template bool Seqstack:getTop(T& x) /假设栈不空那么函数前往该栈栈顶元素的地址 if (IsEmpty() = true) return false; x = elementstop; return true;留意 Department of Computer Science & Technology, Nanjing University fallDAT

10、A STRUCTURES算法分析：算法分析：GetTop( ) / 取栈顶元素取栈顶元素Push( ) /入栈操作入栈操作Pop( ) /出栈操作出栈操作O(1) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESb0 t0 t1 b10 maxSize-1V Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES if ( DS.t0+1 = DS.t

11、1 ) return 0; if ( i = 0 ) DS.t0+; else DS.t1-; DS.VDS.ti = x; return 1; if ( DS.ti = DS.bi ) return 0; x = DS.VDS.ti; if ( i = 0 ) DS.t0-; else DS.t1+; return 1; int push ( DualStack& DS, Type x, int i)int Pop (DualStack& DS, Type& x, int i) Department of Computer Science & Technolo

12、gy, Nanjing University fallDATA STRUCTURES例：多进制输出例：多进制输出将十进制转换成其它进制将十进制转换成其它进制算法：以算法：以B进制方式输出进制方式输出1.nB,结果压入栈结果压入栈S中；中；2.n的剩余部分为的剩余部分为n/B,用用n/B替代替代n;3.反复上述过程反复上述过程1和和2直到直到n=0;4.从栈中弹出并打印一切数字。从栈中弹出并打印一切数字。5310125124023122021101011 Department of Computer Science & Technology, Nanjing University fal

13、lDATA STRUCTUREStop Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Stack;template class StackNode friend class Stack;private: Type data; /结点数据结点数据 StackNode *link; /结点链指针结点链指针public: StackNode ( T d = 0, StackNode * next = NULL ) : data (d), lin

14、k (next) ; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class LinkedStack : public Stack /链式栈类定义 private: StackNode *top; /栈顶指针 void output(ostream& os, StackNode *ptr, int& i); /递归输出栈的一切元素public: LinkedStack() : top(NULL) /构造函数 LinkedStack(

15、) makeEmpty(); /析构函数 void Push(E x); /进栈 bool Pop(E& x); /退栈 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES bool getTop(E& x) const;/取栈顶取栈顶 bool IsEmpty() const return top = NULL; void makeEmpty();/清空栈的内容清空栈的内容 int k = 1; friend ostream& operator

16、(ostream& os, LinkedStack& s) output(os, s, k); /输出栈元素的重载操作输出栈元素的重载操作 ; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES字符串字符串: (a*(b+c)-d)目的目的: 输入字符串输入字符串,输出匹配的括号和没有匹配的括号输出匹配的括号和没有匹配的括号算法根本思想算法根本思想:从左到右扫描从左到右扫描,把遇到的左括号存放在栈中把遇到的左括号存放在栈中;每当在后续的扫描过程中遇到一个右

17、括号时每当在后续的扫描过程中遇到一个右括号时,就将它与栈就将它与栈顶的左括号相匹配顶的左括号相匹配,并在栈顶删除该左括号。并在栈顶删除该左括号。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES#include #include #include #include “stack.hconst int maxLength = 100;void PrintMatchedPairs(char * expression) stack s(maxLength); int j, l

18、ength = strlen(expression); for (int i = 1;ilength; i+) if (expressioni-1=() s.Push(i); /左括号左括号, 位置进栈位置进栈 else if (expressioni-1=) /右括号右括号 if (s.Pop(j) = true) /栈不空栈不空,退栈胜利退栈胜利 coutj“与与i“匹配匹配endl; else cout“没有与第没有与第i个右括号匹配的左括号个右括号匹配的左括号!endl; while (s.IsEmpty( ) = false) s.Pop(j); cout.endl; ?/栈中还有左

19、括号栈中还有左括号没有与第没有与第j“个左括号相匹配的右括号个左括号相匹配的右括号! Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRU

20、CTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESrst1rst2rst3rst4rst5rst6 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn顺序扫描表达式的每一项，根据它的类型做如下顺序扫描表达式的每一项，根据它的类型做如下相应操作：相应操作：n假设该项是操作数，那么将其压栈；假设该项是操作数，那么将其压栈；n假设该项是操作

21、符假设该项是操作符，那么延续从栈中退出两，那么延续从栈中退出两个操作数个操作数Y和和X，构成运算指令，构成运算指令XY，并将计，并将计算结果重新压栈。算结果重新压栈。n当表达式的一切项都扫描并处置完后，栈顶存放当表达式的一切项都扫描并处置完后，栈顶存放的就是最后的计算结果。的就是最后的计算结果。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES步步 输入输入 类类 型型 动动 作作 栈内容栈内容 1 置空栈置空栈 空空 2 A 操作数操作数 进栈进栈 A 3 B 操作数

22、操作数 进栈进栈 AB 4 C 操作数操作数 进栈进栈 ABC 5 D 操作数操作数 进栈进栈 ABCD 6 - - 操作符操作符 D、C 退栈退栈, 计算计算 C- -D, 结果结果 r1 进栈进栈 ABr1 7 * 操作符操作符 r1、B 退栈退栈, 计算计算 B*r1, 结果结果 r2 进栈进栈 Ar2 8 + 操作符操作符 r2、A 退栈退栈, 计算计算 A+r2, 结果结果 r3 进栈进栈 r3 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES步步 输入输入

23、类类 型型 动动 作作 栈内容栈内容 9 E 操作数操作数 进栈进栈 r3E 10 F 操作数操作数 进栈进栈 r3EF 11 操作符操作符 F、E 退栈退栈, 计算计算 EF, 结果结果 r4 进栈进栈 r3r4 12 G 操作数操作数 进栈进栈 r3r4G 13 / 操作符操作符 G、r4 退栈退栈, 计算计算 r4/G, 结果结果 r5 进栈进栈 r3r5 14 - - 操作符操作符 r5、r3 退栈退栈, 计算计算 r3- -r5, 结果结果 r6 进栈进栈 r6 Department of Computer Science & Technology, Nanjing Univ

24、ersity fallDATA STRUCTURESvoid Calculator : Run ( ) char ch; double newoperand; while ( cin ch&ch != ; ) switch ( ch ) case + : case - : case * : case / : DoOperator ( ch ); break; /计算 default : cin.putback ( ch ); /将字符放回输入流 cin newoperand; /读操作数 S.Push( newoperand ); Department of Computer Scie

25、nce & Technology, Nanjing University fallDATA STRUCTURESvoid DoOperator ( char op ) /从栈从栈S中取两个操作数，构成运算指令并计算进栈中取两个操作数，构成运算指令并计算进栈 double left, right; int succ = S.GetTop( right ); S.Pop( ); if ( succ ) succ = S.GetTop( left ); S.Pop( ); if ( !succ ) return; /退出两个操作数退出两个操作数 switch ( op ) case +: S

26、.Push ( left + right); break; /加加 case -: S.Push ( left - right); break; /减减 case *: S.Push ( left * right); break; /乘乘 case /: if ( right != 0.0 ) S.Push ( left / right); /除除 else cout “除数为除数为0!n ); exit(1); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Dep

27、artment of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES3.2 栈与递归栈与递归n3

28、.2.1 递归的概念递归的概念幂函数：幂函数：xnS(n)= i=1+2+3+n假设曾经求得假设曾经求得xn或或S(n), 计算计算xn+1或或S(n+1)时？时？ Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);时时当当时时当当 1 ,)!1( 0 ,1!nnnnn

29、 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES参数参数 4 计算计算 4*fact(3)参数参数 3 计算计算 3*fact(2)参数参数 2 计算计算 2*fact(1)参数参数 1 计算计算 1*fact(0)参数参数 0 直接定值直接定值 = 1112624 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of

30、Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESf f Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESf f f f f a0a1a2a3a4递归找链尾template void Print ( L

31、istNode *f ) if ( f -link = NULL ) cout data link ); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESf f f f 递归找含x值的结点xtemplate void Print ( ListNode *f, Type& x ) if ( f != NULL ) if ( f - data = x ) cout data link, x ); Department of Computer Science &

32、; Technology, Nanjing University fallDATA STRUCTURES递归递归 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESn挪动时需求留意的事项挪动时需求留意的事项n每次挪动时必需保证从塔底到塔顶碟子的大小每次挪动时必需保证从塔底到塔顶碟子的大小是从大到小的

33、。是从大到小的。 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES#include #include strclass.hvoid Hanoi (int n, String A, String B, String C) /处理汉诺塔问题的算法处理汉诺塔问题的算法 if ( n = 1 ) cout

34、 move A to C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1, B, A, C ); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES如：如：n!long Factorial ( long n

35、) if ( n = 0 ) return 1; else return n * Factorial (n-1); Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES参数参数 4 计算计算 4*fact(3)参数参数 3 计算计算 3*fact(2)参数参数 2 计算计算 2*fact(1)参数参数 1 计算计算 1*fact(0)参数参数 0 直接定值直接定值 = 1112624 Department of Computer Science & Technolo

36、gy, Nanjing University fallDATA STRUCTURES但是，递归并不是一种高效的方法但是，递归并不是一种高效的方法long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); 1n2),Fib(n1)Fib(n0,1nn,)Fib(n Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1)Fib

37、(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)算法的时间复杂度：算法的时间复杂度： O(2n) Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES如何降低算法复杂度如何降低算法复杂度n采用动态规划采用动态规划Dynamic Programmingn经过辅助数组防止反复计算经过辅助数组防止反复计算 Department of Computer Science

38、& Technology, Nanjing University fallDATA STRUCTURESlong FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback + oneback; twoback = oneback; oneback = Current; return Current;算法的时间复杂度：算法的时间复杂度：O(n) Department of Computer

39、Science & Technology, Nanjing University fallDATA STRUCTURES方法：方法：单向递归和尾递归：单向递归和尾递归：直接用迭代实现直接用迭代实现 其他情形：借助栈其他情形：借助栈 实现实现 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES单向递归：斐波那契数列单向递归：斐波那契数列l o n g F i b ( l o n g n ) if ( n = 1 ) return n; else return Fib

40、 (n-1) + Fib (n-2); long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = 0 ) cout An = 0 ) cout value An endl; n-; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESa0 a1 a2 an-1frontrear Department of Comput

41、er Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Queue public: Queue (int = 10); /构造函数构造函数 void EnQueue (Type x); /进队进队 int DeQueue (Type& x); /出队列出队列 int GetFront (Type& x); /取队头元素值取队头元素值 void MakeEmpty ( ); /置空队列置空队列 int IsEmpty ( ) const ; /判队列空否判队列空否 int

42、IsFull ( ) const; /判队列满否判队列满否 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES队列的顺序存储表示#include template class Queue private: int rear, front;/队尾队尾, 队头指针队头指针 Type *elements; /队列元素数组队列元素数组 int maxSize; /最大元素个数最大元素个数public: Queue (int sz = 10); Queue ( ) delete e

43、lements; void EnQueue (Type x); /进队进队 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESfront rear空队列front rearA进队进队Afront rearB进队进队A Bfront rearC, D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F GC D E F Gfront rearH进队进队,溢出溢出 Departm

44、ent of Computer Science & Technology, Nanjing University fallDATA STRUCTURESfront rearB进队进队A Bfront rearC, D进队进队A B C Dfront rearA退队退队B C Dfront rearB退队退队C Dfront rearE,F,G进队进队C D E F GC D E F Gfront rearH进队进队,溢出溢出 Department of Computer Science & Technology, Nanjing University fallDATA STRU

45、CTURES 初始化：初始化： front=rear= -1 进队时：进队时： rear = rear + 1，再将新元素按，再将新元素按 rear 指示位置参与；队尾指针指示实践队尾位置。指示位置参与；队尾指针指示实践队尾位置。出队时：出队时：front = front + 1，队头指针指示实践，队头指针指示实践队头的前一位置，再将下标为队头的前一位置，再将下标为 front 的元素取。的元素取。 队满时：队满时：rear = maxsize 1;再进队将溢出假再进队将溢出假溢出溢出 ； 队空时队空时:front = rear;再出队将队空处置。再出队将队空处置。 Department of

46、 Computer Science & Technology, Nanjing University fallDATA STRUCTURES队列的顺序存储表示队列的顺序存储表示循环队列循环队列 Circular Queue01234567front01234567front01234567frontrearAABCrearrear空队列空队列A进队进队B, C进队进队0123456701234567A退队退队B退队退队01234567D,E,F,G,H,I 进队进队frontBCrearAfrontBCrearfrontCrearDEF GHI Department of Comput

47、er Science & Technology, Nanjing University fallDATA STRUCTURES Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES01234567frontCrearDEF GH01234567frontCrearDEF GHI假设是：假设是： rear= front ？01234567frontrearAA Department of Computer Science & Technology, Nanji

48、ng University fallDATA STRUCTURES int DeQueue (Type& x); /退队退队 int GetFront (Type& x); /取队头元素取队头元素 void MakeEmpty ( ) front = rear = 0; int IsEmpty ( ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return ;(rear-front+maxSize) % maxSi

49、ze Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate int Queue : DeQueue (Type& x) if ( IsEmpty ( ) ) return 0; front = (front+1) % maxSize; x = elementsfront; return 1;template int Queue : GetFront (Type& x) if ( IsEmpty ( ) ) return 0; x = elem

50、ents( front+1) % maxSize; return 1; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURESfrontrear Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Queue;template class QueueNode friend class Queue;private: Type d

51、ata; /队列结点数据队列结点数据 QueueNode *link; /结点链指针结点链指针public: QueueNode ( Type d = 0, QueueNode *next = NULL ) : data (d), link (next) ; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate class Queue private: QueueNode *front, *rear; /队头、队尾指针指针队头、队尾指针指针public: Q

52、ueue ( ) : rear ( NULL ), front ( NULL ) Queue ( ); void EnQueue (Type x); int DeQueue (Type& x); int GetFront (Type& x); void MakeEmpty ( ); /实现与实现与Queue( )同同 Department of Computer Science & Technology, Nanjing University fallDATA STRUCTURES int IsEmpty ( ) const return front = NULL; ;

53、 template Queue : Queue ( ) /队列的析构函数队列的析构函数 QueueNode *p; while ( front != NULL ) /逐个结点释放逐个结点释放 p = front; front = front-link; delete p; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate void Queue : EnQueue (Type item) /将新元素将新元素item插入到队列的队尾插入到队列的队尾 if (

54、 front = NULL ) /创建第一个结点创建第一个结点front = rear = new QueueNode (item, NULL); else /队列不空队列不空, 插入插入 rear-link = new QueueNode (item, NULL); rear = rear-link; Department of Computer Science & Technology, Nanjing University fallDATA STRUCTUREStemplate Type Queue : DeQueue ( ) if ( IsEmpty ( ) ) return 0; /判队空判队空 QueueNode *p = front; Type x = front-data; front = front-link; delete p; return x;template Type Queue : GetFront ( ) if ( IsEm