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

         1. 讄���点结构�ؓ(f��)(data,link)�Q�试用一个全局指针p和某�U�链接结构实��C��个队�?/span>,��d���C�意�?/span>,�q�给出入�?/span>addq和出�?/span>deleteq�q�程,要求它们的时间复杂性都�?/span>O(l)�Q�不�?/span>new�?/span>dispose旉����Q��?a target="_blank">东南大学 1996 �?/span> �Q?/span>10分）(j��)�?/span>

　　【参考答案�?/span>

　　[题目分析]本题要求用链接结构实��C��个队列，我们可用链表�l�构来实现。一般说�Q�由于队列的先进先出性质�Q�所以队列常��N��头指针和队尾指针。但题目中仅�l�出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O�Q?/span>1�Q�，因此我们用只讑ְ�指针的��@环链表来实现队列�?/span>

　　PROC addq(VAR p:linkedlist,x:elemtp);

　　//p是数据域�?/span>data、链域�ؓ(f��)link的用循环链表表示的队列的���指针，本算法是入队操作�?/span>

　　new(s); //甌���新结炏V��假设有内存�I�间�Q�否则系�l�给出出错信息�?/span>

　　s�?/span>.data:=x; s�?/span>.link:=p�?/span>.link;//��?/span>s�l�点入队�?/span>

　　p�?/span>.link:=s; p:=s; //���指�?/span>p�U�至新的队尾�?/span>

　　ENDP;

　　PROC deleq(VAR p:linkedlist,VAR x:elemtp);

　　// p是数据域�?/span>data、链域�ؓ(f��)link的用循环链表表示的队列的���指针，本算法实现队列元素的出队�Q�若出队成功�Q�返回出队元素，否则�l�出��p�|信息�?/span>

　　IF �Q?/span>p�?/span>.link=p�Q?/span>THEN[writeln(“空队列�?/span>);return(0);]//带头�l�点的��@环队列�?/span>

　　ELSE[s:=p�?/span>.link�?/span>.link; //扑ֈ�队头元素�?/span>

　　p�?/span>.link�?/span>.link:=s�?/span>.link; //删队头元素�?/span>

　　x:=s�?/span>.data; //�q�回出队元素�?/span>

　　IF (p=s) THEN p:=p�?/span>.link; //队列中只有一个结点，出队后成为空队列�?/span>

　　dispose(s); //回收出队元素所占存储空间�?/span>

　　]

　　ENDP;

　　[���法讨论]上述入队���法中，因链表结构，一般不必考虑�I�间溢出问题�Q�算法简单。在出队���法中，首先要判断队列是否�ؓ(f��)�I�，另外�Q�对出队元素�Q�要判断是否因出队而成为空队列。否则，可能��D��因删除出队结点而将���指针删掉成为“�?zh��n)�挂变量”�?/span>