设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是D(1)(不计new和dispose时间)。

admin2019-08-15 39

问题设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是D(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 ↑．1ink；／／将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 ↑．1ink ↑．1ink：=s ↑．1ink；／／删队头元素 x：=s ↑．data；／／返回出队元素 if(p==s)then p：=p ↑．link；／／队列中只有一个结点，出队后成为空队列 dispose(s)；／／回收出队元素所占存储空间 } endp；提示：上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。

解析

转载请注明原文地址:https://kaotiyun.com/show/5OCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是D(1)(不计new和dispose时间)。

计算机408

学硕统考专业

《中国国民党改组宣言》发表的时间是()。

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

设计一个算法，求无向图G(采用邻接表存储)的连通分量个数。

某DRAM芯片内部存储元排列成1024．×1024的矩阵，且已知其存取周期为0．1μs，最大刷新间隔为2ms。当采用异步刷新方式时，死时间()。

设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号以及花括号，嵌套的顺序随意，如：“{[()]()}”。试编写算法，实现判定给定表达式中所含括号是否正确配对的出现。

已知小写英文字母“a”的ASCⅡ码值为61H，现字母“g”被存放在某个存储单元中，若采用偶校验(假设最高位作为校验位)，则该存储单元中存放的十六进制数是()。

下列对压缩数据库的叙述中，错误的是()

虚寒痢的治法是

某产妇，剖宫产后第6天顺利出院，护士交代其产后复查的时间是

下列各种晶体中，熔化时需破坏共价键的是()。

基金规模越大，基金托管费率越高。()

商业银行风险管理涉及大量的数据，下列各项属于外部数据的有()。

公民、法人或者其他组织不服复议决定的，可以在收到复议决定书之日起2个月内向人民法院提起诉讼。()

计算机的指令系统能实现的运算有()。

Thenuclearageinwhichthehumanraceisliving,andmaysoonbedying,beganforthegeneralpublicwiththedroppingofana

Herparentsdiedwhenshewasyoungsoshewas______byhergrandma.