首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2018-08-12
56
问题
设结点结构为(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://jikaoti.com/ti/YcfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
晚清时期清帝年号的正确排序是()
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
宁夏回族自治区的设立时间是()。
隋在统一全国的过程中,平定江南是一个重要的部分,帮助完成岭南一带平定的是()
绿林军领袖为了大影响,拥立汉宗室()为皇帝,恢复汉的国号,以公元23年为更始元年。
首次提出“长期共存,互相监督”观念的是在文件()中。
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
张居正改革期间,调任抗倭名将()镇守蓟门,对安定北方发挥了积极作用。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
一个SPOOUNG系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程I通过输入缓冲区为进程P输入数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPOO
随机试题
张某与赵某系邻居,二人因宅基地问题产生纠纷。两家发生争吵,张某一时气愤,手持铁棍来到赵某家中,将赵某家一辆自行车砸坏,赵某上前将铁棍抢走,张某遂拿起赵某家中的铁锨将赵某打致轻微伤。派出所民警对铁棍和铁锨处理正确的是()。
某酒厂生产的“天下景”牌葡萄酒,其包装正面和两侧的图形、字体、色彩均与已经在我国注册的驰名商标“万宝路”牌卷烟盒相近似,其封口上印的标识也与“万宝路”卷烟封口相近似。该厂所在地的市场监督管理局发现后,责令该厂停止销售这种葡萄酒,收缴其全部外包装,并处以罚款
某商场为庆祝开业三周年,制作了一个长方形大蛋糕,并切成四块,如图所示。假设这个蛋糕可供350人享用,左下角那块蛋糕平均可供50人享用,右上角那块蛋糕平均可供70人,则中间最大块蛋糕平均可供多少人享用?
关于手术产新生儿的护理,正确的是
猩红热患儿进行病原学检查时,在治疗前多用
患者近期因工作压力大,出现经行乳房胀满疼痛,伴乳头痒痛,甚则痛不可触衣,经行不畅,血色暗红,小腹胀痛,胸闷胁胀,精神抑郁,苔薄白,脉弦。治疗应首选的方剂是
在建设项目周期的决策阶段中,可行性研究是______的最重要的一个环节。
下列项目中,不属于原始凭证的是()。
()认为,当市场上存在套利机会时,投资者会不断进行套利交易,直到套利机会消失为止。
(2017·陕西)能以自己的名义依法行使国家行政权并能独立地承担法律责任的组织称为()
最新回复
(
0
)