数据结构与算法

# 笔记
# 数据结构

数据结构全值指南

14 mins.15k30

数据结构概述

什么是数据结构：

维基百科中的定义为“数据结构(data structure)是计算机中存储、组织数据的方式”。这个简单的定义点出了数据结构的两个核心内容：存储结构和逻辑结构。

存储结构表示了数据在计算机内存中的物理存储方式，而逻辑结构表示了数据元素之间的关系和组织方式。

举个例子：
假设我们有一个通讯录，里面存储了姓名和电话号码。我们可以将这个通讯录看作一个数据结构。而通讯录的存储结构可以是一个数组（按姓名排序），也可以是一个链表（按插入顺序），甚至可以是一个哈希表（快速查找）。而逻辑结构则表示了姓名和电话号码之间的对应关系。

为什么学习数据结构很重要？：

目前随着深度学习和大数据领域的快速发展，算法工程在各个行业和企业中的应用逐渐广泛，作为一个学习者，学习数据结构是理解，读懂算法的基础，而作为未来的相关工作者，数据结构是提高算法效率和性能的关键。

本文目标与适用人群

本文旨在为初学者提供一个全面的数据结构入门指南，帮助读者理解数据结构的基本概念、分类和应用。适用于计算机科学专业的学生、以及对数据结构感兴趣的初学者。

本文将使用类C语言进行示例代码的编写，读者需要具备一定的C语言编程或抽象语言基础。

数据结构的核心：时间复杂度与空间复杂度

在学习和选择数据结构时，两个核心概念至关重要：

时间复杂度（Time Complexity）
时间复杂度衡量的是算法或操作随着输入规模增长所需时间的变化趋势，通常使用大 O 表示法：

O(f(n)) 表示算法在最坏情况下，其运行时间或空间消耗最多为 f(n) 的某个常数倍。

通俗理解：它不关心具体运行了多少秒，而是关心数量级。也就是说，输入增加一倍，运行时间或空间增长多少。

无论是形式上还是含义和用法上，这个表示方法都和数学中的佩亚诺余项有点像（扯远了）

操作	时间复杂度示例
访问数组元素	O(1)
查找链表元素	O(n)
排序数组	O(n log n)
BFS遍历图	O(V + E)

不同数据结构在插入、删除、访问等操作上，效率可能有天壤之别。比如：

数组访问快（O(1)），但插入慢（O(n)）；
链表插入快（O(1)），但访问慢（O(n)）；
堆适合快速取最大/最小值（O(log n)）；
哈希表查找非常快（O(1) 平均），但最坏情况下是 O(n)。

空间复杂度（Space Complexity）
空间复杂度关注的是算法运行所需的额外内存空间大小。

比如：

存储一个长度为 n 的数组需要 O(n) 空间；
使用递归时，调用栈的空间也要算进去。

合理选择数据结构，可以在时间和空间之间做出权衡。例如，如果你需要频繁访问元素，优先考虑数组或哈希表；如果你希望节省内存或者需要动态插入删除，链表可能更合适。

数据结构分类

数据结构可以根据不同的标准进行分类，常见的分类方式包括：

线性结构与非线性结构：
- 线性结构：数据元素之间存在一对一的关系，如数组、链表、栈、队列等。
- 非线性结构：数据元素之间存在多对多或一对多的关系，如树、图等。
静态结构与动态结构：
- 静态结构：数据结构的大小在编译时确定，如数组。
- 动态结构：数据结构的大小可以在运行时动态变化，如链表、树等。
物理结构与逻辑结构：
- 物理结构：数据在计算机内存中的存储方式，如顺序存储、链式存储等。
- 逻辑结构：数据元素之间的关系和组织方式，如集合、序列等。

线性数据结构

线性数据结构的存储方式主要分为顺序存储和链式存储。

链式存储是指数据元素通过指针或引用连接在一起，就像一条项链一样。

顺序存储是指数据元素在内存中连续存储，通常使用数组实现。

示例：
顺序结构：

索引	数据
0	1
1	5
2	3
…	…

链式结构：

索引	数据	指针
0	1	4
…	…	…
4	5	8
…	…	…
…	…	…
8	3	9

🔢 1. 数组（Array）

📘 定义

数组是一种顺序存储的线性结构，它将一组相同类型的数据元素按照一定顺序排列在一段连续的内存空间中。每个元素通过索引访问。

⚙️ 基本操作与时间复杂度

操作	描述	时间复杂度
访问元素	根据索引直接访问	O(1)
插入元素	插入到中间需移动后续元素	O(n)
删除元素	删除中间元素需移动后续元素	O(n)
遍历	遍历整个数组	O(n)

✅ 优点

支持随机访问，读取速度快。
实现简单、易于理解。

❌ 缺点

大小固定，扩展不灵活。
插入/删除代价高（除非操作在尾部，因为任何中间元素的增删都要将后面的数据进行移动）。

🛠 示例代码

int arr[5] = {1, 2, 3, 4, 5}; // 定义一个整型数组

// 访问元素
printf("%d", arr[2]); // 输出第3个元素：3

// 插入元素（在末尾）
arr[5] = 6; // 假设数组大小足够

// 删除元素（假设删除第3个元素）
for (int i = 2; i < 4; i++) {
    arr[i] = arr[i + 1]; // 将后续元素前移
}
// 注意：实际操作中需要处理数组大小和边界问题

// 遍历数组
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]); // 输出数组元素
}

有很多教材会使用结构体来定义数组元素，这当然是一种十分清晰的表示方法，并且提高了数组包含的元素类型的灵活性，但在实际应用中通常以实际需求为主，如果没有额外信息，那么出于简洁和效率的考虑，直接使用基本数据类型数组更为常见。

📌 应用场景

存储固定大小的数据集（如成绩表、统计数组）
动态数组（如 C++ 的 vector、Python 的 list）是其变种

🔗 2. 链表（Linked List）

📘 定义

链表由若干个节点组成，每个节点包含：

数据域（Data）
指针域（Next）：指向下一个节点

根据链接方式不同分为：

单向链表
双向链表
循环链表

⚙️ 基本操作与时间复杂度

操作	描述	时间复杂度
访问元素	需从头节点依次查找	O(n)
插入节点	若已知位置，插入效率高	O(1)
删除节点	若已知位置，删除效率高	O(1)
遍历节点	从头节点开始遍历	O(n)
查找元素	遍历链表	O(n)

✅ 优点

插入和删除灵活，不需要移动其他元素。
支持动态扩展，不需预留空间。

❌ 缺点

不支持随机访问，查找效率低。
占用更多内存（存储指针）。

🛠 示例代码（C语言）

/*实现一个普通单链表*/

struct Node {
    int data;
    struct Node* next;
};
struct Node* head = NULL; // 链表头部

// 插入节点
void insert(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->next = head; // 插入到头部
    head = newNode;
}

// 删除节点
void delete(int x) {
    struct Node* current = head;
    struct Node* prev = NULL;
    while (current != NULL) {
        if (current->data == x) {
            if (prev == NULL) {
                head = current->next; // 删除头节点
            } else {
                prev->next = current->next; // 删除中间或尾节点
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

// 访问节点
int get(int index) {
    struct Node* current = head;
    for (int i = 0; i < index && current != NULL; i++) {
        current = current->next;
    }
    return current ? current->data : -1; // 返回-1表示索引越界
}

// 遍历链表
void traverse() {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 查找节点
int find(int x) {
    struct Node* current = head;
    int index = 0;
    while (current != NULL) {
        if (current->data == x) {
            return index; // 返回索引
        }
        current = current->next;
        index++;
    }
    return -1; // 未找到
}

📌 应用场景

动态数据集合（如队列、栈的链式实现）
LRU缓存、哈希表冲突处理（拉链法）

📦 3. 栈（Stack）

📘 定义

栈是一种先进后出（LIFO）的线性结构，只允许在一端进行插入和删除操作，该端称为“栈顶”。

⚙️ 基本操作与时间复杂度

操作	描述	时间复杂度
push	向栈顶压入元素	O(1)
pop	弹出栈顶元素	O(1)
top/peek	获取栈顶元素	O(1)
isEmpty	判断栈是否为空	O(1)

✅ 优点

操作简单，符合递归、嵌套结构的特点。
实现函数调用栈、括号匹配等场景。

❌ 缺点

不支持随机访问。
容量受限于实现方式（定长数组或内存）。

🛠 示例代码（C语言）

#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;

void push(int x) {
    if (top < MAX_SIZE - 1)
        stack[++top] = x;
}

int pop() {
    if (top >= 0)
        return stack[top--];
}

int isEmpty() {
    return top == -1;
}

int peek() {
    if (top >= 0)
        return stack[top];
    return -1; // 栈空时返回-1
}

📌 应用场景

函数递归、括号匹配、表达式求值
深度优先搜索（DFS）

🚦 4. 队列（Queue）

📘 定义

队列是一种**先进先出（FIFO）**的线性结构，只允许：

在队尾插入（Enqueue）
在队头删除（Dequeue）

变种包括：

循环队列
双端队列（Deque）
优先队列

⚙️ 基本操作与时间复杂度

操作	描述	时间复杂度
enqueue	入队操作（队尾）	O(1)
dequeue	出队操作（队头）	O(1)
front/rear	查看队头或队尾元素	O(1)
isEmpty	判断队列是否为空	O(1)

✅ 优点

适合按时间顺序处理任务。
实现简单、结构清晰。

❌ 缺点

静态数组实现会浪费空间（解决方法：循环队列）
动态队列需要管理指针

🛠 示例代码（C语言）

#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = 0, rear = 0;

void enqueue(int x) {
    if ((rear + 1) % MAX_SIZE != front)
        queue[rear = (rear + 1) % MAX_SIZE] = x;
}

int dequeue() {
    if (front != rear)
        return queue[front = (front + 1) % MAX_SIZE];
}

int isEmpty() {
    return front == rear;
}

int frontElement() {
    if (front != rear)
        return queue[(front + 1) % MAX_SIZE];
    return -1; // 队列空时返回-1
}

int rearElement() {
    if (front != rear)
        return queue[rear];
    return -1; // 队列空时返回-1
}

📌 应用场景

消息队列、打印任务排队
广度优先搜索（BFS）
生产者-消费者模型

📊 小结：线性结构对比

结构	随机访问	插入效率	删除效率	应用典型
数组	O(1)	O(n)	O(n)	固定数据集合
链表	O(n)	O(1)*	O(1)*	动态增删集合
栈	O(n)	O(1)	O(1)	递归、括号匹配
队列	O(n)	O(1)	O(1)	排队系统、BFS

* 插入/删除需已知位置的前驱节点

非线性数据结构

1. 树（Tree）

📘 定义

树是一种非线性数据结构，由节点组成，有以下相关概念：

根节点：树的顶端节点，没有父节点。
子节点：根节点以下的节点，具有父节点。
叶子节点：没有子节点的节点。
深度：节点到根节点的路径长度。
高度：节点到叶子节点的最长路径长度。

⚙️ 基本操作与时间复杂度

操作	描述	时间复杂度
插入节点	在树中插入新节点	O(log n)
删除节点	删除指定节点	O(log n)
查找节点	查找指定节点	O(log n)
遍历	遍历所有节点（前序、中序、后序）	O(n)

✅ 优点

适合表示层次结构数据，如文件系统、组织结构等。
支持快速查找、插入和删除操作。

❌ 缺点

实现复杂度较高。
不支持随机访问。

🛠 示例代码（C语言）

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void insert(struct TreeNode** root, int data) {
    if (*root == NULL) {
        *root = createNode(data);
    } else if (data < (*root)->data) {
        insert(&(*root)->left, data);
    } else {
        insert(&(*root)->right, data);
    }
}

void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

void preorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void postorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}

int search(struct TreeNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root != NULL; // 返回1表示找到，0表示未找到
    }
    if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}

void deleteTree(struct TreeNode* root) {
    if (root != NULL) {
        deleteTree(root->left);
        deleteTree(root->right);
        free(root);
    }
}

📌 应用场景

文件系统、组织结构树
数据库索引（B树、B+树）
二叉搜索树（BST）用于快速查找

特殊的树

1. 二叉树（Binary Tree）

二叉树是每个节点最多有两个子节点的树结构。常见的二叉树类型包括：

满二叉树：每个节点都有两个子节点，且所有叶子节点在同一层。
完全二叉树：除了最后一层外，其他层都是满的，且最后一层的叶子节点从左到右排列。
平衡二叉树：左右子树高度差不超过1的二叉树，如 AVL 树。

2. 二叉搜索树（Binary Search Tree, BST）

二叉搜索树是一种特殊的二叉树，满足以下性质：

左子树所有节点的值小于根节点的值。

右子树所有节点的值大于根节点的值。
示例：

struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
};
void insertBST(struct BSTNode** root, int data) {
    if (*root == NULL) {
        *root = createNode(data);
    } else if (data < (*root)->data) {
        insertBST(&(*root)->left, data);
    } else {
        insertBST(&(*root)->right, data);
    }
}
void inorderBST(struct BSTNode* root) {
    if (root != NULL) {
        inorderBST(root->left);
        printf("%d ", root->data);
        inorderBST(root->right);
    }
}

复杂度分析：

插入、删除、查找操作的平均时间复杂度为 O(log n)，最坏情况下为 O(n)（当树退化为链表时）。

3. 平衡二叉树（AVL Tree）

AVL 树是一种自平衡的二叉搜索树，保证任意节点的左右子树高度差不超过1。通过旋转操作保持平衡。
构造AVL树的代码示例：

// AVL 树节点结构
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    int height;
} Node;

// 获取高度
int height(Node* node) {
    return node ? node->height : 0;
}

// 计算最大值
int max(int a, int b) {
    return a > b ? a : b;
}

// 创建新节点
Node* newNode(int key) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->left = node->right = NULL;
    node->height = 1; // 新节点高度为1
    return node;
}

// 获取平衡因子（左高-右高）
int getBalance(Node* node) {
    return node ? height(node->left) - height(node->right) : 0;
}

// 右旋
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

// 左旋
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

// 插入并自动平衡
Node* insert(Node* node, int key) {
    // 1. 正常 BST 插入
    if (node == NULL)
        return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // 不允许重复键
        return node;

    // 2. 更新当前节点的高度
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. 获取平衡因子
    int balance = getBalance(node);

    // 4. 四种不平衡情况（旋转）

    // 左左
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // 右右
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // 左右
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node; // 无需旋转
}

4. 红黑树（Red-Black Tree）

红黑树是一种自平衡的二叉搜索树，具有以下性质：

节点是红色或黑色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色。
从任何节点到其每个叶子节点的路径上，黑色节点的数量相同。

5. 堆（Heap）

堆是一种特殊的完全二叉树，分为最大堆和最小堆：

最大堆：每个节点的值大于或等于其子节点的值。
最小堆：每个节点的值小于或等于其子节点的值。

⚙️ 基本操作与时间复杂度

操作	描述	时间复杂度
插入节点	在堆中插入新节点	O(log n)
删除节点	删除堆顶节点	O(log n)
查找节点	查找堆顶节点	O(1)

✅ 优点

支持快速获取最大/最小值。
常用于实现优先队列。

❌ 缺点

不支持随机访问。

🛠 示例代码（C语言）

struct Heap {
    int* data;
    int size;
    int capacity;
};

struct Heap* createHeap(int capacity) {
    struct Heap* heap = (struct Heap*)malloc(sizeof(struct Heap));
    heap->data = (int*)malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(struct Heap* heap, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap->size && heap->data[left] > heap->data[largest])
        largest = left;
    if (right < heap->size && heap->data[right] > heap->data[largest])
        largest = right;

    if (largest != index) {
        swap(&heap->data[index], &heap->data[largest]);
        heapify(heap, largest);
    }
}

void insert(struct Heap* heap, int value) {
    if (heap->size == heap->capacity) {
        printf("Heap is full\n");
        return;
    }
    heap->data[heap->size] = value;
    heap->size++;

    for (int i = (heap->size - 1) / 2; i >= 0; i--) {
        heapify(heap, i);
    }
}

int extractMax(struct Heap* heap) {
    if (heap->size == 0) {
        printf("Heap is empty\n");
        return -1; // 返回-1表示堆为空
    }
    int max = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return max;
}

void deleteHeap(struct Heap* heap) {
    free(heap->data);
    free(heap);
}

➗ k叉树的快速计算

完全k叉树是一种每个节点最多有k个子节点的树结构。对于完全k叉树，可以快速计算其节点数、深度等属性。

节点数计算

对于满k叉树，节点数可以通过以下公式计算：
[ N = k^{h+1} - 1/{k - 1} ]
其中，( N ) 是节点数，( k ) 是每个节点的子节点数，( h ) 是树的高度。

深度计算

树的深度可以通过以下公式计算：
[ h = log_k(N * (k - 1) + 1) ]

每层节点数上限计算

对于完全k叉树，叶子节点数可以通过以下公式计算：
[ L = k^h ] (h从0开始)

第i节点的父亲节点索引计算

父亲节点的索引：[parent(i) = (i - 1) / k] (向下取整)

第i节点的第j个子节点索引计算

子节点的索引：[child(i, j) = k * i + j + 1] (j从0开始)

第i节点的第j个兄弟节点索引计算

兄弟节点的索引：[sibling(i, j) = i + j] (j从-1开始，表示前一个兄弟节点)

第i节点的第j个祖先节点索引计算

祖先节点的索引：[ancestor(i, j) = (i - 1) / k^j] (j从0开始，表示父节点)

信息系统设计与开发

信息系统设计与开发

参考资料左美云.信息系统与开发管理教程[M].北京:清华大学出版社.2021 信息系统的基础知识信息的定义信息是可以传输和处理的数据和知识，是管理和决策的重要...

Thanafox shared on Jun 12, 2025

项目开发

Molecular Diffusion Model(MDM)复现项目

项目规划项目目标：根据论文和Github上的开源代码，复现出MDM(Molecular Diffusion Model)模型，并实现可以生成尽可能接近指定能量...

Thanafox shared on May 25, 2025

Comments

What do you think?

NickName

E-Mail(Optional)

Comments

Latest
Oldest
Hottest

No comment yet.

Thanafox

常应常静，常清净矣。

69k
Words
19
Articles
10
Categories
33
Tags

早上好呀～

数据结构全值指南

数据结构概述

什么是数据结构：

为什么学习数据结构很重要？：

本文目标与适用人群

数据结构的核心：时间复杂度与空间复杂度

数据结构分类

线性数据结构

🔢 1. 数组（Array）

📘 定义

⚙️ 基本操作与时间复杂度

✅ 优点

❌ 缺点

🛠 示例代码

📌 应用场景

🔗 2. 链表（Linked List）

📘 定义

⚙️ 基本操作与时间复杂度

✅ 优点

❌ 缺点

🛠 示例代码（C语言）

📌 应用场景

📦 3. 栈（Stack）

📘 定义

⚙️ 基本操作与时间复杂度

✅ 优点

❌ 缺点

🛠 示例代码（C语言）

📌 应用场景

🚦 4. 队列（Queue）

📘 定义

⚙️ 基本操作与时间复杂度

✅ 优点

❌ 缺点

🛠 示例代码（C语言）

📌 应用场景

📊 小结：线性结构对比

非线性数据结构

1. 树（Tree）

📘 定义

⚙️ 基本操作与时间复杂度

✅ 优点

❌ 缺点

🛠 示例代码（C语言）

📌 应用场景

特殊的树

1. 二叉树（Binary Tree）

2. 二叉搜索树（Binary Search Tree, BST）

3. 平衡二叉树（AVL Tree）

4. 红黑树（Red-Black Tree）

5. 堆（Heap）

⚙️ 基本操作与时间复杂度

✅ 优点

❌ 缺点

🛠 示例代码（C语言）

➗ k叉树的快速计算

节点数计算

深度计算

每层节点数上限计算

第i节点的父亲节点索引计算

第i节点的第j个子节点索引计算

第i节点的第j个兄弟节点索引计算

第i节点的第j个祖先节点索引计算

信息系统设计与开发

Molecular Diffusion Model(MDM)复现项目

Preview:

Thanafox