首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-01-04
34
问题
设结点结构为(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://kaotiyun.com/show/oLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述两德统一的过程。(南京大学1999年世界近现代史真题)
分析商代的阶级关系。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
解放军渡江战役中横渡长江的东西两个攻击点是()。
有研究者提出,1850年以后的34年中,流人中国的白银是之前34年的两倍。出现这一现象的原因是()
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
随机试题
A.病理性第二心音分裂B.第三心音C.主动脉瓣关闭不全D.二尖瓣狭窄E.肺动脉瓣关闭不全左侧卧位时舒张期杂音清楚
有关盐酸乙胺丁醇的叙述,正确的有
(2011年)在等精度测量条件下,对某管道压力进行了10次测量,获得如下数据(单位:kPa):475.3,475.7,475.2,475.1,474.8,475.2,475.0,474.9,475.1,475.1。则该测量列平均值的标准误差等于()
根据《生产安全事故报告和调查处理条例》(国务院令第493号),一般事故应当逐级上报至()安全生产监督管理部门和负有安全生产监督管理职责的有关部门。
在Word中,()是用来快速选定文本内容的区域,它定位于文档编辑区左侧的空白区域。
某女,25岁,护士,患甲状腺机能亢进两年,经药物治疗症状已控制。1个月前,丈夫接到被录取为研究生的通知书,要去外地读书。高兴之余,担心甲亢加重而无人照料,当天夜里突然惊醒,心慌、心跳加快、呼吸困难,有窒息感和濒死感,恐惧不安,全身发抖、出汗,遂到医
对于消极的课堂行为,采用适当的惩罚【】
【2015.河南驻马店】布卢姆的()仍然是测验的重要指标体系。
政府了解和反馈民意的主要渠道是()。
YouarepreparingforanEnglishtestandareinneedofsomereferencebooks.Writealettertothesalesdepartmentofabooks
最新回复
(
0
)