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

第4章 队列 4.1 知识点分析 队列的基本概念 （1）队列是一种特殊的、只能在表的两端进行插入或删除操作的线性表。允许插入元素的一端称为队尾，允许删除元素的一端称为队首。 （2）队列的逻辑结构和线性表相同，其最大特点是“先进先出”。 （3）队列的存储结构有顺序队列和链队列之分，要求掌握队列的C语言描述方法。 （4）重点掌握在顺序队列和链队列上实现：进队、出队、读队头元素、显示队列元素、判队空和判队满等基本操作。 （5）熟悉队列在计算机软件设计中的典型应用，能灵活应用队列的基本原理解决一些实际应用问题。 顺序队列 （1）顺序队列用内存中一组连续的存储单元顺序存放队列中各元素，一般用一维数组作为队列的顺序存储空间。除了队列的数据以外，一般还设有队首和队尾两个指针。 typedef struct { datatype Q[MAXLEN]； int front=–1, rear=–1； // 定义队头、队尾指针，并置队列为空 }Queue； （2）顺序队列缺点是存在“假溢出”现象。 3．循环队列 （1）为了解决顺序队列中的“假溢出”现象，把数组想象成一个首尾相连的环，即队首的元素Q[0]与队尾的元素Q[MAXLEN–1]连接起来，存储在其中的队列称为循环队列。 （2）一般规定：当front= =rear，表示循环队列为空； 当front= =（rear+1）% MAXLEN，表示循环队列为满。 （3）在定义结构体时，附设一个存储循环队列中元素个数的变量n，当n= =0时表示队空；当n= = MAXLEN时为队满。 循环队列的结构体类型定义： typedef struct { datatype data[MAXLEN]； int front，rear； int n； // 用以记录循环队列中元素的个数 }csequeue； // 循环队列变量名 （4）入队操作时：p-rear= (p-rear+1) % MAXLEN； 出队操作时：p-front= (p-front+1) % MAXLEN； 链队列 （1）队列的链式存储结构称为链队列（或链队）。链首结点为队头，链尾结点为队尾。 （2）链队列的描述： typedef struct queuenode { datatype data; 　struct queuenode *next; }queuenode; 　　 // 链队结点的类型datatype typedef struct { queuenode *front,*rear; }linkqueue; // 将头指针、尾指针封装在一起的链队如下图 （3）若队头指针为Q-front，队尾指针为Q-rear，则队头元素的引用为Q-front-data，队尾元素的引用为Q-rear-data。 （4）初始时置Q-front=Q-rear=NULL。 （5）入队操作，与链表中链尾插入操作一样；出队操作，与链表中链首删除操作一样。 （6）队空标志为Q-front==NULL；对于链队列而言，一般不会出现队满。 4.2 典型习题分析 【例1】 线性表、栈、队列有什么异同？ 分析：n个（同类）数据元素的有限序列称为线性表。线性表的特点是数据元素之间存在“一对一”的关系。栈和队列都是操作受限制的线性表，它们和线性表的相同之处是数据元素之间都存在“一对一”的关系。 不同之处是：线性表允许在表中任意位置进行插入或删除操作。栈是只允许在一端（栈顶）进行插入或删除操作的线性表，其最大的特点是“后进先出”；队列是只允许在一端（队尾）进行插入，另一端（队首）进行删除操作的线性表，其最大的特点是“先进先出”。 【例2】 队列Q，经过下列运算后，x 的值是（ ）。 InitQueue(Q)； // 初始化队列 InQueue(Q,a); InQueue(Q,b); OutQueue(Q,x); InQueue(Q,c); OutQueue(Q,x); ReadFront (Q,x); A．a B．b C．c D．1 分析：经过三次入队和两次出队运算以后，队中只有一个元素，即c，最后执行读队头元素运算时，输出到x的值就是c，所以选答案C。 【例3】 设栈s和队列q初态都为空，元素a、b、c、d、e、f依次进栈，元素出栈后即进入队列，若6个元素出队的序列是b、d、c、f、e