《《数据结构》(C语言版)第三章_栈和队列》由会员分享，可在线阅读，更多相关《《数据结构》(C语言版)第三章_栈和队列（71页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列3.1 栈栈3.2 栈的应用举例栈的应用举例3.4 队列队列3.3 栈与递归的实现栈与递归的实现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栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型2学习提要：学习提要：1.1.掌握栈和队列这两种抽象数据类型的特点，掌握栈
2、和队列这两种抽象数据类型的特点， 并能在相应的应用问题中正确选用它们。并能在相应的应用问题中正确选用它们。2.2.熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应 注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.3.熟练掌握循环队列和链队列的基本操作实现熟练掌握循环队列和链队列的基本操作实现 算法，特别注意队满和队空的描述方法。算法，特别注意队满和队空的描述方法。4.4.理解递归算法执行过程中栈的状态变化过程。理解递归算法执行过程中栈的状态变化过程。重难点内容：重难点内容： 顺序栈的相关操作、循环队列的判空判满顺序栈的相关操作、循环队
3、列的判空判满33.1 栈（栈（stack）3.1.1 栈的类型定义栈的类型定义3.1.2 栈的表示和实现栈的表示和实现4 栈的栈的定义：定义：限定仅在限定仅在表尾表尾进行插入或删除进行插入或删除操作的线性表。不含元素的空表称操作的线性表。不含元素的空表称空栈。空栈。ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)特点：特点：后进先出（后进先出（LIFO）3.1.1 栈的类型定义栈的类型定义表尾表尾栈顶栈顶 表头表头栈底栈底5 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i
4、=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack栈的抽象数据类型定义：栈的抽象数据类型定义：6InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit( )7一、顺序栈一、顺序栈3.1.2 栈的表示和实现栈的表示和实现/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREME
5、NT 10; typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; SqStack;8实现：实现：一维数组一维数组sMtop123450进栈进栈Push(&S, e)A栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450空栈空栈topbasebasetoptop出栈出栈Pop(&S,&e)123450ABCDEFtoptoptoptop栈空basetoptop栈底指针
6、base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置9 Status InitStack (SqStack &S) / 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;10 Status Push (SqStack &S, SElemType e) if (S.top - S.bas
7、e = S.stacksize) /栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top + + = e; return OK; 11Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的
8、栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if ( S.top = S.base ) return ERROR; e = *- -S.top; return OK;120M-1栈栈1底底栈栈1顶顶栈栈2底底栈栈2顶顶在一个程序中同时使用两个栈在一个程序中同时使用两个栈13二、链栈二、链栈 栈的链式存储结构。栈的链式存储结构。 栈顶指针栈顶指针就是链表的头指针。就是链表的头指针。注意注意: 链栈中链栈中指针的方向指针的方向栈顶指针栈顶指针a1anan-114v入栈操作入栈操作push(&S, e)v 出栈操作出栈操作pop(&S,&e) .栈底toptopxptop .
9、栈底topqp-next=top ; top=p q=top ; top=top-next 153.2 栈的应用栈的应用3.2.1 数制转换数制转换3.2.2 括号匹配的检验括号匹配的检验3.2.3 行编辑程序问题行编辑程序问题3.2.4 迷宫求解迷宫求解3.2.5 表达式求值表达式求值163.2.1 数制转换数制转换十进制十进制N和其他和其他d进制数的转换原理进制数的转换原理: N=( N div d )*d + N mod d 其中：其中：div为为整除整除运算，运算， mod为为求余求余运算运算17toptop4top40top405 例如：例如： (1348)10=(2504)8，其运
10、算过程如下：，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序top405218 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 ); /conversion193.3.2 括号匹配的检验括号匹配的检验
11、则则 检验括号是否匹配检验括号是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。假设在表达式中假设在表达式中（）或（）或（ ）等为正确的格式，等为正确的格式，（ ）或（）或（ ）或）或 （）（）)均均为不正确的格式。为不正确的格式。20分析可能出现的分析可能出现的不匹配不匹配的情况的情况: :到来的右括弧到来的右括弧并非是所并非是所“期待期待”的；的；例如：例如：考虑下列括号序列：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是到来的是“不速之客不速之客”；直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括弧。的括弧。21算
12、法的设计思想：算法的设计思想：1）凡出现）凡出现左括弧左括弧，则，则进栈进栈；2）凡出现）凡出现右括弧右括弧，首先检查栈是否空，首先检查栈是否空 若若栈空栈空，则表明该，则表明该“右括弧右括弧”多余多余， 否则否则和栈顶元素和栈顶元素比较，比较， 若若相匹配相匹配，则，则“左括弧出栈左括弧出栈” ， 否则表明否则表明不匹配不匹配。3）表达式检验结束时，）表达式检验结束时， 若若栈空栈空，则表明表达式中，则表明表达式中匹配正确匹配正确， 否则表明否则表明“左括弧左括弧”有余有余。223.2.3 行编辑程序问题行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器
13、” ? 不恰当不恰当!合理的作法是：合理的作法是： 设立一个输入缓冲区，用以接受用设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户输入的一行字符，然后逐行存入用户数据区，并假设户数据区，并假设“#”为退格符，为退格符，“”为退行符。为退行符。23假设从终端接受了这样两行字符：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行： while (*s) putchar(*s+);24 while (ch != EOF & ch != n) switch (ch) case # :
14、 Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；253.2.4 迷宫求解迷宫求解通常用的是通常用的是“穷举求解穷举求解”的方法。的方法。26求迷宫路径算法的求迷宫路径算法的基本思想基本思想是：是：v若当前位置若当
15、前位置“可通可通”，则纳入路，则纳入路径，径， 继续前进继续前进;v若当前位置若当前位置“不可通不可通”，则，则后退，换方向继续探索后退，换方向继续探索;v若四周若四周“均无通路均无通路”，则将，则将当前位置从路径中删除出去。当前位置从路径中删除出去。27设定当前位置当前位置的初值为入口位置； do 若若当前位置可通当前位置可通， 则则将当前位置插入栈顶插入栈顶； 若若该位置是出口位置，则则算法结束； 否则切换否则切换当前位置的东邻方块为 新的当前位置； 否则否则 while (栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法： 28若若栈不空栈不空
16、且且栈顶位置尚有其他方向未被探索栈顶位置尚有其他方向未被探索，则则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空栈不空但但栈顶位置的四周均不可通栈顶位置的四周均不可通，则则删去栈顶位置；/ 从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置， 直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。29 typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中 的 “坐标位置” int di; / 从此通道块走向下一 通道块的“方向” SElem
17、Type; / 栈的元素类型30 Status MazePath ( MazeType maze, PosType start, PosType end ) InitStack(S); curpos = start; / 设定“当前位置”为“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 当当前前位位置置可可以以通通过过，即即是是未未曾曾走走到到过过的的通道块通道块 else while ( !StackEmpty(S) ); return (FALSE);/ MazePath 31FootPrint (curpos); e = ( curs
18、tep, curpos, 1 );Push (S,e); / 加入路径if ( curpos = end ) return (TRUE); / 到达终点curpos = NextPos ( curpos, 1 ); / 下一位置是当前位置的东下一位置是当前位置的东邻邻curstep+;32 else / 当前位置不能通过 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通过的标记，并退回一步 / while if (e.di4) e.di+; Pu
19、sh ( S, e); / 换下一个方向探索 curpos = NextPos (curpos, e.di ); / 设定当前位置是该新方向上的相邻块 / if / if / else33 限于二元运算符的表达式定义: Exp = S1 OP S2 操作数操作数 : 变量、常量、表达式变量、常量、表达式 运算符运算符 : 算术运算符、关系运算符、算术运算符、关系运算符、 逻辑运算符逻辑运算符 界限符：界限符：括号、结束符括号、结束符3.2.5 表达式求值表达式求值34表达式求值的算法：表达式求值的算法：算符优先法算符优先法根据运算优先关根据运算优先关系的规定来实现对表达式的编系的规定来实现对表
20、达式的编译或解释执行。译或解释执行。35例：例：3 * ( 7 2 )OPND栈栈OPTR栈栈CCC3*(C7CC2C275C*531536例：例：3 * ( 7 2 ) OPTR栈栈 OPND栈栈 输入输入 操作操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 * ( 7 2 ) # PUSH( OPTR, * )3 # * 3 ( 7 2 ) # PUSH( OPTR, ( )4 # * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPN
21、D, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND )37OperandType EvaluateExpression( ) / 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #)
22、if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是运算符则进栈 else / while return GetTop(OPND); / EvaluateExpression 38switch ( precede(GetTop(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch39r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程
23、程33.3 栈栈与递归的实现与递归的实现40 当在一个函数的运行期间调用当在一个函数的运行期间调用另一个函数另一个函数时，在运行该被调用函数时，在运行该被调用函数之前之前，需先完成，需先完成三件事三件事: : (1) (1)将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息信息传传递给被调用函数递给被调用函数保存保存; ; (2) (2)为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区; ; (3) (3)将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。41 从被调用函数从被调用函数返回返回调用函数调用函数之前之前，应该完成应该完成: : (1) (1)保
24、存保存被调函数的被调函数的计算结果计算结果; ; (2) (2)释放释放被调函数的被调函数的数据区数据区; ; (3) (3)依照被调函数保存的返回地址依照被调函数保存的返回地址将将控制转移控制转移到调用函数。到调用函数。42多个函数嵌套调用的规则是多个函数嵌套调用的规则是：后调用先返回后调用先返回此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”。递归过程指向过程中占用的数据区，递归过程指向过程中占用的数据区，称之为称之为递归工作栈递归工作栈每一层的递归参数合成一个记录，每一层的递归参数合成一个记录，称之为称之为递归工作记录递归工作记录栈顶记录指示当前层的执行情况，栈顶记录指示当前层的
25、执行情况，称之为称之为当前活动记录当前活动记录栈顶指针，栈顶指针， 称之为称之为当前环境指针当前环境指针43例：递归的执行情况分析 void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i1时，先把上面n-1个圆盘从X移到Y，然后将n号盘从X移到Z，再将n-1个盘从Y移到Z。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的
26、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); / 将y上编号为至n-1的圆8 /盘移到z, x作辅助塔8 9 执行情况：执行情况：递归工作栈保存内容：形参n, x, y, z和返回地址（返回地址用语句行号表示）。工作记录结构：返回地址nxyz void hanoi(int n,char
27、x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 abc1230 3 a b c0 3 a b c6 2 a c b0 3 a b c6 2 a c b6 1 a b cabc0 3 a b c6 2 a c babc0 3 a b c6 2 a c b8 1 c a babc0 3 a b c0 3 a b c6 2 a c b void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 mo
28、ve(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 abc0 3 a b c6 2 a c babc0 3 a b c8 2 b a c0 3 a b c8 2 b a c 6 1 b c aabc0 3 a b c void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 0 3 a b c8 2 b a
29、 c void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 abc0 3 a b c8 2 b a c8 1 a b cabc0 3 a b c栈空0 3 a b c8 2 b a c0 3 a b c8 2 b a c3.4 队列队列3.4.1 队列的类型定义队列的类型定义3.4.2 链队列链队列3.4.3 循环队列循环队列54队列队列是限定只能在表的一端进行插入，在表是限定只能在表的一端进行插
30、入，在表的另一端进行删除的线性表。的另一端进行删除的线性表。a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)队列特点：队列特点：先进先出先进先出( (FIFOFIFO) )3.4.1 队列的类型定义队列的类型定义队尾队尾(rear)允许允许插入插入的一端的一端队头队头(front)允许允许删除删除的一的一端端55 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中约定其中a1 端为端为队列头队列头， an 端为端为队列尾队列尾基本操
31、作：基本操作：队列的抽象数据类型定义：队列的抽象数据类型定义： ADT Queue56队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()57typedef struct QNode/ 结点类型结点类型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct
32、/链队列类型链队列类型 QueuePtr *front ; /队头指针 QueuePtr *rear ; /队尾指针 LinkQueue;3.4.2 链队列队列的链式表示和实现链队列队列的链式表示和实现58a1anQ.frontQ.rearQ.frontQ.rear空队列空队列59 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; retu
33、rn OK;60 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;61 Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR i
34、f (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;623.4.3 循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现 #define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾
35、指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;63实现：实现：用一维数组实现用一维数组实现baseM123450空队列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J2,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfrontv存在问题：存在问题：l当当front=0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出l当当front0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出假
36、溢出假溢出64v解决方案解决方案l队首固定，每次出队剩余元素向下移动队首固定，每次出队剩余元素向下移动浪费时间浪费时间l循环队列循环队列u 基本思想：把队列基本思想：把队列设想成环形设想成环形，让，让base0接在接在baseM-1 之后，若之后，若rear+1=M,则令则令rear=0;u实现：利用实现：利用“模模”运算运算u入队：入队： baserear = e; rear = (rear+1)%M; u出队：出队： e = basefront; front = (front+1)%M; u队满、队空判定条件队满、队空判定条件65012345rearfrontJ5J6J7012345rea
37、rfrontJ4J9J8J4,J5,J6出队J7,J8,J9入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外另外设一个标志位设一个标志位以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front3.使用一个计数器记录队列中元素的总数使用一个计数器记录队列中元素的总数J5J6012345rearfront初始状态J466 Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (QElemType *) mallo
38、c (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; 67Status EnQueue (SqQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;68 Status DeQueue (S
39、qQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;69第三章作业补充作业：补充作业：1. 设将整数设将整数1、2、3、4依次进栈，但只要出栈时栈依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：答下有问题： （1）若入栈次序为）若入栈次序
40、为push(1)，pop()，push(2），），push(3)，pop()，pop( )，push(4)，pop( )，则出栈则出栈的数字序列为什么？的数字序列为什么？ （2）请分析）请分析1、2、3、4的的24种排列中，哪些序种排列中，哪些序列可以通过相应的入出栈得到。列可以通过相应的入出栈得到。 2. 写出检验括号匹配的算法。写出检验括号匹配的算法。703.12 写出以下程序段的输出结果（队列中的元素写出以下程序段的输出结果（队列中的元素 类型类型QElemType 为为char）。）。Void main( ) Queue Q; InitQueue(Q); Char x=e, y=c; EnQueue(Q, h); EnQueue(Q, r); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, a); While ( !QueueEmpty(Q) ) DeQueue(Q, y); Printf(y); Printf(x);71
