首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-01-04
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 ↑.datal.=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 ↑.link; //找到队头元素 p ↑.link ↑.link:=s↑.link; //删队头元素 x:=s ↑.data; //返回出队元素 if(p==s)then p:=p ↑.link; //队列中只有一个结点,出队后成为空队列 dispose(s); //回收出队元素所占存储空间 } endp; 提示:上述入队算法中,因链表结构,一般不必考虑空间溢出问题,算法简单。在出队算法中,首先要判断队列是否为空,另外,对出队元素,要判断是否因出队而成为空队。否则,可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。
解析
转载请注明原文地址:https://kaotiyun.com/show/oLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述斯巴达的阶级结构、政治制度和社会风尚
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
1980-1987年撒哈拉以南非洲人均国民生产总值增长率为-2.9%。大部分国家经济急剧下滑,非洲的80年代被称“为失去发展的十年”。出现这现象关键原因在于这些国家
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
关于营养支持的叙述,下列错误的是()。
患儿,9岁。前牙反牙合,反覆盖浅,上牙合发育不足,ANB角﹣2°,下牙合平面角40°如果使用前方牵引矫正器,适宜的前方牵引施力点为
我国信用证为可撤销、转让的跟单信用证。
(2020年)甲公司是一家医疗行业投资机构,拟对乙医院进行投资。乙医院是一家盈利性门诊医院,其营业收入为门诊收入。营业成本包括医生及护士薪酬、药品材料成本等,近年来乙医院发展态势良好,甲公司拟于2020年末收购其100%股权,目前甲公司已完成该项目的可行性
甲、乙、丙、丁投资设立A普通合伙企业,主要经营电子科技产品。合伙人甲同他人合作经营与A普通合伙企业相竞争的业务,获得20万元的收益,同时甲的行为给合伙企业造成了10万元的损失。根据合伙企业法律制度的规定,下列表述正确的有()。
下列谱例中的低声部使用了哪种写作技法?()
班级组织60名同学一起春游,38个人想玩过山车,30个人想玩激流勇进,15个人想玩海盗船,有10个人两个游戏都想玩,有一些人三个游戏都想玩,还有3个人三个游戏都不想玩。如果将三个游戏都想玩的人平均分成两组,共有多少种不同的分法?()
foreignaffairs
一个完整的计算机系统应当包括()。
Olderpeoplewhoholdtemporaryorpart-timejobsafterretirementenjoybetterphysicalandmentalhealththanthosewhostopw
最新回复
(
0
)