首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-01-04
81
问题
设结点结构为(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://www.kaotiyun.com/show/oLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
评析郑和下西洋的历史条件和意义。
论述尼德兰革命的背景、主要过程及影响
近代自然科学产生的条件及其发展情况。
简述第二次世界大战对战后国际关系的影响。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
在下列哪个条约中,最先出现了片面最惠国待遇?()
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题:第一,仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略,已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
下列制度不是战国时代开始推行的是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
在下列排序方法中不需要对排序码进行比较就能进行排序的是()。
随机试题
有关第二次世界大战期间法国抵抗法西斯的各种行动,按时间顺序正确的是()
患者,女,21岁。1年前右足外伤,近日感觉右足疼痛。X线片见下图:该病最可能的诊断是
白带多属黄带多屑
安全生产法的适用范围包括()。
加快的成倍节拍流水施工的特点是( )。
甲对乙享有50000元债权,已到清偿期限,但乙一直宣称其无力清偿欠款;甲调查后发现下列情况,乙均怠于行使债权,其中,甲可以代位行使其债权的有()。
下列各项中,属于在境内销售服务、无形资产或者不动产的有()。
Racket,din,clamor,noise,whateveryouwanttocallit,unwantedsoundisAmerica’smostwidespreadnuisance.Butnoiseismor
Alzheimer’sdiseasehasnocure.Thereare,however,fivedrugs—knownandapproved—thatcanslowdownthedevelopmentofitssym
Everybodyknowswhathehastodo,_____?
最新回复
(
0
)