《数据结构教学》cha(1)

1、.第三章 栈和队列.通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。 线性表线性表 栈栈 队列队列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栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型.3.1 栈的类型定义栈的类型定义3.2 栈类型的实现栈类型的实现3.3 栈的应用举例栈的应用举例3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现. 栈的类型定义栈的类型定义 ADT St

2、ack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack.栈的特点栈的特点栈：栈：限定只能在表的一端进行插入和删除限定只能在表的一端进行插入和删除的特殊的线性表的特殊的线性表 设栈设栈s=（a1，a2，. . . ,ai，. . . ，an），其中其中a1是栈底元素，是栈底元素， an是栈顶元素。是栈顶元素。 a1 a2 . an进栈进栈出栈出栈栈顶栈顶栈底栈底.设数组设数组S是一个顺序栈，栈的最大容量是一个顺序

3、栈，栈的最大容量stacksize=4 ，初始状态，初始状态top=0栈中的运算：栈中的运算：1.设置空栈设置空栈 ； 2. 插入一个新的栈顶元素插入一个新的栈顶元素 3. 删除栈顶元素；删除栈顶元素； 4. 读取栈顶元素读取栈顶元素 。 10S42310basestop=xtop=top+1top 10 25 30S42310topbasetop=top-1x=stop栈空栈空10进进栈栈30出栈出栈S42310top=0top栈满栈满 top=stacksize 10 25 30 40S42310top=4base.栈的定义（顺序表）#define STACK_INI_SIZE 100 /

4、存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef structSElemType *base;SElemType *top;int stacksize;SqStack;.InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit(). InitStack(&S) 操作结果：构造一个空栈

5、S。.DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。.StackEmpty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。.StackLength(S)初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。. GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an . ClearStack(&S)初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。.Push(&S, e) 初始条件：栈 S 已存

6、在。 操作结果：插入元素 e 为新的栈顶元素。a1a2ane .Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 .3.2栈类型的实现栈类型的实现顺序栈顺序栈链栈链栈./- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 类似于线性表的顺序映象实现，指向表尾的

7、指针可以作为栈顶指针。. Status InitStack (SqStack &S)/ 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 ; S.stacksize = STACK_INIT_SIZE; return OK;. Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (Elem

8、Type *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;.Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if = S.

9、base) return ERROR; e = *-S.top; return OK;注意：判定栈空的条件注意：判定栈空的条件.Status GetTop (SqStack &S, SElemType &e) / 若栈不空，用e返回其值，并返回OK； / 否则返回ERROR if = S.base) return ERROR; e = *(S.top-1); return OK;.Status StackEmpty(SqStack S)if(S.top=S.base) return 1;else return 0;.栈顶指针链栈链栈a1an注意注意: 链栈中链栈中指针的方向指针

10、的方向an-1. 栈的应用举例栈的应用举例例一、例一、 数制转换数制转换例二、例二、 括号匹配的检验括号匹配的检验例三、例三、 行编辑程序问题行编辑程序问题例四、例四、 迷宫求解迷宫求解例五、例五、 表达式求值表达式求值例六、例六、 实现递归实现递归. 例一、例一、 数制转换数制转换 算法基于原理： N = (N div d)d + N mod d .例如：例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序.void conversion () Ini

11、tStack(S); scanf (%d,&N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion.例二、例二、 括号匹配的检验括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）)均为不正确的格式。则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。.分析可能出现的不匹配不匹配的情况: 到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客

12、”； 直到结束，也没有到来所“期待”的括弧。.算法的设计思想：算法的设计思想：1）凡出现左括弧左括弧，则进栈进栈；2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余， 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” ， 否则表明不匹配不匹配。3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达式中匹配正确匹配正确， 否则表明“左括弧左括弧”有余有余。.Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch

13、 of expi case 左括弧:Push(S,expi); i+; break; case”)”: if(NOT StackEmpty(S)&GetTop(S)=“(“ Pop(S,e); i+; else state = 0; break; if (StackEmpty(S)&state) return OK; .例三、行编辑程序问题例三、行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器” ? 并不恰当！. 设立一个输入缓冲区，用以接受设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存用户输入的一行字符，然后逐行存入用户数据

14、区，并假设入用户数据区，并假设“#”为退格为退格符，符，“”为退行符。为退行符。 在用户输入一行的过程中，允许在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时用户输入出差错，并在发现有误时 可以及时更正。可以及时更正。合理的作法是：.假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while (*s) putchar(*s+);. while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearS

15、tack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；.例四、例四、 迷宫求解迷宫求解通常用的是“穷举求解穷举求解”的方法# #$# #$# $# # # # # #.求迷宫路径算法的基本思想基本思想是： 若当前位置若当前位置“可通可通”，则纳入路，则纳入路径，继续前进径，继续前进

16、; 若当前位置若当前位置“不可通不可通”，则后退，则后退，换方向继续探索换方向继续探索; 若四周若四周“均无通路均无通路”，则将当前，则将当前位置从路径中删除出去。位置从路径中删除出去。.设定当前位置的初值为入口位置； do 若当前位置可通若当前位置可通， 则则将当前位置插入栈顶插入栈顶； 若若该位置是出口位置，则则算法结束； 否则切换否则切换当前位置的东邻方块为 新的当前位置； 否则否则 while (栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法： .若若栈不空且栈顶位置尚有其他方向未被探索栈不空且栈顶位置尚有其他方向未被探索，则则设定新的当前

17、位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空但栈顶位置的四周均不可通栈不空但栈顶位置的四周均不可通，则则删去栈顶位置；/ 从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置， 直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。. 限于二元运算符的表达式定义: 表达式表达式 := (操作数操作数) + (运算符运算符) + (操作数操作数) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数例五、例五、 表达式求值表达式求值. 表达式的三种标识方法：

18、表达式的三种标识方法：设设 Exp = S1 + OP + S2则称则称 OP + S1 + S2 为前缀表示法前缀表示法 S1 + OP + S2 为中缀表示法中缀表示法 S1 + S2 + OP 为后缀表示法后缀表示法 .一个中缀式到其他式子的转换方法这里给出一个中缀表达式a+b*c-(d+e)第一步：按照运算符的优先级对所有的运算单位加括号式子变成：(a+(b*c)-(d+e)第二步：转换前缀与后缀表达式前缀：把运算符号移动到对应的括号前面则变成拉：-(+(a*(bc)+(de)把括号去掉：-+a*bc+de前缀式子出现后缀：把运算符号移动到对应的括号后面则变成拉：(a(bc)*)+(d

19、e)+)-把括号去掉：abc*+de+-后缀式子出现前缀式，后缀式是不需要用括号来进行优先级的确定的。.例如: Exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论结论:1）操作数之间的相对次序不变）操作数之间的相对次序不变;2）运算符的相对次序不同）运算符的相对次序不同;3）中缀式丢失了括弧信息， 致使运算的次序不确定;4)前缀式的运算规则前缀式的运算规则为:连续出现的两个操作数和在它们连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一之前且紧靠它们的运算符构成一个最

20、小表达式个最小表达式; 5)后缀式的运算规则后缀式的运算规则为: 运算符在式中出现的顺序恰为运算符在式中出现的顺序恰为 表达式的运算顺序表达式的运算顺序; 每个运算符和在它之前出现每个运算符和在它之前出现 且且 紧靠它的两个操作数构成一个最小紧靠它的两个操作数构成一个最小 表达式。表达式。.如何从后缀式求值？如何从后缀式求值？先找运算符，先找运算符， 再找操作数再找操作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f.l如何从原表达式求得后缀式？如何从原表达式求得后缀式？ 每个运算符的运算次序要由它之后它之后的一个运算符的一个运算符来定，在后缀式中，优先数

21、高的运算符领先于优先数低的运算符。分析 “原表达式” 和 “后缀式”中的运算符:原表达式: a + b c d / e f 后缀式: a b c + d e / f .从原表达式求得后缀式的规律为：从原表达式求得后缀式的规律为：1) 设立操作数栈；栈；2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”；3) 若当前字符是操作数， 则直接发送给后缀式。.4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：从原表达式求得后缀式的规

22、律为：.void transform(char suffix , char exp ) InitStack(S); Push(S, #); Scanf(EXP,ch); /p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree .switch (ch) case ( : Push(S, ch); break; case ) :

23、Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch.将中缀表达式转换为前缀表达式：将中缀表达式转换为前缀表达式：(1)初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2)从右至左扫描中缀表达式；(3)遇到操作数时，将其压入S2；(4)遇到运算符时，比较其与S1栈顶运算符的优先级：

24、(4-1)如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；(4-2)否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；(4-3)否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5)遇到括号时：(5-1)如果是右括号“)”，则直接压入S1；(5-2)如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；(6)重复步骤(2)至(5)，直到表达式的最左边；(7)将S1中剩余的运算符依次弹出并压入S2；(8)依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。.将中缀表达

25、式转换为后缀表达式：将中缀表达式转换为后缀表达式：与转换为前缀表达式相似，遵循以下步骤：(1)初始化两个栈：运算符栈S1和储存中间结果的栈S2；(2)从左至右扫描中缀表达式；(3)遇到操作数时，将其压入S2；(4)遇到运算符时，比较其与S1栈顶运算符的优先级：(4-1)如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；(4-2)否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；(4-3)否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；(5)遇到括号时：(5-1)如果

26、是左括号“(”，则直接压入S1；(5-2)如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；(6)重复步骤(2)至(5)，直到表达式的最右边；(7)将S1中剩余的运算符依次弹出并压入S2；(8)依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。.例六、实现递归例六、实现递归 将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：. 保存被调函数

27、的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：.多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区 .递归工作栈：递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：当前活动记录：栈顶记录指示当前层的 执行情况。当前环境指针

28、：当前环境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数同一函数进行嵌套调用，例如：.void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 2 if (n=1)3 move(x, 1, z); / 将编号为的圆盘从x移到z4 else 5 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔6 move(x, n, z); / 将编号为n的圆盘从x移到z7 hanoi(n-1, y, x, z); /

29、 将y上编号为至n-1的8 /圆盘移到z, x作辅助塔9 .3.4 队列的类型定义队列的类型定义 a1 , a2 , a3 , a4 , an-1 , an 队 列 示 意 图队头队尾 队列队列是一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为先进先出先进先出（FIFOFIFO）表）表。.队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为

30、队列尾队列尾基本操作：基本操作： ADT Queue.队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit().InitQueue(&Q) 操作结果：操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：队列Q被销毁

31、， 不再存在。. QueueEmpty(Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。. QueueLength(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：返回Q的元素个数，即队列的长度。. GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：用e返回Q的队头元素。a1a2an . ClearQueue(&Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：将Q清为空队列。. EnQueue(&Q, e) 初始条件：初始条件：队列Q已存在。 操作

32、结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane . DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an .3.5 队列类型的实现队列类型的实现3.5.1 链队列链队列链式映象循环队列循环队列顺序映象.3.5.1 链队列链队列链式映象 an a2 a1 an a2 a1 删删 除除 一个元素一个元素 添加添加 一个元素一个元素e a1 a2 anQ.frontQ.rear 队头队尾.链队列的实现链队列的实现 typedef struct QNode / 结点类型结点类型 QElemT

33、ype data; struct QNode *next; QNode, *QueuePtr;.typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;a1an空队列空队列. Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next

34、 = NULL; return OK;. 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;. Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e

35、 返回其值，并返回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;.3.5.2 循环队列循环队列顺序映象顺序存储结构(a) 线性队列 (b) 循环队列.(a)线性队列线性队列 3 2 1 0 (a)rear=front=0(队空）队空） e3 (c)e1,e2出队，出队，e3入队入队 队队 满满rear =2fr

36、ont e1 e2 (b)rearfront(b)e1,e2 入队入队队空时，队空时， 令令rear=front=0，当当有新元素入队时，尾指针加有新元素入队时，尾指针加1，当，当有元素出队时，头指针加有元素出队时，头指针加1。frontrear =3.(b) 循环队列循环队列 rear front 0 1 2 3(3) 队空队空队满条件队满条件：注：实际上为了避免与队空标注：实际上为了避免与队空标志冲突，还留有一个空间。志冲突，还留有一个空间。将头尾连接成一将头尾连接成一个环，形成循环个环，形成循环队列。队列。 rear(1)一般情况一般情况 front 0 1 2 3e4e3 (2) 队满

37、队满 front e3 e4 0 1 2 3 reare2.循环队列的实现循环队列的实现#define MAXQSIZE 100 /最大队列长度 typedef struct ElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;. Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType

38、); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; .Status EnQueue (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;. Status DeQueue (SqQueue &Q, ElemType &

39、e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;.例例1：舞伴问题：舞会上，男士们和女士们进入舞厅舞伴问题：舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待

40、下一轮舞曲。则较长的那一队中未配对者等待下一轮舞曲。 舞伴问题的类型描述：舞伴问题的类型描述：typedef struct char name20; char sex; /性别，F表示女性，M表示男性 Person;typedef Person datatype; /队列中元素的数据类型为Person 3.5.3 队列的应用例子队列的应用例子.舞伴问题的算法：舞伴问题的算法：void DancePartner(Person dancer,int num) /结构数组dancer中存放跳舞的男女，num是跳舞的人数。 int i; Person p; SqQueue *Mdancers,*Fda

41、ncers; InitQueue(Mdancers); /男士队列初始化 InitQueue(Fdancers); /女士队列初始化 for( i=0; i(8,8)*/ int i,j,find=0,di,k;SqQueue Q;InitQueue(Q,200);ElemType e,d;e.i=1;e.j=1;e.pre=-1;EnQueue(Q,e); /(1,1)入队入队 mg11=*; /将其赋值将其赋值*,以避免回过来重复搜索以避免回过来重复搜索 while (!QueueEmpty(Q) & !find) k=Q.front;DeQueue(Q,e); /出队出队, 不是循环队列不是循环队列,该元素仍在队中该元素仍在队中i=e.i; j=e.j;if (i=8 & j=8)/*找到了出口找到了出口,输出路径输出路径*/ find=1;cout找到一条路径找到一条路径:endl;print(Q,e);/调用调用print函数输出路径函数输出路径return;.for (di=0;di=3;di+)/把每个可走的方块插入队列中把每个可走的方块插入队列中 switch(di) case 0:i=e.i; j=e.j+1; break; /