首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2018-08-12
90
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:linkedlist,x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s↑.data:=x;s↑.link:=p↑.link; //将s结点入队 p↑.link:=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 t.link; //找到队头元素 p↑.link↑.link:=s↑.link; //删队头元素 x:=s↑.data; //返回出队元素 if(p:=s)then p:=p↑.link; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp; 提示:上述入队算法中,因链表结构,~般不必考虑空间溢出问题,算法简单。在出队算法中,首先要判断队列是否为空,另外,对出队元素,要判断是否因出队而成为空队。否则,可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。
解析
转载请注明原文地址:https://kaotiyun.com/show/O5Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
诸侯国的国君如何用人呢?有人主张:“左右皆曰不可,勿听;诸大夫皆曰不可,勿听;国人皆曰不可,然后察之,见不可焉,然后去之。”这种主张最终可能出自下列哪位思想家之口()。
下列关于新三民主义的性质表述最准确的是()。
建国初期的土地改革与解放战争时期的土改最主要的区别是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
在下列哪个条约中,最先出现了片面最惠国待遇()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
记载了用竿标日测影以求日高的方法,并认识了勾股定理的算书是()。
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参与预政事,并受封为侯,这是宦官用权和封侯的开始。
以下是计算两个向量点积的程序段:floatdotproduct(floatxL83ffloaty[8])floatsum=0.0;inti;for(i=0;i<8;1++)sum+=x[i]*y[i);re
随机试题
舌的运动神经为
分段诊刮正确的操作是
以下药物中具有避光作用的是
采用频数分布直方图分析工程质量波动情况时,如果出现孤岛型分布,说明()。
当泵站的泵房远离水源时,应利用()将水源引至前池和进水池。
路基防排水设计中,当地下水埋深较深或为固定含水层时,可采用()。
甲公司当期将一栋出租期满的办公楼予以出售。该办公楼的账面原价为1000万元,期末按公允价值计量,其持有期间公允价值累计净增加额为300万元,出售所得价款为1400万元。在不考虑其他因素的情况下,甲公司对该项出售交易应确认的收入为()万元。
在学校事故中应负法律责任的学校,如果不具备法人资格,应由()承担赔偿责任。
()对于寺庙相当于乘警对于()
根据我国现行宪法的规定,国家主席可以行使的职权有()(2010年一法综一第28题)
最新回复
(
0
)