devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

python实现数据结构--线性表_python线性表

作者：我家自动化 | 2024-05-07 14:34:53

赞

踩

python线性表

线性表

1 定义

线性表是由 n （ n > = 0 ） n（n>=0） n（n>=0）个数据元素（节点） a 1 、 a 2 、 a 3 、 … 、 a n a1、a2、a3、…、an a1、a2、a3、…、an 成的有限序列。该序列中的所有节点都具有相同的数据类型。其中，数据元素的个数 n n n 称为线性表的长度。

当n=0时，称为空表。当n>0时，为非空的线性表，记作(a1,a2,…,an)。
　　
线性表的主要存储结构：

  • 顺序存储结构：顺序表
  • 链式存储结构：单链表、双链表、循环链表

2 顺序表

定义：把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元中，用这种方法存储的线性表称为顺序表，即顺序存储的线性表。

特点：

  • 线性表的逻辑顺序与物理顺序一致。
  • 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现的。可以直接根据存储单元的个数和大小计算出任意元素的存储地址。
基本操作
1. 初始化顺序表

​ 初始化顺序表时先给顺序表分配内存空间，声明数组的最大容量。Python中实例对象初始化一般会用到 __init__()方法。代码实现如下：

def __init__(self, max):
　　'''
　　初始化
　　:paramma:顺序表最大容量
　　'''
　　sel.max = max
　　sel.index = 0
　　self.data = [None for_ in range(self.max)]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
2. 按下标值查找元素

​ 通过下标值来查找元素，如果下标值合法，则返回该下标值上元素，否则抛出异常，代码实现如下。

def __getitem__(self, index):
  '''
  获取下标值为index的元素
  ：param index:下标值
  ：return : 下标值为 index 的元素
  '''
	if index < 0 or index >= self.index:
    	raise IndexError('index非法')
 	else:
		return self.data[index]

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
3．修改下标值为index的位置的元素

​ 修改下标值为 index 的元素的值，如果 index 非法，则抛出异常；否则修改数据元素的值，代码实现如下。

def__setitem__(self,index,value):
  '''
  修改下标值为index的元素的值
  :paramindex:下标值
  :paramvalue:待替换的元素
  :return:
  '''
  if index < 0 or index >= self.index:
    raiseIndexError('index非法')
  else:
    self.data[index] = value


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
4．判断顺序表是否为空

​ 若顺序表为空，则 self.index 为0，所以只需要判断 self.index 是否为 0 即可，代码实现如下:

def empty(self):
  '''
   判断顺序表是否为空
   :return:TrueorFalse
  '''
  return self.index is 0

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
5．插入表头元素

​ 插入元素前需要先判断顺序表是否已经达到最大容量，如果达到最大容量，则退出程序；否则在顺序表尾部插入元素，代码实现如下:

def append(self, value):
	'''
	表尾插入元素
	:paramvalue:待插入的元素
	:return:顺序表已满的出口
	'''
  if self.index is self.max:
    return
  else:
    self.data[self.index] = value
    self.index += 1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
6．在顺序表中任意位置插入元素

​ 先判断 index 下标值是否合法，若不合法，则抛出异常；若合法，则通过 for 循环将下标值为index 及其之后的元素向后移动一个位置，并在下标值index所在的位置添加元素，代码实现如下:

def insert(self,index,value):
  '''
  在顺序表中任意位置插入元素
  :param index:待插入元素的位置
  :param value:待插入元素的值
  '''
  #若index非法，则抛出异常
  if index < 0 or index > self.index:
    raiseIndexError('idnex非法')
  #若index刚好为顺序表尾
  if index = self.index:
    self.append(value)
  #通过for…in…将下标值为index及其之后的元素向后移动一个位置
  else:
    self.data += [value]
    for i in range(self.index, index, -1):
      self.data[i] = self.data[i-1]
    self.data[index] = value
    self.index += 1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
7．删除表尾元素

​ 删除元素前需要先判断顺序表是否为空，empty() 方法用来判断顺序表是否为空，这里可以直接调用。如果顺序表为空，则退出程序；否则将 self.index 减1，代码实现如下:

def pop(self):
  '''
  删除表尾元素
  :return: 顺序表为空的出口
  '''
  if self.empty():
    return
  self.index += 1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
8．删除任意位置的元素

​ 先判断下标值是否合法，不合法就抛出异常；否则用for循环将index后面的所有元素都向前移动一个位置，覆盖 index 原本的值，代码实现如下：

def delete(self, index):
  '''
  顺序表中删除任意位置的元素
  :param index:删除下标值为 index 的元素
  '''
  # 下标不合法，抛出异常
  if self.empty() or index >= self.index:
    raise IndexError('index 非法')
  # 下标合法，通过for循环将index后面的所以元素都向前移动一个位置，从而覆盖index原本的值
  for i in range(index, self.index):
    self.data[i] = self.data[i+1]
  self.index -= 1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
9．获取顺序表的长度

​ 初始化时，self.index 为0，每当向顺序表中添加一个元素时，self.index 加1；删除元素时，self.index 减 1，所以 self.index 记录着顺序表中元素的个数，代码实现如下:

def length(self):
  '''
  获取顺序表的长度
  :return:当前顺序表中元素的个数
  '''
  return self.index

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
10．遍历顺序表

​ 先判断顺序表是否为空，若顺序表为空，则抛出异常；否则遍历输入顺序表的数据元素，代码实现如下:

def traversal(self):
  '''
  遍历顺序表
  '''
  for i in range(self.index):
    print(self.data[i],end=" ")

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
3 单链表

定义： 若要用一组任意的存储单元存储线性表的数据元素，则需要把这些分散的元素 ”链“ 起来，这种方法存储的线性表称为线性链表，简称链表。

特点： 存储链表中的节点的一组任意的存储单元可以是连续的，也可以是不连续的，即逻辑上相邻的数据元素在位置上不一定相邻

**实现：**为了正确表示节点间的逻辑关系，每个存储单元需要包含两部分的内容:

  • 值域 ( d a t a ) (data) (data) : 存放节点的值

  • 指针域 ( n e x t ) (next) (next) : 用来存放节点的直接后继指针。

    这两部分组成了链表中的节点结构，即单链表存储结构，如图所示：

​ 单链表节点定义代码如下： 
class Node(object):
  def __init__(self, val):
    # 存放节点的数据域
    self.val = val
    # 指向后继节点的指针
    self.next = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
基本操作
1. 单链表初始化
class SingleLinkedList(object):
  def __init__(self):
    '''
    单链表初始化
    '''
    # 声明头指针、尾指针均指向空
    self.head = None
    self.tail = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
2. 判断单链表是否为空

​ 若表头指针指向空，则单链表为空；若表头节点不指向空，则单链表不为空，代码实现如下：

def empty(self):
  '''
  判断单链表是否为空
  :return: 如果单链表为空返回True,否则返回False
  '''
  return self.head is None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
3. 获取单链表长度

​ 遍历整个单链表，若当前节点不为空，则单链表长度加 1，代码实现如下：

def length(self):
  '''
  获取单链表的长度
  :return:返回单链表的长度
  '''
  # size 用来计算单链表的长度
  size = 0
  # 声明 cur 指针，用来遍历单链表
  cur = self.head
  while cur != None:
    size += 1
    cur = cur.next
  return size

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
4. 头插法

​ 情况一：链表为空，将头、尾指针指向新节点，新节点成为表头节点。

​ 情况二：链表不为空，将新节点的直接后继指针指向头结点，如图所示：

​ 代码实现如下：

def prepend(self, val):
  '''
  头插法
  :param val: 待插入的关键字
  '''
  newNode = Node(val)
  # 如果链表为空
  if self.head is None:
    # 头、尾指针指向新节点
    self.head = newNode
    self.tail = newNode
  # 如果链表不为空
  else:
    # 将新节点的后继指针指向头结点
    newNode.next = self.next
    self.head = newNode

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
5. 在链表中间位置插入节点

​ 将新节点插入链表的第 i i i 个位置时，需要先遍历单链表到第 i − 1 i-1 i−1 个节点，将第 i − 1 i-1 i−1 个位置的节点的直接后继指针指向新节点，将新节点的直接后继指针指向第 i i i 个位置，是的新节点成为第 i i i 个位置的新节点，如图所示。

​ 代码实现如下：

def insert(self, index, value):
  '''
  在链表的中间位置插入新节点
  :param
  	index: 在下标值index 处插入元素， index 从0开始
  	value: 新节点的数据域
  '''
  # 声明指针 cur ,用来遍历链表
  cur = self.head
  # 遍历停止的条件， cur 指向下标为 index-1 的节点
  for i in range(index-1):
    cur = cur.next
  # temp 指针指向原来的第 index 个节点
  temp = cur.next
  newNode = Node(value)
  # 将新节点的后继指针指向 temp
  newNode.next = temp
  # 将第 index 个节点的直接后继指向新节点
  cur.next = newNode

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
6. 尾插法

​ 情况一：单链表为空，将头、尾指针指向新节点

​ 情况二：单链表不为空，将表尾节点直接后继指向新节点，如图所示：

代码实现如下：

def append(self, val):
  '''
  尾插入法
  :param val: 待插入的数据元素
  '''
  newNode = Node(val)
  # 如果单链表为空
  if self.empty():
    # 头指针、尾指针指向新节点
    self.head = newNode
    self.tail = newNode
  # 如果单链表不为空
  else:
    # 尾节点的后继指针指向新节点
    self.tail.next = newNode
    # 尾指针指向新节点
    self.tail = newNode

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
7. 删除头结点

​ 情况一：单链表为空，无法删除，抛出异常

​ 情况二：单链表不为空且只有一个节点，将头、尾指针指向空

​ 情况三：单链表不为空且有多个节点，将头指针指向第二个节点，如图所示：

​ 代码实现：

def del_first(self):
  '''
  删除头结点
  '''
  if self.empty():
    raise IndexError('链表为空')
  # 单链表只有一个节点
  if self.length() == 1:
    self.head = None
    self.tail = None
  # 链表长度大于1
  else:
    self.head = self.head.next

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
8. 删除单链表中任意位置的节点

​ 遍历单链表到第 i − 1 i-1 i−1 个位置的节点。将第 i − 1 i-1 i−1 个位置的节点的指针指向第 i + 1 i+1 i+1 个位置的节点。如图所示：

​ 代码如下：（注：说下标值得时候是从0开始的，但是说“第”的时候是从1开始的，第一个第二个…元素等）

def delete(self, index):
  '''
  删除任意位置的节点
  :param index: 要删除下标值为 index 位置的节点，
  '''
  if self.empty():
    raise IndexError('链表为空')
  # 如果 index 非法，则抛出异常
  if index < 0 or index >= self.length():
    raise IndexError('Index 非法')
  if index == 0:
    self.del_first()
  else index == self.length() - 1:
    self.del_last()
  else:
    pre = self.head
    # 通过for循环使pre指针指向第index个节点
    for i in range(index - 1):
      pre = pre.next
    pre.next = pre.next.next  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
9. 删除尾节点

​ 情况一：单链表为空，无法删除节点，抛出异常

​ 情况二：单链表不为空但只有一个节点，将头、尾指针指向空

​ 情况三：单链表不为空且有多个节点，将尾指针指向导数第二个节点，并将导数第二个节点的后继指针指向空。如图所示：

代码实现：

def del_last(self):
  '''
  	删除尾节点
  '''
  if self.empty():
    raise IndexError('链表为空')
  if self.length() == 1:
    self.head = None
    self.tail = None
  else:
    pre = self.head
    cur = pre.next
    
    while  cur.next is not None:
      pre = cur
      cur = cur.next
    cur = None
    pre.next = None
    self.tail = pre

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
10. 查找节点

在单链表中查找值为 key 的节点，从表头开始顺序查找，若存在节点的值等于key，则查找成功，否则查找失败，代码实现如下：

def find(self, key):
  '''
  :param key: 关键字
  :return  查找成功返回True，失败返回False
  '''
  cur = self.head
  while cur != None:
    if key == cur.val:
      return True
    cur = cur.next
  return False  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
单链表域顺序表的比较

  1. 空间上

    • 顺序表：在初始化时需要分配好存储空间，即顺序表存储空间的大小是固定的。当线性表长度变化较大时，即不知道需要存储多少元素时，就难以确定存储空间的大小，存储空间分小了，不能够存储足够的元素，容易溢出；存储空间分大了，又会造成空间浪费。
    • 单链表：可按需分配，不用考虑表的存储空间多大比较合适。

  2. 时间上

    • 顺序表：顺序表查找元素操作时间复杂度为 O ( 1 ) O(1) O(1), 因为顺序表示用一组连续的存储单元来存储数据元素的，所以插入和删除元素的时候需要向后或者向前移动元素，时间复杂度为 O ( n ) O(n) O(n)
    • 单链表：单链表是用一组任意的存储单元来存储数据元素的，所以在查找元素时操作的时间复杂度为 O ( n ) O(n) O(n), 插入和删除元素操作不需要移动表中的元素，改变指针即可，因此时间复杂度为 O ( 1 ) O(1) O(1)

4 双链表

​ **单链表的不足：**在单链表中，当前节点只能指向它的后继节点，如果要访问当前节点的前一个节点，就需要从头开始遍历。为了更方便的访问当前节点的前一个节点，引入了双链表。

​ **定义：**双链表是在单链表的基础上增加一个指针指向前驱节点，其存储结构如图所示。

​ 代码实现：

class Node(object):
  def __init__(self, val):
    # 存放节点中的数据域
    self.val = val
    # 后继指针
    self.next = None
    # 前驱指针
    self.prev = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

​ 双链表初始化

class DoubleLinkedList(object):
  def __init__(self):
    '''
    双链表初始化:要将链表的头指针和尾指针指向空
    '''
    # 声明头指针，将头指针指向空
    self.head = None
    # 声明尾指针，将尾指针指向空
    self.tail = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
基本操作
1. 判断双链表是否为空
def empty(self):
  '''
  判断双链表是否为空
  :return : 如果头指针指向空，则双链表为空，返回True，否则不为空，返回FALSE
  '''
  return self.head is None  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
2. 获取双链表长度

​ 遍历双链表，每经过一个节点，链表长度加一，代码实现如下：

def length(self):
  '''
  获取链表长度
  :return: 返回链表长度
  '''
  # 用来记录链表长度
  size = 0
  # cur 指针用来遍历链表
  cur = self.head
  # cur 指针不指向空，表示尚未遍历到表尾节点
  while cur != None:
    # 链表长度加1
    size += 1
    # 将cur指针指向当前节点的直接后继节点
    cur = cur.next
  return size

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
3. 头插法

​ 头插法就是将新节点插入到表头。

  • 如果双链表为空，则将透支着指向新节点，新节点成为表头节点
  • 如果双链表不为空，则将新节点的指针指向表头节点，将表头节点的前驱指针指向新节点，使新节点成为表头节点。

如图所示：

代码实现如下：

def prepend(self, var):
  '''
  头插法
  :param
  		val: 待插入的关键字
  '''
  # 新节点
  newNode = Node(val)
  # 链表为空
  if self.empty():
    # 将表头指针、表尾指针指向新节点
    self.head = newNode
    self.tail = newNode
  # 链表不为空
  else:
    # 将头结点的前驱指针指向新节点
    self.head.prev = newNode
    # 将新节点的后继指针指向头结点
    newNode.next = self.head
    # 将表头指针指向新节点
    self.head = newNode  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
4. 在链表任意位置插入新节点

​ 将新节点插入到链表中的第i个位置时，首先要遍历链表到链表的第 i − 1 i-1 i−1个位置的几点，再进行两个操作：

  • 将新节点的后继指针指向第i个位置的节点，第i个位置节点的直接前驱指针指向新节点
  • 将第 i − 1 i-1 i−1 个位置节点的后继指针指向新节点，新节点的前驱指针指向第 i − 1 i-1 i−1 个位置的节点

代码实现如下：

def insert(self, index, val):
  '''
  :Desc
  			在链表任意位置添加节点，若该任意位置为index，则在第index个节点后插入元素
  :param
  			index: 位置下标
  			val: 关键字
  '''
  # 声明pre指针
  pre = self.head 
  newNode = Node(val)
  # 将pre指针遍历到双链表中的第index个节点
  for i in range(index - 1):
    pre  = pre.next
  # 第index个节点的后继节点
  next = pre.next
  # 将新节点的额后继指针指向链表的第index+1 个节点
  newNode.next = next
  # 链表中第index + 1 个节点的寝取指针指向新节点
  next。prev = newNode
  # 第index个节点的后继指针指向新节点
  pre.next = newNode
  # 新节点的前驱指针指向链表的第index个节点
  newNode.prev = pre  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
5. 尾插法

​ 尾插发就是将新节点插入到表尾。

  • 如果双链表为空，则将表尾指针、表头指针指向新节点，新节点成为表尾节点（表头节点）
  • 如果双链表不为空，则将表尾节点的直接后继指向新节点，新节点的前驱指针指向表尾节点，新节点成为表尾节点

如图所示：

代码如下：

def append(self, val):
  '''
  尾插发
  :param 
  		val: 待插入的关键字
  '''
  # 新节点
  newNode = Node(val)
  # 如果双链表为空
  if self.empty():
    # 将表头指针、表尾指针指向新节点
    self.head = newNode
    self.tail = newNode
  # 如果双链表不为空
  else:
    # 将尾节点的后继指针指向新节点
    self.tail.next = newNode
    # 将新节点的前驱指针指向尾节点
    newNode.prev = self.tail
    # 尾指针指向新节点，即新节点变为链表新的尾节点
    self.tail = newNode

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
6. 删除头结点

​ 将头结点的后继指针指向空，将头结点的下一个节点的前驱指针也指向空，此时表头节点和链表分离，删除头结点操作成功。如图所示。

代码实现如下：

def del_first(self):
  '''
  删除头结点
  '''
  # 双链表为空，抛出异常
  if self.empty():
    raise IndexError('Index 非法')
  # 双链表不为空
  # 将表头指针指向头结点的后继节点，即双链表原来的第二个节点成为新节点
  self.head = self.head.next
  # 将新的头结点的前驱指针指向空
  self.head.prev = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
7. 在双链表中间任意位置删除节点

​ 在链表中遍历到第 i − 1 i-1 i−1 个节点，将第 i − 1 i-1 i−1 个节点的后继指针指向第 i + 1 i+1 i+1 个节点，将第 i i i 个节点的前驱指针指向空；将第 i i i 个节点的后继指针指向空，将第 i + 1 i+1 i+1 个节点的前驱指针指向第 i − 1 i-1 i−1 个节点，即可删除链表的第 i i i 个节点。如图所示：

代码如下：

def delet(self, index):
  '''
  在双链表中间任意位置删除节点
  :param
     index: 删除下标为index的节点，头节点下标为0
  '''
  pre = self.head
  for i in range(index - 1):
    pre = pre.next
  pre.next  = pre.next.next

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
8. 删除尾节点
  • 双链表为空，抛出异常
  • 双链表不为空，但只有一个节点元素，直接将表头指针、表尾指针指向空即可
  • 双链表不为空且有多个节点，将为节点的前驱指针指向空，将表尾导数第二个节点的后继指针指向空即可

如图所示：

代码如下：

def del_last(self):
  '''
  删除表尾节点
  '''
  if self.empty():
    raise IndexError('index 非法')
  # 双链表不为空
  # 将表尾指针指向尾节点的前驱节点
  self.tail = self.tail.prev
  #将导数第二个节点的后继指针指向空，使其成为新的尾节点
  self.tail.next = None

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
9. 查找节点

​ 查找一个值为 k e y key key 的节点，从表头开始进行顺序查找，若节点的值等于 k e y key key , 则朝招成功；若双链表中不存在值等于 k e y key key 的节点，则朝招失败。代码实现如下：

def find(self, key):
  '''
  在双链表中查找关键字key
  :param key: 关键字
  :return : 查找成功返回True，查找失败返回False
  '''
  # 声明cur指针，指向头结点
  cur = self.head
  # 利用cur指针来遍历双链表
  while cur is not None:
    if key == cur.val:
      return True
    cur = cur.next
	return False

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

5 循环链表

**分类：**循环单链表、循环双链表。此处介绍循环单链表

**循环单链表的特点：**循环单链表域单链表的区别是尾节点的后继指针不是指向空，而是指向头结点，由此形成了一个环，因此，从单链表中的任何一个节点除法都能找到其他节点，这是单链表所不能实现的。

存储结构：

  • 定义：循环单链表中的几点的存储结构域单链表节点的存储结构相同，有一个值域和指针域，存储结构如图所示：

  • 代码实现：

    • 循环单链表节点的定义：
    class Nde(object):
  def __init__(self, val):
    self.val = val
    self.next = None

    • 1
    • 2
    • 3
    • 4
    • 循环单链表的初始化
    class CircleLinkedList(object):
  def __init__(self):
    '''
    初始化、声明头指针、尾指针，并将它们指向空    
    '''
    self.head = None
    self.tail = None

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
基本操作
1. 判断是否为空

​ 若循环单链表的表头、表尾指针指向空，则链表为空，否则链表不为空。代码实现如下：

def empty(self):
  return self.head is None

  • 1
  • 2
2. 获取循环单链表的长度

​ 获取循环单链表，每经过一个节点，链表长度加一，获取链表长度，代码实现如下：

def length(self):
  size = 0
  if self.empty():
    return size
  cur = self.head
  # cur 指向当前链表的第一个元素，即当前链表的长度从第一个元素开始计算，长度 +1
  size += 1
  # cur的后继节点不是头结点，即cur不指向尾节点
  while cur.next is not self.head:
    size += 1
    cur = cur.next
  return size

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
3. 尾插入法
  • 链表为空，将表头、表尾指针指向新节点
  • 链表不为空，将尾节点的直接后继指针指向新节点，新节点的后继指针指向头节点，如图所示：

代码实现如下：

def append(self, val):
  '''
  尾插法
  :param val:待插入的关键字
  '''
  newNode = Node(val)
  if self.empty():
    self.head = newNode
    self.tail = newNode
  else:
    self.tail.next = newNode
    self.tal = newNode
    self.tail.next = self.head    

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
4. 删除节点
  • 链表为空，无法删除，抛出异常
  • 链表不空且只有一个节点，将头尾指针指向空
  • 链表不空且有多个节点，将链表中的导数第二个节点的直接后继指向头结点，将尾节点的直接后继指向空

如图所示：

代码如下：

def delete(self):
  '''
  删除节点
  '''
  if self.empty():
    raise IndexError('链表为空')
  if self.length() == 1:
    self.head == None
    self.tail = None
  else:
    cur = self.head
    temp = cur.next
    # 遍历链表，找到导数第二个节点
    while temp.next is not self.head:
      cur = cur.next
      temp = cur.next
    # 将尾指针指向导数第二个节点，使之成为新的尾节点
    self.tail = cur
    # 新的尾节点直接后继指向表头节点
    self.tail.next = self.head  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
5. 查找节点

在链表中查找数值为key的节点，从头节点向后遍历，判断是否有节点的值等于key，若有，则查找成功，否则查找失败，代码实现如下：

def find(self, key):
  '''
  查找某个关键字
  :param  key: 关键字
  :return : 存在则返回True，否则返回False
  '''
  cur = self.head
  while cur.next != self.head:
    if key == cur.var:
      return True
    cur = cur.next
  return False

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
6. 遍历循环链表

若链表为空，则无法遍历链表，退出程序；若链表不为空，则从表头开始向后遍历，并且打印节点的数据域，代码实现如下。

def travesal(self):
  '''
  遍历循环链表
  '''
  if self.empty():
    raise IndexError('链表为空')
  cur = self.head
  # 当cur的直接后继指针不是指向头结点是时，即cur尚未指向尾节点时
  while cur.next is not self.head:
    print(cur.val, end = ' ')
    cur = cur.next
  # 打印尾节点
  print(cur.val)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/549703
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号