1.什么是线性表

线性表的概念

• 定义：线性表是由n个数据元素组成的有限序列。每个数据元素（除了第一个和最后一个）都有且仅有一个前驱和一个后继。
• 逻辑结构：线性表的逻辑结构可以用一个序列来表示，例如 L=(a1,a2,…,an)。
• 长度：线性表的长度是元素的个数，通常用n表示。

线性表的ADT（抽象数据类型）定义

• 数据元素：数据元素的集合 D={a1,a2,…,an}。
• 关系：元素之间的关系集合 S={<ai,ai+1>∣ai,ai+1∈D,i=1,2,…,n−1}。
• 基本操作：初始化线性表
  • 销毁线性表
  • 清空线性表
  • 判断线性表是否为空
  • 获取线性表的长度
  • 定位元素的位置

总结

• 线性表是数据结构中最基本的一种，其逻辑结构简单明了，每个元素都有明确的前驱和后继关系。
• ADT定义为线性表的操作提供了规范，使得线性表的实现和使用更加灵活和方便。

2.顺序表

插入元素操作的详细分析

• 操作步骤：
  • 检查表是否已满：如果表已满，则无法插入新元素。
  • 检查插入位置是否合法：插入位置 i 必须在 0 到 length 之间（包括 length）。
  • 移动元素：将从位置 i 开始的所有元素向后移动一个位置，为新元素腾出空间。
  • 插入新元素：将新元素 e 插入到位置 i。
  • 更新表长：表长 length 增加 1。
• Python 代码实现：

def list_insert_sq(L, i, e):if L['length'] >= MAXSIZE:return "Error: List is full"if not (0 <= i <= L['length']):return "Error: Invalid position"# 在位置j插入元素efor j in range(L['length'] - 1, i - 1, -1):
        L['elem'][j + 1] = L['elem'][j]    L['elem'][i] = e
    L['length'] += 1return "Insertion successful"

• 时间复杂度分析：
  • 最好情况：插入到末尾（i = length），不需要移动元素，时间复杂度为 O(1)。
  • 最坏情况：插入到开头（i = 0），需要移动所有元素，时间复杂度为 O(n)。
  • 平均情况：平均需要移动一半的元素，时间复杂度为 O(n)。

删除元素操作

• 操作步骤：
  • 检查表是否为空：如果表为空，则无法删除元素。
  • 检查删除位置是否合法：删除位置 i 必须在 0 到 length-1 之间。
  • 移动元素：将从位置 i+1 开始的所有元素向前移动一个位置，覆盖被删除的元素。
  • 更新表长：表长 length 减少 1。
• Python 代码实现：

这里是删除位置线性表中位置为i的元素，所以只要判断位置i是否合法，而不用判断元素是否存在

def list_delete_sq(L, i, e):if L['length'] == 0:return "Error: List is empty"if not (0 <= i < L['length']):return "Error: Invalid position"    e = L['elem'][i]for j in range(i, L['length'] - 1):
        L['elem'][j] = L['elem'][j + 1]    L['length'] -= 1return "Deletion successful"

如果是删除元素e，那么需要检验元素是否存在表中

def list_delete_sq(L, e):if L['length'] == 0:return "Error: List is empty"# 遍历线性表，检验元素e是否存在for i in range(L['length']):if L['elem'][i] == e:# 删除元素for j in range(i, L['length'] - 1):
                L['elem'][j] = L['elem'][j + 1]
            L['length'] -= 1return "Deletion successful"# 如果遍历完都没有找到元素ereturn "Error: element is not in List"

• 时间复杂度分析：
  • 最好情况：删除最后一个元素（i = length-1），不需要移动元素，时间复杂度为 O(1)。
  • 最坏情况：删除第一个元素（i = 0），需要移动所有元素，时间复杂度为 O(n)。
  • 平均情况：平均需要移动一半的元素，时间复杂度为 O(n)。

查找元素操作

• 操作步骤：
  • 遍历顺序表：从头到尾遍历顺序表，查找指定的元素。
  • 返回结果：如果找到元素，返回其位置；否则返回未找到的提示。
• Python 代码实现：

def list_search_sq(L, e):for i in range(L['length']):if L['elem'][i] == e:return ireturn "Element not found"

• 时间复杂度分析：
  • 最好情况：元素在第一个位置，时间复杂度为 O(1)。
  • 最坏情况：元素在最后一个位置或不存在，时间复杂度为 O(n)。
  • 平均情况：时间复杂度为 O(n)。

总结

• 优点：
  • 随机访问：可以快速访问任意位置的元素。
  • 存储简单：使用连续的内存空间，实现简单。
• 缺点：
  • 空间限制：需要预先分配空间，可能浪费空间或空间不足。
  • 插入和删除操作耗时：需要移动大量元素，时间复杂度为 O(n)。

3.链表

链表的概念

• 定义：链表是线性表的一种物理存储结构，使用一组任意的存储单元来存储线性表的数据元素。每个元素包含一个数据域和一个指针域，指针域指向下一个元素。
• 特点：非连续存储：数据元素在内存中可以分散存储。
  • 动态存储：可以动态地分配和释放存储空间，不需要预先分配固定大小的空间。

链表的存储结构

• 结点定义：

class ListNode:def __init__(self, data=None):
        self.data = data
        self.next = None

• 链表定义：

class LinkedList:def __init__(self):
        self.head = None

链表的基本操作

初始化链表

• 操作步骤：创建一个空的链表，头指针 head 指向 None。
• Python 代码实现：

def init_linked_list(self):
    self.head = None

获取链表长度

• 操作步骤：从头结点开始遍历链表，计数节点个数。
• Python 代码实现：

def get_length(self):
    count = 0
    current = self.headwhile current:
        count += 1
        current = current.nextreturn count

获取第i个元素的值

• 操作步骤：从头结点开始遍历链表，找到第 i 个节点。
• Python 代码实现：

def get_element(self, i):if i < 0:return "Error: Index out of range"
    current = self.head
    index = 0while current:if index == i:return current.data
        current = current.next
        index += 1return "Error: Index out of range"

插入元素

• 操作步骤：创建新节点：分配空间并初始化新节点。
  • 找到插入位置：遍历链表找到第 i-1 个节点。
  • 插入新节点：调整指针，将新节点插入链表中。
• Python 代码实现：

def insert(self, i, data):if i < 0:return "Error: Invalid index"
    new_node = ListNode(data)if i == 0:
        new_node.next = self.head
        self.head = new_nodeelse:
        current = self.head
        index = 0while current and index < i - 1:
            current = current.next
            index += 1if not current:return "Error: Index out of range"
        new_node.next = current.next
        current.next = new_node

删除元素

• 操作步骤：找到要删除的节点：遍历链表找到第 i 个节点。
  • 调整指针：将前一个节点的指针指向要删除节点的下一个节点。
  • 释放节点空间：删除节点。
• Python 代码实现：

def delete(self, i):if i < 0:return "Error: Invalid index"if i == 0:if self.head:
            self.head = self.head.nextelse:return "Error: List is empty"else:
        current = self.head
        index = 0while current and index < i - 1:
            current = current.next
            index += 1if not current or not current.next:return "Error: Index out of range"
        current.next = current.next.next

总结

• 优点：动态存储：可以动态地分配和释放存储空间，不需要预先分配固定大小的空间。
  • 插入和删除操作高效：不需要移动大量元素，只需调整指针，时间复杂度为 O(1)。
• 缺点：随机访问困难：不能直接通过下标访问元素，需要从头结点开始遍历，时间复杂度为 O(n)。
  • 额外空间开销：每个节点需要额外的空间存储指针域。

4.循环链表

循环链表的基本概念

• 定义：循环链表是一种特殊的链表，其特点是最后一个节点的指针域指向链表的头节点，形成一个环形结构。
• 类型：循环单链表：最后一个节点的 next 指针指向头节点。
  • 循环双向链表：最后一个节点的 next 指针指向头节点，头节点的 prior 指针指向最后一个节点。

循环链表的存储结构

• 节点定义：

class Node:def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prior = None  # 仅在双向循环链表中使用

• 链表定义：python

class CircularLinkedList:def __init__(self):
        self.head = None

循环链表的基本操作

初始化循环链表

• 操作步骤：创建一个空的循环链表，头指针 head 指向 None。
• Python 代码实现：

def init_circular_linked_list(self):
    self.head = None

插入元素

• 操作步骤：创建新节点：分配空间并初始化新节点。
  • 找到插入位置：遍历链表找到插入位置。
  • 插入新节点：调整指针，将新节点插入链表中，并更新指针形成环。
• Python 代码实现：

def insert(self, data):
    new_node = Node(data)if self.head is None:
        self.head = new_node
        new_node.next = new_node  # 形成环else:
        current = self.headwhile current.next != self.head:
            current = current.next
        new_node.next = self.head
        current.next = new_node

删除元素

• 操作步骤：找到要删除的节点：遍历链表找到要删除的节点。
  • 调整指针：将前一个节点的 next 指针指向要删除节点的下一个节点，并更新指针形成环。
  • 释放节点空间：删除节点。
• Python 代码实现：

def delete(self, data):if self.head is None:return "Error: List is empty"
    current = self.head
    prev = Nonewhile True:if current.data == data:if current == self.head:if current.next == self.head:
                    self.head = Noneelse:while current.next != self.head:
                        current = current.next
                    current.next = self.head.next
                    self.head = self.head.nextelse:
                prev.next = current.nextreturn "Deletion successful"
        prev = current
        current = current.nextif current == self.head:breakreturn "Error: Element not found"

遍历链表

• 操作步骤：从头节点开始遍历链表，直到回到头节点。
• Python 代码实现：

def traverse(self):if self.head is None:return "List is empty"
    current = self.headwhile True:print(current.data, end=" -> ")
        current = current.nextif current == self.head:breakprint("Head")

总结

• 优点：环形结构：可以方便地从任意节点开始遍历整个链表。
  • 操作灵活：插入和删除操作不需要特殊处理头尾节点。
• 缺点：复杂性：实现和操作相对复杂，需要特别注意指针的更新和环的维护。