用python(1) 输入一个正整数n(n>2),建立带头结点的整数双链表L,L=(a_1,a_2,…a_n),其中a_i=i。在该双链表中每个结点除了有prior、data和next这3个属性外,还有一个访问频度属性freq,初始时该值为0。 (2) 可以多次按整数x(1≤x≤n)查找,每次查找x时令元素值为x的结点的freq值加1,并调整表中结点的次序,使其访问频度的递减顺序排列,以便使频繁访问的结点总是靠近表头。
时间: 2023-05-13 09:04:27 浏览: 215
PAT乙级练习题_1025“反转链表”_python解题
以下是用 Python 实现该问题的代码:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.prior = None
self.next = None
self.freq = 0
class DoubleLinkedList:
def __init__(self, n):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prior = self.head
self.length = n
for i in range(1, n+1):
node = Node(i)
node.prior = self.tail.prior
node.next = self.tail
self.tail.prior.next = node
self.tail.prior = node
def find(self, x):
node = self.head.next
while node != self.tail:
if node.data == x:
node.freq += 1
self.adjust(node)
return node
node = node.next
return None
def adjust(self, node):
while node.prior != self.head and node.freq > node.prior.freq:
node.prior.freq, node.freq = node.freq, node.prior.freq
node.data, node.prior.data = node.prior.data, node.data
node, node.prior = node.prior, node
L = DoubleLinkedList(n)
```
该代码实现了一个带头结点的双向链表,每个节点除了有 prior、data 和 next 属性外,还有一个 freq 属性,表示该节点的访问频度。在查找元素时,会将该元素对应的节点的 freq 属性加 1,并调整链表中节点的顺序,使其按照访问频度的递减顺序排列。
阅读全文