数据结构讲义-栈与队列.ppt

* * * typedef struct Qnode { QElemType data; struct Qnode *next; } Qnode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; data next 队首结点 ∧ Q.front 队尾结点 Q.rear 3.4.3 链接表示的队列： Q.front 和 Q.rear 分别是队首和队尾指针。它们指示着队首的前一结点和队尾结点。 3.4 队列 * * data next Q.front Q.rear ∧ data next Q.front 队尾结点(队首结点) Q.rear ∧ 队首结点 ∧ data next Q.front 队尾结点 Q.rear 链（接）队列的操作： 3.4 队列 * * Status EnQueue (LinkQueue Q, QElemType e ) { 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 ; Status DeQueue (LinkQueue Q, QElemType e ) { if ( Q.rear == Q.front) return( ERROR ) ; p = Q.front-next; e = p-data; Q.front-next = p-next; if( Q.rear == p ) Q.rear = p; free( p ); return OK; } // DeQueue ; 3.4 队列 * * 队列的应用举例 — 逐行打印二项展开式 (a + b)i 的系数 杨辉三角形 (Pascal’s triangle) 3.4 队列 * * 分析第 i 行元素与第 i+1行元素的关系 目的是从前一行的数据可以计算下一行的数据 3.4 队列 * * 3.4 队列 从第 i 行数据计算并存放第 i+1 行数据 * * 3.4 队列 void YangHui ( int n ) { SqQueue q; int s=0, t; InitQueue(q); EnQueue (q, 1); EnQueue (q, 1); for( int i=1; i=n; i++ ) //逐行计算 { printf(“\n”); EnQueue (q, 0); for ( int j=1; j=i+2; j++ ) //根据上行系数求下行系数 { DeQueue (q, t); EnQueue (q, s+t); s = t; if ( j != i+2 ) printf(“%3d”, s); //不输出每行结尾的0 } } } 利用队列打印二项展开式系数的程序 * * 本章课后作业 “数据结构题集（C 语言版）” P21-24 1、3、16 P23-26 9、10、30 单周星期一交作业！ * * * * * * * * * * * * * * * * * * * * * * * * * * 柳 青 Email: liuqing@ynu.edu.cn School of Software , Yunnan University 数据结构 (Data Structure) * * 3.1、栈 (Stack) 3.2、栈的应用举例 3.3、栈与递归的实现 3.4、队(Queue)  第三章 栈和队列 * * 3.1 栈 (Stack) 3.1.1 定义 栈(Stack) ：限定仅只能在表尾端进行插入和删除的线性表。 栈顶(top)： 表尾端被称之为栈顶。栈顶之上为top指针。 栈底(Bottom)：和表尾相对应的另一端，称之为栈底。 特点：后进先出（LIFO）。 a1 a2 an-1 an …… t