首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2018-08-12
32
问题
设结点结构为(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
学硕统考专业
相关试题推荐
中国共产党在过渡时期总路线的主要内容是“一化三改造”,其中“一化”是指()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发展
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
1628年出版了《心血运动论》一书,论证了血液在全身的循环运动,使生理学发展为科学的是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
元朔二年(前127),汉武帝采纳()的建议,允许诸侯王推“私恩”,把王国土地的一部分分给子弟为列候,由皇帝制定这些侯国的名号,隶属于汉郡,地位与县相当。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
某工厂有一个仓库可以存放甲、乙两种零部件,甲零件可以存放m件,乙零件可以存放n件,车间A专门生产甲零件,每次1件,每生产1件存放进仓库1件;车间B专门生产零件乙,每次1件,每生产1件存放进仓库1件。总装车间每次从仓库取出2件甲零件、1件乙零件组装成成品,车
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
随机试题
对于二次补充侦查的案件,人民检察院仍然认为证据不足,不符合起诉条件的,如何处理?()
急性血源性骨髓炎的护理措施。
预真空压力蒸汽灭菌的监测有哪些基本要求?
女性患者最常见的霍奇金淋巴瘤组织学类型是
患者,女,45岁。反复对称性双手、双足关节肿痛10年,晨僵2~3小时,近1个月出现咳嗽、咳痰、有时喘憋、不发热。查体:双手轻度关节变形,双肺底可闻少许的细小湿性啰音。最可能的诊断是
男性,42岁,胃大部切除术(毕Ⅱ式):术后一年出现上腹部烧灼痛,进食后加重,抑酸剂治疗无效。治疗措施最合理的是
梅,高洁傲岸;兰,优雅空灵;竹,虚心有节;菊,冷艳清贞。千百年来,梅兰竹菊“四君子”以其清雅淡泊的品质,一直为古今文人墨客所钟爱。这表明()。①整体和部分是辩证统一的②共性寓于个性之中③对立和差别以同一为前提④不同事物有不同的矛盾
阅读下列材料,完成下列小题。大班科学活动:改装工具。准备:几大盆水;每个幼儿一箩筐材料:完好和有洞的桶、瓶、塑料袋;小箩筐、漏斗、漏网等:一组辅助材料:皮筋、橡皮泥、透明胶、塑料纸、剪刀、线等。活动开始,教师提出活动要求和注意
我国公务员的处分分为:警告、记过、记大过、降级、撤职五级。()
我国宪法规定的庇护权的含义是
最新回复
(
0
)