第三章栈和队列.ppt

3.1 栈 问题的递归描述（定义） 　递归定义包括两项 　基本项（终止项）：描述递归终止时　　　　问题的求解； 递归项：将问题分解为与原问题性质　　　　相同，但规模较小的问题； 如阶乘函数： 　n!= 1* 2* 3* 4 * (n-1)* n 　n!递归定义 　n!= 1 当 n=1 时 　　　　　　　n!= n (n-1)! 当n 1 时 解决方案---循环队列 基本思想：把队列设想成环形， 让Q.base[0]接在Q.base[M-1]之后; 实现：利用“模”运算实现指针变化 入队： Q.rear=(Q. rear+1)%M; 出队： Q.front=(Q.front+1)%M; 队满、队空判定条件 typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; typedef struct QNode {// 结点类型 ElemType data; struct QNode *next; } QNode, *QueuePtr; 链队列的有关操作 空队 Q.front Q.rear ∧ X Q.front ∧ Q.rear X入队 Y Q.front ∧ Q.rear Y入队 X Y Q.front ∧ Q.rear X出队 X Y出队 Q.front Q.rear ∧ Status InitQueue (LinkQueue Q) { // 构造一个空队列Q } Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue Q, QElemType e) { // 插入元素e为Q的新的队尾元素 } ∧ a1 Q.front Q.rear ∧ e p p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue Q, QElemType e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR } if (Q.front == Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; Status DestroyQueue_L (LinkQueue Q){ // 回收链队列动态申请的空间 } while(Q.front != NULL){ Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; } return OK; Status QueueEmpty_L (LinkQueue Q) { // 判断队列Q是否为空 } // 若队头指针等于队尾指针，则队为空 if (Q.front == Q.rear) return OK; return FALSE; #define M 100 //最大队列长度 typedef struct { ElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空， // 指向队列头元素 int rear; // 尾指针，若队列不空，指向