首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-11-14
47
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:l。inkedlist,x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.data:=x;s ↑.1ink:=p ↑.link; //将s结点入队 p ↑.1ink:=s;p:=s; //尾指针p移至新的队尾 endp; (2)proc deleq(Var p:linkedlist,Var x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针,本算法实 //现队列元素的出队,若出队成功,返回出队元素,否则给出失败信息 if(p ↑.link==p)then{writeln(”空队列”):return(0);} //带头结点的循环队列 、 else{s:=p ↑.link ↑.link; //找到队头元素 p ↑.link ↑.link:=s ↑.link; //删队头元素 x:=s ↑.data; //返回出队元素 if(p==s)then p:=p ↑.link; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp; 提示:上述入队算法中,因链表结构,一般不必考虑空间溢出问题,算法简单。在出队算法中,首先要判断队列是否为空,另外,对出队元素,要判断是否因出队而成为空队。否则,可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。
解析
转载请注明原文地址:https://kaotiyun.com/show/YxRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
尼克松主义的内容及其意义。
【开明专制】南京大学2004年世界近现代史真题
以下内容不属于中国共产党为解决中西部落后问题,巩固发展国防事业而采取的三线建设的是()。
斯大林模式的突出特点是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
下列有关《布列斯特和约》的说法中,错误的一项是()。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
明清时期继续采取“重农抑商”的政策,结果导致了()。
为了限制三帅的权力过大,宋代在中央设立()机构,主管全国的军队调动、训练、供给等事宜。
周王室的两大官僚系统是()。
随机试题
照海通于
药品不良反应的监测方法包括
【2012专业案例真题下午卷】某企业供电系统计算电路如下图所示:图中35kV电缆线路采用交联聚乙烯铜芯电缆,长度为3.5km,电缆截面为150mm2,35kV电缆有关参数见下表:假定车间变压器额定容量为SN=2000kV.A,空载损耗为P
我国自改革开放以来,()的概念逐渐被广泛接受与应用,并已在我国投资项目分析和评价中发挥积极作用。
循环经济评价指标体系(宏观)的指标中,单位国内生产总值能耗的计算公式为()。
硫酸二甲酯泄漏后,先将()洒在污染处进行中和,也可用漂白粉或5倍水浸湿污染处,再用()浸湿,最后用热水和冷水各冲洗一次。
以下关于宽限期的说法,正确的是()。
《中华人民共和国教师法》的正式施行是从()开始的。
恰好有两位数字相同的三位数共有多少个?
因果性联系所揭示的是先后相继、彼此制约的事物或现象之间的________关系,结果对于原因来说,具有合理性和必然性。因果联系的两个条件:一是必须是先行后续的关系,二是必须是引起与被引起的关系,这两个条件________。填入画横线部分最恰当的一项是:
最新回复
(
0
)