一、线性表的基本概念
数据元素：线性表中的基本单位，每个元素都是线性表的一部分。
数据项：数据元素的具体值。
存储位置：线性表中的元素在内存中的具体存储位置。
线性表按存储结构可以分为顺序表和链表两大类：
1.1顺序表：
顺序表是用一段连续的存储单元依次存储线性表中的元素。
**优点：**可以快速访问任意位置的元素（时间复杂度为 O(1)）。
**缺点：**插入和删除操作效率较低（时间复杂度为 O(n)），需要移动大量元素；在存储空间不足或溢出时需要进行空间扩展或缩减。
1.2链表：
链表是由一系列结点组成的，每个结点包含数据元素和指向下一个结点的指针。### 链表分类
可以分为单链表、双向链表和循环链表等
单链表：每个结点只包含一个指向后继结点的指针。
双向链表：每个结点包含两个指针，分别指向前驱结点和后继结点。
循环链表：尾结点的指针指向头结点，形成一个环。
优点：插入和删除操作效率较高（时间复杂度为 O(1)），不需要移动大量元素。
缺点：无法快速访问任意位置的元素（时间复杂度为 O(n)），需要遍历链表。
1.3线性表的基本操作
初始化：创建一个空的线性表。
销毁：销毁线性表，释放存储空间。
插入：在指定位置插入一个新元素。
删除：删除指定位置的元素。
查找：查找指定值的元素，返回其位置。
更新：更新指定位置的元素值。
遍历：依次访问线性表中的每个元素。
1.4线性表的应用
线性表广泛应用于各种场景，例如：
1.5数据的存储和管理。
实现其他数据结构和算法，如栈、队列、哈希表等。
操作系统中的进程调度、内存管理等。
数据库系统中的表操作。
二、线性表的基本操作
2.1 初始化
初始化是创建一个空的线性表。根据存储方式的不同，初始化的方式也不同。
顺序表的初始化
顺序表用数组来表示，因此初始化时需要分配一段连续的存储空间。
# 顺序表的初始化
def init_sequence_list():
sequence_list = [] # 创建一个空列表
return sequence_list
# 使用示例
sequence_list = init_sequence_list()
print(sequence_list) # 输出: []
链表的初始化
链表用结点来表示，因此初始化时需要创建一个头结点。
# 定义链表的结点
class Node:
def __init__(self, data=None):
self.data = data # 结点的数据
self.next = None # 指向下一个结点的指针
# 链表的初始化
def init_linked_list():
head = Node() # 创建一个空的头结点
return head
# 使用示例
linked_list = init_linked_list()
print(linked_list.data) # 输出: None
print(linked_list.next) # 输出: None
2.2 插入操作
插入操作是在线性表的指定位置插入一个新元素。
顺序表的插入
在顺序表中插入元素时，需要将插入位置后的所有元素向后移动一位，以腾出插入位置。
# 顺序表的插入操作
def insert_sequence_list(sequence_list, index, element):
if index < 0 or index > len(sequence_list):
print("插入位置不合法")
return False
sequence_list.insert(index, element)
return True
# 使用示例
sequence_list = [1, 2, 3, 4]
insert_sequence_list(sequence_list, 2, 99)
print(sequence_list) # 输出: [1, 2, 99, 3, 4]
链表的插入
在链表中插入元素时，需要找到插入位置的前一个结点，然后修改指针。
# 链表的插入操作
def insert_linked_list(head, index, element):
if index < 0:
print("插入位置不合法")
return False
new_node = Node(element) # 创建新结点
current = head
for _ in range(index):
if current.next is None:
print("插入位置不合法")
return False
current = current.next
new_node.next = current.next
current.next = new_node
return True
# 使用示例
linked_list = init_linked_list()
insert_linked_list(linked_list, 0, 1)
insert_linked_list(linked_list, 1, 2)
insert_linked_list(linked_list, 1, 99)
current = linked_list.next
while current:
print(current.data, end=" ") # 输出: 1 99 2
current = current.next
2.3 删除操作
删除操作是删除线性表的指定位置的元素。
顺序表的删除
在顺序表中删除元素时，需要将删除位置后的所有元素向前移动一位。
# 顺序表的删除操作
def delete_sequence_list(sequence_list, index):
if index < 0 or index >= len(sequence_list):
print("删除位置不合法")
return False
del sequence_list[index]
return True
# 使用示例
sequence_list = [1, 2, 99, 3, 4]
delete_sequence_list(sequence_list, 2)
print(sequence_list) # 输出: [1, 2, 3, 4]
链表的删除
在链表中删除元素时，需要找到删除位置的前一个结点，然后修改指针。
# 链表的删除操作
def delete_linked_list(head, index):
if index < 0:
print("删除位置不合法")
return False
current = head
for _ in range(index):
if current.next is None:
print("删除位置不合法")
return False
current = current.next
if current.next is None:
print("删除位置不合法")
return False
current.next = current.next.next
return True
# 使用示例
linked_list = init_linked_list()
insert_linked_list(linked_list, 0, 1)
insert_linked_list(linked_list, 1, 99)
insert_linked_list(linked_list, 2, 2)
delete_linked_list(linked_list, 1)
current = linked_list.next
while current:
print(current.data, end=" ") # 输出: 1 2
current = current.next
2.4 查找操作
查找操作是查找线性表中指定值的元素，返回其位置。
顺序表的查找
# 顺序表的查找操作
def find_sequence_list(sequence_list, element):
try:
index = sequence_list.index(element)
return index
except ValueError:
return -1
# 使用示例
sequence_list = [1, 2, 3, 4]
index = find_sequence_list(sequence_list, 3)
print(index) # 输出: 2
链表的查找
# 链表的查找操作
def find_linked_list(head, element):
current = head.next # 跳过头结点
index = 0
while current:
if current.data == element:
return index
current = current.next
index += 1
return -1
# 使用示例
linked_list = init_linked_list()
insert_linked_list(linked_list, 0, 1)
insert_linked_list(linked_list, 1, 2)
insert_linked_list(linked_list, 2, 3)
index = find_linked_list(linked_list, 3)
print(index) # 输出: 2