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

发布于:2024-07-06 ⋅ 阅读:(118) ⋅ 点赞:(0)

一、线性表的基本概念

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

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


网站公告

今日签到

点亮在社区的每一天
去签到