寒假学习总结

整个寒假都走在数据结构与算法的路上，深入学习了其中多个板块，刷了一些与之对应的题目，下面来一期总结（c）

（emmm，主播在寒假试着去学习了几大语言的语法基础（丢丢） 如Java c++ python，从中感受自己真正热爱的语言是谁，已经确定好岗位与语言，408  语言基础以及岗位技术栈的学习会提上日程）

一.搜索算法：深度优先搜索（DFS）与广度优先搜索（BFS）是图和树遍历的基本算法。

DFS常用于找寻所有可能解，BFS常用于求最短路径

1. 迷宫问题：在求解迷宫中从起点到终点的路径问题时，DFS 和 BFS 都可使用。DFS 会沿着一条路径一直深入探索，直到无法继续或找到终点，若走错则回退尝试其他路径，优点是代码实现相对简单，递归性强，能快速找到一条可行路径，但可能不是最短路径；BFS 从起点开始逐层向外扩展，先访问距离起点近的点，因此当找到终点时，走过的路径就是最短路径，缺点是需要维护队列来存储待访问的节点，空间复杂度相对较高。
2. 图的遍历：对于给定的图，要求遍历图中所有节点。比如在社交网络关系图中，要访问所有用户节点。DFS 从一个起始节点开始，递归访问其邻接节点，能快速深入探索图的结构，适合对图的连通性判断等；BFS 则从起始节点开始，逐层访问其邻居节点，可用于计算节点间的最短距离或寻找最小步数问题。
3. 连通分量查找：在一个无向图中，需要找出所有的连通分量。DFS 可以从图中任意一个未访问的节点出发，递归地访问其所有连通的节点，标记已访问的节点，直到所有节点都被访问过，每一次从新的未访问节点开始的 DFS 过程都能找到一个新的连通分量；BFS 同样从一个未访问节点开始，使用队列逐层扩展访问其邻居节点，当队列为空时，一个连通分量查找完成，重复此过程直到所有节点被访问。
4. 棋盘问题：在棋盘上的棋子移动问题，如八皇后问题、马走日等。以马走日为例，DFS 可以通过递归尝试马的每一种可能走法，直到找到目标位置或遍历完所有可能，能快速探索各种走法组合；BFS 则按照马的走法规则，从起始位置开始逐层扩展，记录每个位置的步数，当找到目标位置时，记录的步数就是最少步数。

两种算法在题目中各具优势 各具缺点。

ok，讲完两种搜索算法，来看它们具体实现，DFS通常使用栈实现而与之对应的BFS则由队列实现，所以现在来到数据结构的版块

二.数据结构：栈，队列，散列表（哈希表），二叉树。（c语言无具体函数，手动实现）

栈:栈是一种后进先出的数据结构，只允许在一端进行操作（入栈，出栈）

1. 栈的应用
   • 括号匹配问题：例如判断一个字符串中的括号（如圆括号、方括号、花括号）是否匹配。可以使用栈来解决，遍历字符串，遇到左括号时将其压入栈中，遇到右括号时检查栈顶元素是否为对应的左括号，如果是则将栈顶元素弹出，否则括号不匹配。遍历结束后，如果栈为空，则说明括号完全匹配，否则不匹配。比如对于字符串 “([{}])”，就可以通过栈来判断其括号是匹配的。
   • 表达式求值：在计算中缀表达式（如 “3 + ( 4 * 2 - 1)”）的值时，可以使用两个栈，一个用于存储操作数，一个用于存储操作符。遍历表达式，遇到操作数就压入操作数栈，遇到操作符时，根据操作符的优先级与栈顶操作符比较，若当前操作符优先级低或相等，则从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符进行计算，并将结果压入操作数栈，重复此过程直到遍历结束。最后操作数栈中剩下的元素就是表达式的值。
   • 函数调用和递归模拟：在一些需要模拟函数调用过程或递归过程的题目中，可以使用栈来记录函数调用的参数、局部变量等上下文信息。例如在实现一个简单的递归算法的非递归版本时，通过栈来保存需要回溯的状态。

栈的基本功能代码实现

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100// 定义栈的结构体
typedef struct Stack {int top;int data[MAX_SIZE];
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1;
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否已满
int isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}// 入栈操作
void push(Stack *s, int value) {if (isFull(s)) {printf("Stack is full!\n");return;}s->data[++(s->top)] = value;
}// 出栈操作
int pop(Stack *s) {if (isEmpty(s)) {printf("Stack is empty!\n");return -1;}return s->data[(s->top)--];
}// 获取栈顶元素
int peek(Stack *s) {if (isEmpty(s)) {printf("Stack is empty!\n");return -1;}return s->data[s->top];
}

队列：队列是一种先进先出的数据结构，允许在头部出队列，尾部入队列

1. 队列的应用
   • 广度优先搜索（BFS）：在图或树的遍历中，BFS 算法使用队列来存储待访问的节点。从起始节点开始，将其加入队列，然后不断从队列中取出节点，访问该节点，并将其未访问的邻居节点加入队列，直到队列为空。例如在迷宫问题中，求从起点到终点的最短路径，可以使用 BFS 结合队列来实现。
   • 任务调度：假设有一个多任务处理系统，任务按照到达的顺序依次进入队列，系统从队列头部取出任务进行处理，这就是典型的队列应用。比如打印机的任务队列，打印任务按照提交的先后顺序依次打印。
   • 滑动窗口问题：在一些数组相关的题目中，如求滑动窗口内的最大值或最小值，可以使用队列（双端队列）来实现。通过维护队列中元素的顺序，使其满足窗口内元素的相关要求，从而高效地解决问题。例如，对于数组 [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小为 3，使用双端队列可以在 O (n) 的时间复杂度内求出每个窗口内的最大值。

队列基本功能代码实现

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100// 定义队列的结构体
typedef struct Queue {int front;int rear;int data[MAX_SIZE];
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = q->rear = -1;
}// 判断队列是否为空
int isQueueEmpty(Queue *q) {return q->front == -1;
}// 判断队列是否已满
int isQueueFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}// 入队操作
void enqueue(Queue *q, int value) {if (isQueueFull(q)) {printf("Queue is full!\n");return;}if (q->front == -1) {q->front = q->rear = 0;} else {q->rear = (q->rear + 1) % MAX_SIZE;}q->data[q->rear] = value;
}// 出队操作
int dequeue(Queue *q) {if (isQueueEmpty(q)) {printf("Queue is empty!\n");return -1;}int value = q->data[q->front];if (q->front == q->rear) {q->front = q->rear = -1;} else {q->front = (q->front + 1) % MAX_SIZE;}return value;
}// 获取队头元素
int frontElement(Queue *q) {if (isQueueEmpty(q)) {printf("Queue is empty!\n");return -1;}return q->data[q->front];
}

散列表：又称哈希表，是根据键（key）直接访问值（value)的数据结构，通过一个哈希函数将键映射到表中一个位置来访问记录，时间复杂度能达到o（1）

最简单的一个哈希函数 hash(key)=key,那么如果由两个键生成到同一个哈希值，这时就会产生哈希冲突，通常办法为取模运算hash(key)=key%(table_size),还会使用线性探测减少哈希冲突，还有更多更好减少哈希冲突的方法，由于主播没学，就不过多讲解

下面是哈希表基础功能的实现

KeyValue hashTable[HASH_SIZE];// 简单的哈希函数
unsigned int hash(int key1, int key2)
{return ((unsigned long long)key1 * 1000000007 + key2) % HASH_SIZE;
}// 插入或更新键值对
void insert(int key1, int key2, int value)
{unsigned int index = hash(key1, key2);// 线性探测解决哈希冲突while (hashTable[index].isOccupied && (hashTable[index].key1 != key1 || hashTable[index].key2 != key2)){index = (index + 1) % HASH_SIZE;}// 若该位置未被占用，标记为已占用if (!hashTable[index].isOccupied){hashTable[index].isOccupied = 1;hashTable[index].key1 = key1;hashTable[index].key2 = key2;}// 更新值hashTable[index].value = value;
}// 根据键查找值
int find(int key1, int key2) 
{unsigned int index = hash(key1, key2);unsigned int start = index;// 线性探测查找键值对while (hashTable[index].isOccupied) {if (hashTable[index].key1 == key1 && hashTable[index].key2 == key2){return hashTable[index].value;}index = (index + 1) % HASH_SIZE;// 若回到起始位置，说明未找到if (index == start){break;}}return 0;
}

二叉树 ：二叉树是一种树形数据结构，每个节点最多有两个子节点，通常被称作左子节点和右子节点。

二叉树遍历方式有

先序遍历：

// 前序遍历
void preOrder(TreeNode* root) {if (root != NULL) {printf("%d ", root->data);preOrder(root->left);preOrder(root->right);}
}

中序遍历：

// 中序遍历
void inOrder(TreeNode* root) {if (root != NULL) {inOrder(root->left);printf("%d ", root->data);inOrder(root->right);}
}

后序遍历：

// 后序遍历
void postOrder(TreeNode* root) {if (root != NULL) {postOrder(root->left);postOrder(root->right);printf("%d ", root->data);}
}

 emmmm，还有已知中序与二之一求另一，看主播以前的文章

三.算法思想：DP 二分 并查集

1.动态规划是一种通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算，从而解决复杂问题的算法策略。它通常适用于具有重叠子问题和最优子结构性质的问题。

2.二分查找是一种在有序数组中查找特定元素的高效算法。它通过将数组分成两部分，每次比较中间元素与目标元素的大小，然后根据比较结果缩小查找范围，直到找到目标元素或确定目标元素不存在。时间复杂度为O（log n）

3.并查集是一种用于处理不相交集合的合并与查询问题的数据结构。它支持两种主要操作：

• 合并（Union）：将两个不相交的集合合并为一个集合。
• 查找（Find）：确定一个元素所属的集合。

   四。图论算法

最小生成树算法：prime与kruskal（主播只学过kruskal）

实现步骤

将图中的所有边按照权值从小到大进行排序：可以使用快速排序、归并排序等排序算法，将边按照权值升序排列。

1. 初始化一个空的边集合作为最小生成树：这个集合初始时不包含任何边。
2. 依次遍历排序后的边：对于每条边，如果将其加入到当前的边集合中不会形成环，则将该边加入到边集合中；否则，跳过这条边。
3. 重复步骤 3：直到边集合中的边数等于顶点数减 1，此时边集合构成的就是图的最小生成树。

kruskal的简单实现

#include <stdio.h>#define MAX_VERTICES 100
#define MAX_EDGES 100// 定义边的结构体
typedef struct {int src, dest, weight;
} Edge;// 定义图的结构体
typedef struct {int V, E;Edge edges[MAX_EDGES];
} Graph;// 比较函数，用于 qsort 按边的权值从小到大排序
int compare(const void *a, const void *b) {Edge *edge1 = (Edge *)a;Edge *edge2 = (Edge *)b;return edge1->weight - edge2->weight;
}// 查找元素所在的集合
int find(int parent[], int i) {while (parent[i] != i) {i = parent[i];}return i;
}// 合并两个集合
void unionSets(int parent[], int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);parent[xroot] = yroot;
}// Kruskal 算法实现
void kruskalMST(Graph *graph) {int V = graph->V;Edge result[MAX_VERTICES - 1];  // 存储最小生成树的边int e = 0;  // 最小生成树的边数int i = 0;  // 当前遍历的边的索引// 按边的权值从小到大排序qsort(graph->edges, graph->E, sizeof(Edge), compare);// 为每个顶点分配一个集合int parent[MAX_VERTICES];for (int v = 0; v < V; ++v) {parent[v] = v;}// 遍历排序后的边while (e < V - 1 && i < graph->E) {Edge next_edge = graph->edges[i++];int x = find(parent, next_edge.src);int y = find(parent, next_edge.dest);// 如果加入这条边不会形成环，则加入最小生成树if (x != y) {result[e++] = next_edge;unionSets(parent, x, y);}}// 输出最小生成树的边printf("最小生成树的边集合：\n");int total_weight = 0;for (i = 0; i < e; ++i) {printf("(%d - %d) 权值: %d\n", result[i].src, result[i].dest, result[i].weight);total_weight += result[i].weight;}printf("最小生成树的总权值: %d\n", total_weight);
}int main() {Graph graph;graph.V = 4;  // 顶点数graph.E = 5;  // 边数// 添加边graph.edges[0].src = 0;graph.edges[0].dest = 1;graph.edges[0].weight = 10;graph.edges[1].src = 0;graph.edges[1].dest = 2;graph.edges[1].weight = 6;graph.edges[2].src = 0;graph.edges[2].dest = 3;graph.edges[2].weight = 5;graph.edges[3].src = 1;graph.edges[3].dest = 3;graph.edges[3].weight = 15;graph.edges[4].src = 2;graph.edges[4].dest = 3;graph.edges[4].weight = 4;// 调用 Kruskal 算法kruskalMST(&graph);return 0;
}

 

这个寒假的学习让我在数据结构与算法领域取得了显著进步。理论与实践结合，提升了我的问题解决能力和编程技巧。未来，我将继续深入学习高级算法和数据结构，如线段树、树状数组等，并参与更多算法竞赛，提升自己的算法水平。相信这段学习经历会为我今后的学习和工作打下坚实的基础，激励我在计算机科学领域不断探索前行。