首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
设结点结构为(data,link),试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleq过程,要求它们的时间复杂性都是O(1)(不计new和dispose时间)。
admin
2018-08-12
82
问题
设结点结构为(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
学硕统考专业
相关试题推荐
1951年底到1952年春,中国共产党在党政机构工作人员中开展运动的内容是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
以下不是巴黎和会的主要议题的是()
第一个五年计划的具体时间段是()。
中国共产党主张和平解决西安事变的主要目的是()。
文艺复兴运动兴起的时间是()。
头下军州中,除了()和一半田租之外要全部上交辽中央,其他都归头下主所有。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
某机的主要部件如下图所示。(1)请补充各部件间的主要连接线,并注明数据流动方向。(2)拟出指令SUB(R1),—(R2)的执行流程(含取指过程与确定后继指令地址)。该指令的含义是进行减法操作,源操作数地址和目的操作数地址分别在寄存器R1和R2中,目的
随机试题
关于再生障碍性贫血病因的叙述,下列哪项错误?
女性,21岁。反复尿频、尿急、尿痛2年,加重伴肉眼血尿、发热2天。以下检查不提示上尿路感染的是
填充后浇带可采用微膨胀混凝土,强度等级比原结构强度提高一级,并保持至少()d的湿润养护。
下列各项中,应列入利润表“营业成本”项目的有()。
运输动植物、动植物产品和其他检疫物过境(含转运的),( )应当持货运单和输出国家或者地区政府动植物检疫机关出具的证书,向进境口岸出入境检验检疫机关报检。
大宝是名大学本科生,在学习过程中,他倾向于从现实问题出发联系到抽象问题,再从抽象问题回到现实问题中去。大宝在学习方面的认知风格属于()。
关于盗窃罪的理解,下列选项正确的是
【B1】【B11】
Theexaminationswhetherconsideredgoodorbad
Womenarequiteoftencompetentdrivers,buttheyareveryseldomconsistentlyfirstclass.Atbesttheyareamildhazard,at【C
最新回复
(
0
)