C语言队列课件

4.4队列队列的概念及运算(逻辑结构)1队列只允许在表的一端进行插入，而在另一端进行删除。队头允许删除的一端队尾允许插入的一端队列的概念出队入队队头队尾a1

a2

an

...

队列是先进先出表2队列的基本运算：

创建一个空队列

QueuecreateEmptyQueue(void)

判队列是否为空队列

int

isEmptyQueue(Queuequ)

往队列中插入一个元素

voidenQueue(Queuequ,DataTypex)

从队列中删除一个元素

voiddeQueue(Queuequ)

求队列头部元素的值

DataType

frontQueue(Queuequ)

队列的运算34.5队列的实现4.5.1.顺序队列4.5.2.链队列44.5.1顺序队列

队列的顺序存储结构简称为顺序队列。顺序队列实际上是运算受限的顺序表。

由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当前队头元素和队尾元素在向量空间中的位置。5#defineMAXNUM100struct

SeqQueue{datatypeq[MAXNUM];

intf,r;};typedef

struct

SeqQueue*PSeqQueue;PSeqQueuesq;顺序队列的定义4.5.1顺序队列6fr76543210k1k2k3frrfk8k7①队列空④队列数组越界顺序队列②约定③队列满k1k2k3fk8rk4k5k6k7开始：sq->f=0;sq->r=0;入队：

sq->data[sq->r]=x;sq->r++;出队：

sq->f++;顺序队列的入队和出队4.5.1顺序队列8元素个数（队列长度）:（sq->r)-(sq->f)

若（sq->r)-(sq->f)=0，则队列长度为0，即空队列。再出队会“下溢”

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

sq->r=(sq->r+1)%MAXNUM出队：

sq->f=(sq->f+1)%MAXNUM采用循环队列克服“假上溢”4.5.1顺序队列13

某一元素出队后，若头指针已从后面追上尾指针，则当前队列为空：

sq->f=sq->r

某一元素入队后，若尾指针已从后面追上头指针，则当前队列为满：

sq->f=sq->r

因此，仅凭

sq->f=sq->r

是无法区别队列空还是队列满。

判断队空和队满4.5.1顺序队列14解决办法标志变量测试尾指针在循环意义下是否等于头指针

判别队列满的条件：

(sq->r+1)%MAXNUM=sq->f使sq->f=sq->r

成为判断队列空的条件4.5.1顺序队列元素个数是MAXNUM-115sq.rearsq.frontk1k2k7k6k5k4k3sq.frontsq.rear图(a)空队列图(b)队列满

图4.9循环队列4.5.1顺序队列在循环队列上实现五种基本运算：

1.置空队

2.判队空

3.取队头元素

4.入队

5.出队17循环队列front=n-3……an-3an-2012MaxQsize-1rear=n-1n-3rear=n-1an-3an-20.1...front=n-3n-2插入元素：rear顺时针移动一位front=n-3……an-3an-2012MaxQsize-1rear=0xn-3an-3rear=0an-20.1n-1...front=n-3n-2xrear=(rear+1)MODMaxQSize删除元素：front顺时针移动一位front=(front+1)MODMaxQSize;rear0front=9.1...CD删除Crearfront=00.1...D循环队列front指定队首位置，删除一个元素就将front顺时针移动一位；

rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；

count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。队空：count=0队满：count=

MaxQSize数组队列实现在队列的头部取出元素。普通的队列由于空间利用率不高，所以我们一般都用循环队列。循环队列中最重要的的两个操作就是判断是否为空和是否已满。当head==tail时，表示队列为空。当(tail+1)%MAX_SIZE==head，表示队列已满。我判断队满的方法：牺牲一个单元来区分对空和队满，入队时少用一个队列单元，相当于浪费一个存储空间。“队头指针的队尾指针的下一位置作为队满的标志”。进队列

EnQueue(intvalue){//要先判断队列是否已满

if((tail+1)%QUEUE_SIZE==head){

printf("队列已满，无法从队尾插入元素\n");}else{

queue[tail]=value;tail=(tail+1)%QUEUE_SIZE;}}/出队列intDeQueue(){inttemp;if(tail==head){printf("队列为空，元素无法出队列\n");}else{temp=queue[head];

head=(head+1)%QUEUE_SIZE;

}

printf("%d\n",temp);

returntemp;

/判断队列是否为空intIsEmpty(){if(head==tail){printf("队列为空\n");return1;}

printf("队列不为空\n");return0;}判断队列是否已满/***我这里判断队满的的方法：牺牲一个单元来区分队空和队满，入队时少用一个队列单元。如果数组的大小为Size,那么实际只能存放(Size-1)个元素。（这是比较常用的判满的方式）**/

intIsFull(){

if((tail+1)%QUEUE_SIZE==head){printf("队列已满\n");return1;}

printf("队列未满\n");return0;}/打印出队列元素voidPrintQueue(){

for(inti=head;i<tail;i++){printf("%d",queue[i]);}printf("\n");}#include<stdio.h>#defineQUEUE_SIZE200intqueue[QUEUE_SIZE];inthead=0;//头指针inttail=0;//尾指针intmain（）{EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8);PrintQueue();DeQueue();DeQueue();PrintQueue();return0;1.置空队PSeqQueue

createEmptyQueue_seq(void){

PSeqQueuesq;sq=(PSeqQueue)malloc(sizeof(struct

SeqQueue));if(sq==NULL)

printf("Outofspace!!\n"); else {sq->f=0; sq->r=0; } return(sq);}

292.判队空int

isEmptyQueue_seq(PSeqQueuesq){return(sq->f==sq->r);}

303.取队头元素DataType

frontQueue_seq(PSeqQueuesq)/*对非空队列,求队列头部元素

*/{return(sq->q[sq->f]);}314.入队voidenQueue_seq(PSeqQueuesq,DataTypex)/*在队列中插入一元素x*/{if((sq->r+1)%MAXNUM==sq->f)

printf("Fullqueue.\n");else { sq->q[sq->r]=x; sq->r=(sq->r+1)%MAXNUM; }}

325.出队voiddeQueue_seq(PSeqQueuesq)/*删除队列头部元素

*/{ if(sq->f==sq->r)

printf("EmptyQueue.\n"); else sq->f=(sq->f+1)%MAXNUM;}

334.5.2链队列

队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。

显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。34

k0

k1

k2

kn-1….

图4.10队列的链接表示plqu

fr

structNode;

typedef

structNode*pNode;

structNode{DataTypeinfo;

pNode link;};

struct

LinkQueue{PNode f;

PNode r;};

typedef

struct

LinkQueue,*PLinkQueue;队列的链接表示36

^

*plqu头结点plqu->fplqu->r

头结点

队头结点plqu->fplqu->r空和非空的链队列...

^

374.5.2链队列在链队列上实现的五种基本运算如下：

1.置空队

2.判队空

3.取队头结点数据

4.入队

5.出队381.置空队（算法4.21）PLinkQueue

createEmptyQueue_link(){PLinkQueue

plqu;

plqu=(PLinkQueue)malloc(sizeof(struct

LinkQueue));if(plqu!=NULL){

plqu->f=NULL;

plqu->r=NULL;}else

printf("Outofspace!!\n"); return(plqu);}392.判队空（算法4.22）int

isEmptyQueue_link(PLinkQueue

plqu){ return(plqu->f==NULL);}

403.取队头结点数据（算法4.25）DataType

frontQueue_link(PLinkQueue

plqu)/*在非空队列中求队头元素

*/{ return(plqu->f->info);}

414.入队（算法4.23）voidenQueue_link(PLinkQueue

plqu,DataTypex){PNodep;p=(PNode)malloc(sizeof(structNode));if(p==NULL)

printf("Outofspace!");else{p->info=x; p->link=NULL;if(plqu->f==NULL) {plqu->f=p; plqu->r=p; }else {plqu->r->link=p; plqu->r=p; }}}

425.出队（算法4.24）voiddeQueue_link(PLinkQueue

plqu){PNodep; if(plqu->f==NULL)

printf("Emptyqueue.\n"); else {p=plqu->f;

plqu->f=plqu->f->link; free(p); }}43农夫过河问题

:

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。显然，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河?

4.6队列的应用—农夫过河问题*44

用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索，另一种是深度优先(depth_first)。－－实现这两种策略所依赖的数据结构正好是前面介绍的队列和栈。本节讨论队列的应用，所以下面重点介绍广度优先的策略。4.6队列的应用—农夫过河问题*45模拟农夫过河问题：用四位二进制数分别顺序表示农夫、狼、白菜和羊的位置。

0表示在南岸，1表示在北岸Path：15，6，14，2，11，1，9，0从初始状态0到最终状态15的动作序列为：

队列的应用

－－医院门诊部病人管理系统工作过程：当一病人进入门诊室时，负责挂号的义务人员就根据观察和简短询问发给他一个从0（病危）到4（一般）变化的优先数，让他到相应优先数队列中去排队等待。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人就诊。原则：优先级高的先考虑，同一优先级中，则先来先考虑。47队列的应用

－－医院门诊部病人管理系统组织数据的方式－－数据结构分析：

系统中的数据：病人的姓名，优先数，到达时间

48队列的应用

－－医院门诊部病人管理系统组织方式一：若病人以其到达门诊部的先后次序组织到一个队列，则具体到达时间可不考虑。到达次序优先数姓名12345672303021林文郑江鲁明陈真李军王红张兵这样的单队列对按就诊原则来确定下一就诊病人是很不方便的，还将破坏队列的操作原则。49队列的应用

－－医院门诊部病人管理系统组织方式二：多个队列（队列数组）：队列数组的第i个元素是优先级为i的队列。优先数隐含在队列的编号中。鲁明01234李军张兵林文王红郑江陈真^^^^^50队列的应用

－－医院门诊部病人管理系统就病人管理系统来说，功能菜单中至少有以下两个功能： （1）病人登记AddPatient()①提示并读入病人优先数i；

②提示并读入病人名

③调用链队列的入队算法EnQueue()

（2）确定下一个就诊病人GetPatient()

按就诊原则确定和显示下一个就诊病人名即：若优先数0的队列非空，则下一就诊病人为队首元素，否则，考虑优先数1的队列；依次类推。

51线性表存储结构

运算

队列链表顺序表

栈

顺序栈

链栈

顺序队列

链队列

线性表小结52顺序表typedef

int

datatype;#defineMAXNUM1024typedef

struct{datatypedata[MAXNUM];intlast;}sequenlist;53链表typedef

int

datatype;typedef

structnode{datatypedata;structnode*next;}linklist;linklist*head,*p;54

顺序栈

typedef

int

datatype;#defineMAXNUM64typedef

struct{datatypedata[MAXNUM];

inttop;}PSeqStack;PSeqStack*s;55

链栈

typedef

int

datatype;typedef

structnode{datatypedata;

structnode*next;}linkstack;linkstack*top;56

顺序队列

typedef

struct{datatypedata[MAXNUM];

intf,r;}sequeue;sequeue*sq;57

链队列

typedef

struct{linklist*f,*r;}linkqueue;linkqueue*q;582.6设计一算法，逆置带头结点的动态单链表L。voidreverse(linklist*L)/*假设链表带有头结点*/{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*/

592.10已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。linklist*ra,*rb,*rc;voidsort(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;60while(p){s=p;p=p->next;

if((s->data>=‘0’)&&(s->data<=‘9’)){s->next=ra->next;ra->next=s;

ra=s;}

/*将数字字符结点链接到A表*/

elseif((s->data>=‘a’)&&(s->data<=‘z’)||(s->data>=‘A’)&&(s->data<=‘Z’)){s->next=rb->next;rb->next=s;

rb=s;}

/*将字母字符结点链接到B表*/

else{s->next=rc->next;rc->next=s;

rc=s;}

/*将其它字符结点链接到C表*/

}/*while*/}/*sort*/613.3设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。intJudgement1(linklist*head)/*若对称返回1，否则返回0*/{PSeqStack*s;

linklist*p;

inti,n=0;/*n为计数器，记录链表的长度*/p=head;

/*先用循环求出链表的长度*/while(p){n++;p=p->next;}623.3设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。SETNULL(s);/*设置空栈s*/p=head;/*先将一半字符进栈*for(i=1;i<=n/2;i++){PUSH(s,p->data);p=p->next;}/*若字符个数为基数，则跳过中间的字符*if(n%2)p=p->next;633.3设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。/*当字符串未扫描完毕且栈非空时进行匹配*/while(p&&!EMPTY(s))if(p->data!=POP(s)break;elsep=p->next;if(!p&&EMPTY(s))return1;elsereturn0;}/*Judgement*/643.4设计算法判断一个算术表达式的圆括号是否正确配对Judgement2()

/*判断表达式是否配对，表达式以‘#’结束*/{PSeqStack

sta;charch,chpop;

intvalid;

SETNULL(&sta);

PUSH(&sta,‘#’);/*把’#’放在栈底*/

ch=getchar();valid=TRUE;

/*valid为FALSE表示括号配对失败*/65

while(ch!=‘#’){if(ch==‘(’)/*读入字符为左括号时进栈*/PUSH（&sta,ch）；

elseif(ch==‘)’)/*读入字符为右括号时出栈*/{chpop=POP(&sta);if(chpop==‘#’)/*右括号多于左括号*/{valid=FALSE;break;}}/*else*/

ch=getchar();/*读入下一字符*/}/*while*/

3.4设计算法判断一个算术表达式的圆括号是否正确配对66if(POP(&sta)!=‘#’）

valid=FALSE;/*左括号多于右括号*/if(valid)

print