2019考研数据结构C语言版详解答案：栈和队列(13)
《数据结构(C语言版)》考试内容两大类：概念，算法。自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。要想把数据结构这门专业课复习好，除了做练习题，还要掌握2019考研计算机数据结构(C语言版)基础知识，只有基础知识掌握牢固，才能在做数据结构算法题目时得心应手。本次新东方在线整理了数据结构C语言版答案详解，各位考生可以对照着题目与答案详解，把计算机专业课的数据结构复习一遍。3.29
如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围(如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好)。
解：
#define MaxQSize 4
typedef int ElemType;
typedef struct{
ElemType *base;
int front;
int rear;
Status tag;
}Queue;
Status InitQueue(Queue& q)
{
q.base=new ElemType;
if(!q.base) return FALSE;
q.front=0;
q.rear=0;
q.tag=0;
return OK;
}
Status EnQueue(Queue& q,ElemType e)
{
if(q.front==q.rear&&q.tag) return FALSE;
else{
q.base=e;
q.rear=(q.rear+1)%MaxQSize;
if(q.rear==q.front)q.tag=1;
}
return OK;
}
Status DeQueue(Queue& q,ElemType& e)
{
if(q.front==q.rear&&!q.tag)return FALSE;
else{
e=q.base;
q.front=(q.front+1)%MaxQSize;
q.tag=0;
}
return OK;
}
设标志节省存储空间，但运行时间较长。不设标志则正好相反。
页:
[1]