综合 数据结构03

上节课知识点回顾线性表的逻辑结构线性表的顺序存储线性表的链式存储如果限定线性表插入删除的位置--受限的线性表回顾（练一练）2023/2/52．用链表表示线性表的优点是（

）。(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同2023/2/53若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（

）存储方式最节省运算时间。(A)单链表(B)仅有头指针的单循环链表

(C)双链表(D)仅有尾指针的单循环链表通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n栈和队列是两种常用的数据类型2023/2/55

第3章栈和队列

栈，也叫堆栈，是最常用也是最重要的数据结构之一。比如编译器中的语法识别、数学表达式的处理、程序运行中的函数及过程的调用等，都要用到栈的有关特性。它们是栈应用于实际问题的典型。3.1栈

栈和队列是两种常用的数据类型2023/2/561．栈的定义

栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。

特点：后进先出栈又称为“后进先出”的线性表，简称LIFO表。

LastInFirstOut3.1.1栈的定义和运算

栈顶栈底内容提纲2023/2/51.栈的类型定义和实现

逻辑

顺序链式2.栈的应用举例2023/2/582．栈的基本运算初始化栈InitStack(S)设置一个空栈S。压栈Push(S,x)将元素x插入栈S中，使x成为栈S的栈顶元素。出栈Pop(S,x)当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素取栈顶元素GetTop(S,x)

若栈S不空，则由x返回栈顶元素。判栈空Empty(S)

若栈S为空栈，结果为1，否则结果为0。

2023/2/59

3.1.2栈的顺序存储结构及其基本运算的实现

栈有两种存储表示方法:顺序存储和链式存储1.栈的顺序存储结构

栈的顺序存储结构简称为顺序栈。通常由一个一维数组和一个记录栈顶元素位置的变量组成。练一练2023/2/510一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是()A.2,3,4,1,5B.5,4,1,3,2C.2,3,1,4,5D.1,5,4,3,22023/2/511ElemType为栈中元素的数据类型，可以根据需要而指定为某种具体的类型。

data域:为一个一维数组，用于存储栈中元素。

top域:栈顶指针。取值范围为0～MaxSize-1。

top=-1表示栈空，top=MaxSize-1表示栈满。#defineMaxSize<存储数据元素的最大个数>typedefstruct{ElemTypedata[MaxSize];inttop;}STACK;顺序栈的C语言描述如下：2023/2/512。

顺序栈的几种状态（最大长度MaxSize为4）（a）当栈中没有数据元素时，表示为栈空。栈顶元素所对应的下标值top=-1。（b）表示在（a）基础上执行Push(S,‘A’)后得到这种状态。（c）又有三个元素B、C、D先后入栈，此时栈顶元素的下标值top=3。栈已满。（d）表示在（c）状态下，执行一次Pop(S，x)运算得到。（e）表示在（d）状态下，执行三次Pop(S，x)运算得到。此时栈顶下标值top=-l，又变成栈空状态

2023/2/5132．基本运算在顺序存储结构的实现初始化栈InitStack(S)

voidInitStack(STACK*S){S->top=-1;}

压栈Push(S,x)

intPush(STACK*S,ElemTypex){if(S->top==MaxSize-1){printf("\nStackisfull!");return0;}S->top++;S->data[S->top]=x;return1;}212023/2/5142023/2/515出栈Pop(S,x)intPop(STACK*S,ElemType*x){if(Empty(S)){printf("\nStackisfree!");return0;}*x=S->data[S->top];S->top--;return1;}X2023/2/516

取栈顶元素GetTop(S,x)

intGetTop(STACK*S,ElemType*x){

if(Empty(S)){printf("\nStackisfree!");return0;}*x=S->data[S->top];return1;}判栈空Empty(S)intEmpty(STACK*S){return(S->top==-1?1:0);}栈的应用举例数制转换

算法基于原理：

N=(Ndivd)×d+Nmodd

2023/2/518

例如：（1348)10=(2504)8

，其运算过程如下：

NNdiv8Nmod8

13481684

168210

2125

202计算顺序输出顺序除基取余逆序法2023/2/5193．栈的共享存储单元

两个栈共享大小为m的内存空间时，分配方法的示意图如下两个栈的共享存储单元可用C语言描述如下：#defineMaxSize<共享存储单元的最大长度>typedefstruct{ElemTypedata[MaxSize];inttop[2];}STACK;2023/2/520（1）两个栈共享存储单元的压栈算法intPush(STACK*S,ElemTypex,intk){if(S->top[0]+1==S->top[1]){printf("\nstackisfull!");return0;}if(k==0){S->top[0]++;S->data[S->top[0]]=x;}//栈0else{S->top[1]--;S->data[S->top[1]]=x;}//栈1return1;}2023/2/521（2）两个栈共享存储单元的出栈算法intPop(STACK*S,intk,ElemType*x){if((k==0)&&(S->top[0]==-1)){printf("\nstackisfree!");return0;}if((k==1)&&(S->top[1]==MaxSize)){printf("\nstackisfree!");return0;}if(k==0){*x=S->data[S->top[0]];S->top[0]--;}else{*x=S->data[S->top[1]];S->top[1]++;}return1;}2023/2/5223.1.3栈的链式存储结构及其基本运算的实现1.栈的链式存储结构

栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈链栈的C语言描述如下：typedefstructsnode{//定义链栈结点类型

ElemTypedata;structsnode*next;}LinkSTACK;LinkSTACK*top;链栈结构示意图2023/2/523链栈的几种状态:2023/2/5242．基本运算在链式存储结构的实现栈初始化

voidInitStack(LinkSTACK**top){if(!*top=(LinkSTACK*)malloc(sizeof(LinkSTACK)))returnOVERFLOW;(*top)->next=NULL;}top’topnext2023/2/525压栈运算

intPush(LinkSTACK**top,ElemTypex){LinkSTACK*s;s=(LinkSTACK*)malloc(sizeof(LinkSTACK));s->data=x;s->next=(*top)->next;(*top)->next=s;return1;}判断栈空

intEmpty(LinkSTACK**top){return((*top)->next==NULL?1:0);}2023/2/526出栈运算

intPop(LinkSTACK**top,ElemType*x)

{LinkSTACK*s;if(Empty(top)){printf("\nstackisfree!");return0;}s=(*top)->next;*x=s->data;(*top)->next=s->next;free(s);return1;}2023/2/527取栈顶元素

intGetTop(LinkSTACK**top,ElemType*x){if(Empty(top)){printf("\nstackisfree!");return0;}*x=(*top)->next->data;return1;}应用举例1、表达式求解2、递归程序2023/2/528

表达式的三种标识方法：设

Exp=S1+OP

+S2则称OP

+S1+S2

为前缀表示法

S1+

OP

+S2

为中缀表示法

S1+S2+

OP

为后缀表示法

例如:Exp=ab

+

(cd/e)f前缀式:+

ab

c/def中缀式:ab

+

cd/ef后缀式:ab

cde/f

+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:

运算符在式中出现的顺序恰为表达式的运算顺序;

每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。如何从后缀式求值？先找运算符，再找操作数例如：

abcde/f+abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？

每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+b

cd/e

f

后缀式:abc+de/f

从原表达式求得后缀式的规律为：1)设立运算符栈；2)设表达式的结束符为“#”，

予设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前运算符的优先数高于栈顶运算符，则进栈；5)否则，退出栈顶运算符发送给后缀式；

6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：2023/2/535下图展示了算术表达式3×（7-2）求值的动态过程

2023/2/536递归是一种非常重要的数学概念和解决问题的方法，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多问题的算法设计。在计算机内部，通过栈来实现递归算法。所以递归是栈的一个实际应用。

3.3栈与递归2023/2/537采用递归算法求解正整数n的阶乘n!数学定义求n的阶乘的递归函数算法如下:longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}2023/2/538进行fact(4)调用的系统栈的变化情况

2023/2/539函数fact(4)的递归调用过程的执行流程内容提纲2023/2/51.队列的类型定义和实现

逻辑

顺序链式2.队列的应用举例2023/2/541

3.4.1队列的定义和运算

1．队列的定义

队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。

特点：队列中数据元素的入队和出队过程是按照“先进先出”的原则进行的。因此，队列又称为“先进先出”的线性表，简称FIFO表。FirstInFirstOut3.4队列队头队尾queue2023/2/542

2．队列的基本运算队列初始化InitQueue(SQ)

设置一个空队列SQ。入队列EnQueue(SQ，x)

将x插入到队列SQ的队尾。出队OutQueue(SQ，x)

将队头元素赋给x，并删除队头元素。取队头元素GetHead(SQ，x)

由x返回队头结点的值。

判队列空Empty(SQ)队列SQ是否为空。若为空返回1，否则返回0。练一练栈和队列的共同点是()。A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点2023/2/5432023/2/544

3.4.2队列的顺序存储结构及其基本运算的实现队列有两种存储表示方法:顺序存储和链式存储1．队列的顺序存储结构队列的顺序存储结构简称顺序队。顺序队是用一维数组依次存放队列中的元素和分别指示队列的首端和队列的尾端的两个变量组成。这两个变量分别称为“队头指针”和“队尾指针”。顺序队列的数据类型定义如下#defineMaxSize<队列的最大容量>typedefstruct{ElemTypedata[MaxSize];intfront,rear;}SQUEUE;2023/2/545顺序队列（MaxSize=5）的几种状态

（a）表示空队列，

rear=front=0。（b）元素A入队后，

rear=1，front=0。（c）B，C依次入队后，

rear=3，front=0。（d）A，B，C依此出队后,rear=front=3。（e）D入队后,rear=4,front=3。（f）D出队后，rear=front=4。2023/2/546如图所示是具有五个存储单元的循环队列（a）表示空队列，

rear=front=0。（b）元素A入队后，

rear=1，front=0。（c）B，C，D依次入队后，

rear=4，front=0。（d）A出队后,front=1,rear=4。（e）B，C，D出队后,rear=front=4。

环形队列指针SQ的四要素如下• 队空：SQ->rear==SQ->front• 队满：(SQ->rear+1)%MaxSize==SQ->front进队操作：SQ->rear=(SQ>rear+1)%MaxSize;SQ->data[SQ->rear]=x;•出队操作：SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];。2023/2/5472023/2/5482．基本运算顺序队列的实现队列初始化

voidInitQueue(SQUEUE*SQ){SQ->rear=SQ->front=0;}

入队列intEnQueue(SQUEUE*SQ,ElemTypex){if((SQ->rear+1)%MaxSize==SQ->front){printf("\nQueueisfull!");return0;}SQ->rear=(SQ->rear+1)%MaxSize;SQ->data[SQ->rear]=x;return1;}2023/2/549出队intOutQueue(SQUEUE*SQ,ElemType*x){if(Empty(SQ)){printf("\nQueueisfree");return0;}SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];return1;}判队列空intEmpty(SQUEUE*SQ){return(SQ->rear==SQ->front)?1:0;}

2023/2/5503.4.3队列的链式存储结构及其基本运算的实现

1.队列的链式存储结构

队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。链队结构示意图2023/2/551链队运算指针变化情况2023/2/5522．基本运算链队的实现队列初始化

voidInitQueue(SQUEUE*LQ){QTYPE*p;p=(QTYPE*)malloc(sizeof(QTY