《《数据结构》(C语言版)第三章-栈和队列解析.ppt》由会员分享，可在线阅读，更多相关《《数据结构》(C语言版)第三章-栈和队列解析.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、234 栈的栈的定义：定义：限定仅在限定仅在表尾表尾进行插入或删除进行插入或删除操作的线性表。不含元素的空表称操作的线性表。不含元素的空表称空栈。空栈。ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)特点：特点：后进先出（后进先出（LIFO）表尾表尾栈顶栈顶 表头表头栈底栈底5 ADT Stack 数据对象数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作：基本操作： ADT Stack栈的抽象数据类型定义：栈的抽象数据类型定义：P45P456
2、InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit( )7一、顺序栈一、顺序栈 P46-47/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize;
3、/栈当前可使用最大容量 SqStack;8实现：实现：一维数组一维数组sMtop123450进栈进栈Push(&S, e)A栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450空栈空栈topbasebasetoptop出栈出栈Pop(&S,&e)123450ABCDEFtoptoptoptop栈空basetoptop栈底指针base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置9 Status InitStack (SqStack
4、 &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.base = S.stacksize) /栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (
5、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的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if ( S.top = S.base ) return ERROR;
6、e = *- -S.top; return OK;120M-1栈栈1底底栈栈1顶顶栈栈2底底栈栈2顶顶在一个程序中同时使用两个栈在一个程序中同时使用两个栈13二、链栈二、链栈 栈的链式存储结构。栈的链式存储结构。 栈顶指针栈顶指针就是链表的头指针。就是链表的头指针。注意注意: 链栈中链栈中指针的方向指针的方向栈顶指针栈顶指针a1anan-114v入栈操作入栈操作push(&S, e)v 出栈操作出栈操作pop(&S,&e) .栈底toptopxptop .栈底topqp-next=top ; top=p q=top ; top=top-next ; free(q);15163.2.1 数制转换
7、数制转换十进制数十进制数N和其他和其他d进制数的转换原理进制数的转换原理: N=( N div d ) d + N mod d 其中：其中：div为为整除整除运算，运算， mod为为求余求余运算运算17toptop4top40top405 例如：例如： (1348)10=(2504)8，其运算过程如下：，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序top405218 void conversion( ) P48 算法3.1 /对于输入的任意一个非负十进制整数， /打印输出与其等值的八进制数 initsta
8、ck ( 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 括号匹配的检验括号匹配的检验 则则 检验括号是否匹配检验括号是否匹配的方法可用的方法可用“期待的急迫程度期待的急迫程度”这个概念来描述。这个概念来描述。假设在表达式中假设在表达式中（）或（）或（ ）等为正确的格式，等为正确的格式，（ ）或（）或（ ）或）或 （）（）)均均为不正确的格式。为不正确的格式。20分析可能出
9、现的分析可能出现的不匹配不匹配的情况的情况: :到来的右括弧到来的右括弧并非是所并非是所“期待期待”的；的；例如：例如：考虑下列括号序列：考虑下列括号序列： ( ) ( ) 1 2 3 4 5 6 7 8到来的是到来的是左括弧左括弧；直到结束，也没有到来直到结束，也没有到来所所“期待期待”的括弧。的括弧。21算法的设计思想：算法的设计思想：1）凡出现）凡出现左括弧左括弧，则，则进栈进栈；2）凡出现）凡出现右括弧右括弧，首先检查栈是否空，首先检查栈是否空 若若栈空栈空，则表明该，则表明该“右括弧右括弧”多余多余， 否则否则和栈顶元素和栈顶元素比较，比较， 若若相匹配相匹配，则，则“左括弧出栈左括
10、弧出栈” ， 否则表明否则表明不匹配不匹配。3）表达式检验结束时，）表达式检验结束时， 若若栈空栈空，则表明表达式中，则表明表达式中匹配正确匹配正确， 否则表明否则表明“左括弧左括弧”有余有余。223.2.3 行编辑程序问题行编辑程序问题如何实现？如何实现？“每接受一个字符即存入存储器每接受一个字符即存入存储器” ? 不恰当不恰当!合理的作法是：合理的作法是： 设立一个输入缓冲区，用以接受用设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户输入的一行字符，然后逐行存入用户数据区，并假设户数据区，并假设“#”为退格符，为退格符，“”为退行符。为退行符。23假设从终端接受了这样两行字
11、符：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行：则实际有效的是下列两行： while (*s) putchar(*s+);24 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
12、 != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符P50算法3.2将从栈底到栈顶的字符传送至调用过程的数据区；253.2.4 迷宫求解迷宫求解通常用的是通常用的是“穷举求解穷举求解”的方法。的方法。迷宫的表示方法：迷宫的表示方法：P50 图图3.4“当前位置当前位置”：搜索过程中某一：搜索过程中某一时刻所在图中某个方块的位置。时刻所在图中某个方块的位置。26求迷宫路径算法的求迷宫路径算法的基本思想基本思想是：是：v若当前位置若当前位置“可通可通”，则纳入路径，则纳入路径，继续前进并把当前位置切换为下一继续前进并把当前位置切换为下一位置位置;
13、v若当前位置若当前位置“不可通不可通”，则后退，则后退，换方向继续探索换方向继续探索;v若四周若四周“均无通路均无通路”，则将当前位，则将当前位置从路径中删除出去。置从路径中删除出去。27设定当前位置当前位置的初值为入口位置； do 若若当前位置可通当前位置可通， 则则将当前位置插入栈顶插入栈顶； 若若该位置是出口位置，则则算法结束； 否则切换否则切换当前位置的东邻方块为 新的当前位置； 否则否则 while (栈不空）栈不空）；求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法： 28若若栈不空栈不空且且栈顶位置尚有其他方向未被探索栈顶位置尚有其他方向未被探索，则则设
14、定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块栈顶位置的下一相邻块；若若栈不空栈不空但但栈顶位置的四周均不可通栈顶位置的四周均不可通，则则删去栈顶位置；/ 从路径中删去该通道块 若若栈不空，则则重新测试新的栈顶位置， 直至直至找到一个可通的相邻块或出栈至栈空；若若栈空栈空，则则表明迷宫没有通路。29 typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中 的 “坐标位置” int di; / 从此通道块走向下一 通道块的“方向” SElemType; / 栈的元素类型30 Status MazePath (
15、 MazeType maze, PosType start, PosType end ) InitStack(S); curpos = start; / 设定“当前位置”为“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 当前位置可以通过，即是未曾走到过的通道块当前位置可以通过，即是未曾走到过的通道块 else while ( !StackEmpty(S) ); return (FALSE);/ MazePath P51-52 算法3.331FootPrint (curpos); e = ( curstep, curpos, 1 );Push
16、 (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+; Push ( S, e); / 换下一个方向探
17、索 curpos = NextPos (e.seat, e.di ); / 设定当前位置是该新方向上的相邻块 / if / if / else33 限于二元运算符的表达式定义: Exp = S1 OP S2 操作数操作数 : 变量、常量、表达式变量、常量、表达式 运算符运算符 : 算术运算符、关系运算符、算术运算符、关系运算符、 逻辑运算符逻辑运算符 界限符：界限符：括号、结束符括号、结束符3.2.5 表达式求值表达式求值34表达式求值的算法：表达式求值的算法：算符优先法算符优先法根据运算优先关根据运算优先关系的规定来实现对表达式的编系的规定来实现对表达式的编译或解释执行。译或解释执行。P53
18、 表表3.1 算符间优先关系算符间优先关系35例：例：3 * ( 7 2 )OPND栈栈OPTR栈栈CCC3*(C7CC2C275C*531536OperandType EvaluateExpression( ) P53-54 算法算法3.4 / 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar()
19、; / 不是运算符则进栈 else / while return GetTop(OPND); / EvaluateExpression 37switch ( precede(GetTop(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch38例：例：3 * ( 7 2 ) OPTR栈栈 OPND栈栈 输入输入 操作操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 *
20、( 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( OPND, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND )39r主程序主程序srrrs子过程子过程1
21、rst子过程子过程2rst子过程子过程340 当在一个函数的运行期间调用当在一个函数的运行期间调用另一个函另一个函数数时，在运行该被调用函数时，在运行该被调用函数之前之前，需先完，需先完成三件事成三件事: : (1) (1)将所有的实在参数、返回地址等将所有的实在参数、返回地址等信息信息传递给被调用函数传递给被调用函数保存保存; ; (2) (2)为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区; ; (3) (3)将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。41 从被调用函数从被调用函数返回返回调用函数调用函数之前之前，应该完成应该完成: : (1) (1)保
22、存保存被调函数的被调函数的计算结果计算结果; ; (2) (2)释放释放被调函数的被调函数的数据区数据区; ; (3) (3)依照被调函数保存的返回地址依照被调函数保存的返回地址将将控制转移控制转移到调用函数。到调用函数。42多个函数嵌套调用的规则是多个函数嵌套调用的规则是：后调用先返回后调用先返回此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”。递归过程指向过程中占用的数据区，递归过程指向过程中占用的数据区，称之为称之为递归工作栈递归工作栈每一层的递归参数合成一个记录，每一层的递归参数合成一个记录，称之为称之为递归工作记录递归工作记录栈顶记录指示当前层的执行情况，栈顶记录指示当前层的
23、执行情况，称之为称之为当前活动记录当前活动记录栈顶指针，栈顶指针， 称之为称之为当前环境指针当前环境指针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 / 的
24、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移到z hanoi(n-1, y, x, z); / 将y上编号为至n-1的圆 /盘移到z, x作辅助塔8 9 执行情况：执行情况：递归工作栈保存内容：形参n, x, y, z和返回地址（返回地址用语句行号表示）。工作记录结构：返回地址nxyz void hanoi(int n,char x,
25、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 move
26、(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 c
27、 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 c5354队列队列是限定只能在表的一端进行插入，在表是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。的另一端进行删除的线性表。a1 a2 a3.an 入队出队frontrea
28、r队列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 端为端为队列尾队列尾基本操作：基本操作：队列的抽象数据类型定义：队列的抽象数据类型定义： ADT Queue56队列的基本操作：队列的
29、基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit() 双端队列双端队列 P60 图图3.957typedef struct QNode/ 结点类型结点类型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /链队列类型链队列类型 QueuePtr *front ; /队头指针
30、 QueuePtr *rear ; /队尾指针 LinkQueue;3.4.2 链队列队列的链式表示和实现链队列队列的链式表示和实现P6158a1anQ.frontQ.rearQ.frontQ.rear空队列空队列P61 图3.10,图3.1159 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;60 Status E
31、nQueue (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 if (Q.front = Q.re
32、ar) 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; / 尾指针，若队列不空，指向 / 队列尾
33、元素 的下一个位置 SqQueue;63实现：实现：用一维数组实现用一维数组实现baseM P63 图图3.12123450空队列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrearrear123450frontJ1,J2,J3入队rear123450J1,J2,J3出队J1J2J3frontfrontfrontfrontv存在问题：存在问题：l当当front=0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出l当当front0,rear=M时，再有元素入队发生溢出时，再有元素入队发生溢出假溢出假溢出6
34、4v解决方案解决方案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队满、队空判定条件队满、队空判定条件65012345rearfrontJ4J5J6012345rearfront
35、J3J8J7J3,J4,J5出队J6,J7,J8入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外另外设一个标志位设一个标志位以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front3.使用一个计数器记录队列中元素的总数使用一个计数器记录队列中元素的总数J4J5012345rearfront初始状态J366 Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (QElemType *) malloc (MAX
36、QSIZE *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 (SqQueue
37、 &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）若入栈次序为）若入栈次序为push(
38、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);