《数据结构课件CH3 栈和队列》由会员分享，可在线阅读，更多相关《数据结构课件CH3 栈和队列（91页珍藏版）》请在金锄头文库上搜索。
1、9/16/20249/16/2024通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种特殊的线性表，是操作受限栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性的线性表，称限定性DS。9/16/20249/16/20243.3 栈的应用举例栈的应用举例3.1 栈的类型定义栈的类型定义3.2 栈类型的实现栈类型的实现3
2、.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现练习9/16/20249/16/2024栈的定义和特点定义：限定仅在表尾表尾进行插入或删除操作的线 性表，表尾栈顶栈顶，表头栈底栈底，不含 元素的空表称空栈。特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)3.1 栈的类型定义栈的类型定义9/16/20249/16/2024 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a
3、1 端为栈底。 基本操作：基本操作： ADT Stack栈的抽象数据类型定义9/16/20249/16/2024InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()9/16/20249/16/2024 InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。9/16/20249/16/2024StackE
4、mpty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈， 则返回 TRUE，否则 FALE。9/16/20249/16/2024 StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个 数，即栈的长度。9/16/20249/16/2024 GetTop(S, &e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an 9/16/20249/16/2024 ClearStack(&S)初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。9/16/20249/16/2024 Push(&S, e) 初始条件：栈 S 已存
5、在。 操作结果：插入元素 e 为新的 栈顶元素。a1a2ane 9/16/20249/16/2024Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 e = an9/16/20249/16/20243.2栈类型的实现栈类型的实现3.2.1 顺序栈顺序栈3.2.1 链链 栈栈9/16/20249/16/2024 类似于线性表的顺序映象实现，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指向表尾的指针top，指示栈顶元素在顺序栈中的位置，称为栈顶指针栈顶指针。连续存储单元的基址用指针base指示，
6、称为栈底指针栈底指针。3.2.1 顺序栈顺序栈9/16/20249/16/2024/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;top的初值指向栈底：的初值指向栈底：top=base，此条件也可作为判栈空的条件；，此条件也可作为判栈空的条件； 在实际使用中，在实际使用中，top 始终指向栈顶元素的下一个位置上；始终指向栈顶元素的下一个位置上；入栈（插入新的栈顶元素）：入栈（插入新的栈顶元素）：top
7、增增1；出栈（删除栈顶元素）：出栈（删除栈顶元素）： top减减1。9/16/20249/16/2024top=0123450栈栈S 空空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶前的空位置，初值为前的空位置，初值为0top123450进栈进栈Atop出栈出栈栈栈 满满BCDEF设数组大小为设数组大小为Mtop=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空 0M-1栈栈1底底栈栈1顶顶栈栈2
8、底底栈栈2顶顶为减少溢出的概率，可以在同一段内存中同时使用两个栈为减少溢出的概率，可以在同一段内存中同时使用两个栈.StackLength(S)basebasebase9/16/20249/16/2024 Status InitStack (SqStack &S, int maxsize) / 构造一个最大空间为 maxsize 的空顺序栈 S S.base = new ElemTypemaxsize; if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = maxsize; return OK;9/16/2024
9、9/16/2024 Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满 return OVERFLOW; *S.top+ = e; return OK;9/16/20249/16/2024Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用 e 返回其值，并返回OK； / 否则返回ERROR if (S.top = = S.base) return ERROR; e = *-S.top; return OK;9/16/20249/
10、16/20243.2.1 链链 栈栈注意注意: 链栈中链栈中指针的方向指针的方向栈顶指针a1anan-1栈底结点定义结点定义typedef struct node int data; struct node *link; node;9/16/20249/16/2024入栈入栈出栈出栈 .栈底toptopxptop .栈底topq9/16/20249/16/20243.3 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序问题行编辑程序问题 例四、例四、 迷宫求解迷宫求解 例五、例五、 表达式求值表达式求值 例六、例六、 实现
11、递归实现递归9/16/20249/16/2024 例一、例一、 数制转换数制转换 算法基于原理： (N)d1 = (N div d2)d2 + N mod d2 9/16/20249/16/2024例如：例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序9/16/20249/16/2024void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; w
12、hile (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion9/16/20249/16/2024例二、例二、 括号匹配的检验括号匹配的检验 假设在表达式中，只有（）（）两种括号，如：（）（）、（ ）等为正确的格式，（ ）或（ ）或 （）（） ）均为不正确的格式。 检验括号是否匹配的方法可用:“期待的急迫程度”这个概念来描述。9/16/20249/16/2024分析可能出现的不匹配的情况: :到来的右括号非是所“期待”的;例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是“不速之客”;直到结束，也没有到来所“期待
13、”的括号;9/16/20249/16/2024算法的设计思想：算法的设计思想：1）凡出现左括号左括号，则进栈进栈；2）凡出现右括号右括号，首先检查栈是否空： 若栈空栈空，则表明该“右括号右括号”多余多余不匹配不匹配 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括号出栈左括号出栈” 否则表明不匹配不匹配3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达式中匹配正确匹配正确 否则表明“左括号左括号”有余有余不匹配不匹配9/16/20249/16/2024Status matching(string& exp) int state = 1; i=0； while (iLength(
14、exp) & state) switch (expi) case ”(” ,”: case”)”: if (StackEmpty(S)&state) return OK; .作业作业 9/16/20249/16/2024例三、行编辑程序问题例三、行编辑程序问题 常用的文本编辑器如：常用的文本编辑器如：word、记事、记事本，最简单的文本编辑器实现的功能是：本，最简单的文本编辑器实现的功能是：接受用户从终端输入的程序或数据，并接受用户从终端输入的程序或数据，并存入用户的数据区。存入用户的数据区。 思考：如何实现？思考：如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器” ” ? ?
15、 并不恰当！9/16/20249/16/2024 设立一个输入缓冲区，用以接受设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存用户输入的一行字符，然后逐行存入用户数据区入用户数据区; 并假设并假设“#”为退格为退格符，符，“”为退行符。为退行符。 在用户输入一行的过程中，允在用户输入一行的过程中，允许用户输入出差错，并在发现有误时许用户输入出差错，并在发现有误时 可以及时更正。可以及时更正。合理的作法是：9/16/20249/16/2024假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while
16、(*s) putchar(*s+);9/16/20249/16/2024Void LineEdit ( ) InitState(S); ch=getchar( ); DestroyStake(S);/ LineEdit 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
17、(ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；将从栈底到栈顶的字符传送至调用过程的数据区；9/16/20249/16/2024例四、例四、 迷宫求解迷宫求解通常用的是“穷举求解穷举求解”的方法9/16/20249/16/20244上1右2下3左 1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$9/16/20249/16/2024求迷宫路径算法的基本思想基本思想是：若当前位置若当前位置“可通可通”，则纳入路径，继续
18、前，则纳入路径，继续前进进;若当前位置若当前位置“不可通不可通”，则后退，换方向继，则后退，换方向继续探索续探索;若四周若四周“均无通路均无通路”，则将当前位置从路径，则将当前位置从路径中删除出去。中删除出去。 所谓当前位置所谓当前位置“可通可通”，即此位置既不在当，即此位置既不在当前路径上，也不是已删除掉的前路径上，也不是已删除掉的“不可通不可通”的的位置位置; 9/16/20249/16/2024设定当前位置的初值为入口位置； do 若当前位置可通若当前位置可通， 则则将当前位置插入栈顶插入栈顶； 若若该位置是出口位置，则则算法结束； 否则切换否则切换当前位置的东邻方块为 新的当前位置；
19、否则否则 while (栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法： 9/16/20249/16/2024若若栈不空且栈顶位置尚有其他方向未被探索栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通栈不空但栈顶位置的四周均不可通，则则删去栈顶位置；/ 从路径中删去该通道块从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置， 直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。9/16/20249/16
20、/2024 typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中的“坐标位置” int di; / 从此通道块走向下一通道块的“方向” SElemType; / 栈的元素类型 9/16/20249/16/2024 Status MazePath ( MazeType maze, PosType start,PosType end ) / 若迷宫maze中从入口 start到出口 end的通道,则求得一条存 / 放在栈中(从栈底到栈顶),并返回TRUE；否则返回FALSE InitStack(S); curpos = sta
21、rt; / 设定“当前位置”为“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 当前位置可通,即未曾走过的通道块 FootPrint (curpos); / 留下足迹 e = ( curstep, curpos, 1 ); Push (S,e); / 加入路径 if ( curpos = end ) return (TRUE); / 到达终点（出口） curpos = NextPos ( curpos, 1 ); /下一位置是当前位置东邻 curstep+; / 探索下一步 /if 9/16/20249/16/2024 else / 当前位置
22、不能通过 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通过的标记，并退回一步 / while if (e.di1时，先把上面时，先把上面n-1个圆盘从个圆盘从A移到移到B,然后将然后将n号盘从号盘从A移到移到C,再将再将n-1个盘从个盘从B移到移到C。即把求解即把求解n个圆盘的个圆盘的Hanoi问题转化为求解问题转化为求解n-1个圆盘的个圆盘的Hanoi问题，依次类推，问题，依次类推，直至转化成只有一个圆盘的直至转化成只有一个圆盘的Hanoi问
23、题问题 算法算法算法算法：ABC1239/16/20249/16/20240void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从将编号为的圆盘从x移到移到z3 else 4hanoi(n-1, x, z, y); /将将x上编号为至上编号为至n-1的圆盘移到的圆盘移到y, z作辅助塔作辅助塔5 move(x, n, z); / 将编号为将编号为n的圆盘从的圆盘从x移到移到z6 hanoi
24、(n-1, y, x, z); / 将将y上编号为至上编号为至n-1的圆盘移到的圆盘移到z, x作辅助塔作辅助塔 7 8 9/16/20249/16/2024 main() int m; printf(Input number of disks”); scanf(%d,&m); printf(”Steps : %3d disks”,m); 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
25、,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 63219/16/20249/16/2024 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)
26、(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) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 62211339/16/20249/16/2024 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);
27、(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) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 02233119/16/20249/16/2024 main() int m; printf(Input the number of disks sca
28、nf(%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) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0栈空3 A B C 02 B A C 82211339/16/20249
29、/16/2024回文游戏：顺读与逆读字符串一样（不含空格）回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串读入字符串2.去掉空格（原串）去掉空格（原串）3.压入栈压入栈4.原串字符与出栈字符依次比较原串字符与出栈字符依次比较 若不等，非回文若不等，非回文 直到栈空都相等，回文直到栈空都相等，回文字符串：字符串：“madam im adam”栈的其它应用栈的其它应用9/16/20249/16/20249/16/20249/16/2024队列的定义及特点队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线
30、性表另一端进行删除的线性表队尾队尾(rear)允许插入的一端允许插入的一端队头队头(front)允许删除的一端允许删除的一端队列特点：先进先出队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)双端队列双端队列a1 a2 a3.an 端1端2入队出队入队出队3.4 队列的类型定义队列的类型定义9/16/20249/16/2024 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， a
31、n 端为队列尾队列尾基本操作：基本操作：队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue9/16/20249/16/2024队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()9/16/20249/16/2024InitQueue(&Q) 操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q) 初始条件：初始条件
32、：队列Q已存在。 操作结果：操作结果：队列Q被销毁， 不再存在。9/16/20249/16/2024QueueEmpty(Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：若Q为空队列，则 返回TRUE，否则返回FALSE。9/16/20249/16/2024 QueueLength(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：返回Q的元素个数，即队列的长度。9/16/20249/16/2024 GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：用e返回Q的队头元素。a1a2an 9/16/20249/16/2024 ClearQ
33、ueue(&Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：将Q清为空队列。9/16/20249/16/2024 EnQueue(&Q, e) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane 9/16/20249/16/2024 DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an 9/16/20249/16/20243.5 队列类型的实现队列类型的实现 链链 队队 列列链式映象循环队列循环队列顺序映象9/16/20249/16/2024 type
34、def struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;链队列链队列链式映象9/16/20249/16/2024typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列9/16/20249/16/2024 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.
35、front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;9/16/20249/16/2024 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = new QNode; if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;9/16/2024
36、9/16/2024 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; free (p); return OK;if (Q.rear = p) Q.rear = Q.front;a1Q.frontQ.rear9/16/20249/16/2024队列的顺序存储结构队列的顺序存储结构实
37、现：用一维数组实现实现：用一维数组实现sqM-1队空rear = 0front=0123450123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针设两个指针front,rear,约定：约定：rear指示队尾元素下一位置；指示队尾元素下一位置；front指示队头元素，指示队头元素，初值初值front=rear=0。空队列条件：空队列条件：front=rear入队列：入队列：sqrear+=x;出队列：出队列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出队J1J2J3fron
38、tfrontfront顺序映象9/16/20249/16/2024实现：利用实现：利用“取模取模”运算运算入队：入队： sqrear=x; rear=(rear+1)%M; 出队：出队： x=sqfront; front=(front+1)%M; 队满、队空判定条件队满、队空判定条件存在问题存在问题设数组大小为设数组大小为M，则：则：当当front=0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出当当front 0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出假溢出假溢出解决方案解决方案 ？队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素
39、向下移动浪费时间，效率低浪费时间，效率低发生假溢出时再移动发生假溢出时再移动 循环队列循环队列循环队列循环队列基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让sq0接在接在sqM-1之后，之后，若若rear=M,则令则令rear=0;0M-11frontrear.9/16/20249/16/2024012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.1.另外另外设一个标志设一
40、个标志以区别队空、队满以区别队空、队满2 2. .少用一个元素空间少用一个元素空间： 队空：队空：front = rearfront = rear 队满：队满：( (rear+1)%rear+1)% M = frontM = frontrear9/16/20249/16/2024#define MAXQSIZE 100 /最大队列长度最大队列长度typedef struct QElemType *base; / 动态分配存储空间动态分配存储空间 int front; / 头指针，若队列不空，头指针，若队列不空， / 指向队列头元素指向队列头元素 int rear; / 尾指针，若队列不空，指向
41、尾指针，若队列不空，指向 / 队列尾元素队列尾元素 的下一个位置的下一个位置 SqQueue;循环队列的实现9/16/20249/16/2024 Status InitQueue (SqQueue &Q, int maxsize) / 构造一个最大存储空间为 maxsize 的 / 空循环队列 Q Q.base =(QElemType *)malloc (maxsize *sizeof(QElemType); if (!Q.base) exit (OVERFLOW); Q.front = Q.rear = 0; return OK; 9/16/20249/16/2024Status EnQue
42、ue (SqQueue &Q, ElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;9/16/20249/16/2024 Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR;
43、 e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;9/16/20249/16/2024练练 习习1、设设一一数数列列的的顺顺序序为为1，2，3，4，5，6，通通过过队队列列操操作作可可以以得得到到（ ）的输出序列。的输出序列。 A、 3，2，5，6，4，1 B、 1，2，3，4，5，6 C、 6，5，4，3，2，1 D、 4，5，3，2，6，12、若若进进栈栈序序列列为为整整数数1、2、3，则则通通过过入入进进栈栈和和出出栈栈操操作作可可能能得得到到的的整整数数的不同排列个数为（的不同排列个数为（ ）。）。 A、3
44、B、4 C、5 D、6BC9/16/20249/16/2024 读读程序或函数，回答程序或函数，回答问题问题 3、设链设链式存式存储线储线性表的数据性表的数据类类型定型定义义如下如下typedef char DataType;typedef struct node DataType data; Struct node *next; ListNode; 带头结带头结点的点的链链表表L是一个是一个递递增有序增有序链链表，按表，按链链接接顺顺序，它序，它们们的的值值依次依次为为1、3、5、7、9、10、11、14则经则经函数函数调调用用 Ex(L，5，10)后，后，链链表表 L中的元素依次是什么？中
45、的元素依次是什么？试试指出函数指出函数Demo()完成什么工作。完成什么工作。void Ex(ListNode *L, DataType min, DataType max) ListNode *p, *q, *r;q = L; p = L-next; /链链表表L带头结带头结点点while(p & p-data next;while(p & p-data next; free(r);q-next = p; 9/16/20249/16/20244、设链设链式存式存储顺储顺序表的数据序表的数据类类型定型定义义如下，如下，试试指出以下函数完成什么工作。指出以下函数完成什么工作。如指如指针为针为 L
46、的的链链表（表（带头结带头结点）有点）有10个元素，按个元素，按链链接接顺顺序，它序，它们们的的值值依次依次为为 4、3、4、5、3、6、4、7、3、5，则经则经函数函数调调用用 Tp(L)后，后，链链表表 L中的元素依次是什么？中的元素依次是什么？typedef char DataType;typedef struct node DataType data; Struct node *next; ListNode;void Tp(ListNode *L) ListNode *p, *q, *r;for(p = L; p; p = p-next) for(q = p, r = q-next;
47、r; r = q-next) if (r-data != p-data) q = r; else q-next = r-next; free(r); 9/16/20249/16/2024status Ju (DlistNode *h) DlistNode *p, *q; p = h-next; q = h-prior; while(p!=q & p-prior != q) if(p-data = q-data) p = p-next; q= q-prior; else return False; return True; 5、以下函数中，、以下函数中，h是是带头结带头结点的双向循点的双向循环链环链表的表的头头指指针针。说说明函数的功能明函数的功能 。 9/16/20249/16/2024http:/
