计算机软件技术基础-课件 04ch2(3)-DS线性结构

Ch2线性结构

2.2栈和队列

2.2.1栈

1栈的定义及基本运算

2栈的存储结构和运算实现

3栈的应用

2.2.2队列

1队列的定义及基本运算

2队列的存储结构和运算实现

3队列应用举例

操作受限的线性表栈（Stack）运算只在表的一端进行队列（Queue）运算只在表的两端进行

2.2.1栈（stack）

1栈的定义及基本运算定义：栈是限定在表的一端进行插入和删除运算的线性表。允许插入和删除的一端称为栈顶(top），另一端称为栈底（bottom）。如给定栈s＝（a1，a2，…，an），栈中元素按a1，a2，…，an的顺序进栈，则称a1是栈底元素，an是栈顶元素。后进先出（LIFO）表

栈的基本运算(1)栈初始化：Init_Stack()初始条件：栈不存在。操作结果：构造一个空栈(不含任何元素）。(2)判栈空：IsEmpty_Stack(s)/EMPTY(S)初始条件：栈s已存在。操作结果：若s为空栈返回为1(T)，否则返回为0(F)。(3)入栈：Push_Stack(s，x)初始条件：栈s已存在。操作结果：在栈s顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。

栈的基本运算(4)出栈：Pop_Stack(s)初始条件：栈s存在且非空。操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。(5)读栈顶元素：GetTop_Stack(s)初始条件：栈s存在且非空。操作结果：栈顶元素作为结果返回，栈不变化。

仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶;表头(即a1端)称为栈底。例如：栈S=(a1,a2,a3,……….,an-1,an)插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！栈：2栈的存储结构和运算实现存储结构： 用顺序栈或链栈存储均可，但以顺序栈更常见。逻辑结构： 与线性表相同，仍为一对一关系。运算规则： 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。实现方式：关键是编写入栈和出栈函数，具体实现因顺序栈或链栈的不同而不同。Q1：堆栈是什么？它与一般线性表有什么不同？

堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：1:1逻辑结构：1:1存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取/删减运算规则：后进先出“进”＝插入=压入=PUSH（an+1)“出”＝删除=弹出=POP(an)1）顺序栈栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。栈底位置是固定不变的，可以将栈底位置设置在数组的两端的任何一个端点。栈顶位置是随着进栈和退栈操作而变化。需用一个整型变量top来指示当前栈顶的位置(通常称top为栈顶指针)。顺序栈的类型定义只需将顺序表的类型定义中的长度cnt改为top即可。1）顺序栈利用一组地址连续的存储单元依次存放从栈底到栈顶的若干数据元素。(1)定义：

#defineMaxSize1024typedefstructstack{ElemTypedata[MaxSize];

/*用一维数组存放自栈底到栈顶的数据元素*/inttop;

/*附设一个位置变量top*/}SeqStack;

设S是SeqStack类型的指针变量。若栈底位置在数组低端，即s–>data[0]是栈底元素.那么：进栈：出栈：空栈：栈满：上溢：下溢：1）顺序栈s–>top加1；s–>top减1；s–>top=-1；s–>top=MaxSize-1。当栈满时再做进栈运算必定产生的空间溢出;当栈空时再做出栈运算产生的溢出。设数组S是一个顺序栈栈S的最大容量MaxSize=4，初始状态top=－1

10S[4]2310basetop=top+1S[top]=xtop

10

25

30S[4]2310topbase*x=S[top]top=top-1栈空10进栈30出栈S[4]2310top=-1top栈满top=MaxSize-1

10

25

30

40S[4]2310top=3basetop1）顺序栈(2)初始化SeqStack*Init_SeqStack(){ SeqStack*s; s=(SeqStack*)malloc(sizeof(SeqStack));

s->top=-1; returns;};#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return0;S->top++;S->data[S->top]=x;return(1);}a2a3a4987654321a10top（3）入栈操作#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return(0);

S->top++;S->data[S->top]=x;return(1);}a2a3a4987654321a10top（3）入栈操作#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return(0);S->top++;

S->data[S->top]=x;return(1);}a2a3a4987654321a10topx（3）入栈操作

intPop(SeqStack*S,ElemType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{*x=S->data[S->top];/*返回出栈元素*/S->top--;return(1);}

}通过指针变量x，带回出栈元素a2a3a4987654321a10top（4）出栈操作a2a3a4987654321a10top*x

intPop(SeqStack*S,ElemType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{

*x=S->data[S->top];/*返回出栈元素*/

S->top--;return(1);}

}（4）出栈操作（5）取栈顶元素elemtypeGetTop(SeqStack*s){ if(s->top<0) return0；//栈空

elsereturn(s->data[s->top]);}顺序栈的共享为两个栈申请一个共享的一维数组空间S[M]将两个栈的栈底分别放在一维数组的两端，分别是0，M－1a1a2a3b5b4b3b2b10M－1top1top2a1a2a3

0M－1top共享栈的结构定义a1a2a3b5b4b3b2b10M－1top1top2#defineM100typedefstructstack{ElemTypedata[M];inttop1,top2;}SharedStack;共享栈的操作a1a2a3b5b4b3b2b10M－1top1top2判空：判满：

top1==-1&&top2==M;top1+1==top2;共享栈的初始化SharedStack*InitSharedStack(){ SharedStack*s; s=(SharedStack*)malloc(sizeof(SharedStack)); s->top1=-1; s->top2=M; returns;}共享栈的进栈操作intPush(SharedStack*S,ElemTypex,inti){ if(S->top[0]+1==S->top[1])return(0); switch(i)//i=1或2，表示堆栈号

{ case1:

S->top1++; S->data[S->top1]=x;break;

case2: S->top2--; S->data[S->top2]=x;break; default: return(0);} return(1);}共享栈的出栈操作intPop(SharedStack*S,ElemType*x,inti){switch(i){ case1: if(S->top1==-1)return(0); *x=S->data[S->top1]; S->top1--;break;

case2: if(S->top2==M)return(0); *x=S->data[S->top2]; S->top2++;break; default: return(0);}return(1);}例一个栈的输入序列为1、2、3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？

（312出栈序列存在吗？）答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3、1出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。2）链栈栈的链式存储结构称为链栈它是运算受限的单链表。插入和删除操作仅限制在表头位置（通常情况）上进行。栈顶指针就是链表的头指针。(栈底)(栈顶)topa3a2a4a1^2）链栈链栈的类型说明如下：(类似单链表结点定义)#defineLinkStack

structLstackTypeLinkStack{ElemTypedata；

LinkStack

next；

}；进栈算法（带头结点）intPush(LinkStack*top,ElemTypee){LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));p->data=e;p->next=top->next;top->next=p;return(1);}a1a2an∧basetop2）链栈进栈元素e进栈算法intPush(LinkStack*top,ElemTypee){LinkStack*p;

p=(LinkStack*)malloc(sizeof(LinkStack));p->data=e;p->next=top->next;top->next=p;return(1);}

Pa1a2an∧basetop2）链栈进栈算法intPush(LinkStack*top,ElemTypee){LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));p->data=e;p->next=top->next;top->next=p;return(1);}

ePa1a2an∧basetop2）链栈进栈算法intPush(LinkStack*top,ElemTypee){LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));p->data=e;p->next=top->next;top->next=p;return(1);}

ePa1a2an∧basetop2）链栈进栈算法intPush(LinkStack*top,ElemTypee){LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));p->data=e;

p->next=top->next;

top->next=p;return(1);}

ePa1a2an∧basetop2）链栈出栈算法（带头结点）intPop(LinkStack*top,ElemType*x){LinkStack*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}a1a2an∧basetop2）链栈指针变量带回出栈元素的值出栈算法intPop(LinkStack*top,ElemType*x){LinkStack*temp;

temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}tempa1a2an∧basetop2）链栈出栈算法intPop(LinkStack*top,ElemType*x){LinkStack*temp;temp=top->next;if(temp==NULL)return(0);

top->next=temp->next;*x=temp->data;free(temp);}tempa1a2an∧basetop2）链栈出栈算法intPop(LinkStack*top,ElemType*x){LinkStack*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}tempa1a2an∧basetop*xa12）链栈出栈算法intPop(LinkStack*top,ElemType*x){LinkStack*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}tempa1a2an∧basetop*xa12）链栈初始化intInit_LinkStack(LinkStack**ptop){*ptop=NULL;//ptop为指向头指针top的指针return1;}a1a2an∧basetop2）链栈：不带头结点（教材）主函数：LinkStack*top;Init_LinkStack(&top); //初始化入栈a1a2an∧basetop2）链栈：不带头结点（教材）主函数：Push_LinkStack(&top,10); //入栈操作

xs出栈a1a2an∧basetop2）链栈：不带头结点（教材）主函数：ElemTypevalue;Pop_LinkStack(&top,&value); //出栈操作p*xa1采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。说明3栈的应用

问：为什么要设计堆栈？它有什么独特用途？1）调用函数或子程序非它莫属；2）递归运算的有力工具；3）用于保护现场和恢复现场；4）简化了程序设计的问题。例：见书

自学

Ch2线性结构

2.2栈和队列

2.2.1栈

1栈的定义及基本运算

2栈的存储结构和运算实现

3栈的应用

2.2.2队列

1队列的定义及基本运算

2队列的存储结构和运算实现

3队列应用举例

Review操作受限的线性表栈（Stack）运算只在表的一端进行队列（Queue）运算只在表的两端进行Review2.2.2队列（queue）

1）队列的定义及基本运算定义：队列是限定所有的插入操作在表的一端进行，而删除操作在表的另一端进行的线性表（头删尾插）允许插入的一端称为队尾—入队/进队；允许删除的一端称为队头—出队/离队；先进先出(FirstInFirstOut)的线性表，简称FIFO表通常设置：队头指针front—指向队头元素的前一个位置；队尾指针rear—指向队尾元素所在的存储位置；注意：删除元素后队列不向前移动元素

下图是队列的示意图：出队入队队头队尾

a1

a2

…

an

2.2.2队列（queue）队尾：在队列中，允许插入的一端队头：在队列中，允许删除的一端2）队列的基本运算(1)队列初始化：Init_Queue()初始条件：队q不存在。操作结果：构造了一个空队。(2)判队空操作：IsEmpty_Queue(q)

初始条件：队q存在。操作结果：若q为空队则返回为1，否则返回为0。(3)入队操作：In_Queue(q,x)初始条件：队q存在。操作结果：对已存在的队列q，插入一个元素x

到队尾，队发生变化。(4)出队操作：Out_Queue(q,x)/DELETE(q)初始条件：队q存在且非空。操作结果：删除队首元素，并返回其值，队发生变化。(5)读队头元素：Front_Queue(q,x)

初始条件：队q存在且非空。操作结果读队头元素，并返回其值，队不变。2）队列的基本运算2队列的存储结构及运算实现与线性表相同，仍为一对一关系。顺序队或链队，以循环顺序队列更常见。只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。◆存储结构◆运算规则◆实现方式

◆逻辑结构

队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（FIFO）的线性表。例如：队列Q=(a1

,a2,a3,……….,an-1,an)在队尾插入元素称为入队；在队首删除元素称为出队。队首队尾问：为什么要设计队列？它有什么独特用途？离散事件的模拟（模拟事件发生的先后顺序）；操作系统中的作业调度（一个CPU执行多个作业）；3.简化程序设计。答：1）顺序队列类型定义：#defineMaxSize1024typedefstructqueue{ElemTypedata[MaxSize];intrear,front;}SeqQueue;SeqQueue*q;e1,e2出队，e4入队队满e1e2e3

(b)rearfronte1,e2,e3入队

队空时，令rear=front=-1；当有新元素入队时，尾指针加1；当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素rear=front=-1(队空)front

3210(a)rearrear=3(c)e3e4front1）顺序队列顺序队示意图sq(队尾)(队首)fronta1a2a3dataa40.......99rear②队列会满吗？会，因为数组有长度限制，而且数组前端空间无法释放。①空队列的特征？约定：front==rear队尾后地址入队(尾部插入)：sq->rear++;sq->data[sq->rear]=x;出队(头部删除)：sq->front++; *x=sq->data[sq->front];讨论：SeqQueue*sq;假溢出

有缺陷？③怎样实现入队和出队操作？入队出队问：什么叫“假溢出”？如何解决？答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。front=-1front=-1front=2front=2front=5rear=-1rear=2rear=2rear=5rear=5(a)(b)(c)(d)(e)a5a6543210a5a6543210543210a1a2543210543210a3a4队列已满队列已满2）循环队列队列的结构空间首尾相连解决假溢出的途径———采用循环队列循环队列顺序队列a3a2a1frontrear023..在循环队列中进行出队、入队操作时，头指针、尾指针仍要加1，朝前移动。只不过当头/尾指针指向数组上界（MaxSize-1）时，其加1操作的结果是指向数组的下界0。这种循环意义下的加1操作可以描述为：

if(i+1==MaxSize)i=0;elsei++;利用模运算可简化为：i=(i+1)%MaxSizea3a2a112340rearfrontMaxSize-1MaxSize-2MaxSize-1a3a112340rearfront循环队列顺序队列在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案：①使用一个计数器记录队列中元素个数（即队列长度）；②少用一个单元，约定令队满特征为front=(rear+1)%MaxSize；★新问题：a2a5a4a6a7a8rearMaxSize-1a3a2a1frontrear023..MaxSize-2MaxSize-1（少用一个单元的）循环队列的状态判定如下：初始的空队列：操作过程中队列已空：操作过程中队列已满：a3a2a112340rearfront循环队列N-1front＝rear＝0；front＝rear；front＝(rear＋1)%MaxSize；（1）循环队列的入队操作思路：a）需要判断队列是否为满b）队尾指针后移，插入数据元素（2）循环队列的出队操作思路：a）需要判断队列是否为空b）队头指针后移，返回数据元素J2J3 J1J4

J5frontrear问3：

在具有MaxSize个单元的循环队列中，队满时共有多少个元素？MaxSize-1个6

问2：左图中队列长度L=？问题：循环队列中的“长度”到底是指总长度还是数据元素个数？一般情况下的长度（L）是指元素个数（不含头结点或空闲单元），而MaxSize才是指所有单元总数，即“容量”。问1：左图中队列容量

MaxSize

=？5

3）链队列队列的链式存储，称为链队列。

ana2a1

LQ.frontLQ.rear队头队尾注意：队头永远指向头