首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-01-04
29
问题
设结点结构为(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://jikaoti.com/ti/TJfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
如何全面分析十月革命的历史条件及特点?
中国第一个资产阶级革命团体兴中会建立的时间是()。
在下列哪个条约中,最先出现了片面最惠国待遇()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
随机试题
前列腺素E的生理功能之一是
某患G1P0,37孕周来诊。幼年患急性肾炎。检查:BP24.0/14.6kPa(180/110mmHg),下肢水肿(++),宫高29cm,Hb120g/L,Ht0.38,眼底A:V为1:2,尿蛋白(+++),尿比重1.020,B超双顶径为8.6cm。该
小波通过做游戏的方式来确定周末活动,他随机地往单位圆内投掷一点,若此点到圆心的距离大于,则周末去看电影;若此点到圆心的距离小于,则去打篮球;否则,在家看书,则小波周末不在家看书的概率为______。
目前我们使用的手机等电子产品中的电池都属于化学类电池,经过多次使用,电池中的电解质和金属极板之间会产生化学反应,金属极板的表面会出现一层钝化层,钝化层会阻止电流的产生与通过,使电池的内电阻增加,电池能提供的电量也会随之下降,从而导致电池容量慢慢衰减,造成电
垃圾:垃圾桶:清洁工
(2008年)求极限
Videogameswillbeforcedtocarrycigarette-stylehealthwarningsunderproposalstoprotectchildrenfromunsuitabledigital
在32位的计算机中,一个char型数据所占的内存长度的字节是
无符号二进制整数01011010转换成十进制整数是
Readthetextsfromamagazinearticlehowtomaintainasustainableloverelationship.Forquestions61to65,matchthenameo
最新回复
(
0
)