C语言队列课件

1、C语言队列课件C语言队列课件队列队列只允许在表的一端进行插入，而在另一端只允许在表的一端进行插入，而在另一端进行删除。进行删除。队头队头允许删除的一端允许删除的一端队尾队尾允许插入的一端允许插入的一端队列的概念队列的概念出队出队入队入队队头队头队尾队尾a1 a2 an . 队列是先进先出表队列是先进先出表3队列的基本运算：队列的基本运算： 创建一个空队列创建一个空队列Queue createEmptyQueue ( void ) 判队列是否为空队列判队列是否为空队列int isEmptyQueue ( Queue qu ) 往队列中插入一个元素往队列中插入一个元素void enQueue (

2、Queue qu, DataType x ) 从队列中删除一个元素从队列中删除一个元素void deQueue ( Queue qu ) 求队列头部元素的值求队列头部元素的值DataType frontQueue ( Queue qu ) 队列的运算队列的运算44.5 4.5 队列的实现队列的实现4.5.1. 顺序队列顺序队列4.5.2. 链队列链队列54.5.1 4.5.1 顺序队列顺序队列 队列的顺序存储结构简称为顺序队列。顺序队队列的顺序存储结构简称为顺序队列。顺序队列实际上是运算受限的顺序表。列实际上是运算受限的顺序表。 由于队列的队头和队尾的位置均是变化的，因由于队列的队头和队尾的位

3、置均是变化的，因而要设置两个指针，分别指示当前队头元素和队尾而要设置两个指针，分别指示当前队头元素和队尾元素在向量空间中的位置。元素在向量空间中的位置。6#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;PSeqQueue sq;PSeqQueue sq;顺序

4、队列的定义顺序队列的定义4.5.1 4.5.1 顺序队列顺序队列7fr76543210k1k2k3frrfk8k7队列空队列空队列数组越界队列数组越界顺序队列顺序队列约定约定队列满队列满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 顺序队列顺序队列9元素个数（队列长度）元素个数（队列长度）: :（sq-r) - (sq-f)

5、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 顺序队列顺序队列1076543210frk1k2k3frrfk6k5队列空队列空队列数组越界队列数组越界顺序队列顺序队列4.5.1 4.5.1 顺序队列顺序队列假上溢：当前队列并不满，但不能入队。假上溢：当前队列并不满，但不能入队。每次

6、出队时向前移一位置。每次出队时向前移一位置。大量移动元素大量移动元素循环队列循环队列原因原因:被删除元素的空间没有再被使用被删除元素的空间没有再被使用解决解决:12采用循环队列克服采用循环队列克服“假上溢假上溢”。sq-rsq-fMAXNUM-101指针移动方向指针移动方向13入队：入队：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 出队：出队： sq-f=(sq-f+1)%MAXNU

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

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

9、序队列顺序队列在循环队列上实现五种基本运算：在循环队列上实现五种基本运算： 1.1.置空队置空队 2.2.判队空判队空 3.3.取队头元素取队头元素 4.4.入队入队 5.5.出队出队18循环队列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 = (rear+1) MOD MaxQSize删除元素

10、：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_SIZE; /出队列 int DeQueue三

12、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; 判断队列是否已满 /* * 我这里判断队满的的方法： 牺牲一个单元来区分队空和队满，入队时少用一个队列单元。如果数组的大小为Size,那么实际只能存放(

13、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 head=0;/头指针int tail=0;/尾指针 i

14、nt 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);else sq-f = 0; sq-r = 0;return

15、 (sq); 302. 2. 判队空判队空int isEmptyQueue_seq( PSeqQueue sq ) return (sq-f = sq-r); 313. 3. 取队头元素取队头元素DataType frontQueue_seq( PSeqQueue sq )/* 对非空队列对非空队列,求队列头部元素求队列头部元素 */ return (sq-qsq-f); 324. 4. 入队入队void enQueue_seq( PSeqQueue sq, DataType x )/* 在队列中插入一元素在队列中插入一元素x */ if( (sq-r + 1) % MAXNUM = sq-f

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

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

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

19、队（算法）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); 402. 2. 判队空判队空（算法）（算法）int isEmptyQueue_link( PLinkQueue plqu ) return (plqu-f = NULL); 413. 3. 取队头结点

20、数据取队头结点数据（算法）（算法）DataType frontQueue_link( PLinkQueue plqu )/* 在非空队列中求队头元素在非空队列中求队头元素 */ return (plqu-f-info); 424. 4. 入队入队（算法）（算法）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 = NU

21、LL; if (plqu-f = NULL) plqu-f = p; plqu-r = p; else plqu-r-link = p; plqu-r = p; 435. 5. 出出队队（算法）（算法）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);44农夫过河问题农夫过河问题 : : 一个农夫带着一只狼、一只羊和一棵白菜，身一个农夫带着一只狼、一只羊和一棵白菜，身处河

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

23、列的应用农夫过河问题农夫过河问题* *45 用计算机实现上述求解的搜索过程可以采用两种不同的用计算机实现上述求解的搜索过程可以采用两种不同的策略：策略： 一种是广度优先一种是广度优先(breadth_first)(breadth_first)搜索，搜索， 另一种是深度优先另一种是深度优先(depth_first)(depth_first)。实现这两种策略所依赖的数据结构正好是前面介绍实现这两种策略所依赖的数据结构正好是前面介绍的队列和栈。的队列和栈。本节讨论队列的应用，所以下面重点介绍广度优先的本节讨论队列的应用，所以下面重点介绍广度优先的策略。策略。 4.6 4.6 队列的应用队列的应用农夫

24、过河问题农夫过河问题* *46模拟农夫过河问题：用四位二进制数分别顺序表示农模拟农夫过河问题：用四位二进制数分别顺序表示农 夫、狼、白菜和羊的位置。夫、狼、白菜和羊的位置。 0表示在南岸，表示在南岸，1表示在北岸表示在北岸Path：15，6，14，2，11，1，9，0从初始状态从初始状态0到最终状态到最终状态15的动作序列为：的动作序列为： 队列的应用 医院门诊部病人管理系统 工作过程：当一病人进入门诊室时，负责挂号的义务人员就根据观察和简短询问发给他一个从0（病危）到4（一般）变化的优先数，让他到相应优先数队列中去排队等待 。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人就诊。 原则

25、：优先级高的先考虑，同一优先级中，则先来先考虑。48队列的应用 医院门诊部病人管理系统 组织数据的方式数据结构分析： 系统中的数据：病人的姓名，优先数，到达时间 49队列的应用 医院门诊部病人管理系统4组织方式一：若病人以其到达门诊部的先后次序组织到一个队列，则具体到达时间可不考虑。到达次序 优先数姓名 1 2 3 4 5 6 7 2 3 0 3 0 2 1林文郑江鲁明陈真李军王红张兵这样的单队列对按就诊原则来确这样的单队列对按就诊原则来确定下一就诊病人是很不方便的，定下一就诊病人是很不方便的，还将破坏队列的操作原则。还将破坏队列的操作原则。50队列的应用 医院门诊部病人管理系统4组织方式二：

26、多个队列（队列数组）：队列数组的第i个元素是优先级为i的队列。优先数隐含在队列的编号中。鲁明鲁明01234李军李军张兵张兵林文林文王红王红郑江郑江陈真陈真51队列的应用 医院门诊部病人管理系统就病人管理系统来说，功能菜单中至少有以下两个功能：就病人管理系统来说，功能菜单中至少有以下两个功能：（1）病人登记）病人登记AddPatient( ) 提示并读入病人优先数提示并读入病人优先数i； 提示并读入病人名提示并读入病人名 调用链队列的入队算法调用链队列的入队算法EnQueue三三 （2）确定下一个就诊病人）确定下一个就诊病人 GetPatient( ) 按就诊原则确定和显示下一个就诊病人名按就诊

27、原则确定和显示下一个就诊病人名 即：若优先数即：若优先数0的队列非空，则下一就诊病人为队首元素，否则，考虑优先数的队列非空，则下一就诊病人为队首元素，否则，考虑优先数1的队列；的队列；依次类推。依次类推。 52线线性性表表存储结构存储结构 运运 算算 队列队列 链链 表表顺序表顺序表 栈栈 顺序栈顺序栈 链链 栈栈 顺序队列顺序队列 链队列链队列 线性表小结线性表小结53顺序表顺序表typedef int datatype ;#define MAXNUM 1024typedef struct datatype dataMAXNUM ;int last ; sequenlist;54链链 表表t

28、ypedef int datatype;typedef struct node datatype data;struct node *next; linklist;linklist *head, *p;55 顺序栈顺序栈 typedef int datatype;typedef int datatype;#define MAXNUM 64#define MAXNUM 64typedef structtypedef struct datatype dataMAXNUM; datatype dataMAXNUM; int top; int top; PSeqStack; PSeqStack;PSe

29、qStack PSeqStack * *s;s;56 链链 栈栈 typedef int datatype;typedef int datatype;typedef struct nodetypedef struct node datatype data; datatype data; struct node struct node * *next;next; linkstack; linkstack;linkstack linkstack * *top;top;57 顺序队列顺序队列 typedef structtypedef struct datatype dataMAXNUM; data

30、type dataMAXNUM; int f,r; int f,r; sequeue; sequeue;sequeue sequeue * *sq;sq;58 链队列链队列 typedef structtypedef struct linklist linklist * *f , f , * *r;r; linkqueue; linkqueue;linkqueue linkqueue * *q;q;592.6 2.6 设计一算法，逆置带头结点的动态单链表设计一算法，逆置带头结点的动态单链表 L L。void reverse(linklist *L) /*假设链表带有头结点假设链表带有头结点*/

31、 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*/ 602.10 2.10 已知，由单链表表示的线性表中，含有三类字符的数据元素已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法构造三个以（如：字母字符、数字字符和其它字符），试

32、编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。表中的结点空间作为这三个表的结点空间，头结点可另辟空间。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=m

33、alloc(sizeof(linklist); rc-next=ra;61 while (p) s=p; p=p-next; 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; /*将其它字符

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

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

36、个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。符串是否有中心对称关系。要求用尽可能少的时间完成。 /*当字符串未扫描完毕且栈非空时进行匹配当字符串未扫描完毕且栈非空时进行匹配*/ while(p&!EMPTY(s) if (p-data!=POP(s) break; else p=p-next; if (! p&EMPTY(s) return 1; else return 0;/*Judgement*/653.4 设计算法判断一个算术表达式的圆括号是否正确配对设计算法判断一个算术表达式的圆括号是否正确配对Judgement2Judgement2三三 / /* *判断表达式是否配对，表达式以判断表达式是否配对，表达式以#结束结束* */ / PSeqStack sta; 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; / /* *validva