中国铁道出版社数据结构（第二版）单元4练习参考答案

while (!QEmpty(Q))

{

OutQueue (Q,y); printf(y); }; printf(x); }

答：输出为“CHAR”。

五．程序填空

1．假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。

typedef struct queuenode // 定义队列的存储结构 { int data;

struct queuenode *next; }qu;

InQueue(rear,x) // 向队列插入元素为x的函数 { qu *rear； int x；

{ qu *head,*s; s= new qu ; s->data= x ;

if (rear==NULL) // 循环队列为空，则建立一个结点的循环队列 { rear=s; rear->next;} else

{ head= rear->next ; // 循环队列非空，则将s插到后面 rear->next= s ; rear=s;

rear->next =head;}

}

六. 算法设计题

1．设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。

2．用一个循环数组Q[0..MAXLEN-1]表示队列时，该队列只有一个头指针front，不设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。

83

3．一个用单链表组成的循环队列，只设一个尾指针rear，不设头指针，请编写他如下算法： （1） 向循环队列中插入一个元素为x的结点； （2） 从循环队列中删除一个结点。 1． 解：用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器

count用来记录队列中结点的个数。 （1）入队算法：

void inqueqe(int x) { int temp;

if (count==n)

printf(\队列上溢出\\n\else

{ count++

temp=(front+count)%n; Queue[temp]=x }

}

（2）出队算法：

int outqueue() { int temp;

if (count==0)

printf(\队列下溢出\\n\else

{ temp=Queue[front]; front=(front+1)%n; count--;

return temp; } }

2．解：队列为空：count==0

队列为满：count=MAXLEN

队尾第一个元素位置==(front+count)%MAXLEN 队首第一个元素位置==(front+1)%MAXLEN const MAXLEN=100; int queue[MAXLEN];

int front,count; // 定义队头和计数器count

（1）初始化队列

void init() {

front=1; count=0; }

84

（2）判定队空

int QEmpty() {

if (count==0)

return(1);

else

return(0);}

（3）读队头元素

void ReadFront(int queue[],x)

{

if (count==0)

printf(\下溢出\\n\

else {

front=(front+1)%MAXLEN; x=queue[front];

} } （4）入队操作

void InQueue(int queue[],int x) {

int place;

if (count==MAXLEN)

printf(\上溢出\\n\

else {

count++;

place=(front+count)%MAXLEN; queue[MAXLEN]=x;

} } （5）出队操作

void OutQueue(int queue[]) // 删除队列头元素 {

if (count==0)

printf(\队列下溢出\\n\

else {

front=(front+1)%MAXLEN; count--;

} } 3．

85

（1）解：定义本题队列的结点类型如下：

typedef struct linknode {

int data;

struct linknode *next;

}qu;

qu *rear;

inqueue(int x) // 向队列插入结点x {

qu *head, *s;

s=(qu *) new qu; // 创建一个新结点 s->data=x;

if (rear==NUlL) // 若队空,则建立一个循环队列 {

rear＝s;

rear->next＝s; }

else // 若不为空，则将s插到后面 {

head=rear->next； rear->next＝s;

rear=s; // rear始终指向最后一个结点 rear->next＝head; } }

(2)解：

void delqueue(rear) {

if (rear==NULL)

printf(\下溢出!\\n\ else {

head=rear->next; // head指向队首结点 if (head==rear)

rear=NULL // 只有—个结点则直接删除该结点

else

rear->next=head->next // 否则删除第一个结点

delete head； // 释放队首结点 } }

86