• / 65
  • 下载费用:10 金币  

栈和队列.ppt

关 键 词:
栈和队列.ppt
资源描述:
第4章 栈和队列,4.1 栈及其基本运算 4.2 队列及其基本运算 注意:栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是运算规则较线性表有更多的限制 。,4.1 栈及其基本运算,1.什么是栈,,在栈中,允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。,,栈(stack ) 是限定在一端进行插入与删除的线性表。,在图4-1中,栈元素是以a1,a2,…,an 的顺序进栈,而出栈(退栈)的次序却是 an,an-1 , … ,a2,a1。也就是说栈是“先进后出”或,,“后进先出”的线性表。通常用整型变量top (也称top为栈顶指针或栈顶指示器)来指示当前栈顶的位置。,往栈中插入一个元素称为进栈(入栈)运算。从栈中删除一个元素(即删除栈顶元素)称为退栈(出栈)运算。栈顶指针top 动态地反映了栈中元素的变化情况。图4-2说明了在顺序栈中进栈和退栈时栈中元素和TOP的关系。,,2.栈的顺序存储及其基本运算栈的顺序结构通常用一个一维数组和一个整形变量来实现。利用数组来存储栈中的所有元素,利用整形变量指示栈顶元素的下标位置。顺序栈的类型可定义如下:,栈这种数据结构在日常生活中经常见到。例如,学生军训时使用的自动步枪子弹夹,就是一种栈的结构,最先压入子弹夹中的子弹最后才能射出。,#define MaxSize 100 /*设预分配的栈空间最多为100个元素*/ typedef char ElemType; /*设栈元素的数据类型为字符型*/ typedef struct {ElemType stack[MaxSize];int top;/*top指示栈顶元素的位置*/ }SeqStack;,设s是SeqStack类型的指针变量,在顺序栈中,一般用s-top==0表示空栈,但用C语言描述时,由于约定数组的下标从0开始,故用s-top==-1表示空栈;向栈中插入一个元素时(进栈),首先使s-top加1以指示新的栈顶位置,然后再把元素赋值到这个位置。当从栈中删除一个元素时(出栈),首先取出栈顶元素,然后使s-top减1以指示新的栈顶位置。当s-top已经指向了MaxSize-1表示栈满。向一个满栈插入元素和从一个空栈删除元素会产生上溢或下溢。上溢是一种出错状态应该避免,下溢则常用来作为程序控制转移的条件。,栈的五种基本运算是:构造一个空栈、判断栈是否为空、进栈、退栈与读栈顶元素。下面介绍相应的算法。,1)构造空栈构造空栈是指栈的初始化即给s-top赋值-1,算法如下: void InitStack(SeqStack *s) {s-top=-1; },2)判断栈是否为空判断栈是否为空是指判断s-top是否等于-1,若是,则表示栈空返回1;否则返回0,算法如下: int StackEmpty(SeqStack *s)/*int可省略不要*/ {return s-top==-1; },3) 进栈,进栈也称入栈或压栈,是指在栈顶位置插入一个新元素。操作时,首先将栈顶指针s-top 加1以指示新的栈顶位置,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置(即s-top==MaxSize-1)时,说明栈空间已满。向一个满栈插入元素会产生“上溢”错误,算法如下:,void push(SeqStack *s,ElemType x) { /* 插入一个值为x的新元素*/if(s-top==MaxSize-1){printf(“\n 栈已满,上溢!“);exit(1);}++s-top; /*栈顶指针加1*/s-stack[s-top]=x; /*值为x的新元素进栈*/ },4)出栈出栈也称退栈,是指删除栈顶元素。操作时,首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针s-top 减1。当栈顶指针为s-top==-1时,说明栈空。此时进行出栈操作会产生“下溢”错误,算法如下:,,ElemType pop(SeqStack *s) {if(StackEmpty(s)){ /*调用判断空栈函数若栈空则下溢!*/printf(“\n 栈已空,下溢!“);exit(1);}return s-stack[s-top--]; /*返回栈顶元素,栈顶指针减1*/},5)读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。必须注意,这个运算不删除栈顶元素只是将它的值赋给一个变量,因此在这个运算中栈顶指针不会改变。但当栈为空时,就读不到栈顶元素了,算法如下:,,ElemType GetTop(SeqStack *s) {if(StackEmpty(s)){printf(“\n 栈已空!“);exit(1);}return s-stack[s-top]; /*若栈非空,则返回栈顶元素,但不删除*/ },3.栈的链式存储结构及运算栈的链式存储结构可通过单链表来实现,在单链表中,每一个结点表示栈中的一个元素。由于栈是在链表头部进行操作的,故链式栈不需要设置头结点。栈顶指针就是链表的头指针,它唯一的确定了一个栈。假设将元素a1,a2,a3,…,an顺序进栈,则a1为栈底元素,an为栈顶元素,如图4-3所示。,对链式栈的基本操作与顺序栈相类同,通常进栈和出栈,相对使用较多。进栈就是向链栈的栈顶插入一个元素。此时,可使该元素结点的指针域,指向原来的栈顶结点,而栈顶指针则修改为指向该元素的结点,这样,该结点就成为新的栈顶结点。 出栈就是从链栈的栈顶删除一个元素。此时可取出栈顶元素并使栈顶指针指向原栈顶结点的后继结点。链栈的类型说明及其常见基本操作如下:1) 链栈的类型说明,typedef char ElemType; /* 新类型ElemType是字符型*/ typedef struct stacknode {ElemType data;/*栈的值域是字符型*/struct stacknode *next; }StackNode; /*StackNode为结构型*/ typedef struct{StackNode *top;/*栈顶指针*/ }LinkStack; /*LinkStack为结构类型*/,2) 链栈的基本操作①构造一个空链栈 void InitStack(LinkStack *s) {s-top=NULL; /*栈顶指针置空*/ }②判断链栈是否为空栈 int StackEmpty(LinkStack *s) { /*若栈空,则返回1否则返回0*/return s-top==NULL; },③进栈(入栈或压栈) void push(LinkStack *s,ElemType x) { StackNode *p;p=(StackNode *)malloc( sizeof(StackNode)); if(!p){ printf(“\n 存储分配失败!“);exit(1);}p-data=x; /*新结点值域赋值x*/p-next=s-top;/*新结点*p插入到栈顶*/s-top=p; /*修改栈顶指针*/ },④退栈(出栈) ElemType pop(LinkStack *s) {ElemType x;StackNode *p;p=s-top;if(StackEmpty(s)){/*调用判断栈是否为空的函数,若栈空,则下溢*/printf(“\n 栈已空,下溢!“);exit(1);},x=p-data;/*x赋值欲删的栈顶结点数据*/ s-top=p-next; /*删除栈顶结点,修改栈顶指针*/free(p); /*释放已删结点的空间*/return x;/*返回已删结点的数据*/ },,⑤读链栈的栈顶元素 ElemType GetTop(LinkStack *s) {if(StackEmpty(s)){printf(“\n 栈已空!“);exit(1);}return s-top-data; /*若链栈非空,则返回栈顶元素,但不删除*/ },4. 栈的应用举例数制转换过程是栈的典型应用。例如将一个十进制整数n转换为r进制数,通常采用“除基数r取余法”的转换方法(即先将n逐次除以r,然后倒序写出余数)。在转换过程中依次所得的余数,就是由低到高得到的r进制数中的每一位数字。系统将余数存储到一个栈中,第一个余数存在栈底、最后一个余数存在栈顶。输出时,系统从栈顶依次释放余数所占存储区,也就是说由高到低输出每一数位的值,最终得到转换结果。图4-4所示的是将十进制数74转换为八进制数的过程,结果为八进制数112。,下面给出将十进制正整数n转换为r进制数的程序。,#include #include /*头文件stdlib.h中含有exit()*/ #define MaxSize 100 /*说明欲分配的栈空间最多为100个元素*/ typedef int ElemType; /*说明栈元素的数据类型为整型*/,typedef struct { ElemType stack[MaxSize];int top;}SeqStack;/* SeqStack为结构类型*/ void InitStack(SeqStack *s){ /*将顺序栈s初始化为空栈*/s-top=-1;} int StackEmpty(SeqStack *s){ /*判断栈s是否为空若为空则返回1*/return s-top==-1;},void push(SeqStack *s,ElemType x) { /*进栈,即向栈s中插入元素*/if(s-top==MaxSize-1){printf(“\n stack overflow!“);exit(1);}++s-top;s-stack[s-top]=x;},int pop(SeqStack *s) { /*退栈,即删除栈s的栈顶元素*/if(StackEmpty(s)){printf(“\n stack underflow!“);exit(1);}return s-stack[s-top--]; },void conversion(long num,int r) { /*用除r取余法将结果保存到栈s中*/SeqStack s;int k;int x;InitStack(/*修改num的值为被r除的商*/},printf(“\n“) ;while(!StackEmpty(} },void main(){ /*主函数*/long n;,int r; printf(“\n inpute n,r :“) ; scanf(“%ld ,%d “, /*调用转换函数并输出转换结果*/ }注:r可为8、2、16等。例如,当运行此程序时,n为74,r为2,则转换结果为二进制数1001010。,4.2 队列及其基本运算,1.什么是队列,队列(queue )是一种只允许在表的一端进行插入,而在另一端进行删除的线性表。允许插入(入队)的一端称为队尾(rear),允许删除(出队)的一端称为队头(front)。不含元素的队列称为空队列。若将元素按a1,a2,a3,…,an 的顺序入队,则a1为队头元素,an为队尾元素,如图4-5所示。,退出队列时,也只能按a1,a2,a3,…,an 的顺序出队。这和日常生活中的排队是一致的。,在队列中,最先插入的元素,将最先能够被删除。反之,最后插入的元素,将最后才能被删除。因此,队列又称为“先进先出” 或后进后出的线性表。,队列也有顺序存储和链式存储两种情况。,2. 队列的顺序存储结构和基本运算,队列的顺序存储结构称为顺序队列。顺序队列通常用一个一维数组来存放队列中的数据元素。此外,还需设置两个整形变量front和rear作为队头指示器和队尾指示器,分别指示队头和队尾元素在向量空间中的位置。,我们约定在队列初始化时,这两个指示器均置0值。入队时,将新元素插入到rear所指位置后,再将rear的值加1;出队时,删除front所指位置的元素后,再将front的值加1并返回被删元素。由此可见,当队头和队尾指示器值相等时,队列为空 。在非空队列里,front始终指向队头元素,而rear始终指向队尾元素的下一位置。在队列中,队尾指示器 rear 与队头指示器 front 共同反映了队列中元素动态变化的情况。,假设给队列分配的最大存储空间为4(如图4-6所示)。在图4-6(b)所示满队列状态下,如果还有新元素请求入队,则会出现“上溢” 错误。,在图4-6(c)所示状态下,如果还有新元素请求入队,这时,虽然队列的实际可用空间没有占满,但由于尾指针已超越存储空间的上界,故不能做入队操作,否则会出现“假上溢”的错误;在图4-6(d)所示状态下,如果还要进行出队操作,由于这时队列已空,队列的头、尾指针均已超越存储空间的上界,故不能进行出队操作,否则会出现“下溢”的错误。,3.循环队列及其运算为避免发生顺序队列的“假上溢”现象,充分利用队列的存储空间,可以将顺序队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用,我们称这样的队列为循环队列,如图4-7所示。,在循环队列中进行出队、入队操作时,头、尾指针仍要加1,只不过当头尾指针指向上界时,其加1的操作结果是指向下界0。假设当前循环队列最多能容纳 MAXSIZE个元素,这种循环意义下的加1操作可表示为:,i=(i+1)%MAXSIZE /* i表示front或rear */,在图4-7所示的循环队列中,队列的最大容量是4。在图4-7(b)所示的状态下,再插入元素D,则队列空间就会被占满,变成图4-7(c)所示的状态。此时,存在与4-7(a)相,同的front==rear关系。由此可知,在循环队列中,仅依据头尾指针相等,是无法判断队列是“空”还是“满”。要解决这个问题,常用的方法是:少用一个元素空间,约定入队前,若尾指针加1后等于头指针,则认为队列满(rear所指单元始终为空)先给出循环队列类型的定义;再给出用此方法实现循环队列的几种基本操作。,#define MAXSIZE 100 /*符号常量MAXSIZE代表队列的最大容量100*/ typedef char ElemType; /*说明新类型ElemType是字符型*/ typedef struct {ElemType data[MAXSIZE];int front; int rear; }CircularQueue; /*新类型CircularQueue是结构体*/,1) 构造一个空队列 Void InitQueue(CircularQueue *q) {q-front=q-rear=0; }2)判断队列空 int QueueEmpty(CircularQueue *q) { /*队列为空返回1,否则返回0*/if(q-front==q-rear) exit(1);else exit(0); },3)入队 void InsertQueue(CircularQueue *q,ElemType x) {if((q-rear+1)%MAXSIZE==q-front){printf(“\n 队满,上溢!“); exit(1);}q-data[q-rear]=x; /*新元素插入到队尾*/ q-rear=(q-rear+1)%MAXSIZE;/*尾指针加1*/ },4)出队 ElemType DeleteQueue(CircularQueue *q) {ElemType x;if(QueueEmpty(q)){printf(“\n 队空,下溢!“);exit(1);}x=q-data[q-front]; /*取出队头元素*/q-front=(q-front+1)%MAXSIZE;/*队头指针加1*/return x; },5)读取队头元素 ElemType GetHead(CircularQueue *q) {ElemType x;if(QueueEmpty(q)) {printf(“\n 队空,下溢!“);exit(1); } x=q-data[q-front]; /*取出队头元素*/ return x; },4.链队列队列的链式存储结构称为链队列。因为需要在表头进行删除操作和在表尾进行插入操作,所以在链队列中,需要使用队头和队尾两个指针。其中队尾指针指向链队列的最后一个结点。于是,一个链队列就由一个头指针和一个尾指针唯一地确定了。链队列和线性表的单链表一样,为了操作方便,可以给链队列增加一个头结点,并令头指针指向头结点,如图4-8所示。链队列的类型定义如下:,typedef char ElemType; typedef struct queuenode { /*链队列中的结点类型 */ElemType data;struct queuenode *next; }QueueNode; typedef struct { /*将两个指针封装在一起*/QueueNode *front;/*队头指针*/QueueNode *rear; /*队尾指针*/ }LinkQueue;,图4-8(a)是空链队列的示意图,图中q为LinkQueue型指针;图4-8(b)是非空链队列的示意图。,链队列的基本操作有5种,相应的算法如下:1)构造一个空队列 void InitQueue(LinkQueue *q) {q-front=q-rear=(QueueNode *) malloc(sizeof(QueueNode));/*建新结点*/if(!q-front){printf(“\n 存储分配失败!“);exit(1);}q-front-next=NULL; },,2)判断空队列 int QueueEmpty(LinkQueue *q) {if(q-front==q-rear }3)入队 void InsQueue(LinkQueue *q,ElemType x),{ QueueNode *p;p=(QueueNode *)malloc(sizeof(QueueNode)); if(!p){ printf(“\n 存储分配失败!“);exit(1);}p-data=x;p-next=NULL;q-rear-next=p;/*新结点插入到队尾*/q-rear=p;/*队尾指针指向新结点*/ },4)出队 ElemType DelQueue(LinkQueue *q) {QueueNode *p;ElemType x; if(QueueEmpty(q)){printf(“\n 队列空,下溢!“);exit(1);},p=q-front-next; /*指向队头结点*/x=p-data; /*取出队头结点的数据*/q-front-next=p-next; /*修改队头指针即将队头指针从链上摘下*/if(q-rear==p)q-rear=q-front; /*若取出队头元素后,原队列为空,修改队尾指针*/free(p); /*释放被删的队头结点*/return(x); /*返回队头结点的数据*/ },5)读取队头元素 ElemType GetHead(LinkQueue *q) {QueueNode *p;ElemType x;if(QueueEmpty(q)){printf(“\n 队列空,下溢!“);exit(1);}p=q-front-next; /*指向队头结点*/x=p-data; /*取出队头结点的数据*/return(x); /*返回队头结点的数据*/ },5.队列应用举例,例如,某银行储蓄所有一个服务窗口,该窗口在某个时刻只能接待一位顾客,假设为一位顾客服务的时间为定值,在顾客人数众多时需要在窗口排队,若队列用q表示,顾客到达的时间是随机的,约定按如下方式处理:每单位时间内产生一个随机数arrive (0arrive1),如果arrive 小于prob( 0 prob 1 ,由程序输入的特定值),则记为有1人到达。顾客用整数表示,其值为该顾客进入队列的时间。,时间用time表示,其初值为0,假设time每变化一个单位对应于实际时间1分钟。当顾客到达时,若服务窗口空闲,顾客的等待时间为0,否则等待时间为服务窗口开始为顾客服务的时间减去顾客到达的时间。可以模拟计算在时间段simutime(由程序输入)内,上述服务窗口的总服务人数(cus_num)和每个顾客平均排队所需的等待时间(aver),程序如下:,#include #include #define MAXSIZE 100 /*符号常量MAXSIZE表示100*/,typedef struct {int data[MAXSIZE]; int front; /*队头指针*/int rear; /*队尾指针*/ }queue; /*新类型queue为结构体类型*/ /*队列初始化函数*/ void InitQueue(queue *q) {q-front=q-rear=0; },/*入队函数*/ void EnQueue(queue *q,int x) {if((q-rear+1) % MAXSIZE ==q-front){printf(“\n overflow!“);/*队满上溢*/exit(1);}q-data[q-rear]=x;/*新元素插入队尾*/q-rear=(q-rear+1)%MAXSIZE;/*尾指针加1*/},/*判断队列是否为空函数*/int QueueEmpty(queue *q) { /*队列为空,返回1,否则返回0 */if(q-rear==q-front) return 1;else return 0;},/*出队函数*/int DeQueue(queue *q) {int x;if(QueueEmpty(q)){printf(“\n underflow!“);/*队空下溢*/exit(1);}x=q-data[q-front];/*取出头元素*/q-front=(q-front+1)%MAXSIZE;/*头指针加1*/return x;},/*主函数*/ void main() {queue q;int time,servetime,simutime;int busy=0,sumwaits=0,cus_num=0;float prob,arrive,aver;printf(“\n input the prob: “);/*输入特定检查值*/scanf(“%f“,,printf(“\n input the simutime:“); /*输入模拟时间*/scanf(“%d“,/*窗口有顾客,顾客所需时间自减*/,if(busy==0 /*顾客等待时间累加*/}},if(cus_num==0) aver=0.0 ; else aver=1.0*sumwaits/cus_num;printf(“\n %d cus_num,aver: %4.1f “, cus_num,aver); /*输出服务总人数cus_num 及每位顾客的平均等待时间aver*/} 注:若运行时 prob=0.8,servetime=2,simutime=30,则输出结果为 cus_num=16,aver=6.9 。,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:栈和队列.ppt
链接地址:https://www.weizhuannet.com/p-10071073.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开