数据结构考研分类复习真题 第三章 答案[22]

[题目分析]本题要求用链接结构实现一个队列我们可用链表结构来实现一般说由于队列的先进先出性质所以队列常设队头指针和队尾指针但题目中仅给出一个全局指针p且要求入队和出队操作的时间复杂性是O（）因此我们用只设尾指针的循环链表来实现队列

PROC addq(VAR p:linkedlistx:elemtp);

//p是数据域为data链域为link的用循环链表表示的队列的尾指针本算法是入队操作

new(s); //申请新结点假设有内存空间否则系统给出出错信息

s↑data:=x; s↑link:=p↑link;//将s结点入队

p↑link:=s; p:=s; //尾指针p移至新的队尾

ENDP;

PROC deleq(VAR p:linkedlistVAR x:elemtp);

// p是数据域为data链域为link的用循环链表表示的队列的尾指针本算法实现队列元素的出队若出队成功返回出队元素否则给出失败信息

IF （p↑link=p）THEN[writeln(空队列);return();]//带头结点的循环队列

ELSE[s:=p↑link↑link; //找到队头元素

p↑link↑link:=s↑link; //删队头元素

x:=s↑data; //返回出队元素

IF (p=s) THEN p:=p↑link; //队列中只有一个结点出队后成为空队列

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

]

ENDP;

[算法讨论]上述入队算法中因链表结构一般不必考虑空间溢出问题算法简单在出队算法中首先要判断队列是否为空另外对出队元素要判断是否因出队而成为空队列否则可能导致因删除出队结点而将尾指针删掉成为悬挂变量

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []