C语言队列教学课件

1、4.4 队列队列的概念及运算(逻辑结构)1第1页，共71页。队列只允许在表的一端进行插入，而在另一端进行删除。队头允许删除的一端队尾允许插入的一端队列的概念出队入队队头队尾a1 a2 an . 队列是先进先出表2第2页，共71页。队列的基本运算： 创建一个空队列Queue createEmptyQueue ( void ) 判队列是否为空队列int isEmptyQueue ( Queue qu ) 往队列中插入一个元素void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素void deQueue ( Queue qu ) 求队列头部元素的值DataT

2、ype frontQueue ( Queue qu ) 队列的运算3第3页，共71页。4.5 队列的实现4.5.1. 顺序队列4.5.2. 链队列4第4页，共71页。4.5.1 顺序队列 队列的顺序存储结构简称为顺序队列。顺序队列实际上是运算受限的顺序表。 由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当前队头元素和队尾元素在向量空间中的位置。5第5页，共71页。#define MAXNUM 100struct SeqQueue datatype qMAXNUM; int f,r; ;typedef struct SeqQueue *PSeqQueue;PSeqQueue

3、sq;顺序队列的定义4.5.1 顺序队列6第6页，共71页。fr76543210k1k2k3frrfk8k7队列空队列数组越界顺序队列约定队列满k1k2k3fk8rk4k5k6k7第7页，共71页。开始： sq-f=0; sq-r=0; 入队： sq-datasq-r=x; sq-r+; 出队： sq-f+; 顺序队列的入队和出队4.5.1 顺序队列8第8页，共71页。元素个数（队列长度）:（sq-r) - (sq-f) 若（sq-r) - (sq-f)=0 ，则队列长度为0，即空队列。再出队会“下溢” 若 (sq-r)-(sq-f)=MAXNUM，则队满。队满时再入队会“上溢”4.5.1 顺

4、序队列9第9页，共71页。76543210frk1k2k3frrfk6k5队列空队列数组越界顺序队列第10页，共71页。4.5.1 顺序队列假上溢：当前队列并不满，但不能入队。每次出队时向前移一位置。大量移动元素循环队列原因:被删除元素的空间没有再被使用解决:11第11页，共71页。采用循环队列克服“假上溢”。sq-rsq-fMAXNUM-101指针移动方向12第12页，共71页。入队：if (sq-r+1=MAXNUM) sq-r=0; else sq-r+;利用模运算 sq-r=(sq-r+1)%MAXNUM 出队： sq-f=(sq-f+1)%MAXNUM采用循环队列克服“假上溢”4.5

5、.1 顺序队列13第13页，共71页。 某一元素出队后，若头指针已从后面追上尾指针，则当前队列为空： sq-f=sq-r 某一元素入队后，若尾指针已从后面追上头指针，则当前队列为满： sq-f=sq-r 因此，仅凭 sq-f=sq-r 是无法区别队列空还是队列满。 判断队空和队满4.5.1 顺序队列14第14页，共71页。解决办法标志变量测试尾指针在循环意义下是否等于头指针 判别队列满的条件： (sq-r+1)%MAXNUM=sq-f使 sq-f=sq-r 成为判断队列空的条件4.5.1 顺序队列元素个数是MAXNUM-115第15页，共71页。sq.rearsq.frontk1k2k7k6k

6、5k4k3sq.frontsq.rear图(a)空队列图(b)队列满 图4.9 循环队列第16页，共71页。4.5.1 顺序队列在循环队列上实现五种基本运算： 1.置空队 2.判队空 3.取队头元素 4.入队 5.出队17第17页，共71页。循环队列front= n-3an-3an-2012MaxQsize-1rear=n-1n-3rear= n-1an-3an-20.1.front=n-3n-2第18页，共71页。插入元素 ： rear顺时针移动一位front=n-3an-3an-2012MaxQsize-1rear=0 xn-3an-3rear=0an-20.1n-1.front=n-3n

7、-2xrear = (rear+1) MOD MaxQSize第19页，共71页。删除元素：front顺时针移动一位front = (front+1) MOD MaxQSize;rear0front=9.1.CD删除Crearfront=00.1.D第20页，共71页。循环队列front指定队首位置，删除一个元素就将front顺 时针移动一位； rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位； count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。 队空：count=0队满：count= MaxQSize第21页，共71页。数组队列实

8、现在队列的头部取出元素。普通的队列由于空间利用率不高，所以我们一般都用循环队列。循环队列中最重要的的两个操作就是判断是否为空和是否已满。当head=tail时，表示队列为空。当(tail+1)%MAX_SIZE = head，表示队列已满。我判断队满的方法：牺牲一个单元来区分对空和队满，入队时少用一个队列单元，相当于浪费一个存储空间。“队头指针的队尾指针的下一位置作为队满的标志”。第22页，共71页。进队列 EnQueue(int value) /要先判断队列是否已满 if (tail + 1) % QUEUE_SIZE = head) printf(队列已满，无法从队尾插入元素n); els

9、e queuetail = value; tail = (tail + 1) % QUEUE_SIZE; 第23页，共71页。/出队列 int DeQueue() int temp; if (tail = head) printf(队列为空，元素无法出队列n); else temp = queuehead;head = (head + 1) % QUEUE_SIZE;printf(%dn,temp);return temp; 第24页，共71页。/判断队列是否为空 int IsEmpty() if (head = tail) printf(队列为空n); return 1; printf(队列

10、不为空n); return 0; 第25页，共71页。判断队列是否已满 /* * 我这里判断队满的的方法： 牺牲一个单元来区分队空和队满，入队时少用一个队列单元。如果数组的大小为Size,那么实际只能存放(Size-1)个元素。（这是比较常用的判满的方式） * */ int IsFull() if (tail + 1) % QUEUE_SIZE = head) printf(队列已满n); return 1; printf(队列未满n); return 0; 第26页，共71页。/打印出队列元素 void PrintQueue() for (int i = head; i tail; i+)

11、printf(%d ,queuei); printf(n); 第27页，共71页。 #include #define QUEUE_SIZE 200 int queueQUEUE_SIZE;int head=0;/头指针int tail=0;/尾指针 int main（） EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8); PrintQueue(); DeQueue();DeQueue(); PrintQueue(); return 0; 第28页，共71页。1. 置空队PSeqQueue createEmptyQueue_seq( v

12、oid ) PSeqQueue sq; sq = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (sq=NULL)printf(Out of space! n);else sq-f = 0; sq-r = 0;return (sq);29第29页，共71页。2. 判队空int isEmptyQueue_seq( PSeqQueue sq ) return (sq-f = sq-r);30第30页，共71页。3. 取队头元素DataType frontQueue_seq( PSeqQueue sq )/* 对非空队列,求队列头部元素 */ retur

13、n (sq-qsq-f); 31第31页，共71页。4. 入队void enQueue_seq( PSeqQueue sq, DataType x )/* 在队列中插入一元素x */ if( (sq-r + 1) % MAXNUM = sq-f ) printf( Full queue.n ); else sq-qsq-r = x; sq-r = (sq-r + 1) % MAXNUM; 32第32页，共71页。5. 出队void deQueue_seq( PSeqQueue sq )/* 删除队列头部元素 */ if( sq-f = sq-r )printf( Empty Queue.n )

14、; elsesq-f = (sq-f + 1) % MAXNUM;33第33页，共71页。4.5.2 链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。34第34页，共71页。 k0 k1 k2 kn-1. 图4.10 队列的链接表示plqu fr第35页，共71页。 struct Node; typedef struct Node *pNode; struct Node DataType info; pNodelin

15、k; ; struct LinkQueue PNodef; PNoder; ; typedef struct LinkQueue, *PLinkQueue;队列的链接表示36第36页，共71页。 *plqu头结点plqu-fplqu-r 头结点 队头结点plqu-fplqu-r空和非空的链队列. 37第37页，共71页。4.5.2 链队列在链队列上实现的五种基本运算如下： 1. 置空队 2. 判队空 3. 取队头结点数据 4. 入队 5. 出队38第38页，共71页。1. 置空队（算法4.21）PLinkQueue createEmptyQueue_link( ) PLinkQueue plq

16、u; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue); if (plqu!=NULL) plqu-f = NULL; plqu-r = NULL; elseprintf(Out of space! n);return (plqu); 39第39页，共71页。2. 判队空（算法4.22）int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL);40第40页，共71页。3. 取队头结点数据（算法4.25）DataType frontQueue_link( PLinkQueu

17、e plqu )/* 在非空队列中求队头元素 */ return (plqu-f-info); 41第41页，共71页。4. 入队（算法4.23）void enQueue_link( PLinkQueue plqu, DataType x ) PNode p; p = (PNode )malloc( sizeof( struct Node ) ); if ( p = NULL )printf(Out of space!); else p-info = x; p-link = NULL; if (plqu-f = NULL) plqu-f = p; plqu-r = p; else plqu-r

18、-link = p; plqu-r = p; 42第42页，共71页。5. 出队（算法4.24）void deQueue_link( PLinkQueue plqu ) PNode p; if( plqu-f = NULL ) printf( Empty queue.n ); else p = plqu-f; plqu-f = plqu-f-link; free(p);43第43页，共71页。农夫过河问题 : 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。显然，因为狼能吃羊，而羊爱吃白菜

19、，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河? 4.6 队列的应用农夫过河问题*44第44页，共71页。 用计算机实现上述求解的搜索过程可以采用两种不同的策略： 一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)。实现这两种策略所依赖的数据结构正好是前面介绍的队列和栈。本节讨论队列的应用，所以下面重点介绍广度优先的策略。 4.6 队列的应用农夫过河问题*45第45页，共71页。模拟农夫过河问题：用四位二进制数分别顺序表示农 夫、狼、白菜和羊的位置。 0表示在

20、南岸，1表示在北岸Path：15，6，14，2，11，1，9，0从初始状态0到最终状态15的动作序列为： 第46页，共71页。队列的应用 医院门诊部病人管理系统工作过程：当一病人进入门诊室时，负责挂号的义务人员就根据观察和简短询问发给他一个从0（病危）到4（一般）变化的优先数，让他到相应优先数队列中去排队等待 。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人就诊。原则：优先级高的先考虑，同一优先级中，则先来先考虑。47第47页，共71页。队列的应用 医院门诊部病人管理系统组织数据的方式数据结构分析： 系统中的数据：病人的姓名，优先数，到达时间 48第48页，共71页。队列的应用 医院门

21、诊部病人管理系统组织方式一：若病人以其到达门诊部的先后次序组织到一个队列，则具体到达时间可不考虑。到达次序优先数姓名 1 2 3 4 5 6 7 2 3 0 3 0 2 1林文郑江鲁明陈真李军王红张兵这样的单队列对按就诊原则来确定下一就诊病人是很不方便的，还将破坏队列的操作原则。49第49页，共71页。队列的应用 医院门诊部病人管理系统组织方式二：多个队列（队列数组）：队列数组的第i个元素是优先级为i的队列。优先数隐含在队列的编号中。鲁明01234李军张兵林文王红郑江陈真50第50页，共71页。队列的应用 医院门诊部病人管理系统就病人管理系统来说，功能菜单中至少有以下两个功能：（1）病人登记A

22、ddPatient( ) 提示并读入病人优先数i； 提示并读入病人名 调用链队列的入队算法EnQueue() （2）确定下一个就诊病人 GetPatient( ) 按就诊原则确定和显示下一个就诊病人名 即：若优先数0的队列非空，则下一就诊病人为队首元素，否则，考虑优先数1的队列；依次类推。 51第51页，共71页。线性表存储结构 运 算 队列 链 表顺序表 栈 顺序栈 链 栈 顺序队列 链队列 线性表小结52第52页，共71页。顺序表typedef int datatype ;#define MAXNUM 1024typedef struct datatype dataMAXNUM ;int

23、last ; sequenlist;53第53页，共71页。链 表typedef int datatype;typedef struct node datatype data;struct node *next; linklist;linklist *head, *p;54第54页，共71页。 顺序栈 typedef int datatype;#define MAXNUM 64typedef struct datatype dataMAXNUM; int top; PSeqStack;PSeqStack *s;55第55页，共71页。 链 栈 typedef int datatype;type

24、def struct node datatype data; struct node *next; linkstack;linkstack *top;56第56页，共71页。 顺序队列 typedef struct datatype dataMAXNUM; int f,r; sequeue;sequeue *sq;57第57页，共71页。 链队列 typedef struct linklist *f , *r; linkqueue;linkqueue *q;58第58页，共71页。2.6 设计一算法，逆置带头结点的动态单链表 L。void reverse(linklist *L) /*假设链表

25、带有头结点*/ linklist *p,*s; p=L-next; /*用p指向当前结点*/ L-next=NULL; while (p) s=p; /*用s保存当前结点地址*/ p=p-next; /*链表指针p后移*/ /*将当前结点链到表头*/ s-next=L-next; L-next=s; /*reverse*/ 59第59页，共71页。2.10 已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。linklist

26、 *ra,*rb,*rc;void sort(linklist *head) linklist *s,*p=head; /*建立三个空的循环链表*/ ra=malloc(sizeof(linklist); ra-next=ra; rb=malloc(sizeof(linklist); rb-next=rb; rc=malloc(sizeof(linklist); rc-next=ra;60第60页，共71页。 while (p) s=p; p=p-next; if (s-data=0)&(s-datanext=ra-next; ra-next=s; ra=s; /*将数字字符结点链接到A表*/

27、 else if (s-data=a)&(s-datadata=A)&(s-datanext=rb-next; rb-next=s; rb=s; /*将字母字符结点链接到B表*/ else s-next=rc-next; rc-next=s; rc=s; /*将其它字符结点链接到C表*/ /*while*/ /*sort*/61第61页，共71页。3.3 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。int Judgement1(linklist *head)/*若对称返回 1，否则返回 0*/ PSeqStack *s; linklist *

28、p; int i, n=0; /*n为计数器，记录链表的长度*/ p=head; /*先用循环求出链表的长度*/ while(p) n+ ; p=p-next ; 62第62页，共71页。3.3 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。SETNULL(s); /*设置空栈 s*/p=head;/*先将一半字符进栈*for (i=1;idata); p=p-next; /*若字符个数为基数，则跳过中间的字符*if (n%2) p=p-next;63第63页，共71页。3.3 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关

29、系。要求用尽可能少的时间完成。 /*当字符串未扫描完毕且栈非空时进行匹配*/ while(p&!EMPTY(s) if (p-data!=POP(s) break; else p=p-next; if (! p&EMPTY(s) return 1; else return 0;/*Judgement*/64第64页，共71页。3.4 设计算法判断一个算术表达式的圆括号是否正确配对Judgement2() /*判断表达式是否配对，表达式以#结束*/ PSeqStack sta; char ch,chpop; int valid; SETNULL(&sta); PUSH(&sta,#); /*把#

30、放在栈底*/ ch=getchar(); valid=TRUE; /*valid为FALSE表示括号配对失败*/65第65页，共71页。 while(ch!=#) if (ch=() /*读入字符为左括号时进栈*/ PUSH（&sta,ch）； else if (ch=)/*读入字符为右括号时出栈*/ chpop=POP(&sta); if (chpop=#) /*右括号多于左括号*/ valid=FALSE; break; /*else*/ ch=getchar();/*读入下一字符*/ /*while*/ 3.4 设计算法判断一个算术表达式的圆括号是否正确配对66第66页，共71页。if (POP(&sta)!=# ） valid=FALSE; /*左括号多于右括号*/if (valid) printf(“括号配对成功“）；else printf(“括号配对不成功”）； /*Judg