数据结构讲义3概况课件.ppt

1、2022-11-111柳 青Email:School of Software,Yunnan University 数据结构数据结构(Data Structure)2022-11-1123.1、栈、栈(Stack)(Stack)3.2、栈的应用举例、栈的应用举例3.3、栈与递归的实现、栈与递归的实现3.4、队、队(Queue)(Queue)第三章第三章 栈和队列栈和队列2022-11-1133.1 3.1 栈栈 (Stack)(Stack)3.1.1 3.1.1 定义定义栈栈(Stack)：限定仅只能在表尾：限定仅只能在表尾端进行插入和删除的线性表。端进行插入和删除的线性表。栈顶栈顶(top)：

2、表尾端被称之为栈表尾端被称之为栈顶。栈顶之上为顶。栈顶之上为top指针。指针。栈底栈底(Bottom)：和表尾相对应的和表尾相对应的另一端，称之为栈底。另一端，称之为栈底。特点：特点：后进先出（后进先出（LIFO）。）。a1 a2 an-1 antop栈顶栈顶 Base 栈底栈底2022-11-1143.1 3.1 栈栈 (Stack)(Stack)v栈的抽象数据类型定义：栈的抽象数据类型定义：ADT Stack 数据对象数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系数据关系：R1=|ai-1,ai D,i=2,n 约定约定an端为栈顶，端为栈顶，a1端为栈底。端为栈底

3、。基本操作基本操作：InitStack(&S)/初始化，构造一个空栈初始化，构造一个空栈S。Push(&S,e)/将将 e 插入栈顶，插入栈顶，必须判必须判断断栈是否溢出栈是否溢出，top上移上移。Pop(&S,&e)/删除非空栈删除非空栈S的的栈顶元素至变量栈顶元素至变量e，top下移下移。GetTop(S,&e)/取非空栈取非空栈S的的栈顶元素至变量栈顶元素至变量e，top不变不变。StackLength(S)/返回栈返回栈S的元素个数，即栈的长度。的元素个数，即栈的长度。StackEmpty(S)/若栈若栈S的为空，则返回的为空，则返回TRUE，否则返回，否则返回FALSE。ADT St

4、ack2022-11-115basetoptopAbaseABCtopbasetopbaseABCD注意：因为注意：因为 base=top 是栈空标志，是栈空标志，所以所以 top 指针只能指示真正的栈指针只能指示真正的栈 顶元素之上的数组元素的下标地顶元素之上的数组元素的下标地 址。否则造成矛盾。址。否则造成矛盾。栈满时的处理方法：栈满时的处理方法：1、提示出错，返回操作系统。、提示出错，返回操作系统。2、分配更大的空间。、分配更大的空间。31203.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构(即即顺序栈顺序栈)的表示和实现的表示和实现Typedef struct SElemTyp

5、e *base;SElemType *top;int stacksize;SqStack;3.1 3.1 栈栈2022-11-116#define STACK_INIT_SIZE 100;#define STACK_INCREMENT 10;Status InitStack(SqStack&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;/Init

6、Stack;012 STACK_INIT_SIZE-1s.base数组数组 s.base0,s.base1,s.baseSTACK_INIT_SIZE-1 1.顺序栈的初始化实现：顺序栈的初始化实现：3.1 3.1 栈栈2022-11-117Status Push(SqStack&s,SElemType e)If(s.top-s.base=s.stacksize)s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!s.base)exit(OVERFLOW);s.top=s.ba

7、se+s.stacksize;s.stacksize +=STACKINCREMENT;*s.top+=e;/相当于：相当于：*s.top=e;s.top+两条指令两条指令;return OK;/Push;2.顺序栈的顺序栈的 Push 操作实现：操作实现：3.1 3.1 栈栈2022-11-118函数函数realloc(ptr,size):将将 ptr 指向的存区长指向的存区长度改变为度改变为 size,size 比原先大，必须进行移比原先大，必须进行移动，且返回指向新存区的指针。动，且返回指向新存区的指针。0 1 2 97 98 99ptr0 1 2 98 99 107108 109 pt

8、r3.1 3.1 栈栈2022-11-1193.1 3.1 栈栈 3.顺序栈的顺序栈的 Pop 操作操作实现：实现：若栈若栈S不空，则删除其栈顶元素，用不空，则删除其栈顶元素，用e返回该值；返回该值；否则返回否则返回ERROR。Status Pop(SqStack&s,SElemType&e)If(s.top=s.base)return ERROR;s.top-;e=*s.top /此2句可缩写为 e=*-s.top return OK;/Pop2022-11-1110 data next 栈顶栈顶栈底栈底Stypedef struct Snode SElemType data;struct

9、Snode *next;Snode,*Stackptr;Stackptr S;/S为栈顶指针为栈顶指针InitlinkStack(Stackptr&S)S=NULL /InitlinkStack;S3.1.3 3.1.3 链式链式栈的表示和实现栈的表示和实现1.链式栈的初始化实现：链式栈的初始化实现：3.1 3.1 栈栈2022-11-1111 data next 栈顶栈顶 栈底栈底SStatus Push(Stackptr&s,SElemType e)p=(Stackptr)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=s

10、;s=p;return OK;/Push;data nextpS data next2.链式栈的链式栈的 Push 操作实现操作实现3.1 3.1 栈栈2022-11-1112 data nextpeS data next2.链式栈的链式栈的 Push 操作实现操作实现 data next 栈顶栈顶 栈底栈底SStatus Push(Stackptr&s,SElemType e)p=(Stackptr)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=s;s=p;return OK;/Push;3.1 3.1 栈栈2022-11

11、-1113 data nextp data nextSe2.链式栈的链式栈的 Push 操作实现操作实现3.1 3.1 栈栈 data next 栈顶栈顶 栈底栈底SStatus Push(Stackptr&s,SElemType e)p=(Stackptr)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=s;s=p;return OK;/Push;2022-11-1114 data nextp data nexteS2.链式栈的链式栈的 Push 操作实现操作实现3.1 3.1 栈栈 data next 栈顶栈顶 栈底栈底S

12、Status Push(Stackptr&s,SElemType e)p=(Stackptr)malloc(sizeof(Snode);if(!p)exit(OVERFLOW);p-data=e;p-next=s;s=p;return OK;/Push;2022-11-1115 data next 栈顶栈顶 栈底栈底SStatus Pop(Stackptr&s,SElemType&e)if(!s)return(ERROR);e=s-data;p=s;s=s-next;free(p);return OK;/Pop;data nextSA3.链式栈的链式栈的 Pop 操作实现操作实现3.1 3.1

13、 栈栈2022-11-1116 data nextSpe=AA3.链式栈的链式栈的 Pop 操作实现操作实现3.1 3.1 栈栈 data next 栈顶栈顶 栈底栈底SStatus Pop(Stackptr&s,SElemType&e)if(!s)exit(UNDERFLOW);e=s-data;p=s;s=s-next;free(p);return OK;/Pop;2022-11-1117 data nextSp3.链式栈的链式栈的 Pop 操作实现操作实现3.1 3.1 栈栈 data next 栈顶栈顶 栈底栈底SStatus Pop(Stackptr&s,SElemType&e)if

14、(!s)exit(UNDERFLOW);e=s-data;p=s;s=s-next;free(p);return OK;/Pop;2022-11-1118 data nextS3.链式栈的链式栈的 Pop 操作实现操作实现3.1 3.1 栈栈 data next 栈顶栈顶 栈底栈底SStatus Pop(Stackptr&s,SElemType&e)if(!s)exit(UNDERFLOW);e=s-data;p=s;/p须先定义 s=s-next;free(p);return OK;/Pop;2022-11-1119例如例如10 进制和进制和 8 进制之间的数的转换。进制之间的数的转换。(1

15、348)10 =83*a3+82*a2+8*a1+80*a0 =(2504)8 n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 240523.2 3.2 栈的应用栈的应用3.2.1 3.2.1 数制转换数制转换公式：公式：N=(n div d)*d+n mod d (div(div为整除运算为整除运算,mod,mod为求余运算为求余运算)void conversion()InitStack(S);scanf(“%d”,&N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);print

16、f(“%d”,e);2022-11-11203.2.2 3.2.2 括号匹配检查括号匹配检查Status clarity(linklist L)Initstack(S);for(i=1;iListlength(L);i+)GetElem(L,i,e1);if(e1=()|(e1=)Push(S,e1);else if(e1=)|(e1=)if(Pop(S,e2)=ERROR)|(e1=)&e2!=()|(e1=&e2!=)return ERROR;if StackEmpty(S)return OK;else return ERROR;3.2 3.2 栈的应用栈的应用2022-11-112101

17、23456789 0 1 2 3 4 5 6 7 8 9起点起点终点终点 起点：起点：(x=1,y=1);东东(1,2)南南(2,1)西西(1,0)北北(0,1)XY东东1南南2西西3北北43.2.3 3.2.3 迷宫问题：求从起点到终点的简单路径迷宫问题：求从起点到终点的简单路径方格的四种类型：方格的四种类型：非墙且未经试探的方格非墙且未经试探的方格 墙墙 已在路径上的方格已在路径上的方格 已试探过的无发展前途的方格已试探过的无发展前途的方格方向标记：方向标记：2022-11-1122(1、1)(1、2)(2、1)(1、0)(0、1)(1、3)(2、2)(1、1)(0、2)1、(1、1)、1

18、 2、(1、2)、23、(2、2)、2(2、3)(3、2)路径序号路径序号所在位置所在位置前进方向前进方向 可能的方向：可能的方向：非墙新方格非墙新方格 不是在路径上的方格（因为要求不是在路径上的方格（因为要求 从起点到终点的简单路径）从起点到终点的简单路径）不是无发展前途的已经纳入过路不是无发展前途的已经纳入过路 径的方格径的方格 试探方法：试探方法：穷举求解，试探每一个穷举求解，试探每一个 可能的方向。可能的方向。Typedef struct int step;PosType seat;int di;ElemType;堆栈中记录的数据（组成路径的每堆栈中记录的数据（组成路径的每 个点）类型

19、：个点）类型：3.2.3 3.2.3 迷宫问题：求从起点到终点的简单路径迷宫问题：求从起点到终点的简单路径2022-11-1123Status MazePath(MazeType maze,PosType start,PosType end )Initstack(S);curpos=start;curstep=1;do if(Pass(curpos)/Pass函数：即当前位置可通过 FootPrint(curpos);/FootPrint函数：标记已访问过的方块 e=(curstep,curpos,1);Push(S,e);/加入路径 if (curpos=end )return(TRUE )

20、;/已到达终点 curpos=NextPos(curpos,1);/得到东邻位置，注意1代表东。curstep+;/if else if (!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);/设置非路径标志，后退一步if(e.di=MAXQSIZE (假溢出假溢出)3.4.2 顺序队列顺序队列(循环队列循环队列)：ABCrearArearfrontrearfrontrearfrontD3120frontrearfront3.4 3.4 队列队列2022-11-1128 为充分利用空间，克服上

21、述假溢出现象的方法是为充分利用空间，克服上述假溢出现象的方法是将向量空间想象为一个首尾相接的圆环（图将向量空间想象为一个首尾相接的圆环（图a a），并），并称这种队列为循环队列。称这种队列为循环队列。在循环队列中进行出队、入队操作时，头尾指在循环队列中进行出队、入队操作时，头尾指针仍要加针仍要加1 1，朝前移动。只不过当头尾指针指向向量，朝前移动。只不过当头尾指针指向向量上界（上界（MAXQSIZE-1MAXQSIZE-1）时，其加）时，其加1 1操作的结果是指向向操作的结果是指向向量的下界量的下界0 0。这种循环意义下的加。这种循环意义下的加1 1操作可以描述为：操作可以描述为：if(Q.r

22、ear+1=MAXQSIZE)Q.rear=0;if(Q.rear+1=MAXQSIZE)Q.rear=0;else Q.rear+;else Q.rear+;利用模运算可简化为：利用模运算可简化为：Q.rear=(Q.rear+1)%MAXQSIZEQ.rear=(Q.rear+1)%MAXQSIZE3.4 3.4 队列队列3.4 3.4 队列队列v如图所示：由于入队时尾指针向前追赶头指针，出如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等（图指针均相等（图b、c）。）。v因此，无法通过因此，无法通

23、过Q.front=Q.rear来判断队列来判断队列“空空”还是还是“满满”。v 解决此问题的方法是解决此问题的方法是少用一个元素的空间少用一个元素的空间，约定，约定入队前，测试尾指针在循环意义下加入队前，测试尾指针在循环意义下加1后是否等于头后是否等于头指针，若相等则认为队满（图指针，若相等则认为队满（图d，注意：，注意：Q.rear所指所指的单元始终为空）。的单元始终为空）。2022-11-11303.4 队列01234567J4J5J6Q.forntQ.reara.一般情况01234567J4J5J6J7Q.forntQ.rearc.队满情况J8J9J10J1101234567Q.forn

24、tQ.rearb.队空情况01234567J4J5J6J7Q.forntQ.reard.约定的队满情况J8J9J102022-11-1131Status InitQueue(SqQueue&Q)Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;return OK;/分配队列的存储空间分配队列的存储空间 出队时应先判队是否空：出队时应先判队是否空：条件条件 Q.rear=Q.front 不空则出队，注意不空则出队，注意 Q.front 是否会由最高下标跳至

25、最低下标是否会由最高下标跳至最低下标(循环循环)进队时应先判队是否满：进队时应先判队是否满：条件条件(Q.rear+1)%MAXQSIZE)=Q.front 不满则进队，注意不满则进队，注意 Q.rear 是否会由最高下标跳至最低下标是否会由最高下标跳至最低下标(循环循环)3.4 3.4 队列队列基本操作的实现程序：基本操作的实现程序：2022-11-1132Status EnQueue(SqQueue&Q,QElemType e)if(Q.rear+1)%MAXQSIZE)=Q.front)return(ERROR);/思考：此处能够采用思考：此处能够采用realloc函数函数 Q.base

26、 Q.rear =e;/扩大队列的存储空间？扩大队列的存储空间？Q.rear=(Q.rear+1)%MAXQSIZE);return OK;/EnQueue;3.4 3.4 队列队列Status DeQueue(SqQueue&Q,QElemType&e)if(Q.rear=Q.front)return(ERROR);e=Q.base Q.front ;Q.front=(Q.front+1)%MAXQSIZE;return OK;/DeQueue;2022-11-1133typedef struct Qnode QElemType data;struct Qnode *next;Qnode,*

27、QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;data next 队首结点队首结点Q.front 队尾结点队尾结点Q.rear3.4.3 链队列链队列(链接表示的队列链接表示的队列)Q.front 和和 Q.rear 分别是队首和队尾指针。它分别是队首和队尾指针。它们指示着队首的前一结点和队尾结点。们指示着队首的前一结点和队尾结点。3.4 3.4 队列队列2022-11-1134 data nextQ.frontQ.rear data nextQ.front 队尾结点队尾结点(队首结点队首结点)Q.rear 队首结

28、点队首结点 data nextQ.front 队尾结点队尾结点Q.rear链链（接接）队列的操作：队列的操作：3.4 3.4 队列队列2022-11-1135Status 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;/EnQueue;Status DeQueue(LinkQueue&Q,QElemType&e)if(Q.rear=Q.front)return(E

29、RROR);p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=p;free(p);return OK;/DeQueue;3.4 3.4 队列队列2022-11-1136队列的应用举例队列的应用举例 逐行打印二项展开式逐行打印二项展开式 (a a+b b)i i 的系数的系数杨辉三角形杨辉三角形 (Pascals triangle)3.4 3.4 队列队列 1 1 i=1 1 2 12 1 3 3 13 1 4 6 4 14 1 51010 5 15 1 6152015 6 162022-11-1137分析第分析第 i

30、i 行元素与第行元素与第 i i+1+1行元素的关系行元素的关系目的是从前一行的数据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据3.4 3.4 队列队列2022-11-11383.4 3.4 队列队列从第从第 i i 行数据计算并存放第行数据计算并存放第 i i+1+1 行数据行数据2022-11-11393.4 3.4 队列队列void YangHui(int n)SqQueue q;int s=0,t;InitQueue(q);EnQueue(q,1);EnQueue(q,1);for(int i=1;i=n;i+)/逐行计算 printf(“n”);EnQueue(q,0);for(int j=1;j=i+2;j+)/根据上行系数求下行系数 DeQueue(q,t);EnQueue(q,s+t);s=t;if(j!=i+2)printf(“%3d”,s);/不输出每行结尾的0 利用队列打印二项展开式系数的程序利用队列打印二项展开式系数的程序2022-11-1140本章课后作业 “数据结构题集（C 语言版）”vP23-26v9、10、30