数据结构chapter_3.ppt

第三章 栈和队列 3.1.1抽象数据类型栈的定义 2、栈的基本操作 3、栈的抽象数据类型的定义 3.1.2 栈的表示和实现 1、 顺序栈 2、 链栈 定义是递归的 求解n! 的过程 long Fib ( long n ) { if ( n = 1 ) return n;  else return Fib (n-1) + Fib (n-2); } 【例3】求数组 A 中 n 个整数的和 int sum ( int *A ,int n ) { int result=0; if ( n == 1 ) result = A[0]; else result = A[n-1] + sum(A,n-1); return result; } 3.3队列 3.3.2 链队列 Status InitQueue(SqQueue Q){ Q.base=(QElemType *)malloc(sizeof (QElemType)*MAXQSIZE ); if(!Q.base) return(OVERFLOW); Q.front = Q.rear = 0; return OK; } // InitQueue int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } Status EnQueue(SqQueue Q, QelemType e) { if((Q.rear+1)% MAXSIZE == Q.front) return(ERROR); Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } // EnQueue Status DeQueue(SqQueue Q, QelemType e) { if(Q.front == Q.rear) retrun ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } // DeQueue 上机实验：迷宫问题 main() { int m; printf(Input the number of disks scanf(%d,m); printf(The steps to moving %3d hanoi(m,A,B,C); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } A B C 3 A B C 0 2 B A C 8 1 A B C 8 A B C 3 A B C 0 2 B A C 8 3 A B C 0 栈空 3 A B C 0 2 B A C 8 3.3.1 抽象数据类型队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。 出队 入队 队头 队尾 下图是队列的示意图： a1 a2 a3 an 队列的抽象数据定义见书Ｐ59 双端队列:就是限定插入和删除操作在表的两端进行的线性表。 尽管双端队列看起来似乎比栈和队列更灵活