怎么做网站游戏,内蒙古建设工程造价信息网官网官方网页,wordpress降级,百度西安分公司地址一、线性表的基本概念
数据元素#xff1a;线性表中的基本单位#xff0c;每个元素都是线性表的一部分。 数据项#xff1a;数据元素的具体值。 存储位置#xff1a;线性表中的元素在内存中的具体存储位置。 线性表按存储结构可以分为顺序表和链表两大类#xff1a;
1.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, dataNone):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
