数据�l�构�W�三章设计题�?qi��ng)参考答案[8]_跨考网

         1. 假设以带头结点的循环链表表示队列�Q��ƈ且只设一个指针指向队������点，但不讑֤�指针�Q�如图所�C�（�~�者略�Q�，请写出相应的入队列和出队列算法。�?a target="_blank">西安�?sh��)子�U�技大学 1999计应�?/span> �?/span> �Q?/span>10分）�?/span>

　　【参考答案�?/span>

　　本题与上题本质上相同�Q�现用类C语言�~�写入队和出队算法�?/span>

　　�Q?/span>1�Q?/span>void EnQueue (LinkedList rear, ElemType x)

　　// rear是带头结点的循环��N��列的���指针，本算法将元素x插入到队����?/span>

　　{ s= (LinkedList) malloc (sizeof(LNode)); //甌����l�点�I�间

　　s->data=x; s->next=rear->next; //��?/span>s�l�点铑օ�队尾

　　rear->next=s; rear=s; //rear指向新队��?/span>

　　}

　　�Q?/span>2�Q?/span>void DeQueue (LinkedList rear)

　　// rear是带头结点的循环��N��列的���指针，本算法执行出队操作，操作成功输出队头元素�Q�否则给出出错信息�?/span>

　　{ if (rear->next==rear) { printf(“队�I?/span>\n�?/span>); exit(0);}

　　s=rear->next->next; //s指向队头元素�Q?/span>

　　rear->next->next=s->next; //队头元素出队�?/span>

　　printf (“出队元素是”，s->data);

　　if (s==rear) rear=rear->next; //�I�队�?/span>

　　free(s);

　　}

　　2. 如果允许在��@环队列的两端都可以进行插入和删除操作。要求：(x��)

　　�Q?/span>1�Q�写出��@环队列的�c�d��定义�Q?/span>

　　�Q?/span>2�Q�写出“从队尾删除”和“从队头插入”的���法。【北方交通大�?/span> 1994 �?/span> �Q?/span>12分）�?/span>

　　【参考答案�?/span>

　　[题目分析] 用一�l�数�l?/span> v[0..M-1]实现循环队列�Q�其�?/span>M是队列长度。设队头指针 front和队���指�?/span>rear�Q�约�?/span>front指向队头元素的前一位置�Q?/span>rear指向队尾元素。定�?/span>front=rear时�ؓ(f��)队空�Q?/span>(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展�?/span>

　　�Q?/span>1�Q?/span>#define M 队列可能辑ֈ�的最大长�?/span>

　　typedef struct

　　{ elemtp data[M];

　　int front,rear;

　　} cycqueue;

　　�Q?/span>2�Q?/span>elemtp delqueue ( cycqueue Q)

　　//Q是如上定义的循环队列�Q�本���法实现从队���ֈ�除，若删除成功，�q�回被删除元素，否则�l�出出错信息�?/span>

　　{ if (Q.front==Q.rear) {printf(“队列空�?/span>); exit(0);}

　　Q.rear=(Q.rear-1+M)%M; //修改队尾指针�?/span>

　　return(Q.data[(Q.rear+1+M)%M]); //�q�回出队元素�?/span>

　　}//从队���ֈ�除算法结�?/span>

　　void enqueue (cycqueue Q, elemtp x)

　　// Q是顺序存储的循环队列�Q�本���法实现“从队头插入”元�?/span>x�?/span>

　　{if (Q.rear==(Q.front-1+M)%M) {printf(“队满�?/span>; exit(0);)

　　Q.data[Q.front]=x; //x 入队�?/span>

　　Q.front=(Q.front-1+M)%M; //修改队头指针�?/span>

　　}// �l�束从队头插入算法�?/span>