设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O1)(不计new和dispose时间)。

admin2016-03-29  53

问题 设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O1)(不计new和dispose时间)。

选项

答案本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:linkedlistl x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.data:=x;s ↑.1ink:=p ↑.link; //将s结点入队 p ↑.link:=s;p:=s; //尾指针p移至新的队尾 endp; (2)proc deleq(val p:linkedlist,var x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针,本算法实 //现队列元素的出队,若出队成功,返回出队元素,否则给出失败信息 if(p ↑.1ink==p)then{writeln(”空队列”);return(0);} //带头结点的循环队列 else{s:=p ↑.link t.link; //找到队头元素 p ↑.link ↑.1ink:=s ↑.link; //删队头元素 x:=s ↑.data,; //返回出队元素 if(p:=s)then p:=p ↑.1ink; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp;

解析
转载请注明原文地址:https://kaotiyun.com/show/VnRi777K
0

最新回复(0)