C语言队列课件

1、4.4 4.4 队列队列队列的概念及运算队列的概念及运算( (逻辑结构逻辑结构) )1队列队列只允许在表的一端进行插入，而在另一端只允许在表的一端进行插入，而在另一端进行删除。进行删除。队头队头允许删除的一端允许删除的一端队尾队尾允许插入的一端允许插入的一端队列的概念队列的概念出队出队入队入队队头队头队尾队尾a1 a2 an . 队列是先进先出表队列是先进先出表2队列的基本运算：队列的基本运算： 创建一个空队列创建一个空队列Queue createEmptyQueue ( void ) 判队列是否为空队列判队列是否为空队列int isEmptyQueue ( Queue qu ) 往队列中插入

2、一个元素往队列中插入一个元素void enQueue ( Queue qu, DataType x ) 从队列中删除一个元素从队列中删除一个元素void deQueue ( Queue qu ) 求队列头部元素的值求队列头部元素的值DataType frontQueue ( Queue qu ) 队列的运算队列的运算34.5 4.5 队列的实现队列的实现4.5.1. 顺序队列顺序队列4.5.2. 链队列链队列44.5.1 4.5.1 顺序队列顺序队列 队列的顺序存储结构简称为顺序队列。顺序队队列的顺序存储结构简称为顺序队列。顺序队列实际上是运算受限的顺序表。列实际上是运算受限的顺序表。 由于队

3、列的队头和队尾的位置均是变化的，因由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当前队头元素和队尾而要设置两个指针，分别指示当前队头元素和队尾元素在向量空间中的位置。元素在向量空间中的位置。5#define MAXNUM 100#define MAXNUM 100struct SeqQueuestruct SeqQueue datatype qMAXNUM; datatype qMAXNUM; int f,r; int f,r; ; ;typedef struct SeqQueue typedef struct SeqQueue * *PSeqQueue;PSeqQueue

4、;PSeqQueue sq;PSeqQueue sq;顺序队列的定义顺序队列的定义4.5.1 4.5.1 顺序队列顺序队列6fr76543210k1k2k3frrfk8k7队列空队列空队列数组越界队列数组越界顺序队列顺序队列约定约定队列满队列满k1k2k3fk8rk4k5k6k7开始：开始： sq-f=0;sq-f=0; sq-r=0; sq-r=0; 入队：入队： sq-datasq-r=x; sq-datasq-r=x; sq-r+; sq-r+; 出队：出队： sq-f+; sq-f+; 顺序队列的入队和出队顺序队列的入队和出队4.5.1 4.5.1 顺序队列顺序队列8元素个数（队列长度

5、）元素个数（队列长度）: :（sq-r) - (sq-f)sq-r) - (sq-f) 若（若（sq-r) - (sq-f)=0 sq-r) - (sq-f)=0 ，则队列长度，则队列长度为为0 0，即空队列。再出队会，即空队列。再出队会“下溢下溢” 若若 (sq-r)-(sq-f)=MAXNUM(sq-r)-(sq-f)=MAXNUM，则队满。，则队满。队满时再入队会队满时再入队会“上溢上溢”4.5.1 4.5.1 顺序队列顺序队列976543210frk1k2k3frrfk6k5队列空队列空队列数组越界队列数组越界顺序队列顺序队列4.5.1 4.5.1 顺序队列顺序队列假上溢假上溢：当前队

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

7、 出队出队： sq-f=(sq-f+1)%MAXNUMsq-f=(sq-f+1)%MAXNUM采用循环队列克服采用循环队列克服“假上溢假上溢”4.5.1 4.5.1 顺序队列顺序队列13 某一元素出队后，若头指针已从后面追上尾指针，某一元素出队后，若头指针已从后面追上尾指针，则当前队列为空：则当前队列为空： sq-f=sq-rsq-f=sq-r 某一元素入队后，若尾指针已从后面追上头指针，某一元素入队后，若尾指针已从后面追上头指针，则当前队列为满：则当前队列为满： sq-f=sq-rsq-f=sq-r 因此，仅凭因此，仅凭 sq-f=sq-rsq-f=sq-r 是无法区别是无法区别队列空还是队

8、列满。队列空还是队列满。 判断队空和队满判断队空和队满4.5.1 4.5.1 顺序队列顺序队列14解决办法解决办法标志变量标志变量测试尾指针在循环意义测试尾指针在循环意义下是否等于头指针下是否等于头指针 判别判别队列满队列满的条件：的条件： (sq-r+1)%MAXNUM=sq-f(sq-r+1)%MAXNUM=sq-f使使 sq-f=sq-rsq-f=sq-r 成为判断成为判断队列空队列空的条件的条件4.5.1 4.5.1 顺序队列顺序队列元素个数是元素个数是MAXNUM-115sq.rearsq.frontk1k2k7k6k5k4k3sq.frontsq.rear图(a)空队列图(b)队列

9、满 图4.9 循环队列4.5.1 4.5.1 顺序队列顺序队列在循环队列上实现五种基本运算：在循环队列上实现五种基本运算： 1.1.置空队置空队 2.2.判队空判队空 3.3.取队头元素取队头元素 4.4.入队入队 5.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=0 xn-3an-3rear=0an-20.1n-1.front=n-3n-2xrear = (

10、rear+1) MOD MaxQSize删除元素：front顺时针移动一位front = (front+1) MOD MaxQSize;rear0front=9.1.CD删除删除Crearfront=00.1.D循环队列 front指定队首位置，删除一个元素就将front顺 时针移动一位； rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位； count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。 队空：count=0 队满：count= MaxQSize数组队列实现在队列的头部取出元素。普通的队列由于空间利用率不高，所以我们一般都用循环

11、队列。循环队列中最重要的的两个操作就是判断是否为空和是否已满。当head=tail时，表示队列为空。当(tail+1)%MAX_SIZE = head，表示队列已满。我判断队满的方法：牺牲一个单元来区分对空和队满，入队时少用一个队列单元，相当于浪费一个存储空间。“队头指针的队尾指针的下一位置作为队满的标志”。进队列 EnQueue(int value) /要先判断队列是否已满 if (tail + 1) % QUEUE_SIZE = head) printf(队列已满，无法从队尾插入元素n); else queuetail = value; tail = (tail + 1) % QUEUE_

12、SIZE; /出队列 int DeQueue() int temp; if (tail = head) printf(队列为空，元素无法出队列n); else temp = queuehead;head = (head + 1) % QUEUE_SIZE;printf(%dn,temp);return temp; /判断队列是否为空 int IsEmpty() if (head = tail) printf(队列为空n); return 1; printf(队列不为空n); return 0; 判断队列是否已满 /* * 我这里判断队满的的方法： 牺牲一个单元来区分队空和队满，入队时少用一个队

13、列单元。如果数组的大小为Size,那么实际只能存放(Size-1)个元素。（这是比较常用的判满的方式） * */ int IsFull() if (tail + 1) % QUEUE_SIZE = head) printf(队列已满n); return 1; printf(队列未满n); return 0; /打印出队列元素 void PrintQueue() for (int i = head; i tail; i+) printf(%d ,queuei); printf(n); #include #define QUEUE_SIZE 200 int queueQUEUE_SIZE;int

14、head=0;/头指针int tail=0;/尾指针 int main（） EnQueue(4);EnQueue(1);EnQueue(2);EnQueue(9);EnQueue(8); PrintQueue(); DeQueue();DeQueue(); PrintQueue(); return 0; 1. 1. 置空队置空队PSeqQueue createEmptyQueue_seq( void ) PSeqQueue sq; sq = (PSeqQueue)malloc(sizeof(struct SeqQueue); if (sq=NULL)printf(Out of space! n

15、);else sq-f = 0; sq-r = 0;return (sq); 292. 2. 判队空判队空int isEmptyQueue_seq( PSeqQueue sq ) return (sq-f = sq-r); 303. 3. 取队头元素取队头元素DataType frontQueue_seq( PSeqQueue sq )/* 对非空队列对非空队列,求队列头部元素求队列头部元素 */ return (sq-qsq-f); 314. 4. 入队入队void enQueue_seq( PSeqQueue sq, DataType x )/* 在队列中插入一元素在队列中插入一元素x *

16、/ if( (sq-r + 1) % MAXNUM = sq-f ) printf( Full queue.n ); else sq-qsq-r = x; sq-r = (sq-r + 1) % MAXNUM; 325. 5. 出出队队void deQueue_seq( PSeqQueue sq )/* 删除队列头部元素删除队列头部元素 */ if( sq-f = sq-r )printf( Empty Queue.n ); elsesq-f = (sq-f + 1) % MAXNUM; 334.5.2 4.5.2 链队列链队列 队列的链式存储结构简称为链队列，它是限制仅在队列的链式存储结构简

17、称为链队列，它是限制仅在表头删除和表尾插入的单链表。表头删除和表尾插入的单链表。 显然仅有单链表的头指针不便于在表尾做插入操作，显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确于是，一个链队列由一个头指针和一个尾指针唯一地确定。定。34 k0 k1 k2 kn-1. 图图4.10 队列的链接表示队列的链接表示plqu fr struct Node; typedef struct Node *pNode; struct Node DataType info

18、; pNodelink; ; struct LinkQueue PNodef; PNoder; ; typedef struct LinkQueue, *PLinkQueue;队列的链接表示队列的链接表示36 * *plquplqu头结点头结点plqu-fplqu-r 头结点头结点 队头结点队头结点plqu-fplqu-fplqu-rplqu-r空和非空的链队列空和非空的链队列. 374.5.2 4.5.2 链队列链队列在链队列上实现的五种基本运算如下：在链队列上实现的五种基本运算如下： 1. 1. 置空队置空队 2. 2. 判队空判队空 3. 3. 取队头结点数据取队头结点数据 4. 4.

19、入队入队 5. 5. 出队出队381. 1. 置空队（算法置空队（算法4.214.21）PLinkQueue createEmptyQueue_link( ) PLinkQueue plqu; plqu = (PLinkQueue )malloc(sizeof(struct LinkQueue); if (plqu!=NULL) plqu-f = NULL; plqu-r = NULL; elseprintf(Out of space! n);return (plqu); 392. 2. 判队空判队空（算法（算法4.224.22）int isEmptyQueue_link( PLinkQueu

20、e plqu ) return (plqu-f = NULL); 403. 3. 取队头结点数据取队头结点数据（算法（算法4.254.25）DataType frontQueue_link( PLinkQueue plqu )/* 在非空队列中求队头元素在非空队列中求队头元素 */ return (plqu-f-info); 414. 4. 入队入队（算法（算法4.234.23）void enQueue_link( PLinkQueue plqu, DataType x ) PNode p; p = (PNode )malloc( sizeof( struct Node ) ); if ( p

21、 = 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-link = p; plqu-r = p; 425. 5. 出出队队（算法（算法4.244.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; fr

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

23、不吃白菜。请问农夫该采取什么方案才能将所有的东西运请问农夫该采取什么方案才能将所有的东西运过河过河? ? 4.6 4.6 队列的应用队列的应用农夫过河问题农夫过河问题* *44 用计算机实现上述求解的搜索过程可以采用两用计算机实现上述求解的搜索过程可以采用两种不同的策略：种不同的策略： 一种是一种是广度优先广度优先(breadth_first)(breadth_first)搜索，搜索， 另一种是另一种是深度优先深度优先(depth_first)(depth_first)。实现这两种策略所依赖的数据结构正好是前面实现这两种策略所依赖的数据结构正好是前面介绍的介绍的队列队列和和栈栈。本节讨论队列的

24、应用，所以下面重点介绍本节讨论队列的应用，所以下面重点介绍广度优先广度优先的策略。的策略。 4.6 4.6 队列的应用队列的应用农夫过河问题农夫过河问题* *45模拟农夫过河问题：用四位二进制数分别顺序表示农模拟农夫过河问题：用四位二进制数分别顺序表示农 夫、狼、白菜和羊的位置。夫、狼、白菜和羊的位置。 0表示在南岸，表示在南岸，1表示在北岸表示在北岸Path：15，6，14，2，11，1，9，0从初始状态从初始状态0到最终状态到最终状态15的动作序列为：的动作序列为： 农夫把羊带到北岸; 1 0000 农夫独自回到南岸; 2 1001 农夫把白菜带到北岸; 3 0001 农夫带着羊返回南岸;

25、 5 1101 4 1011 农夫把狼带到北岸; 7 0100 6 0010 农夫独自返回南岸; 8 1110 农夫把羊带到北岸。 9 0110 10 1111 图4.11 广度优先搜索的结果和顺序 队列的应用 医院门诊部病人管理系统 工作过程：当一病人进入门诊室时，负责挂号的义务人员就根据观察和简短询问发给他一个从0（病危）到4（一般）变化的优先数，让他到相应优先数队列中去排队等待 。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人就诊。 原则：优先级高的先考虑，同一优先级中，则先来先考虑。47队列的应用 医院门诊部病人管理系统 组织数据的方式数据结构分析： 系统中的数据：病人的姓名，

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

27、江陈真陈真50队列的应用 医院门诊部病人管理系统就病人管理系统来说，功能菜单中至少有以下两个功能：就病人管理系统来说，功能菜单中至少有以下两个功能：（1）病人登）病人登记记AddPatient( ) 提示并读入病人优先数提示并读入病人优先数i i； 提示并读入病人名提示并读入病人名 调用链队列的入队算法调用链队列的入队算法EnQueue()EnQueue() （2）确定下一个就诊病人）确定下一个就诊病人 GetPatient( ) 按就诊原则确定和显示下一个就诊病人名按就诊原则确定和显示下一个就诊病人名 即：若优先数即：若优先数0的队列非空，则下一就诊病人为队首元素，否则，考虑的队列非空，则下

28、一就诊病人为队首元素，否则，考虑优先数优先数1的队列；依次类推。的队列；依次类推。 51线线性性表表存储结构存储结构 运运 算算 队列队列 链链 表表顺序表顺序表 栈栈 顺序栈顺序栈 链链 栈栈 顺序队列顺序队列 链队列链队列 线性表小结线性表小结52顺序表顺序表typedef int datatype ;#define MAXNUM 1024typedef struct datatype dataMAXNUM ;int last ; sequenlist;53链链 表表typedef int datatype;typedef struct node datatype data;struct

29、node *next; linklist;linklist *head, *p;54 顺序栈顺序栈 typedef int datatype;typedef int datatype;#define MAXNUM 64#define MAXNUM 64typedef structtypedef struct datatype dataMAXNUM; datatype dataMAXNUM; int top; int top; PSeqStack; PSeqStack;PSeqStack PSeqStack * *s;s;55 链链 栈栈 typedef int datatype;typedef

30、 int datatype;typedef struct nodetypedef struct node datatype data; datatype data; struct node struct node * *next;next; linkstack; linkstack;linkstack linkstack * *top;top;56 顺序队列顺序队列 typedef structtypedef struct datatype dataMAXNUM; datatype dataMAXNUM; int f,r; int f,r; sequeue; sequeue;sequeue s

31、equeue * *sq;sq;57 链队列链队列 typedef structtypedef struct linklist linklist * *f , f , * *r;r; linkqueue; linkqueue;linkqueue linkqueue * *q;q;582.6 2.6 设计一算法，逆置带头结点的动态单链表设计一算法，逆置带头结点的动态单链表 L L。void reverse(linklist *L) /*假设链表带有头结点假设链表带有头结点*/ linklist *p,*s; p=L-next; /*用用p指向当前结点指向当前结点*/ L-next=NULL; w

32、hile (p) s=p; /*用用s保存当前结点地址保存当前结点地址*/ p=p-next; /*链表指针链表指针p后移后移*/ /*将当前结点链到表头将当前结点链到表头*/ s-next=L-next; L-next=s; /*reverse*/ 592.10 2.10 已知，由单链表表示的线性表中，含有三类字符的数据元素已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法构造三个以（如：字母字符、数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原循环链表表示的线性表，使每个表中只含同一类的字

33、符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。表中的结点空间作为这三个表的结点空间，头结点可另辟空间。linklist *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 while (p) s=p; p=p-next

34、; if (s-data=0)&(s-datanext=ra-next; ra-next=s; ra=s; /*将数字字符结点链接到将数字字符结点链接到A表表*/ 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*/613.3 设单链表中存放着设单链表中存放着

35、n个字符，试编写算法，判断该字个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。符串是否有中心对称关系。要求用尽可能少的时间完成。int Judgement1(linklist *head)/*若对称返回若对称返回 1，否则返回，否则返回 0*/ PSeqStack *s; linklist *p; int i, n=0; /*n为计数器，记录链表的长度为计数器，记录链表的长度*/ p=head; /*先用循环求出链表的长度先用循环求出链表的长度*/ while(p) n+ ; p=p-next ; 623.3 设单链表中存放着设单链表中存放着n个字符，试编写算法，

36、判断该字个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。符串是否有中心对称关系。要求用尽可能少的时间完成。SETNULL(s); /*设置空栈设置空栈 s*/p=head;/*先将一半字符进栈先将一半字符进栈*for (i=1;idata); p=p-next; /*若字符个数为基数，则跳过中间的字符若字符个数为基数，则跳过中间的字符*if (n%2) p=p-next;633.3 设单链表中存放着设单链表中存放着n个字符，试编写算法，判断该字个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。符串是否有中心对称关系。要求用尽可能少的时间

37、完成。 /*当字符串未扫描完毕且栈非空时进行匹配当字符串未扫描完毕且栈非空时进行匹配*/ while(p&!EMPTY(s) if (p-data!=POP(s) break; else p=p-next; if (! p&EMPTY(s) return 1; else return 0;/*Judgement*/643.4 设计算法判断一个算术表达式的圆括号是否正确配对设计算法判断一个算术表达式的圆括号是否正确配对Judgement2()Judgement2() / /* *判断表达式是否配对，表达式以判断表达式是否配对，表达式以#结束结束* */ / PSeqStack s

38、ta; PSeqStack sta; char ch,chpop; char ch,chpop; int valid; int valid; SETNULL(&sta); SETNULL(&sta); PUSH(&sta,#); PUSH(&sta,#); / /* *把把#放在栈底放在栈底* */ / ch=getchar();ch=getchar(); valid=TRUE; valid=TRUE; / /* *validvalid为为FALSEFALSE表示括号配对失败表示括号配对失败* */ /65 while(ch!=#) while(ch!=#) i

39、f if (ch=() (ch=() / /* *读入字符为左括号时进栈读入字符为左括号时进栈* */ / PUSH PUSH（&sta,ch&sta,ch）；）； else if else if (ch=)(ch=)/ /* *读入字符为右括号时出栈读入字符为右括号时出栈* */ / chpop=POP(&sta); chpop=POP(&sta); if (chpop=#) if (chpop=#) / /* *右括号多于左括号右括号多于左括号* */ / valid=FALSE; break; valid=FALSE; break; / /* *elsee

40、lse* */ / ch=getchar(); ch=getchar();/ /* *读入下一字符读入下一字符* */ / / /* *whilewhile* */ / 3.4 设计算法判断一个算术表达式的圆括号是否正确配对设计算法判断一个算术表达式的圆括号是否正确配对66if (POP(&sta)!=# if (POP(&sta)!=# ） valid=FALSE;valid=FALSE; / /* *左括号多于右括号左括号多于右括号* */ /if (valid) if (valid) printf printf(“(“括号配对成功括号配对成功“）；）；else else printf(“ printf(“括号括号配对不成功配