首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2017-01-04
73
问题
设结点结构为(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
学硕统考专业
相关试题推荐
1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。
评析郑和下西洋的历史条件和意义。
简述第二国际建立的社会历史条件。
格拉古兄弟改革的内容和结果是什么?
下列不是开始于战国时期的制度是()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
随机试题
赵老师从因特网上找到了一份对自己有用的文字材料,他用复制、粘贴命令把它放到Word中,发现里面有大量的无用空格,他打算把这些空格全部去掉,下列方法中最适当的是()。
采用___________技术可以尽可能地全面恢复运行计算机网络所需的数据和系统信息。
下列关于体层摄影,下列说法正确的是
A.天门B.大椎C.断血D.百会E.尾根治疗马感冒、咳嗽、发热、癫痫宜选
家禽体内性成熟后逐渐退化并消失的器官是
患儿,男童,7岁,松动Ⅲ度,舌侧部分萌出,拔时最适合采用
依照《海商法》的规定,下列有关船舶抵押权的表述,正确的有:
简述教学评价的原则。
Iftheuniversalityofimmersion-stylelanguageprograms,emergencytestprepclasses,tiredcollegekidsisanyindication,cra
A、ItrequiredGeorgiatooverwork.B、Itwasrelatedtocheckingpeople’steeth.C、ItmadeGeorgiatiredandunhappy.D、Allthep
最新回复
(
0
)