数据结构从入门到放弃

一. 基础

1. 数据结构基本概念

随机存取（Random Access）是指能够以均等的时间访问数据结构中任意元素的能力

数据结构三要素

• 逻辑结构
  • 线性结构
    • 一般线性表
    • 受限线性表：栈、队列、串
    • 线性表推广：数组
  • 非线性结构
    • 集合
    • 树形结构：一般树、二叉树
    • 图状结构：有向图、无向图
• 存储结构
  • 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元上
    • 优点：可实现随机存取
    • 缺点：只能使用相邻的存储单元，可能产生较多外部碎片
  • 链式存储：不要求逻辑上相邻物理位置也相邻
    • 优点：可以充分利用存储单元
    • 缺点：每个元素因存储指针而占用额外存储空间，且只能实现顺序存取
  • 索引存储：存储元素信息的同时建立附加索引表。索引表中每项称为索引项(一般形式为 (关键字，地址))
    • 优点：检索速度快
    • 缺点：占额外空间，增加和删除数据时也要修改索引表，花费更多时间
  • 散列存储(哈希存储)：根据元素关键字直接算出元素的存储地址
    • 优点：检索、增加和删除数据操作快
    • 缺点：如散列函数不好，可能出现元素存储单元冲突，解决冲突会增加时间和空间开销
• 运算
  • 定义：针对逻辑结构，指出运算的功能
  • 实现：针对存储结构，指出具体操作步骤

1. 逻辑结构

逻辑结构描述了数据元素之间的逻辑关系，通常有以下几种：

1. 集合结构（Set Structure）(非线性)
   • 数据元素之间仅有“属于同一个集合”的关系，元素之间无顺序关系。
2. 线性结构（Linear Structure）
   • 数据元素之间是一对一的关系，通常具有顺序性。
   • 典型例子：数组、链表、栈、队列。
3. 树形结构（Tree Structure）(非线性)
   • 数据元素之间是一对多的层次关系。
   • 典型例子：二叉树、平衡树、B树。
4. 图形结构（Graph Structure）(非线性)
   • 数据元素之间是多对多的关系，可以用节点和边表示。
   • 典型例子：无向图、有向图、加权图。

2. 存储结构

存储结构是指数据在计算机内存中的存储方式，通常有以下几种：

1. 顺序存储结构（Sequential Storage Structure）
   • 数据元素按顺序存储在连续的存储单元中，通常通过数组实现。
   • 适用于随机存取。
2. 链式存储结构（Linked Storage Structure）
   • 数据元素存储在任意存储单元中，通过指针指示数据元素之间的逻辑关系，通常通过链表实现。
   • 适用于顺序存取。
3. 索引存储结构（Indexed Storage Structure）
   • 在存储数据元素的同时，还附加了索引表，通过索引表可以快速找到数据元素。
   • 常用于数据库和文件系统。
4. 散列存储结构（Hashed Storage Structure）
   • 通过散列函数将数据元素映射到存储位置，适用于查找操作频繁的应用场景。
   • 典型例子：哈希表。

组合与选择

不同的逻辑结构可以采用不同的存储结构实现。选择哪种存储结构主要取决于操作的效率需求。例如：

• 数组（线性结构）可以通过顺序存储实现，提供高效的随机访问。
• 链表（线性结构）通过链式存储实现，插入和删除操作较为高效。
• 树（树形结构）可以通过链式存储实现，支持动态插入和删除。
• 图（图形结构）可以通过邻接矩阵（顺序存储）或邻接表（链式存储）实现。

举例：

• 数组：线性结构 + 顺序存储
• 链表：线性结构 + 链式存储
• 栈和队列：线性结构 + 顺序存储或链式存储
• 二叉树：树形结构 + 链式存储
• 哈希表：集合结构 + 散列存储

Python对应

1. 列表（List）

• 逻辑结构：线性结构
• 存储结构：动态数组（顺序存储）
• 特点：支持随机存取，元素可以通过索引直接访问；动态调整大小；支持高效的插入和删除操作。

my_list = [1, 2, 3, 4, 5]

2. 元组（Tuple）

• 逻辑结构：线性结构
• 存储结构：动态数组（顺序存储）
• 特点：类似于列表，但不可变；一旦创建，元素不能修改；支持随机存取。

my_tuple = (1, 2, 3, 4, 5)

3. 字典（Dictionary）

• 逻辑结构：集合结构
• 存储结构：哈希表（散列存储）
• 特点：键值对存储，通过键快速查找值；不保证顺序；动态调整大小。

从python3.7开始改为有序

my_dict = {'a': 1, 'b': 2, 'c': 3}

4. 集合（Set）

• 逻辑结构：集合结构
• 存储结构：哈希表（散列存储）
• 特点：无序不重复元素集；支持快速查找、插入和删除操作。

my_set = {1, 2, 3, 4, 5}

5. 字符串（String）

• 逻辑结构：线性结构
• 存储结构：顺序存储
• 特点：不可变字符序列；支持随机存取。

my_string = "hello"

6. 队列（Queue）

Python中没有内置的队列结构，但可以使用collections.deque来实现。

• 逻辑结构：线性结构
• 存储结构：链式存储
• 特点：双端队列，可以在两端快速插入和删除。

from collections import deque
my_queue = deque([1, 2, 3, 4, 5])

7. 栈（Stack）

Python中没有内置的栈结构，但列表可以用作栈。

• 逻辑结构：线性结构
• 存储结构：动态数组（顺序存储）
• 特点：LIFO（后进先出）结构，使用append和pop操作。

my_stack = [1, 2, 3, 4, 5]
my_stack.append(6)  # 入栈
my_stack.pop()  # 出栈

8. 链表（Linked List）

Python标准库中没有内置的链表，但可以自定义实现。

• 逻辑结构：线性结构
• 存储结构：链式存储
• 特点：动态调整大小，插入和删除操作高效。

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

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

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

my_linked_list = LinkedList()
my_linked_list.append(1)
my_linked_list.append(2)

9. 优先队列（Priority Queue）

可以使用heapq模块实现。

• 逻辑结构：树形结构
• 存储结构：二叉堆（顺序存储）
• 特点：支持快速获取和删除最小（或最大）元素。

import heapq
my_priority_queue = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(my_priority_queue)  # 转换为堆
heapq.heappop(my_priority_queue)  # 删除并返回最小元素

2. 算法与算法评价

算法定义：对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作

度量：时间复杂度和空间复杂度

一个语句的频度: 该语句在算法中被重复执行的次数

时间复杂度

• 计算：取 算法中所有语句的频度之和中增长最快的项，将其系数置为1作为时间复杂度的度量

• 一般是考虑最坏情况下的时间复杂度，确保算法运行时间不超过它

空间复杂度

• 算法所消耗的存储空间

二. 线性表

三. 栈、队列和数组

四. 串

五. 树

六. 图

七. 查找

八. 排序