首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-11-14
34
问题
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
选项
答案
本题要求用链接结构实现一个队列,可用链表结构来实现。一般说,由于队列的先进先出性质,所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”,且要求入队和出队操作的时间复杂性是O(1),因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:l。inkedlist,x:elemtp); //p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s); //申请新结点。假设有内存空间,否则系统给出出错信息 s ↑.data:=x;s ↑.1ink:=p ↑.link; //将s结点入队 p ↑.1ink:=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/YxRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二战后主要资本主义国家经济恢复和发展的杠杆是()①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
最早以立法形式巩固大化改新成果的法令是()。
七七事变爆发后,()给中国以巨大的支援,双方签订了(),在政治上给中国以重大支持。
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
詹天佑自主设计修建了中国第一条铁路是在()。
在1956年4月提出实现马克思主义同中国实际“第二次结合”任务的是()。
1980年1月,邓小平在《目前的形势和任务》提出的中国人民长期奋斗的三件大事是()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
假定有一条通带为100kHz的信道,每路信号的带宽为3.2kHz,各路信号间的防护带宽为0.8kHz。若采用频分多路复用,那么最多可以同时传输()路信号。
随机试题
《早雁》中,暗示逃难民众有家难回的诗句是()
下列蒽醌类化合物中,酸性强弱顺序是
A.右心房、右心室大,肺野充血,肺动脉段凸出,主动脉结较小B.右心房、右心室大,肺野清晰,肺动脉段凹陷,主动脉结增大C.右心房、右心室大,肺野清晰,肺动脉段凸出,主动脉结正常D.左心房、左心室大,肺野充血,肺动脉段凸出,主动脉结增大E.左心房、左心
患者,女,70岁。慢性支气管炎病史,憋喘、呼吸困难3天。查体:神志清,体温37.8℃,脉搏102次/分,呼吸30次/分,血压100/60minHg,双肺呼吸音低,可闻及干啰音及哮鸣音,腹软,肝肋下2cm可触及,质中等,腹水征(+),双下肢水肿(+)。考
二妙散的功用是
目前上海和深圳证券交易所的权证交易()。
某企业2016年度利润总额为500万元,其中公司债券利息收入为15万元。假定当年按税法核定的全年业务招待费的扣除标准为300万元,实际发生的业务招待费为290万元,税收滞纳金为10万元。假定该企业无其他纳税调整项目,适用的所得税税率为25%。该企业2016
在分析会计报表时,若采用趋势分析法对相同指标进行对比时,必须注意()问题。
20世纪末到21世纪初,信息传播的途径进一步________,最突出的是视听手段和互联网空前快速的发展,声音和图像________涌到了大家的面前;连那些识字不多的百姓,也能通过电视获得不少信息。填入画横线部分最恰当的一项是:
强调“法国今后仍然坚持中央集权制的课程管理体制,课程大纲以《政府公报》的形式颁布,各地必须认真实施”“课程编制应以学生为中心,使全体学生具备较高的素质”“对学科体系进行综合改革,既有从小学到高中课程融为一体的纵向综合改革,也有各科知识融会贯通的横向综合改革
最新回复
(
0
)