python 链表数据结构,python顺序表和链表

　　CircularLinkedList是链式存储结构的另一种形式。它将链表中最后一个节点的指针指向链表的头节点，使整个链表首尾相连形成一个环，使得链表的操作更加方便灵活。本文将详细介绍循环链表的相关知识，有需要的可以参考一下。

　　00-1010 0.学习目标1。循环链表介绍2。循环单链表的实现2.1循环单链表的基本操作2.2简单的实现方法2.3循环单链表的应用实例2.4循环单链表基本操作的复杂操作3。循环双向链表的实现3.1循环双向链表的基本操作3.2循环双向链表的应用实例

　　循环链表是链式存储结构的另一种形式。它将链表中最后一个节点的指针指向链表的头节点，使整个链表首尾相连形成一个环，使得链表的操作更加方便灵活。我们介绍了单链表和双链表。在本节中，我们将基于单链表和双链表实现循环链表和循环双链表及其相关操作。

　　通过本节，您应掌握以下内容：

　　循环链表的基本概念及其优缺点

　　循环链表及其操作实现

　　双向链表及其操作的实现

0. 学习目标

　　在单链表/双链表中，最后一个节点的指针字段是None，所以链表中的任何数据都只能从链表头开始顺序访问，不允许任意位置的随机查询访问。如果被查询的节点在链表的末尾，就需要遍历整个链表。

　　循环链表是一种特殊的链表。在循环链表中，首尾点相连，使整个链表首尾相连形成一个环，也就是说，链表中的最后一个节点指向第一个节点；换句话说，循环链表中的所有节点都指向下一个节点，每个节点都有一个后继节点。

　　循环链表的好处是从链表中的任意一个节点开始，可以沿着指针链找到表中的其他节点，所以没有节点指向无；同时不占用额外的存储空间，只需要改变最后一个节点的指针就可以让操作更加方便灵活。

　　循环链表可以基于单链表和双链表。通常，基于单链表的循环链表称为循环单链表，基于双链表的循环链表称为循环双链表。两种循环链表的示意图如下：

　　注：由于我们对链表已经非常熟悉，所以只简单介绍一下链表中的类似操作，我们的主要精力将集中在有差异的操作上。

1. 循环链表简介

　　类似于单链表，我们来实现一个有头节点的循环单链表类，用头指针标识链表的开头。如果你还不了解单链表，可以参考《单链表及其操作实现》的相关介绍。

2. 循环单链表实现

　　单链表的基本操作大部分和单链表一样，只是循环遍历的条件需要从current==None改为current！=头部

　　2.1.1循环单链表的初始化

　　初始化循环单链表函数时，创建的头节点指针字段next不为空，而是指向自身：

　　类循环链接列表：

　　def __init__(self):

　　头节点=节点()

　　self.head=头节点

　　头节点。下一个=头节点

　　self.length=0

　　2.1.2获取循环单链表的长度

　　重载__len__从对象返回length的值，以查找循环单链表的长度：

　　def __len__(self):

　　返回自身长度

　　2.1.3读取指定位置的元素。

　　重载__getitem__操作用于读取链表中指定位置的元素。同样，我们也可以修改指定位置的元素。我们只需要重载__setitem__操作，它们的时间复杂度为O(n):

　　def __getitem__(self，index):

　　如果索引自身长度-

　　 1 or index < 0:

　　 raise IndexError("CircularLinkedList assignment index out of range")

　　 else:

　　 count = -1

　　 current = self.head

　　 while count < index:

　　 current = current.next

　　 count += 1

　　 return current.data

　　 def __setitem__(self, index, value):

　　 if index > self.length - 1 or index < 0:

　　 raise IndexError("CircularLinkedList assignment index out of range")

　　 else:

　　 count = -1

　　 current = self.head

　　 while count < index:

　　 current = current.next

　　 count += 1

　　 current.data = value

　　我们可以发现，这两个操作与单链表的操作完全相同。

　　2.1.4 查找指定元素

　　在循环单链表中查找指定元素的操作与单链表基本相同，使用 current 指针沿后继链依次遍历每个结点，并判断其值是否等于指定值 value，若是则返回该结点索引，否则继续往后搜索；只是循环遍历是否完成的条件需要由 current == None 改为 current != head：

 def locate(self, value):
　　 count = 0
　　 current = self.head.next
　　 while current != self.head and current.data != value:
　　 count += 1
　　 current = current.next
　　 if current and current.data == value:
　　 return count
　　 else:
　　 raise ValueError("{} is not in sequential list".format(value))

　　2.1.5 在指定位置插入新元素

　　由于有 length 属性的原因，我们可通过 length 判断插入位置是否合法，因此在循环单链表中的指定位置插入新元素与在单链表指定位置插入新元素完全相同：

 def insert(self, index, data):
　　 count = -1
　　 current = self.head
　　 # 判断插入位置的合法性
　　 if index > self.length or index < 0:
　　 raise IndexError("CircularLinkedList assignment index out of range")
　　 else:
　　 node = Node(data)
　　 while count < index:
　　 # 查找插入位置
　　 previous = current
　　 current = current.next
　　 count += 1
　　 # 插入新结点
　　 node.next = previous.next
　　 previous.next = node
　　 self.length += 1

　　2.1.6 删除指定位置元素

　　要删除链表中第i个结点，同样首先找到删除位置的前一个结点 previous，指针 current 指向要删除的结点，将 previous 的指针域修改为待删除结点 current 的后继结点的地址，删除后的结点需动态的释放：

 def __delitem__(self, index):
　　 if index > self.length - 1 or index < 0:
　　 raise IndexError("CircularLinkedList assignment index out of range")
　　 else:
　　 count = -1
　　 previous = self.head
　　 while count < index - 1:
　　 previous = previous.next
　　 count += 1
　　 current = previous.next
　　 previous.next = current.next
　　 self.length -= 1
　　 del current

　　2.1.7 其它一些有用的操作

　　[1] 使用 str 函数调用对象上的 __str__ 方法可以创建适合打印的字符串表示：

 def __str__(self):
　　 head = self.head
　　 s = "["
　　 current = self.head.next
　　 count = 0
　　 while current != head:
　　 count += 1
　　 s += str(current)
　　 current = current.next
　　 if count < self.length:
　　 s += -->
　　 s += "]"
　　 return s

　　[2] 删除指定元素，其时间复杂度与删除指定位置元素相同，都为O(n)：

 def del_value(self, value):
　　 previous = self.head
　　 current = self.head.next
　　 while current != self.head:
　　 if current.data == value:
　　 previous.next = current.next
　　 self.length -= 1
　　 del current
　　 return
　　 else:
　　 previous = current
　　 current = current.next
　　 raise ValueError("The value provided is not present!")

　　[3] 为了方便的在链表尾部追加新元素，可以实现函数 append：

 def append(self, value):
　　 node = Node(value)
　　 current = self.head.next
　　 while current.next != self.head:
　　 current = current.next
　　 node.next = current.next
　　 current.next = node
　　 self.length += 1

2.2 简单的实现方法

　　从上述实现，我们可以看到，CircularLinkedList 类的代码中大部分与 SinglyLinkedList 类完全相同，如果你对继承机制还有印象的话，我们也可以令 CircularLinkedList 继承自在《单链表及其操作实现》中实现的 SinglyLinkedList，简化循环单链表的实现。

from SinglyLinkedList import SinglyLinkedList
　　class CircularLinkedList(SinglyLinkedList):
　　 """
　　 利用继承机制仅需要实现循环单链表与单链表中不同的操作,仅需要重载父类中：
　　 __init__(), locate(), del_value(), __str__(), append() 函数即可
　　 相关代码在上一小节已经给出，这里不再赘述
　　 """
　　 pass

2.3 循环单链表应用示例

　　接下来，我们将测试上述实现的循环单链表，以验证操作的有效性。首先初始化一个链表 cllist，并在其中追加若干元素：

cllist = CircularLinkedList()
　　# 在循环单链表末尾追加元素
　　cllist.append(apple)
　　cllist.append(lemon)
　　# 在指定位置插入元素
　　cllist.insert(0, banana)
　　cllist.insert(2, orange)

　　我们可以直接打印链表中的数据元素、链表长度等信息：

print(循环单链表 cllist 数据为：, cllist)
　　print(循环单链表 cllist 长度为：, len(cllist))
　　print(循环单链表 cllist 第 0 个元素为：, cllist[0])
　　cllist[0] = pear
　　print(修改循环单链表 cllist 后数据元素为：, cllist)

　　以上代码输出如下：

循环单链表 cllist 数据为： [banana-->apple-->orange-->lemon]
循环单链表 cllist 长度为： 4
循环单链表 cllist 第 0 个元素为： banana
修改循环单链表 cllist 后数据元素为： [pear-->apple-->orange-->lemon]
　　

　　接下来，我们将演示在指定位置添加/删除元素、以及如何查找指定元素等：

# 在指定位置添加/删除结点
　　cllist.insert(1, grape)
　　print(在位置 1 添加 grape 后循环单链表 cllist 数据：, cllist)
　　del(cllist[2])
　　print(修改循环单链表 cllist 后数据：, cllist)
　　# 删除指定元素
　　cllist.del_value(pear)
　　print(删除 pear 后循环单链表 cllist 数据：, cllist)
　　cllist.append(watermelon)
　　print(添加 watermelon 后循环单链表 cllist 数据：, cllist)

　　以上代码输出如下：

在位置 1 添加 grape 后循环单链表 cllist 数据： [pear-->grape-->apple-->orange-->lemon]
修改循环单链表 cllist 后数据： [pear-->grape-->orange-->lemon]
删除 pear 后循环单链表 cllist 数据： [grape-->orange-->lemon]
添加 watermelon 后循环单链表 cllist 数据： [grape-->orange-->lemon-->watermelon]
　　

2.4 利用循环单链表基本操作实现复杂操作

　　[1] 将两个循环单链表首尾相接进行合并，连接示例如下图所示：

　　与单链表不同，循环单链表的连接不仅需要遍历第一个链表找到最后一个结点连接到第二个链表上，还需要遍历第二个链表，使第二个链表的尾结点的 next 指针指向第一个链表的头结点，具体实现如下：

def merge(cllist1, cllist2):
　　 current = cllist1.head
　　 while current.next != cllist1.head:
　　 current = current.next
　　 # 若cllist2不为空，进行连接操作
　　 if cllist2.head.next != cllist2.head:
　　 current.next = cllist2.head.next
　　 current2 = cllist2.head.next
　　 while current2.next != cllist2.head:
　　 current2 = current2.next
　　 current2.next = cllist1.head
　　 cllist1.length += len(cllist2)
　　 return cllist1
　　# 算法测试
　　cllist1 = CircularLinkedList()
　　cllist2 = CircularLinkedList()
　　for i in range(5):
　　 cllist1.append(i)
　　 cllist2.append((i+1)*5)
　　print(循环单链表 cllist1：, cllist1)
　　print(循环单链表 cllist2：, cllist2)
　　result = merge(cllist1, cllist2)
　　print(循环链表连接结果：, result)

　　算法执行结果如下：

循环单链表 cllist1： [0-->1-->2-->3-->4]
循环单链表 cllist2： [5-->10-->15-->20-->25]
循环单链表连接结果： [0-->1-->2-->3-->4-->5-->10-->15-->20-->25]
　　

3. 循环双链表实现

　　类似于双向链表，接下来我们实现一个带有头结点的循环双链表类，并用头指针标识链表的开头，如果你还不了解双向链表，可以参考《双向链表及其操作实现》相关介绍。

3.1 循环双链表的基本操作

　　由于循环双链表类DoubleLinkedCircularList的代码中大部分与双向链表类DoublyLinkedList完全相同，因此我们借助继承机制来简化循环双链表的实现，DoublyLinkedList类的实现参考《双向链表及其操作实现》。

from DoublyLinkedList import DoublyLinkedList
　　class Node:
　　    def __init__(self, data=None):
　　        self.data = data
　　        self.next = None
　　        self.previous = None
　　    def __str__(self):
　　        return str(self.data)

　　循环双链表的初始化，不仅需要将头结点的 next 指针指向自身外，previous 指针同样需要指向自身：

class DoubleLinkedCircularList(DoublyLinkedList):
　　 def __init__(self, data=None):
　　 self.length = 0
　　 # 初始化头结点
　　 head_node = Node() 
　　 self.head = head_node
　　 self.head.next = self.head
　　 self.head.previous = self.head

　　定位元素位置，同样只需要修改遍历完成条件即可：

 def locate(self, value):
　　 count = 0
　　 current = self.head.next
　　 while current != self.head and current.data != value:
　　 count += 1
　　 current = current.next
　　 if current and current.data == value:
　　 return count
　　 else:
　　 raise ValueError("{} is not in sequential list".format(value))

　　相比于双链表，循环双链表的删除和插入操作更加方便，由于其循环特性的原因，并不需要考虑所删除或插入的结点是否是链表中的最后一个结点：

 def __delitem__(self, index):
　　 # 删除指定位置结点
　　 if index > self.length - 1 or index < 0:
　　 raise IndexError("DoubleLinkedCircularList assignment index out of range")
　　 else:
　　 count = -1
　　 current = self.head
　　 while count < index:
　　 current = current.next
　　 count += 1
　　 current.previous.next = current.next
　　 current.next.previous = current.previous
　　 self.length -= 1
　　 del current
　　 def del_value(self, value):
　　 # 删除链表中的指定元素
　　 current = self.head
　　 while current.next != self.head:
　　 if current.data == value:
　　 current.previous.next = current.next
　　 current.next.preious = current.previous
　　 self.length -= 1
　　 del current
　　 return
　　 else:
　　 current = current.next
　　 raise ValueError("The value provided is not present!")
　　 def insert(self, index, data):
　　 count = 0
　　 current = self.head
　　 # 判断插入位置的合法性
　　 if index > self.length or index < 0:
　　 raise IndexError("DoubleLinkedCircularList assignment index out of range")
　　 else:
　　 new_node = Node(data)
　　 while count < index:
　　 current = current.next
　　 count += 1
　　 new_node.next = current.next
　　 current.next.previous = new_node
　　 new_node.previous = current
　　 current.next = new_node
　　 self.length += 1

　　由于继承的缘故，并不需要在子类中重写相同的操作(类如查找指定元素等)，最后我们重载一些其它有用的操作：

  def append(self, data):
　　        new_node = Node(data)
　　        current = self.head
　　        while current.next != self.head:
　　            current = current.next
　　        new_node.next = current.next
　　        current.next.previous = new_node
　　        new_node.previous = current
　　        current.next = new_node
　　        self.length += 1
　　    def __str__(self):
　　        head = self.head
　　        s = "["
　　        current = self.head.next
　　        count = 0
　　        while current != head:
　　            count += 1
　　            s += str(current)
　　            current = current.next
　　            if count < self.length:
　　                s += <-->
　　        s += "]"
　　        return s

3.2 循环双链表应用示例

　　接下来，我们测试上述实现的循环双链表，以验证操作的有效性：

dlclist = DoubleLinkedCircularList()
　　# 在链表末尾追加元素
　　dlclist.append(apple)
　　dlclist.append(lemon)
　　# 在指定位置插入元素
　　dlclist.insert(0, banana)
　　dlclist.insert(2, orange)
　　print(循环双链表 dlclist 数据为：, dlclist)
　　print(循环双链表 dlclist 长度为：, len(dlclist))
　　# 查找指定元素，这里就是调用父类的locate方法
　　print(apple 在 dlclist 中序号为：, dlclist.locate(apple))
　　# 获取指定位置元素
　　print(循环双链表 dlclist 第 0 个元素为：, dlclist[0])
　　# 修改数据元素
　　dlclist[0] = pear
　　print(修改循环双链表 dlclist 后数据元素为：, dlclist)
　　del(dlclist[2])
　　print(修改循环双链表 dlclist 后数据：, dlclist)
　　# 删除指定元素
　　dlclist.del_value(pear)
　　print(删除 pear 后循环双链表 dlclist 数据：, dlclist)

　　上述程序输出如下所示：

循环双链表 dlclist 数据为： [banana<-->apple<-->orange<-->lemon]
循环双链表 dlclist 长度为： 4
apple 在 dlclist 中序号为： 1
循环双链表 dlclist 第 0 个元素为： banana
修改循环双链表 dlclist 后数据元素为： [pear<-->apple<-->orange<-->lemon]
修改循环双链表 dlclist 后数据： [pear<-->apple<-->lemon]
删除 pear 后循环双链表 dlclist 数据： [apple<-->lemon]
　　

　　以上就是Python数据结构之循环链表详解的详细内容，更多关于Python循环链表的资料请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。