代码收藏家 数据结构之线性表（python）
华子目录
线性表的定义
线性表：零个或多个数据元素的有限序列线性关系。将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。复杂的线性表中，一个数据元素可以有若干个数据项组成。线性表又可以分为顺序表（顺序存储结构）和链表（链式存储结构）前驱与后继
左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”
1.顺序表（顺序存储结构）
地址连续的存储单元依次存储线性表的数据元素。
python列表与数组的区别
列表
列表是顺序表，不是链式表列表（其他语言称为数组）是一种基本数据类型列表取值a[2]时，列表中的每一个格子存的是值的地址。当进行a[2]时，它取得是a[2]的地址。通过地址指向来取值。python不需要提前申请列表长度，因为python内部会自动申请内存。python列表插入和删除的时间复杂度都是O(n)数组
数组取值时a[2]，假如说电脑是32位，a开头编号是100，内存内部会执行100+2*4=108，取到a[2]对应的值。数组元素类型要相同数组长度固定1.1插入数据
向已有顺序表中插入数据元素，根据插入位置的不同，可分为以下3种情况：
在表头插入元素在表的中间位置插入元素在表尾插入元素虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：
插入位置元素以及后续的元素整体向后移动一个位置插入的元素放到腾出来的位置上实例
在 {1,2,3,4,5} 的第 3 个位置上插入元素 6，实现过程如下：
顺序表存储第 3 个数据元素的位置
3 以及后续元素 4 和 5 整体向后移动一个位置
新元素 6 放入腾出的位置
1.2删除元素
从顺序表中删除指定元素，实现起来非常简单，只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。
后续元素整体前移一个位置，会直接将目标元素删除，可间接实现删除元素的目的实例
从 {1,2,3,4,5} 中删除元素 3 的过程如图所示：
1.3查找元素
顺序表中查找目标元素，可以使用多种查找算法实现，比如说二分查找算法、插值查找算法等。
1.4修改元素
顺序表修改元素的实现过程是：
找到目标元素直接修改该元素的值1.5综合示例
import random
class SqList:
# 初始化顺序表
def __init__(self, length):
self.length = length #表示顺序表的长度（元素个数）
self.sqlist = [random.randint(1, 100) for i in range(length)] #顺序表内容
# 返回所有元素
def ShowList(self):
return self.sqlist
# 遍历所有元素
def ErgodList(self):
for i in range(self.length):
print(f"第{i+1}个元素值为{self.sqlist[i]}")
# 取值（按位取值）
def GetElement(self, i):
# 首先判断插入的位置是否在合法范围内[0,length-1]
if i < 1 or i > self.length:
return False
return self.sqlist[i - 1]
# 查找
def FindElement(self, e):
for i in range(self.length):
if e == self.sqlist[i]:
print(f"查找的元素在第{i+1}个位置")
break
else:
print("无查找元素")
# 插入
def InsertList(self, i, e):
if i < 1 or i > self.length+1:
return False
self.sqlist.insert(i - 1, e)
self.length += 1
return True
# 删除（按位删除）
def DeleteList_space(self, i):
if i < 1 or i > self.length:
return False
self.sqlist.pop(i - 1)
self.length -= 1
return True
# 删除（按值删除）
def DeleteList_value(self, e):
for i in range(self.length):
if e == self.sqlist[i]:
self.sqlist.pop(i)
self.length -= 1
return True
return False
# 修改（按值修改）
def SetElement(self, eold, enew):
for i in range(self.length):
if eold == self.sqlist[i]:
self.sqlist[i] = enew
return True
return False
# 修改（按位修改）
def SetElement_space(self, i, enew):
if i < 1 or i > self.length:
return False
self.sqlist[i-1] = enew
return True
l = eval(input("请输入初始化长度："))
my_sqlist = SqList(l) #初始化对象
# 输出所有值
mylist = my_sqlist.ShowList()
print(mylist)
print("------------------------------------------------")
# 遍历元素
my_sqlist.ErgodList()
print("------------------------------------------------")
# 插入元素
i, e = map(int, input("请输入插入元素的位置和值(空格分割)：").split())
my_sqlist.InsertList(i, e)
print(f"插入后列表：{my_sqlist.sqlist}")
print("------------------------------------------------")
# 删除（按值删除）
e = eval(input("请输入要删除的值："))
my_sqlist.DeleteList_value(e)
print(f"删除之后的列表{my_sqlist.sqlist}")
print("------------------------------------------------")
# 删除（按位删除）
i = eval(input("请输入删除元素的位置："))
my_sqlist.DeleteList_space(i)
print(f"删除之后的列表{my_sqlist.sqlist}")
print("------------------------------------------------")
# 修改 （按值修改）
old, new = map(int, input("请输入需要修改的值和新值：").split())
my_sqlist.SetElement(old, new)
print(f"修改之后的列表{my_sqlist.sqlist}")
print("------------------------------------------------")
# 修改（按位修改）
i, new = map(int, input("请输入需要修改的位置和新值：").split())
my_sqlist.SetElement_space(i, new)
print(f"修改之后的列表{my_sqlist.sqlist}")
print("------------------------------------------------")
# 查找
e = eval(input("请输入要查找的值："))
my_sqlist.FindElement(e)
请输入初始化长度：5
[98, 27, 99, 63, 54]
------------------------------------------------
第1个元素值为98
第2个元素值为27
第3个元素值为99
第4个元素值为63
第5个元素值为54
------------------------------------------------
请输入插入元素的位置和值(空格分割)：6 99
插入后列表：[98, 27, 99, 63, 54, 99]
------------------------------------------------
请输入要删除的值：99
删除之后的列表[98, 27, 63, 54, 99]
------------------------------------------------
请输入删除元素的位置：2
删除之后的列表[98, 63, 54, 99]
------------------------------------------------
请输入需要修改的值和新值：98 0
修改之后的列表[0, 63, 54, 99]
------------------------------------------------
请输入需要修改的位置和新值：2 66
修改之后的列表[0, 66, 54, 99]
------------------------------------------------
请输入要查找的值：0
查找的元素在第1个位置
进程已结束,退出代码0
2.单链表
直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针。这两部分信息组成数据元素 ai 的存储映像，称为结点(Node)。n个结点链结成一个链表，即为线性表(a1，a2，…，an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点其他节点：链表中其他的节点
链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。2.1单链表的初始化
头指针（如果有必要，可以声明一个头节点）存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系2.2插入元素
同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
头插法：插入到链表的头部（头节点之后），作为首元节点中插法：插入到链表中间的某个位置尾插法：插入到链表的最末端，作为链表中最后一个数据元素虽然新元素的插入位置不固定，但是链表插入元素的思想是固定的，只需做以下3步操作，即可将新元素插入到指定的位置：
插入位置的前一个结点新结点的 next指针 指向插入位置后的结点插入位置前结点的 next指针 指向插入结点示例
例如，我们在链表 {1,2,3,4} 的基础上分别实现在头部、中间部位、尾部插入新元素 5，其实现过程如图1 所示：
新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤 1 ，再执行步骤 2注意
链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行骤步 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤1
2.3删除元素
从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除，但作为一名合格的程序员，要对存储空间负责，对不再利用的存储空间要及时释放。因此，从链表中删除数据元素需要进行以下 2 步操作：
结点从链表中摘下来手动释放掉结点，回收被结点占用的存储空间其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点temp
temp.next = temp.next.next示例
例如，从存有 {1,2,3,4} 的链表中删除元素3，则此代码的执行效果如图 2 所示：
2.4修改元素
修改链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可2.5查找元素
链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的NULL（比对失败的标志）注意，遍历有头节点的链表时，需避免头节点对测试数据的影响2.6综合示例
# 定义节点类，包含两个成员：节点数据域和指向下一个节点的指针域（带有头节点的单链表）
class SingleNode:
def __init__(self, item):
self.item = item #数据域
self.next = None #指针域
class SingleLinkList:
def __init__(self):
self.head = None
# 判断链表是否为空
def is_empty(self):
return self.head == None
# 输出链表长度
def get_length(self):
return len(self.travel())
# 遍历整个链表
def travel(self):
# 思路就是先判断链表是否为空
# 为空直接返回None
# 不为空的话，就先定义一个列表，然后通过next指针从头指针开始遍历，依次将节点存储的值加入列表中，直到下一个指针指向为空，则停止遍历
if self.is_empty():
return None
else:
curlist = []
cur = self.head
while cur != None:
curlist.append(cur.item)
cur = cur.next
return curlist
# 头插法创建单链表
def add(self,newItem):
node = SingleNode(newItem)
node.next = self.head
self.head = node
# 尾插法
def append(self,newItem):
node = SingleNode(newItem)
if self.is_empty():
return self.add(newItem)
# 从头节点开始遍历
nod = self.head
while nod.next != None:
nod = nod.next
nod.next = node
# 指定位置添加元素
def insert(self, pos, newItem): # 在指定pos位置上添加newItem元素
# 链表的插入需要分几种情况
# 第一步：判断pos是否在合理范围内，如果不在，则直接终止
# 第二步：判断pos是否在第一个，如果是则采用头插法
# 第三步：如果pos在最后一个，则采用尾插法
# 第四步：如果即不在头，也不在尾，则通过循环遍历到pos位置，再用insert插入
node = SingleNode(newItem)
cur = self.head
count = 0
if pos == 0:
return self.add(newItem)
elif pos < (self.get_length()):
while count < pos - 1: #找到指定位置的前一个节点
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
elif pos == (self.get_length()):
return self.append(newItem)
else:
return '输入的位置有误，请确认'
# 删除指定位置上的节点
def remove(self, pos):
# 第一步：判断给定的pos是否在合理范围内
# 第二步：通过循环，遍历到pos位置，遍历期间通过next指针依次指向下一个节点
# 第三步：找到指定位置的节点后，通过nod.next = nod.next.next删除
cur = self.head
count = 0
if 1 <= pos < (self.get_length()):
while count < pos - 1: #找到指定位置的前一个节点
cur = cur.next
count += 1
cur.next = cur.next.next
elif pos == 0:
self.head = cur.next
else:
return '输入的位置有误，请确认'
# 查找指定位置的节点值
def find(self, pos):
cur = self.head
count = 0
if 0 <= pos < (self.get_length()):
while count < pos: #找到指定位置的节点
cur = cur.next
count += 1
return cur.item
else:
return '输入的位置有误，请确认'
# 更新链表中某个位置的值
def update(self, pos, newItem):
cur = self.head
count = 0
if 0 <= pos < (self.get_length()):
while count < pos: #找到指定位置的节点
cur = cur.next
count += 1
cur.item = newItem
else:
return '输入的位置有误，请确认'
# 清空链表
def clear(self):
self.head = None
singlelinklist = SingleLinkList() #实例化对象
print("初始化单链表：",singlelinklist)
print("-----------------------------")
print("判断单链表是否为空：",singlelinklist.is_empty())
print("-----------------------------")
# 添加数据
import random
for i in range(10):
singlelinklist.add(random.randint(1,100))
# 遍历数据
print("遍历单链表：",singlelinklist.travel())
print("-----------------------------")
print("判断单链表是否为空：",singlelinklist.is_empty())
print("-----------------------------")
# 末尾添加数据
singlelinklist.append(10)
print("末尾添加元素后的单链表遍历结果：",singlelinklist.travel())
print("-----------------------------")
# 开头添加数据
singlelinklist.add(1)
print("开头添加元素后的单链表遍历结果：",singlelinklist.travel())
print("-----------------------------")
# 查看数据长度
print("单链表长度：",singlelinklist.get_length())
print("-----------------------------")
# 指定位置插入数据，位置从0开始
singlelinklist.insert(1, 13)
print("插入数据后的遍历单链表：",singlelinklist.travel())
print("-----------------------------")
# 删除指定位置数据
singlelinklist.remove(0)
print("删除数据后的遍历单链表：",singlelinklist.travel())
print("-----------------------------")
# 更新指定位置数据
singlelinklist.update(2, 2)
print("更新数据后的遍历单链表：",singlelinklist.travel())
print("-----------------------------")
# 清空所有数据
singlelinklist.clear()
print("清空数据后的遍历单链表：",singlelinklist.travel())
初始化单链表： <__main__.SingleLinkList object at 0x0000020DA4358460>
-----------------------------
判断单链表是否为空： True
-----------------------------
遍历单链表： [39, 42, 88, 51, 64, 60, 66, 29, 29, 35]
-----------------------------
判断单链表是否为空： False
-----------------------------
末尾添加元素后的单链表遍历结果： [39, 42, 88, 51, 64, 60, 66, 29, 29, 35, 10]
-----------------------------
开头添加元素后的单链表遍历结果： [1, 39, 42, 88, 51, 64, 60, 66, 29, 29, 35, 10]
-----------------------------
单链表长度： 12
-----------------------------
插入数据后的遍历单链表： [1, 13, 39, 42, 88, 51, 64, 60, 66, 29, 29, 35, 10]
-----------------------------
删除数据后的遍历单链表： [13, 39, 42, 88, 51, 64, 60, 66, 29, 29, 35, 10]
-----------------------------
更新数据后的遍历单链表： [13, 39, 2, 88, 51, 64, 60, 66, 29, 29, 35, 10]
-----------------------------
清空数据后的遍历单链表： None
作者：^～^前行者～～～
