首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2018-08-12
66
问题
设结点结构为(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://kaotiyun.com/show/O5Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
我国发明生铁冶炼技术是在()。
近代中国各派军阀的共同点有()①始终打着维护共和制度的旗号②利用中央政权排斥异己③都试图夺取中央政权④以帝国主义列强为靠山
民族区域自治制度是在国家的统一领导下,在()实行民族区域自治,设立自治机关,行使自治制度。
秦统一过程中,最先和最后灭掉的国家是()。
1543年,发表了解剖学专著《人体结构》的是()。
中国共产党主张和平解决西安事变的主要目的是()。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
给定页面请求序列RS=cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
给定集合S={0,1,2,3,4),以及优先关系R={0<1,1<4,1<2,2<3,2<4,4<0)。(1)R是偏序关系吗?(2)证明你的结论。
在一个单处理器系统中,存在3个进程,最多有几个进程处于就绪队列()。
随机试题
电桥是把已知标准量与被测量进行比较而测出被测量的值,故称为比较式测量仪器。()
传统的IP地址(IPv4)表示为一个【】的无符号二进制数。
剂量过大能够抑制子宫收缩产生宫缩乏力,但不包括哪种药物:
夏季某餐厅供应蛋炒饭引起近百人食物中毒,发病者潜伏期约8小时,以腹痛、腹泻为主要症状,体温正常,经16~36小时全部恢复。经卫生学调查发现蛋炒饭使用的是前一天的剩饭为预防这种食物中毒的发生,剩余食物食前须彻底加热,一般应为
舌红绛苔少而干见于
小儿、老人、孕妇避免使用甲亢、高烧病人不宜使用
人民法院使用普通程序审理的案件,应当在立案之日起( )个月内审结完成。
按照哈罗德——多马模型,要使经济实现充分就业的均衡增长,其条件是实际增长率大于自然增长率。()
根据《固定资产贷款管理暂行办法》的规定,贷款人应要求借款人在合同中对与贷款相关的重要内容作出承诺,承诺内容包括()。
Ithasbeenjustlysaidthatwhile"wespeakwithourvocalorganswe【C1】con________withourwholebodies."Allofuscommunicat
最新回复
(
0
)