devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

常见数据结构线性表（数组和链表）python实现_python线性表输出列表代码

作者：从前慢现在也慢 | 2024-05-07 14:37:35

赞

踩

python线性表输出列表代码

数组

数据在内存中顺序存储，可以通过下标索引。

特点：支持随机访问，索引元素效率高，插入元素和删除元素效率低。

数组存放空间连续，插入元素时需要将插入位置及后面的元素一次往后移动一位，然后将元素插入到空出的插入位置。

python中的list是一个动态数组，支持动态扩容（2^n），list中封装了数组常用的方法：

  1. >>> list = [3, 5, 7]
  2. >>> list.append(9) # 往数组尾部添加元素
  3. >>> list
  4. [3, 5, 7, 9]
  5. >>> list.insert(2,5) # 在指定位置插入元素
  6. >>> list
  7. [3, 5, 5, 7, 9]
  8. >>> list.pop() # 取数组最后一个元素，会从数组中删除该元素
  9. 9
  10. >>> list
  11. [3, 5, 5, 7]
  12. >>> list.remove(5) # 删除数组中的指定元素，有多个时只删除第一个
  13. >>> list
  14. [3, 5, 7]
  15. >>> list.index(5) # 查找元素在列表中的位置
  16. 1
  17. >>> list.reverse() # 列表反转
  18. >>> list
  19. [7, 5, 3]

在python中通过id()函数来输出列表元素的第地址时，可以看到id的值并不是连续的，这是为什么呢？

  1. >>> arr = ['a','b','c']
  2. >>> for char in arr:
  3.         print(id(char))
  4. 2204167613216
  5. 2204167611536
  6. 2204167474288

因为python的list存的是元素对象的引用而不是元素本身，从下面代码中可以看出来，所以输出的id值是元素对象的引用值，在底层的c语言中是使用数组来实现的。

  1. >>> a = 1
  2. >>> id(a)
  3. 1598830848
  4. >>> b = [a]
  5. >>> id(b)
  6. 9390640
  7. >>> id(b[0])
  8. 1598830848

链表

链表数据在内存中的存储不连续，链表有一系列的节点通过指针依次连接起来，每个节点包含数据域和指针域，数据域存储数据，指针域存储下一个节点的指针。

单向链表

单向链表也叫单链表，是链表中最简单的形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

image.png

因为链表中的数据不是顺序存储的，不能随机访问，因此链表的查询效率低，但是链表在任意位置插入和删除节点时不用移动节点位置，因此插入和删除效率高。

链表实现

通常有以下步骤：

  1. 定义节点
  2. 定义链表
  3. 使用链表 
    1. class Node(object):
    2.     '''1.节点定义'''
    3.  
    4.     def __init__(self,data):
    5.         # 数据域
    6.         self.data = data
    7.         # 指针域，创建时为None
    8.         self.next = None
    9.  
    10. class SingleList(object):
    11.     '''2.链表定义'''
    12.  
    13.     def __init__(self):
    14.         # 链表头
    15.         self.head = None
    16.      
    17. if __name__ == '__main__':
    18.     #3.链表使用
    19.     # 创建链表
    20.     singlelist = SingleList()
    21.     # 创建节点
    22.     node1 = Node(3)
    23.     # 将链表头指向节点
    24.     singlelist.head = node1
    25.     # 创建节点往链表上添加
    26.     node2 = Node(5)
    27.     node1.next = node2
    28.     node3 = Node(7)
    29.     node2.next = node3
    30.  
    31.     # 创建临时变量指向头节点
    32.     temp = singlelist.head
    33.     # 取头节点的数据
    34.     print(temp.data)
    35.     # 取下一个节点的数据
    36.     temp = temp.next
    37.     print(temp.data)

    输出结果：

3

5

上面定义并使用了一个单项链表，但是链表的使用很不方便，获取元素添加和获取需要定位到节点，长度也没法知道，所以需要定义一些常用的方法，方便链表的使用。

链表中的常用方法：

  • is_empty() 链表是否为空
  • length() 链表长度
  • items() 获取链表数据迭代器
  • add(item) 链表头部添加元素
  • append(item) 链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点
  • find(item) 查找节点是否存在
  1. class Node(object):
  2.     '''节点定义'''
  3.  
  4.     def __init__(self,data):
  5.         # 数据域
  6.         self.data = data
  7.         # 指针域，创建时为None
  8.         self.next = None
  9.  
  10. class SingleList(object):
  11.     '''链表定义'''
  12.  
  13.     def __init__(self):
  14.         # 链表头
  15.         self.head = None
  16.  
  17.     def is_empty(self):
  18.         '''链表判空'''
  19.         return self.head is None
  20.  
  21.     def length(self):
  22.         '''链表长度'''
  23.         # 获取初始的头指针
  24.         cur = self.head
  25.         count = 0
  26.         while cur is not None:
  27.             count += 1
  28.             # 指针后移1位
  29.             cur = cur.next
  30.         return count
  31.  
  32.     def datas(self):
  33.         '''链表遍历'''
  34.         cur = self.head
  35.         while cur is not None:
  36.             # 返回生成器
  37.             yield cur.data
  38.             # 指针后移1位
  39.             cur = cur.next
  40.  
  41.     def add(self,data):
  42.         '''在头部插入节点'''
  43.         # 创建新节点
  44.         node = Node(data)
  45.         # 新节点指向原头节点
  46.         node.next = self.head
  47.         # 头节点指向新节点
  48.         self.head = node
  49.  
  50.     def append(self,data):
  51.         '''向尾部插入节点'''
  52.         node = Node(data)
  53.         if self.is_empty():
  54.             # 空链表则直接将head指向node
  55.             self.head = node
  56.         else:
  57.             cur = self.head
  58.             while cur.next is not None:
  59.                 # 将指针移到最后一个节点
  60.                 cur = cur.next
  61.             # 将最后一个节点的指针指向node
  62.             cur.next = node
  63.  
  64.     def insert(self,index,data):
  65.         '''任意位置插入节点'''
  66.         if index <= 0:
  67.             # 在头部插入
  68.             self.add(data)
  69.         elif index >= self.length():
  70.             # 在尾部插入
  71.             self.append(data)
  72.         else:
  73.             cur = self.head
  74.             for i in range(index - 1):
  75.                 cur = cur.next
  76.                 # 创建新节点
  77.             node = Node(data)
  78.             # 将新节点指向就节点
  79.             node.next = cur.next
  80.             # 将旧节点前一个节点指向新节点
  81.             cur.next = node
  82.  
  83.     def remove(self, item):
  84.         """ 删除一个结点 """
  85.         if self.is_empty():
  86.             return
  87.         cur = self.head
  88.         pre = None
  89.         # 第一个元素为需要删除的元素
  90.         if cur.data == item:
  91.             if cur.next != None:
  92.                 cur.next = self.head.next
  93.                 # 调整头部结点
  94.                 self.head = self.head.next
  95.             else:
  96.                 # 只有一个元素
  97.                 self.head = None
  98.         else:
  99.             # 不是第一个元素
  100.             pre = self.head
  101.             while cur.next != self.head:
  102.                 if cur.data == item:
  103.                     # 删除
  104.                     pre.next = cur.next
  105.                     return True
  106.                 else:
  107.                     pre = cur  # 记录前一个指针
  108.                     cur = cur.next  # 调整指针位置
  109.         # 当删除元素在末尾
  110.         if cur.data == item:
  111.             pre.next = self.head
  112.             return True
  113.  
  114.     def find(self, data):
  115.         """ 查找元素是否存在"""
  116.         return data in self.datas()
  117.  
  118.     def printlist(self):
  119.         '''打印链表元素'''
  120.         print('当前链表：')
  121.         for i in self.datas():
  122.             print(i)
  123.  
  124. if __name__ == '__main__':
  125.     # 创建链表
  126.     singlelist = SingleList()
  127.     
  128.     #添加节点
  129.     singlelist.add(3)
  130.     singlelist.append(5)
  131.     singlelist.append(7)
  132.     # 链表长度
  133.     length = singlelist.length()
  134.     print('链表长度:',length)
  135.  
  136.     singlelist.printlist()
  137.  
  138.     # 删除元素
  139.     singlelist.remove(5)
  140.     print('--删除元素--')
  141.     singlelist.printlist()
  142.  
  143.     # 任意位置插入元素
  144.     singlelist.insert(2,666)
  145.     print('--任意位置插入元素--')
  146.     singlelist.printlist()

双向链表

双向链表与与单向链表的区别在于，双向链表的节点包含了两个指针域，如下图，prev指针域指向前一个节点，next指向后一个节点，head指向头节点，第一个节点的prev指针为None，最后一个节点的next为空。

image.png为了方便操作双向链表，也会在链表中定义一些常用的方法。实例如下：

  1. class Node(object):
  2.     '''双链表的节点'''
  3.  
  4.     def __init__(self,data):
  5.         self.data = data
  6.         self.prev = None
  7.         self.next = None
  8.  
  9. class DoubleLinkedList(object):
  10.     '''双向链表'''
  11.  
  12.     def __init__(self):
  13.         self.head = None
  14.         self.tail = None
  15.  
  16.     def is_empty(self):
  17.         return self.head is None
  18.  
  19.     def length(self):
  20.         cur = self.head
  21.         count = 0
  22.         while cur is not None:
  23.             cur = cur.next
  24.             count += 1
  25.         return count
  26.  
  27.     def items(self):
  28.         '''顺序遍历'''
  29.         cur = self.head
  30.         while cur is not None:
  31.             yield cur.data
  32.             cur = cur.next
  33.  
  34.     def add(self,data):
  35.         '''向链表头部添加节点'''
  36.         node = Node(data)
  37.         if self.head is None:
  38.             self.head = node
  39.             self.tail = node
  40.         else:
  41.             node.next = self.head
  42.             self.head.prev = node
  43.             self.head = node
  44.  
  45.     def append(self,data):
  46.         '''向链表尾部添加节点'''
  47.         node = Node(data)
  48.         if self.tail is None:
  49.             self.head = node
  50.             self.tail = node
  51.         else:
  52.             node.prev = self.tail
  53.             self.tail.next = node
  54.             self.tail = node
  55.  
  56.     def insert(self,index,data):
  57.         '''向指定位置添加节点'''
  58.         if index <= 0:
  59.             self.add(data)
  60.         elif index >= self.length():
  61.             self.append(data)
  62.         else:
  63.             node = Node(data)
  64.             cur = self.head
  65.             for i in range(index):
  66.                 cur = cur.next
  67.             # 循环完后cur指向节点index了
  68.             node.next = cur
  69.             node.prev = cur.prev
  70.             cur.prev.next = node
  71.             cur.prev = node
  72.  
  73.     def remove(self, item):
  74.         """ 删除一个结点 """
  75.         if self.is_empty():
  76.             return
  77.         # 当删除的节点在尾部
  78.         if item == self.tail.data:
  79.             self.tail = self.tail.prev
  80.             self.tail.next = None
  81.             return True
  82.         cur = self.head
  83.         pre = None
  84.         # 第一个节点为需要删除的节点
  85.         if cur.data == item:
  86.             # 有多个节点
  87.             if cur.next != None:
  88.                 self.head = cur.next
  89.                 return True
  90.             # 只有一个节点
  91.             else:
  92.                 self.head = None
  93.                 return True
  94.         else:
  95.             # 首尾之外的任意节点
  96.             while cur.next != self.tail:
  97.                 if cur.data == item:
  98.                     pre.next = cur.next
  99.                     cur.next.prev = pre
  100.                     return True
  101.                 else:
  102.                     pre = cur
  103.                     cur = cur.next
  104.  
  105.     def find(self, data):
  106.         """ 查找节点是否存在"""
  107.         return data in self.items()
  108.  
  109.     def print_list(self):
  110.         '''打印链表数据'''
  111.         print('链表当前节点：')
  112.         for node in self.items():
  113.             print(node)
  114.  
  115. if __name__ == '__main__':
  116.     # 实例化双向链表
  117.     doublelist = DoubleLinkedList()
  118.     
  119.     # 向头部添加节点
  120.     doublelist.add(10)
  121.     doublelist.add(20)
  122.     doublelist.print_list()
  123.  
  124.     # 向尾部添加节点
  125.     doublelist.append(30)
  126.     doublelist.append(40)
  127.     doublelist.print_list()
  128.     
  129.     # 任意位置添加节点
  130.     doublelist.insert(2,666)
  131.     doublelist.print_list()
  132.     
  133.     # 删除首尾和任意节点
  134.     doublelist.remove(666)
  135.     doublelist.remove(20)
  136.     doublelist.remove(40)
  137.     doublelist.print_list()

输出结果：

链表当前节点：

20

10

链表当前节点：

20

10

30

40

链表当前节点：

20

10

666

30

40

链表当前节点：

10

30

其他数据结构：栈、队列、树等的实现可以看：python-data-structure

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/549720
推荐阅读
相关标签

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

  

闽ICP备14008679号