数据机构记录顺序表-笔记1

一、线性表的基本概念

数据元素：线性表中的基本单位，每个元素都是线性表的一部分。
数据项：数据元素的具体值。
存储位置：线性表中的元素在内存中的具体存储位置。
线性表按存储结构可以分为顺序表和链表两大类：

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 Falsesequence_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 Falsenew_node = Node(element)  # 创建新结点current = headfor _ in range(index):if current.next is None:print("插入位置不合法")return Falsecurrent = current.nextnew_node.next = current.nextcurrent.next = new_nodereturn 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 2current = current.next

2.3 删除操作

删除操作是删除线性表的指定位置的元素。

顺序表的删除

在顺序表中删除元素时，需要将删除位置后的所有元素向前移动一位。

# 顺序表的删除操作
def delete_sequence_list(sequence_list, index):if index < 0 or index >= len(sequence_list):print("删除位置不合法")return Falsedel 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 Falsecurrent = headfor _ in range(index):if current.next is None:print("删除位置不合法")return Falsecurrent = current.nextif current.next is None:print("删除位置不合法")return Falsecurrent.next = current.next.nextreturn 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 2current = current.next

2.4 查找操作

查找操作是查找线性表中指定值的元素，返回其位置。

顺序表的查找

# 顺序表的查找操作
def find_sequence_list(sequence_list, element):try:index = sequence_list.index(element)return indexexcept 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 = 0while current:if current.data == element:return indexcurrent = current.nextindex += 1return -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