数据结构答案 第4章 队列学习指导

《数据结构答案 第4章 队列学习指导》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章队列4.1知识点分析1．队列的基本概念（1）队列是一种特殊的、只能在表的两端进行插入或删除操作的线性表。允许插入元素的一端称为队尾，允许删除元素的一端称为队首。（2）队列的逻辑结构和线性表相同，其最大特点是“先进先出”。（3）队列的存储结构有顺序队列和链队列之分，要求掌握队列的C语言描述方法。（4）重点掌握在顺序队列和链队列上实现：进队、出队、读队头元素、显示队列元素、判队空和判队满等基本操作。（5）熟悉队列在计算机软件设计中的典型应用，能灵活应用队列的基本原理解决一些实际应用问题。2．顺序队列（1）顺序队列用内存中一组连续的存储单元顺序存放队列中各元素，一般用一维数组作为队

2、列的顺序存储空间。除了队列的数据以外，一般还设有队首和队尾两个指针。typedefstruct{datatypeQ[MAXLEN]；intfront=–1,rear=–1；//定义队头、队尾指针，并置队列为空}Queue；（2）顺序队列缺点是存在“假溢出”现象。3．循环队列（1）为了解决顺序队列中的“假溢出”现象，把数组想象成一个首尾相连的环，即队首的元素Q[0]与队尾的元素Q[MAXLEN–1]连接起来，存储在其中的队列称为循环队列。（2）一般规定：当front==rear，表示循环队列为空；当front==（rear+1）%MAXLEN，表示循环队列为满。（3）在定义结构体时，

3、附设一个存储循环队列中元素个数的变量n，当n==0时表示队空；当n==MAXLEN时为队满。循环队列的结构体类型定义：typedefstruct{datatypedata[MAXLEN]；intfront，rear；intn；//用以记录循环队列中元素的个数}csequeue；//循环队列变量名（4）入队操作时：p->rear=(p->rear+1)%MAXLEN；出队操作时：p->front=(p->front+1)%MAXLEN；4．链队列（1）队列的链式存储结构称为链队列（或链队）。链首结点为队头，链尾结点为队尾。（2）链队列的描述：typedefstructqueuenod

4、e{datatypedata;　structqueuenode*next;}queuenode;　　//链队结点的类型datatypetypedefstruct{queuenode*front,*rear;}linkqueue;//将头指针、尾指针封装在一起的链队如下图31（3）若队头指针为Q->front，队尾指针为Q->rear，则队头元素的引用为Q->front->data，队尾元素的引用为Q->rear->data。（4）初始时置Q->front=Q->rear=NULL。（5）入队操作，与链表中链尾插入操作一样；出队操作，与链表中链首删除操作一样。（6）队空标志为Q->f

5、ront==NULL；对于链队列而言，一般不会出现队满。4.2典型习题分析【例1】线性表、栈、队列有什么异同？分析：n个（同类）数据元素的有限序列称为线性表。线性表的特点是数据元素之间存在“一对一”的关系。栈和队列都是操作受限制的线性表，它们和线性表的相同之处是数据元素之间都存在“一对一”的关系。不同之处是：线性表允许在表中任意位置进行插入或删除操作。栈是只允许在一端（栈顶）进行插入或删除操作的线性表，其最大的特点是“后进先出”；队列是只允许在一端（队尾）进行插入，另一端（队首）进行删除操作的线性表，其最大的特点是“先进先出”。【例2】队列Q，经过下列运算后，x的值是（）。Init

6、Queue(Q)；//初始化队列InQueue(Q,a);InQueue(Q,b);OutQueue(Q,x);InQueue(Q,c);OutQueue(Q,x);ReadFront(Q,x);A．aB．bC．cD．1分析：经过三次入队和两次出队运算以后，队中只有一个元素，即c，最后执行读队头元素运算时，输出到x的值就是c，所以选答案C。【例3】设栈s和队列q初态都为空，元素a、b、c、d、e、f依次进栈，元素出栈后即进入队列，若6个元素出队的序列是b、d、c、f、e、a，则要求栈S的容量至少能存多少个元素？分析：队列操作的原则是“先进先出”，按照题意出队的顺序应该是b、d、c、

7、f、e、a，所以入队的顺序也是b、d、c、f、e、a。栈的操作原则是“后进先出”，要得到b、d、c、f、e、a的出栈次序，必须进行如图4-1所示的操作过程。由此可见栈的空间至少为3。a、b进栈b出栈c、d进栈d、c出栈e、f进栈f、e、a出栈dfbceaaa图4-1进栈出栈过程【例4】循环队列存储在数组A[0..MAXLEN-1]中，设front指向队头，rear指向实际队尾的下一个元素的位置，写出通过队头、队尾指针表示的队列长度Qlen的公式。分析：当rear>=f