计算机数据结构第三章栈和队列概要.ppt

第三章 栈和队列 3.1 栈 栈是仅限定在表的一端操作的线性表。它的插入和删除都只能在表的一端进行。插入操作称为入栈，删除操作称为出栈。 //栈的抽象数据类型定义 ADT Stack { 数据对象：D={ ai | ai?ElemSet, i=1, 2, ..., n, n?0 } 数据关系：R1={ai-1, ai | ai-1, ai?D, i=2, ..., n } 约定an 端为栈顶，a1 端为栈底。 基本操作： InitStack(S) 操作结果：构造一个空栈 S。 DestroyStack(S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 3.2 栈的应用举例 3.2.3 算术表达式求值 3.3 栈与递归 的实现 例1 求n! (用递归调用) 1 n=0 fac= n (n-1)! n0 求n! (用递归调用) 1 n=0 fac= n (n-1)! n0 求n! (用递归调用) 1 n=0,1 fac= n (n-1)! n0 递归的要点： 例2 Hanoi 塔问题 3.4 队列 先看下列过程： 元素出队或入队的指针变化情况： 2.销毁队列 Status DestroyQueue( LinkQueue Q ); // 销毁队列Q Q front rear Q front rear a1 an ∧ an-1 销毁了所有的结点 3.清空队列 Status ClearQueue( LinkQueue Q ); // 将 Q 清为空队列 Q front rear a1 an ∧ an-1 还剩头结点 ^ Q front rear ^ 4.判断队列 Status QueueEmpty( LinkQueue Q ); // 若队列Q为空队列，则返回TURE,否则返回FALSE Q front rear a1 an ∧ FALSE Q front rear TRUE ^ 5.入队 Status EnQueue(LinkQueue Q, QElemType e) //插入元素 e 为Q 中新的队尾元素 e ∧ an ∧ Q front rear a1 an 6.出队 Status DeQueue(LinkQueue Q, QElemType e) //删除 Q 的队头元素，并用 e 返回其值。 Q front rear a1 an ∧ a2 a1 基本操作的算法描述 Status InitQueue( LinkQueue Q ) { // 构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW); // 存储分配失败 Q.front-next = NULL; return OK; }//InitQueue ^ front rear Q Status DestroyQueue( LinkQueue Q ) { // 销毁队列 Q while(Q.front) { Q.rear = Q.front-next; free(Q.front); Q.front = Q.rear; } return OK; } // DestroyQueue Q a1 an ∧ front rear a2 销毁完成 Status EnQueue(LinkQueue Q, QElemType e) { // 插入元素 e 为Q 中新的队尾元素 p = (QueuePtr)malloc(sizeof(QNode)); if ( !p ) exit (OVERFLOW); // 存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; }//EnQueue an ∧ Q front rear a1 an ∧ e p ^ 成功!! Status DeQueue(LinkQueue Q,