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

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

admin2016-03-29  88
问题 设结点结构为(data，link)，试用一个全局指针p和某种链接结构实现一个队列，画出示意图，并给出入队addq和出队deleq过程，要求它们的时间复杂性都是O1)(不计new和dispose时间)。
选项
答案本题要求用链接结构实现一个队列，可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O(1)，因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p：linkedlistl x：elemtp)； ／／p是数据域为data、链域为link的用循环链表表示的队列的尾指针 new(s)； ／／申请新结点。假设有内存空间，否则系统给出出错信息 s ↑．data：=x；s ↑．1ink：=p ↑．link； ／／将s结点入队 p ↑．link：=s；p：=s； ／／尾指针p移至新的队尾 endp； (2)proc deleq(val p：linkedlist，var x：elemtp)； ／／p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实 ／／现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息 if(p ↑．1ink==p)then{writeln(”空队列”)；return(0)；} ／／带头结点的循环队列 else{s：=p ↑．link t．link； ／／找到队头元素 p ↑．link ↑．1ink：=s ↑．link； ／／删队头元素 x：=s ↑．data，； ／／返回出队元素 if(p：=s)then p：=p ↑．1ink； ／／队列中只有一个结点，出队后成为空队列 dispose(s)； ／／回收出队元素所占存储空间 } endp；
解析
转载请注明原文地址:https://www.kaotiyun.com/show/VnRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)