数据结构之线性表（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 randomclass 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 Falsereturn self.sqlist[i - 1]# 查找def FindElement(self, e):for i in range(self.length):if e == self.sqlist[i]:print(f"查找的元素在第{i+1}个位置")breakelse:print("无查找元素")# 插入def InsertList(self, i, e):if i < 1 or i > self.length+1:return Falseself.sqlist.insert(i - 1, e)self.length += 1return True# 删除（按位删除）def DeleteList_space(self, i):if i < 1 or i > self.length:return Falseself.sqlist.pop(i - 1)self.length -= 1return True# 删除（按值删除）def DeleteList_value(self, e):for i in range(self.length):if e == self.sqlist[i]:self.sqlist.pop(i)self.length -= 1return Truereturn False# 修改（按值修改）def SetElement(self, eold, enew):for i in range(self.length):if eold == self.sqlist[i]:self.sqlist[i] = enewreturn Truereturn False# 修改（按位修改）def SetElement_space(self, i, enew):if i < 1 or i > self.length:return Falseself.sqlist[i-1] = enewreturn Truel = 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.单链表

• 为了表示每个数据元素 a_i 与其直接后继数据元素 a_i+1 之间的逻辑关系，对数据元素 a_i 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针。这两部分信息组成数据元素 a_i 的存储映像，称为结点(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 Noneelse:curlist = []cur = self.headwhile cur != None:curlist.append(cur.item)cur = cur.nextreturn curlist# 头插法创建单链表def add(self,newItem):node = SingleNode(newItem)node.next = self.headself.head = node# 尾插法def append(self,newItem):node = SingleNode(newItem)if self.is_empty():return self.add(newItem)# 从头节点开始遍历nod = self.headwhile nod.next != None:nod = nod.nextnod.next = node# 指定位置添加元素def insert(self, pos, newItem): # 在指定pos位置上添加newItem元素# 链表的插入需要分几种情况# 第一步：判断pos是否在合理范围内，如果不在，则直接终止# 第二步：判断pos是否在第一个，如果是则采用头插法# 第三步：如果pos在最后一个，则采用尾插法# 第四步：如果即不在头，也不在尾，则通过循环遍历到pos位置，再用insert插入node = SingleNode(newItem)cur = self.headcount = 0if pos == 0:return self.add(newItem)elif pos < (self.get_length()):while count < pos - 1:    #找到指定位置的前一个节点cur = cur.nextcount += 1node.next = cur.nextcur.next = nodeelif pos == (self.get_length()):return self.append(newItem)else:return '输入的位置有误，请确认'# 删除指定位置上的节点def remove(self, pos):# 第一步：判断给定的pos是否在合理范围内# 第二步：通过循环，遍历到pos位置，遍历期间通过next指针依次指向下一个节点# 第三步：找到指定位置的节点后，通过nod.next = nod.next.next删除cur = self.headcount = 0if 1 <= pos < (self.get_length()):while count < pos - 1:  #找到指定位置的前一个节点cur = cur.nextcount += 1cur.next = cur.next.nextelif pos == 0:self.head = cur.nextelse:return '输入的位置有误，请确认'# 查找指定位置的节点值def find(self, pos):cur = self.headcount = 0if 0 <= pos < (self.get_length()):while count < pos:     #找到指定位置的节点cur = cur.nextcount += 1return cur.itemelse:return '输入的位置有误，请确认'# 更新链表中某个位置的值def update(self, pos, newItem):cur = self.headcount = 0if 0 <= pos < (self.get_length()):while count < pos:    #找到指定位置的节点cur = cur.nextcount += 1cur.item = newItemelse:return '输入的位置有误，请确认'# 清空链表def clear(self):self.head = Nonesinglelinklist = 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