数据结构学习
简单了解一下时间复杂度之类之后，我们接下来学习下面的
持续更完，本人依据知识框架结合chatgpt的定义总结
线性表
线性表是最基本的一种线性数据结构
设 某个线性表中有n个元素，n表示该线性表的长度。
我们想象一个磁条，上面是一格格的储存块，我们要存储一个线性数据结构
有顺序储存结构，所有的储存是顺序储存的，这有一个问题，就是每次都要约定要存多少，否则就不是顺序的了
还有链式存储结构
这是我们讨论的重点
链式储存结构
一般来说，说起链式储存结构就先想到链表
单链表
链表不像顺序储存，是分块储存的，那么这时候，我们就考虑到了：一个块，既需要储存本身要储存的东西，又要储存下一个块的位置信息
即 element|link
定义如下
typedef struct node
{
elemType element
struct node *link
}Node;
typedef struct singleList
{
Node *frist;
int n;
}SiingleList;
我们简单分析一下这个定义：
定义了node，再用Node定义singleList（即单链表）
first表示头指针 n表示单链表中元素的个数
#include <stdio.h>
#include <stdlib.h>
// 单向链表节点结构体
struct Node {
int data; // 节点数据
struct Node* next; // 指向下一个节点的指针
};
// 单向链表头结点指针
struct Node* head = NULL;
// 在链表头部插入一个节点
void insert_at_beginning(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
new_node->data = data; // 设置新节点的数据
new_node->next = head; // 将新节点的下一个节点指向原头节点
head = new_node; // 将链表头节点指针指向新节点
}
// 在链表尾部插入一个节点
void insert_at_end(int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // 创建新节点
new_node->data = data; // 设置新节点的数据
new_node->next = NULL; // 将新节点的下一个节点指向空
if (head == NULL) { // 如果链表为空
head = new_node; // 将链表头节点指针指向新节点
return;
}
struct Node* cur_node = head; // 从链表头开始遍历
while (cur_node->next != NULL) { // 找到链表尾部节点
cur_node = cur_node->next;
}
cur_node->next = new_node; // 将尾部节点的下一个节点指向新节点
}
// 删除一个指定的节点
void delete_node(int data) {
struct Node* cur_node = head; // 从链表头开始遍历
struct Node* prev_node = NULL; // 记录前一个节点
while (cur_node != NULL) {
if (cur_node->data == data) { // 如果找到了要删除的节点
if (prev_node == NULL) { // 如果要删除的节点是头节点
head = cur_node->next; // 将头节点指向当前节点的下一个节点
} else { // 如果要删除的节点不是头节点
prev_node->next = cur_node->next; // 将前一个节点指向当前节点的下一个节点
}
free(cur_node); // 释放当前节点的内存
return;
}
prev_node = cur_node; // 记录前一个节点
cur_node = cur_node->next; // 移动到下一个节点
}
}
// 打印链表中的所有节点
void print_list() {
struct Node* cur_node = head; // 从链表头开始遍历
while (cur_node != NULL) {
printf("%d ", cur_node->data); // 输出当前节点的数据
cur_node = cur_node->next; // 移动到下一个节点
}
printf("\n");
}
int main() {
// 在链表头部插入数据
insert_at_beginning(1);
insert_at_beginning(2);
insert_at_beginning(3);
// 打印链表
printf("链表：");
print_list(); // 输出：3 2 1
// 在链表尾部插入数据
insert_at_end(4);
insert_at_end(5);
// 打印链表
printf("链表：");
print_list(); // 输出：3 2 1 4 5
// 删除数据
delete_node(2);
delete_node(4);
// 打印链表
printf("链表：");
print_list(); // 输出：3 1 5
return 0;
}
双向链表
#include <stdio.h>
#include <stdlib.h>
// 定义双向链表节点
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* head = NULL; // 链表头指针
// 在链表头部插入数据
void insert_at_beginning(int data) {
// 创建新节点
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = data;
new_node->prev = NULL;
// 更新链表头指针
if (head == NULL) {
new_node->next = NULL;
} else {
head->prev = new_node;
new_node->next = head;
}
head = new_node;
}
// 在链表尾部插入数据
void insert_at_end(int data) {
// 创建新节点
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = NULL;
// 找到链表尾部节点
struct Node* last = head;
while (last->next != NULL) {
last = last->next;
}
// 插入新节点
if (last == NULL) {
head = new_node;
new_node->prev = NULL;
} else {
last->next = new_node;
new_node->prev = last;
}
}
// 删除指定节点
void delete_node(struct Node* node) {
// 更新前驱节点的指针
if (node->prev != NULL) {
node->prev->next = node->next;
} else {
head = node->next;
}
// 更新后继节点的指针
if (node->next != NULL) {
node->next->prev = node->prev;
}
// 释放节点内存
free(node);
}
// 打印链表
void print_list() {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 主函数
int main() {
// 在链表头部插入数据
insert_at_beginning(1);
insert_at_beginning(2);
insert_at_beginning(3);
// 打印链表
printf("链表：");
print_list(); // 输出：3 2 1
// 在链表尾部插入数据
insert_at_end(4);
insert_at_end(5);
// 打印链表
printf("链表：");
print_list(); // 输出：3 2 1 4 5
// 删除节点
delete_node(head->next); // 删除第二个节点
// 打印链表
printf("链表：");
print_list(); // 输出：3 1 4 5
return 0;
}
循环列表
#include <stdio.h>
#include <stdlib.h>
// 定义循环链表结点
struct Node {
int data;
struct Node* next;
};
// 插入结点到循环链表中
void insert(struct Node** head_ref, int new_data) {
// 创建新结点
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
// 如果链表为空，则让新结点成为头结点
if (*head_ref == NULL) {
*head_ref = new_node;
new_node->next = *head_ref;
return;
}
// 找到链表的最后一个结点
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// 把新结点插入到链表的尾部
last->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
}
// 删除指定数据的结点
void deleteNode(struct Node** head_ref, int key) {
if (*head_ref == NULL) {
return;
}
struct Node* curr = *head_ref, *prev;
while (curr->data != key) {
if (curr->next == *head_ref) {
printf("Key not found in the list");
return;
}
prev = curr;
curr = curr->next;
}
// 如果链表只有一个结点
if (curr->next == *head_ref && prev == NULL) {
free(curr);
*head_ref = NULL;
return;
}
// 如果删除的是头结点
if (curr == *head_ref) {
prev = *head_ref;
while (prev->next != *head_ref) {
prev = prev->next;
}
*head_ref = curr->next;
prev->next = *head_ref;
free(curr);
}
// 如果删除的是尾结点
else if (curr->next == *head_ref) {
prev->next = *head_ref;
free(curr);
}
// 如果删除的是中间结点
else {
prev->next = curr->next;
free(curr);
}
}
// 打印循环链表中的所有结点
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
}
// 主函数
int main() {
// 初始化双向链表
head = NULL;
// 在双向链表头部插入元素 5
insertAtHead(5);
// 在双向链表头部插入元素 3
insertAtHead(3);
// 在双向链表头部插入元素 1
insertAtHead(1);
// 在双向链表尾部插入元素 7
insertAtTail(7);
// 在双向链表第二个位置插入元素 2
insertAtIndex(2, 2);
// 删除双向链表头部元素
deleteAtHead();
// 删除双向链表尾部元素
deleteAtTail();
// 删除双向链表第二个元素
deleteAtIndex(2);
// 打印双向链表
printf("双向链表：");
display();
return 0;
}
堆栈和队列
堆栈
堆栈（Stack）是一种数据结构，它是一种线性结构，具有后进先出（Last In First Out，LIFO）的特点。在堆栈中，最后压入堆栈的元素最先弹出，而最先压入堆栈的元素最后弹出。
堆栈有两个基本操作：push（压入）和pop（弹出）。push操作将一个元素压入堆栈的顶部，而pop操作则将堆栈顶部的元素弹出。除此之外，还有一个peek（查看）操作，它可以查看堆栈顶部的元素，但并不弹出。
堆栈可以用数组或链表来实现，常用的堆栈有顺序堆栈和链式堆栈。在顺序堆栈中，使用数组来存储堆栈元素；而在链式堆栈中，则使用链表来存储堆栈元素。
堆栈作为一种基本数据结构，有着广泛的应用，以下是堆栈的一些常见应用：
表达式求值：堆栈可以用于中缀表达式转换为后缀表达式，然后再利用堆栈求解后缀表达式的值，实现表达式求值。
函数调用：在程序执行时，每次函数调用时需要将当前的现场保护起来并压入堆栈，等到函数返回时再将现场弹出堆栈恢复，以实现函数调用栈的维护。
括号匹配：使用堆栈可以判断括号是否匹配。当扫描到左括号时，将其压入堆栈；当扫描到右括号时，从堆栈中取出栈顶元素进行匹配，若匹配则继续扫描，否则括号不匹配。
逆波兰表达式：逆波兰表达式（也称后缀表达式）可以使用堆栈实现求解，具体实现过程是遍历表达式中的每一个元素，若是数字则压入堆栈，若是操作符则从堆栈中取出相应的数字进行计算并将结果压入堆栈。
操作系统内存管理：操作系统中的内存分配和回收操作也是通过堆栈来实现的，将内存块压入空闲内存的堆栈中，当需要分配内存时，从堆栈中弹出最顶端的内存块并分配给程序。
队列
队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。队列中的元素只能在队列的一端插入（称为队尾），而只能从另一端删除元素（称为队头）。队列常常用于实现缓存、任务调度、消息传递等应用场景。
比较
堆栈（Stack）是一种后进先出（Last-In-First-Out，LIFO）的数据结构，元素的插入和删除都在同一端进行，这一端称为栈顶。可以将堆栈想象成一叠盘子，每当你往盘子里放一个盘子时，它会被放在盘子堆的最上面，而取盘子时也必须从最上面的盘子开始取。因此，堆栈的插入和删除操作都是在栈顶进行的。
队列（Queue）是一种先进先出（First-In-First-Out，FIFO）的数据结构，元素的插入在队尾进行，删除在队头进行。可以将队列想象成排队等候服务的人群，当一个人来到队列时，他会站在队尾等待服务，而服务员只会从队头开始为第一个人提供服务，因此，队列的插入操作是在队尾进行的，而删除操作是在队头进行的。
虽然堆栈和队列的数据操作顺序不同，但它们都可以使用数组或链表来实现。此外，一些数据结构的操作也可以使用堆栈或队列来实现，比如深度优先搜索可以使用堆栈，广度优先搜索可以使用队列。
数组和字符串
数组是一种由相同类型的元素组成的集合，可以通过索引（下标）来访问其中的元素。数组的特点是随机访问速度快，但在插入和删除操作时需要移动其他元素，时间复杂度为O(n)。
字符串是由一串字符组成的数据类型，通常用于表示文本。字符串的长度可以动态地改变，但其本质上是一个定长的字符数组。字符串也可以使用数组的方式进行访问和操作，例如取出某个字符、合并字符串等。但是字符串的操作需要考虑字符集编码的问题，以及涉及到的复杂度也可能高于数组操作
数组
当我们需要处理大量同种类型的数据时，使用数组是一种非常高效的方式。数组是一种线性的数据结构，其元素可以按照一定的顺序排列，并且每个元素可以通过一个索引（下标）来访问。在大多数编程语言中，数组的元素类型必须是相同的。
数组的特点有：
1.随机访问速度快：由于数组的元素在内存中是连续存储的，因此可以通过计算索引来直接访问指定的元素，速度非常快。
2.长度固定：数组的长度在创建时就已经固定了，不能在程序运行时改变。如果需要动态地添加或删除元素，则需要使用其他数据结构。
3.插入和删除操作效率低：由于数组的长度固定，当需要在数组中插入或删除元素时，需要将后面的元素都向后移动或向前移动，导致操作的时间复杂度为O(n)。
字符串
字符串是一种特殊的数组，它由一串字符组成，并且通常用于表示文本。在大多数编程语言中，字符串也被视为一种基本数据类型，具有自己的特殊语法和函数库。在C语言中，字符串实际上是以字符数组的形式存在的，其中最后一个字符是以NULL（'\0'）作为结束符的。
字符串的特点有：
动态长度：字符串的长度可以动态地改变，我们可以通过添加或删除字符来改变字符串的长度。
不可变性：字符串在创建后不能被修改，如果需要修改字符串，则需要创建一个新的字符串。
字符集编码问题：在处理字符串时，我们需要考虑字符集编码的问题，不同的字符集可能采用不同的编码方式，导致在处理字符串时需要做一些特殊的处理。
树和二叉树
二叉树的遍历
前序遍历（Preorder Traversal）
前序遍历是指先访问根节点，然后按照先左后右的顺序递归地遍历左子树和右子树。具体实现方式如下：
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
visit(root); // 访问根节点
preorderTraversal(root->left);// 递归遍历左子树
preorderTraversal(root->right);// 递归遍历右子树
}
中序遍历（Inorder Traversal）
中序遍历是指先按照先左后右的顺序递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。具体实现方式如下：
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left); // 递归遍历左子树
visit(root); // 访问根节点
inorderTraversal(root->right); // 递归遍历右子树
}
后序遍历（Postorder Traversal）
后序遍历是指先按照先左后右的顺序递归地遍历左子树和右子树，最后访问根节点。具体实现方式如下：
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left); // 递归遍历左子树
postorderTraversal(root->right); // 递归遍历右子树
visit(root); // 访问根节点
}
层序遍历（Level Order Traversal）
层序遍历是按照从上到下、从左到右的顺序逐层遍历每个节点。具体实现方式需要借助队列来实现，代码如下：
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
visit(node);
if (node->left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
}
}
其中 queue 是 C++ 标准库中的队列，visit 是访问节点的函数，具体实现方式可以根据具体问题而定。
递归与非递归
递归遍历二叉树是指通过函数递归的方式遍历树的每一个节点。递归遍历二叉树需要定义一个遍历函数，在函数中对当前节点进行遍历，然后递归调用函数遍历当前节点的左子树和右子树。递归遍历二叉树的代码相对简单，但由于递归的过程会增加函数调用的次数和栈空间的使用，可能会导致程序运行效率较低和栈溢出的问题。
非递归遍历二叉树是指通过循环的方式遍历树的每一个节点。非递归遍历二叉树需要借助栈这个数据结构来辅助遍历。以中序遍历为例，非递归遍历的过程如下：
首先从根节点开始遍历，将根节点入栈。
然后依次将根节点的左子树的节点入栈，直到遇到左子树为空的节点为止。
从栈中取出栈顶节点，遍历该节点，并将其右子树入栈。
重复步骤2和步骤3，直到栈为空。
非递归遍历二叉树的代码比递归遍历复杂，但由于避免了函数调用和栈空间的使用，因此效率更高。
树和森林
森林是多个树组成的集合，即多个树的并集。每个树被称为森林的一棵子树。森林中的树可以为空树。森林可以用于表示非连通的数据结构，比如在一个图中，每个连通分量可以看做一个树，将所有树合并成森林。
1 6 10
/ \ / \ / \
2 3 7 8 11 12
/ \ / \ / \
4 5 9 10 13 14
森林可以用来表示多个独立的树结构。例如，在一个公司的组织架构中，每个部门可以看作是一棵树，而这些部门之间可能并没有直接的关系，因此可以用森林来表示这种情况。又例如，在一张地图上，每个城市可以看作是一个节点，它们之间可能存在多条道路，每条道路可以看作是一个边，这样构成的图可能包含多个连通分量，也可以用森林来表示。
堆和优先权队列
优先队列是一种特殊的队列，其中元素被赋予优先级。当出队时，具有最高优先级的元素先被移除。优先级队列可以基于元素的任何属性排序，例如整数、浮点数、字符或其他自定义类型。在实际应用中，优先级队列经常用于实现调度算法和任务管理，其中需要考虑任务的优先级和处理顺序。
在编程中，优先级队列通常使用堆数据结构实现。堆是一种基于树的数据结构，其中每个节点都具有一个键值，并且具有以下特点：
堆总是一个完全二叉树。
有两种类型的堆：最大堆和最小堆。
最大堆的根节点具有最大的键值，而最小堆的根节点具有最小的键值。
所有非根节点都与它们的父节点相关联，并且根据所使用的特定算法进行排序。
使用堆来实现优先队列的主要原因是因为堆可以在$O(log n)$时间内进行插入、删除和获取最大/最小元素，而无需对队列进行排序。