数据结构 Data Structure 中南大学 主讲人：王国军，郑瑾 中南大学信息院计科系 {csgjwang,zhengjin}@csu.edu.cn http://trust.csu.edu.cn/ 电话：0731-88877711 手机：13508486821 办公室：校本部计算机楼406-B 本PPT根据《数据结构》教材（清华大学）制作，仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。

第三章 栈和队列

线性表 栈 队列 栈和队列是限定插入和删除只能在表的“端点”进行的线性表，又称为限定性的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 栈和队列是两种常用的数据类型。

提 纲 一、栈的类型定义 二、栈的表示与实现 三、栈的应用举例 四、队列的类型定义 五、队列的表示与实现

表头（栈底）是固定的，表尾（栈顶）是浮动的 第一部分 栈（Stack） 表头（栈底）是固定的，表尾（栈顶）是浮动的 一、栈的类型定义 定义：限定仅在表尾进行插入和删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。 an a1 a2 ……... 栈底 栈顶 ... 出栈/弹出 入栈/压栈 栈S=(a1,a2,……,an) 栈底元素 表尾— 表头— 栈顶元素 特点：先进后出（FILO）或后进先出（LIFO）。

一、栈的类型定义 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

StackEmpty(&S) 初始条件：栈S已存在 DestroyStack (&S) 初始条件：栈S已存在 操作结果：销毁栈S ClearStack (&S) 初始条件：栈S已存在 操作结果：将栈置为空栈 StackEmpty(&S) 初始条件：栈S已存在 操作结果：若栈S为空栈则返回TRUE，否则返回FALSE

a1 a2 an … … StackLength(&S) 初始条件：栈S已存在 GetTop(S, &e) 初始条件：栈S已存在

Push(&S, e) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 a1 a2 … … an e

Pop(&S, &e) 初始条件：栈S已存在且非空 a1 a2 … … an-1 an

StackTraverse(&S, visit()) 操作结果：从栈底到栈顶依次对栈S的每个数据元素调用函数visit()，一旦visit()失败，则操作失败 }ADT Stack

二、栈的表示与实现 顺序栈 链 栈 1、顺序栈 栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一个端点； 链 栈 二、栈的表示与实现 1、顺序栈 由于栈是特殊的线性表，因此线性表的存储结构对栈也适用。栈的顺序存储结构称为顺序栈，可用数组来实现顺序栈。因为栈的运算受限性，即： 栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一个端点； 栈顶位置随着进栈和出栈操作而变化，故需用一个整型变量 top 来指示当前栈顶的位置，通常称 top 为栈顶指针。

顺序栈的类型定义 方法一： #define stacksize 6 typedef struct { ElemType data[stacksize]; int top; } SeqStack； top=-1 1 2 3 4 5 栈空 Data数组 方法二： typedef struct { 　ElemType *base; // 存储空间基址 　int top; 　　 // 栈顶指针 　int stacksize; // 允许的最大存储空间 // 以元素为单位 } SeqStack;

S.top == stacksize-1，栈满，此时入栈，则上溢(overflow) 2 3 4 5 F top E top D top 1 2 3 4 5 A B C D E F top C top top B top top A top 栈顶指针S.top始终指向实际栈顶 进栈/插入 top top top S.top == -1，栈空，此时出栈，则下溢(underflow) 出栈/删除

上溢是一种出错状态，应该设法避免之； 下溢通常属于正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。

顺序栈的运算 InitStack (Stack &S，int maxsize=0) {// 构造一个最大存储容量为 maxsize 的空栈 S if (maxsize == 0) 　 maxsize = MAXLISTSIZE; S.base = (ElemType*)malloc(maxsize* sizeof(ElemType)); if (!S.base) exit(OVERFLOW); // 存储分配失败 S.stacksize = maxsize; S.top = 0; 　// 空栈中元素个数为0 }

该结论的前提是top指针初值为0。如果top指针初值为-1，情况将是怎样？ 从名称来讲，“栈顶指针”指示栈顶元素在栈中的位置，但它的值实际上是栈中元素的个数，和顺序表中length的值的含义相同。 图中顺序栈的最大容量为7，当前栈中元素个数为4，因此，我们也可认为栈顶指针总是指在栈顶元素的后面一个位置上。 该结论的前提是top指针初值为0。如果top指针初值为-1，情况将是怎样？

bool GetTop (Stack S, ElemType &e) 　{ // 若栈不空，则用 e 返回S的栈顶元素，并返回TRUE；否则返回FALSE 　　if (S.top == 0) return FALSE; 　　e = *(S.base + S.top-1); // 返回非空栈中栈顶元素 　　return TRUE; 　} *(S.base + S.top-1)是S.base[S.top-1] 的另一种写法，其实质相同。

bool Push (Stack &S, ElemType e) {// 若栈的存储空间不满，则插入元素 e 为新的栈顶元素， // 并且返回 TRUE；否则返回 FALSE 　　if (S.top == S.stacksize)　 // 栈已满，无法进行插入 　　　return FALSE; 　　*(S.base + S.top) = e; // 插入新的元素 　　++S.top;　　　// 栈顶指针后移 　　return TRUE; }

bool Pop (Stack &S, ElemType &e) { // 若栈不空，则删除S的栈顶元素，用 e 返回其值， // 并返回 TRUE；否则返回 FALSE 　　if (S.top == 0) return FALSE; 　　--S.top; 　　　// 栈顶指针前移 e = *(S.base + S.top); // 返回非空栈中栈顶元素 　　return TRUE; }

显然，顺序栈的基本操作的时间复杂度，除“遍历”之外，均为常量阶，即O (1)。

链 栈 链栈的定义更简单，其结点结构和单链表中的结点结构相同。由于栈只在栈顶作插入和删除操作，因此链栈中不需要设置头结点，但要注意链栈中指针的方向是从栈顶指向栈底的，这正好和单链表是相反的。

typedef LinkList LinkStack; typedef struct { LinkStack top; // 栈顶指针 　 int length; // 栈中元素个数 } Stack; void InitStack ( Stack &S ) 　{ // 构造一个空栈 S 　 S.top = NULL; // 设栈顶指针的初值为“空” 　 S.length = 0; // 空栈中元素个数为0 　}

voi Push ( Stack &S, ElemType e ) { // 在栈顶之上插入元素 e 为新的栈顶元素 p = (LNode voi Push ( Stack &S, ElemType e ) 　{ // 在栈顶之上插入元素 e 为新的栈顶元素 　　p = (LNode *)malloc(sizeof(LNode)); 　　 // 建新的结点 　　p -> data = e; 　　p -> next = S.top;　// 链接到原来的栈顶 　　S.top = p; 　　　　// 移动栈顶指针 　　++S.length;　 　 // 栈的长度增1 　}

bool Pop ( Stack &S, ElemType &e ) { // 若栈不空，则删除S的栈顶元素，用 e 返回其值， // 并且返回 TRUE；否则返回 FALSE 　　if ( !S.top )　return FALSE; 　　else 　　{ e = S.top -> data; 　　// 返回栈顶元素 　　 q = S.top; 　　 S.top = S.top -> next;　// 修改栈顶指针 　　 --S.length; 　　　　　 // 栈的长度减少1 　　 free(q);　　　　　 　 // 释放被删除的结点空间 　　 return TRUE; 　　} 　}

原理： N = (N div d)×d + N mod d 三、栈的应用举例 数制转换 原理： N = (N div d)×d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 计算顺序 输出顺序

void conversion () { InitStack(S); scanf ("%d", N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S, e); printf ( "%d", e );

括号匹配的检验 假设在表达式中 （［］（））或［（［ ］［ ］）］ 等为正确的格式， ［（ ］）或（［（ ））或 (( )]) 均为不正确的格式。 则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。

例如：考虑下列括号序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况： 到来的右括弧并非是所“期待”的； 到来的是“不速之客”； 直到结束，所“期待”的括弧也没有到来。

这三种情况对应到栈的操作即为： 　　1．和栈顶的左括弧不相匹配； 　　2．栈中有左括弧但新来的仍是左括弧； 　　3．栈中还有左括弧没有等到和它相匹配的右括弧。

算法的设计思想 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配； 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余。

Status matching(string& exp) { int state = 1; i = 1; InitStack(S); while (i<=Length(exp) && state) { switch (exp[i]) { case "(": {Push(S, exp[i]); i++; break;} case ")": { if(!StackEmpty(S)&&GetTop(S)=="(") {Pop(S, e); i++;} else {state = 0;} break; } … … } if (StackEmpty(S)&&state) return OK; …...

行编辑程序问题 如何实现？ “每接受一个字符即存入存储器” ? 并不恰当！

在用户输入一行的过程中，允许用户输入出差错，并且在发现有误时用户可以及时更正。 合理的做法是： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区；并且假设"#"为退格符，"@"为退行符。

假设从终端接受了这样两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行： while (*s) putchar(*s++);

while (ch != EOF) { //EOF为文件结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break; // 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); }

迷宫求解 通常用的是“穷举求解”的方法 基本思想： 若当前位置“可通”，则纳入路径，继续前进； 若当前位置“不可通”，则后退，换方向继续探索； 若当前位置四周“均无通路”，则将当前位置从路径中删除。

求迷宫中一条从入口到出口的路径的算法 设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置｝ 否则 { 若栈不空且栈顶位置尚有其它方向未被探索， 则设定新的当前位置为：沿顺时针方向旋转 找到的栈顶位置的下一个相邻方块；

若栈不空但栈顶位置的四周均不可通， 则｛删除栈顶位置；// 从路径中删除该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻方块或出栈至栈空； ｝ ｝while (栈不空）； 若栈空，则表明迷宫没有通路。

typedef struct { int ord; 　PosType seat; int di; }SElemType;

Status MazePath(MazeType maze, PosType start, PosType end) { InitStack(S); curpos=start; curstep=1; do { if (Pass(curpos)) { FootPrint (curpos) ; e=(curstep, curpos, 1); Push(S, e); if(curpos==end) return(TURE); curpos=NextPos(curpos, 1); curstep++; }//if

while(e.di==4&&!SatckEmpty(S)) { MarkPrint (e.seat); Pop(S,e); Else { if(!StackEmpty(S)) { Pop(S, e); while(e.di==4&&!SatckEmpty(S)) { MarkPrint (e.seat); Pop(S,e); }//while if(e.di<4) { e.di++; Push(S,e); curpos=NextPos(e.seat, e.di); }//if }//else }while(!StackEmpty(S)); return(FALSE); }//MazePath 迷宫探索成功 迷宫探索失败

表达式求值 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数可以是常量也可以是被说明为常量或变量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符等三类；基本界限符有左右括弧和表达式结束符等。

这里仅限于二元运算符的表达式定义： 表达式 ::= (操作数) + (运算符) + (操作数) 操作数 ::= 标识符 | 表达式 标识符 :: = 常量 | 变量

表达式的三种表示方法 设 Exp = S1 + OP + S2 则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法

例如: Exp = a  b + (c  d / e)  f 结论: 1）操作数之间的相对次序不变； 2）运算符之间的相对次序不同；中缀式的次序和原表达式相同； 3）中缀式丢失了括弧信息，致使运算的次序不确定；因而一般来说没有意义。

例如: Exp = a  b + (c  d / e)  f 4）前缀式的运算规则为： 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式。

例如: Exp = a  b + (c  d / e)  f 5）后缀式的运算规则为： 运算符在式中出现的顺序恰为表达式的运算顺序； 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。

a b  c d e /  f  + c-d/e 如何从后缀式求值？ 例如： ab d/e (c-d/e)f 先找运算符，再找操作数 例如： a b  c d e /  f  + ab d/e c-d/e (c-d/e)f

如何从原表达式求得后缀式？ 分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b  c  d / e  f 每个运算符的运算次序要根据它之后的一个运算符来决定，在后缀式中优先权高的运算符领先于优先权低的运算符。

也就是说，对原表达式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符，如果它的优先权“高或等于”后面的运算，则它的运算先进行，否则就得等待在它之后出现的所有优先权高于它的“运算”都完成之后再进行。 　　显然，保存运算符的结构应该是一个栈，从栈底到栈顶的运算符的优先权是从低到高的，因此它们运算的先后应是从栈顶到栈底的。

从原表达式求得后缀式的规律为： 1) 设立暂存运算符的栈； 2) 设表达式的结束符为“#”, 预设运算符栈的栈底为“#” ； 3) 若当前字符是操作数， 则直接发送给后缀式；

4) 若当前运算符的优先权高于栈顶运算符，则进栈； 5) 否则，退出栈顶运算符发送给后缀式； “(” 对它之前后的运算符起隔离作用， “)”可视为自相应左括弧开始的表达式的结束符。

ch 是运算符，则函数 IN(ch,OP) 的值为“TRUE” void transform(char suffix[ ], char exp[ ]) { InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S)) { if (!IN(ch, OP)) Pass( Suffix, ch); else {switch (ch) { case ( : Push(S, ch); break; case ) : { Pop(S, c); while (c!= ( ) { Pass( Suffix, c); Pop(S, c) } break; } ch 是运算符，则函数 IN(ch,OP) 的值为“TRUE” 将字符 ch 复制到数组 suffix 中

while(GetTop(S, c) && ( precede(c,ch))) default: { while(GetTop(S, c) && ( precede(c,ch))) { Pass(Suffix, c); Pop(S, c); } if ( ch!= # ) Push( S, ch); break; }//default } // switch } // else if ( ch!= # ) { p++; ch = *p; } } // while } // CrtExptree 若c(栈顶运算符)的优先权大于或等于ch(当前运算符)的优先权，则函数precede(c,ch)值为"TRUE" 动画演示

表达式求值——算符优先算法 算法的基本思想： ①为了固定求值顺序，编译系统根据算术四则运算的规则，为每个运算符赋予一个优先权： 运算符 （ ） ∧ ﹡ / + － # 优先权 4 3 2 1 操作数栈S1（初值为空栈）：存放操作数或运算结果 ②设置两 个工作栈 运算符栈S2（初值为"#"）：存放运算符

③ 编译时，计算机从左到右扫描表达式，凡遇到操作数一律进S1栈；凡遇到运算符，则将其优先权与S2栈的栈顶运算符的优先权进行比较：若前者大，则该运算符进栈；反之，S2栈顶运算符出栈，同时S1栈顶上的两个元素相继出栈，形成一次运算的机器指令，并且每次运算结果进S1栈。直至S2栈的栈顶运算符号与当前读入的运算符号都是"#"，算法结束。

例：计算X=4/2∧2+3* 5# # # ∧ + # 1 3*5=15 1+15=16 # 1 # + 1 # + 5 * 3 15 16 2∧2=4 4/4=1 操作数 运算符 操作数 运算符 4 # / 操作数 运算符 # ∧ 2 2 / 4 + # 4 1 3*5=15 1+15=16 操作数 运算符 # ---Reverse Polish Notation 操作数 运算符 1 # + 操作数 运算符 1 # + 5 * 3 15 16

递归 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。

从被调用函数返回调用函数之前，应该完成下列三项任务： 保存被调用函数的计算结果； 释放被调用函数的数据区； 依照被调用函数保存的返回地址将控制转移到调用函数。

多个函数嵌套调用的规则 后调用先返回！ 此时的存储管理实行“栈式管理” 例如： void main( ){ void a( ){ void b( ){ … … … a( ); b( ); … … }//main }// a }// b 函数b的数据区 函数a的数据区 main的数据区

递归：函数直接或间接地调用自身叫递归 实现：建立递归工作栈 递归工作栈：递归过程在执行过程中占用的数据区。 递归工作记录：每一层的递归参数合成为一个记录。 当前活动记录：栈顶记录指示当前层的执行情况。 当前环境指针：递归工作栈的栈顶指针。

过程的嵌套调用 子过程1 r 子过程2 子过程3 r s r s t r 主程序 s t r s r

递归过程及其实现 实例：写出下面程序的运行结果并分析递归的执行情况 void print(int w) main() { int i; { int w=3; if ( w!=0) print(w)； { print(w-1); } for(i=1; i<=w; ++i) printf("%3d,", w); printf("/n"); } 运行结果： 1， 2，2， 3，3，3，

递归调用执行情况： 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1 w （4）w=0 （3）w=1 （4）w=0 （3）w=1 （2）w=2 （1）w=3 top w 2 print(1); （2）w=2 （1）w=3 top (3) 输出：2, 2 w 3 print(2); （1）w=3 top (2) 输出：3, 3, 3 w (4)输出：1 (3) 1 (2) 2 (1) 3 top 返回 (3) 1 (2) 2 (1) 3 top (4) 0 主程序 (3)输出：2, 2 (2) 2 (1) 3 top (1) print(w) w=3; (2)输出：3, 3, 3 (1 ) 3 top 结束 (1)

void hanoi (int n, char x, char y, char z, int &i) { // 将塔座x上按直径由小到大且自上而下编号为1至n // 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n==1) 2 {move(x, 1, z); i++;} // 将编号为１的圆盘从x移到z 3 else { 4 hanoi(n-1, x, z, y, i); // 将x上编号为１至n-1的 //圆盘移到y, z作辅助塔 move(x, n, z); // 将编号为n的圆盘从x移到z i++; 7 hanoi(n-1, y, x, z, i); // 将y上编号为１至n-1的 //圆盘移到z, x作辅助塔 8 }//else 9 }

用栈解决汉诺塔问题 typedef struct { int n; //盘子数目（返回时代表编号） char x,y,z; //起始塔座，辅助塔座和目标塔座 }ElemType; void move(char from, int n, char to) {printf("%3d:%c->%c\n", n, from, to);}

Void hanoi1 (int n,char x,char y,char z) { stack s; ElemType e; char t; InitStack(&s); e.n=n; e.x=x; e.y=y; e.z=z; push(&s,e); //初始参数入栈 while(1) { gettop(s, &e); while(e.n>1) {e.n--; t=e.y; e.y=e.z; e.z=t; push(&s,e); gettop(s, &e); } pop(&s, &e); move(e.x, 1, e.z);

if (stackempty(s)) return; pop(&s,&e); move(e.x, e.n, e.z); e.n--; t=e.x; e.x=e.y; e.y=t; push(&s, e); }

方法二： 由于将n个盘子从x座移至z座的任务可以分为三项任务来完成，即： 将n-1个盘子由x座移到y座； 把第n号盘子从x座移到z座； 将n-1个盘子由y座移到z座。 因此，可以开始把不能解决的问题的参数入栈以后只要栈顶的n大于1，就将其出栈，并将替代它的三项任务入栈。

由于这三项任务的1，3项可能还不能做，还要递归地以另外三项任务代替它们，而中间的移动n号盘的任务可以做，所以要用一个标志来区分。例如：在栈结构中增加一个整数变量tag，其值为1表示还要去递归，其值为0表示移动一个盘子。所以，1，3项任务中tag=1,中间一项tag=0。

void hanoi1 (int n,char x,char y,char z) { stack s; ElemType e; char t; initstack(&s); e.n=n;e.tag=1; e.x=x; e.y=y; e.z=z; push(&s,e); while(1) { gettop(s, &e); while(e.tag!=0&&e.n!=1) {pop(&s,&e); e.n--; t=e.x; e.x=e.y; e.y=t; push(&s,e); e.n--; e.tag=0; t=e.x; e.x=e.y; e.y=t; push(&s,e); e.n--; e.tag=1; t=e.y; e.y=e.z; e.z=t; push(&s,e); gettop(s, &e); } 第3项任务 第1项任务

if(e.n==1) { move(e.x,1,e.z); pop(&s, &e); if (stackempty(s)) return;} else { move(e.x, e.n, e.z); pop(&s, &e); }

在一个程序中两栈共享邻接空间data[M] M-1 栈1底 栈1顶 栈2底 栈2顶 top1 top2 #define stacksize M typedef struct { ElemType data[stacksize]; int top1, top2; } SeqStack; SeqStack S;

特点：利用栈底不变的特性，栈顶向中间延伸 M-1 栈1底 栈1顶 栈2底 栈2顶 top1 top2 特点：利用栈底不变的特性，栈顶向中间延伸 思考： top1=0且top2=M-1 1、何种情况下，两栈均为空？___________________ top1-1= top2或top2+1= top1 2、何种情况下，栈上溢？__________________________ 增加了空间利用率， 减少了每个栈溢出的可能性。 3、两栈共享邻接空间的优点?____________________ ______________________

习 题 用S表示入栈操作，X表示出栈操作，若元素入 栈顺序为1234，为了得到1342出栈顺序，相应 的S和X操作串是什么？ 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈的次序有哪几个？ SXSSXSXX CDBAE、CDBEA、CDEBA

因为栈中最多时有3个元素，所以栈S的容量至少应该是3 3. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少？ 因为栈中最多时有3个元素，所以栈S的容量至少应该是3

作 业 铁路车厢调度如下图所示，请回答： （1） 如果进栈的车厢序列为123，则可能得到的出栈车厢序列是什么？ 作 业 铁路车厢调度如下图所示，请回答： （1） 如果进栈的车厢序列为123，则可能得到的出栈车厢序列是什么？ （2）如果进栈的车厢序列为123456，则能否得到435612和125426的出栈序列，请说明为什么不能得到或者是如何得到(即写出以‘S’表示进栈和以‘X’表示出栈的操作序列）。

设计一个程序，用算符优先算法对算术表达式求值。          （基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。） 3. 练习册P24/3.15, 3.19, 3.31

第二部分 队列 一、队列的类型定义 定义：队列是限定只能在表的一端进行插入(入队），而在表的另一端进行删除（出队）的线性表。 第二部分 队列 一、队列的类型定义 定义：队列是限定只能在表的一端进行插入(入队），而在表的另一端进行删除（出队）的线性表。 队尾(rear) ——允许插入的一端 队首(front) ——允许删除的一端 队尾元素 a1 a2 a3…………………….an 入队/ 插入 出队 / 删除 front rear 队列Q=(a1,a2,……,an) 队首元素 队列特点：先进先出(FIFO)

队列的类型定义 ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ <a i-1, ai > | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头，an 端为队列尾 基本操作： } ADT Queue

队列的基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, &e) ClearQueue(&Q) EnQueue(&Q, e) DeQueue(&Q, &e) QueueTraverse(Q, visit())

InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。

QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 … … an

ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 … … an e

DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 a1 a2 … … an

队列类型的表示与实现 链队列——链式映象 循环队列——顺序映象

typedef struct QNode {// 结点类型 链队列——链式映象 typedef struct QNode {// 结点类型 QElemType data; struct QNode *next; } QNode, *QueuePtr;

a1 ∧ an … ∧ 空队列 typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; a1 ∧ an … Q.front Q.rear Q.front Q.rear ∧ 空队列

} { // 构造一个空队列Q Q.front = Q.rear = （QueuePtr）malloc(sizeof(QNode)); 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) p = (QueuePtr)malloc(sizeof(QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } e p Q.front a1 ∧ an ∧ Q.rear

// 用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; 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; delete (p); return OK; } if (Q.rear == p) Q.rear = Q.front;

顺序队列 类型定义： #define queuesize 100 typedef struct SqQueue { QElemType sq[queuesize]; int front; int rear; } SqQueue； SqQueue Q;

顺序队列的操作 此时若还有元素入队，就会发生溢出，这种溢出称为“假溢出” rear=0 front=0 1 2 3 4 5 队空 1 2 3 队空 1 2 3 4 5 front a1,a2,a3入队 rear 1 2 3 4 5 a4,a5,a6入队 a4 a5 a6 front 1 2 3 4 5 a1,a2,a3 出队 a1 a2 a3 rear rear rear a3 rear front a2 rear front a1 front front 约定： rear是队尾指针 front是队头指针 初值front=rear=0（队空） 出队列：x=sq[front ++] 空队列条件：front==rear front指示队头元素 rear指示队尾元素的后一位置 入队列：sq[rear ++]=x 队满：rear= queuesize

解决方案 元素平移法：队头固定，每次出队时剩余元素向下移动 缺点：浪费时间 循环队列（Circular Queue） rear 1 2 3 4 5 a4 a5 a6 front 缺点：浪费时间 1 2 3 4 5 a4 a5 a6 front rear rear a7 循环队列（Circular Queue） 基本思想：把队列设想成一个首尾相接的环形，让 sq[0]接在sq[queuesize-1] 之后，若rear+1==queuesize,则令rear=0;

此例中queuesize =6 queuesize –1 front=rear 队列满 rear rear front rear rear front a4 a5 a6 queuesize –1 front=rear 队列满 rear a7 rear a8 a9 rear rear a7、a8、a9相继入队

队满、队空判定条件： front 队空：front==rear 队满：front==rear rear 1 2 3 4 5 rear front a4,a5,a6出队 队空：front==rear 队满：front==rear a6 1 2 3 4 5 rear front a7,a8,a9入队 a5 a7 a4 a9 a8 初始状态 队满、队空判定条件： 另外设一个标志位（逻辑变量）以区别队空、队满

队满：front==rear+1(以queuesize为模） 即：front==(rear+1)% queuesize 少用一个元素空间： 队列最大空间 队空：front==rear 队满：front==rear+1(以queuesize为模） 即：front==(rear+1)% queuesize front a4 a5 a6 queuesize –1 rear front=rear+1 队列满 a7 a8 rear rear a7、a8相继入队

循环队列的基本操作 入队：sq[rear]=x; rear=(rear+1)%queuesize; 算法： Status en_cycque(SqQueue &Q, QElemType x) { i= (Q→rear+1)% queuesize; if ((i== Q→front) return OVERFLOW; Q→sq[Q→rear]=x; Q→rear=i; return OK; }

出队：x=sq[front]; front=(front+1)%queuesize; 算法： Status dl_cycque(SqQueue &Q, QElemType &x ） { if(Q→front== Q→rear) return UNDERFLOW; x= Q→sq[Q→front]; Q→front = (Q→front+1)%queuesize; return OK; }

循环队列应用示例 计算并输出 n 行杨辉三角形的值

二项式系数值（杨辉三角形） 第 1 行 1 1 第 2 行 1 2 1 第 3 行 1 3 3 1 第 4 行 1 4 6 4 1 设第 i-1行的值：(a[0]=0) a[1]..a[i] (a[i+1]=0) 则第 i 行的值：b[j] = a[j-1]+a[j], j=1,2,…,i+1

利用循环队列计算二项式的过程 假设只计算三行，则队列的最大容量为 5。 1 1 1 1 1 q.front q.rear q.rear q.front 2 1 1 1 2 1 1 1 q.rear q.front q.rear q.front 2 1 1 2 1 1 1 q.rear q.front q.rear q.front

2 1 1 1 2 1 1 3 3 1 1 3 3 1 1 3 do { DeQueue(Q, s); GetHead(Q, e); 1 1 do { DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf ("%d", e); EnQueue(Q, s+e); } while (e!=0); q.rear q.front 2 1 1 3 q.rear q.front 3 1 1 3 3 1 1 3 q.rear q.front q.rear q.front

void yanghui ( int n ) { // 打印输出杨辉三角形的前 n( n>0 )行 　Queue Q; 　for( i=1; i<=n; i++) 　　 printf (" "); 　printf ("%d\n", 1); // 在中心位置输出杨辉三角形最顶端的“1” InitQueue(Q, n+2);// 设置最大容量为 n+2的空队列 EnQueue(Q, 0 );　// 添加行界值 EnQueue(Q, 1); 　EnQueue(Q, 1 ); // 第一行的值入队列 　k = 1; while ( k < n ) 　　{ // 通过循环队列输出前 n-1 行的值 　　　

　　　for( i=1; i<=n-k; i++) 　　　　 printf (" ");// 输出n-k个空格以保持三角形 　　　EnQueue ( Q, 0 ); // 行界值“0”入队列 　　　do { // 输出第 k 行，计算第 k+1 行 　　　　DeQueue( Q, s ); 　　　　GetHead( Q, e ); 　　　　if (e) printf ("%d ", e); 　　　 // 若e为非行界值0，则打印输出 e 的值并加一空格 　　　　else printf ("\n");//否则回车换行，为下一行输出做准备 　　　　EnQueue(Q, s+e); 　　　} while (e!=0); 　　　k++; 　　 } // while

DeQueue ( Q, e ); // 行界值“0”出队列 while ( DeQueue ( Q, e );　 // 行界值“0”出队列 while (!QueueEmpty (Q) ) { // 单独处理第 n 行的值的输出 　 DeQueue ( Q, e ); 　 printf ("%d ", e) ； } // while } // yanghui

作 业 综合题三