首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-11-14
32
问题
设结点结构为(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
学硕统考专业
相关试题推荐
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
世界天文史上最早实地测量子午线的记录是由谁进行的?()
第二次世界大战期间,苏、美、英三国首脑达成的协议中未能实现的是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
阅读以下史料,并回答问题:心即理也,此心无私欲之蔽,即是天理,不须外面添一分。——《传习录》上朱子所谓格物云者,在即物而穷其理也。即物穷理,是就事事物物上求其所谓定理也。是以吾心而求理于事
1852年,英国驻广州代办密切尔说:“经过和这么一个大国开放贸易十年之久,并且双方都已废除了一切独占制度,而拥有如此庞大人口的中国,其消费我们的制品竟不及荷兰的一半……这好像是一个奇怪的结局。”这是因为()。
到1869年为止,人类已发现了多少种化学元素()。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
一次分配所有资源的方法可以预防死锁的发生,它破坏的死锁四个必要条件中的()。
下列属于实时控制系统的是()。
随机试题
联系实际说明日本商人的谈判风格。
成人24小时尿量少于多少称无尿
患者,男,28岁,车祸时伤及头部,当场有液体从鼻孔、耳道流出,患者昏迷,在回往医院的路上,患者清醒过来,到达医院后又再度陷入昏迷。该患者还合并了颅脑损伤,根据题目描述,该患者是
影响土壤环境的因素中,()与土壤中的重金属化合物的溶解状况密切相关。
一般脚手架定期检查的主要项目有()。
下列各项中不属于工业企业能源消费的有()。
在其他条件不变的情况下,票息越高修正期限越高,存续期限越长修正期限越高,到期收益率越高修正期限越低。()
该企业应缴纳的税种有()。该企业应缴纳所得税税额为()。
认为人的性本能是最基本的自然本能,它是推动人发展的潜在的、无意识的、最根本的动因。提出这一观点的学者是()。
一、注意事项一、本试卷由给定资料与作答要求两部分构成。考试时限为150分钟。其中,阅读给定资料参考时限为40分钟,作答参考时限为110分钟。满分100分。二、所有考生必须按要求作答,未按要求作答的,不得分。二、给定资料1.合理的收
最新回复
(
0
)