企业官网建设流程全解析

简介：这套资料精心整理了C语言数据结构与算法中的核心内容，从图、树等复杂存储结构（如邻接矩阵、邻接表、二叉树）到查找表、线性表、字符串处理，再到排序算法（冒泡、选择、插入、快速排序等）、外部排序、栈与队列以及数组和广义表，覆盖了课程教学与实践应用的常见主题。无论是初学者建立概念框架，还是程序员巩固算法功底、优化代码实现，都可从中获得扎实的参考价值。整个压缩包共含558个文件，体积约12.92MB，主要文件类型包括C语言源代码、Dev-C++工程文件、编译生成的可执行程序以及配套说明文档，便于直接阅读、运行和二次修改。目前已有1977人学习下载，特别适合作为教材配套资料或自学实战素材，帮助读者从原理到实现系统掌握数据结构与算法。

1. 数据结构与算法C语言：从严蔚敏教材到一行可运行代码之间的距离

《数据结构（C语言版）》常年挂在各大高校参考书单和考研408的考纲里，但很多人把它当理论书读完就放下，真正上机手撕代码时才露馅：链表反转写不顺、快排的 partition 边界每次都要试错、KMP 的 next 数组算出来总差一位。这份资源就是把严蔚敏那本教材里的伪代码和典型课后题，落成一套能直接编译运行的 C 语言工程，配套实验报告、习题解析和考点代码。它适合考研408和期末机试的备考者，也适合数据结构知识点背得熟、代码却写不利索的在职开发。数据结构与算法这门课，用 C 语言表达到今天依然是笔试和手撕代码的主流，先把代码落地，后面省的才是真时间。

2. 顺序表与链表：C语言数据结构的两个基础存储结构

顺序存储和链式存储是 C 语言数据结构的第一层分水岭。顺序表靠连续内存，链表靠指针把碎片节点串起来。考试里常问“顺序表插入平均移动多少元素”“链表能不能随机访问”，这些概念背一背就有，但真正动笔写代码时，顺序表扩容、单链表头插尾插、双向链表四指针操作，才是拉开差距的地方。下面逐段拆开这三块。

2.1 顺序表的动态扩容：realloc 的返回值必须拿新变量接

顺序表核心是三个字段：data 指针、length 和 capacity。容量不够时最直接的做法是 realloc，但网上不少示例代码写成了这种危险姿势：

list->data = (int*)realloc(list->data, newCap * sizeof(int));

这个写法在 realloc 失败时会返回 NULL，直接把原来的指针覆盖掉，之前的数据全部丢失。我一般用临时变量接住返回值：

#include <stdio.h> #include <stdlib.h> typedef struct { int *data; int length; int capacity; } SeqList; void initSeqList(SeqList *L, int cap) { L->data = (int*)malloc(cap * sizeof(int)); if (L->data == NULL) { exit(1); } L->length = 0; L->capacity = cap; } void expandSeqList(SeqList *L) { int newCap = L->capacity * 2; int *tmp = (int*)realloc(L->data, newCap * sizeof(int)); if (tmp == NULL) { printf("扩容失败，保持原容量\n"); return; } L->data = tmp; L->capacity = newCap; }

逻辑说明：先把 realloc 的返回值存进 tmp，判断非空后再赋给 L->data。realloc 成功时旧内存由运行时自动回收，不需要手动 free；失败时旧内存块原封不动，只是扩容没有生效。capacity 翻倍而不是加固定值，是为了把插入操作的平均时间复杂度摊到 O(1)，这是动态数组的通用设计。

参数说明：initSeqList 的 cap 是初始容量，我习惯开 4 或 8。扩容因子取 2 是时间换空间，工程里取 1.5 的也不少，主要是减少内存碎片。如果目标是嵌入式或内存受限环境，翻倍会导致分配失败概率上升，改成固定增量更合适。

2.2 单链表头插与尾插：反转和顺序构建的差别

单链表节点就是 data 加 next。头插法新节点永远插在头节点后面，尾插法需要维护一个尾指针。两者应用场景完全不同。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* createNode(int val) { Node* n = (Node*)malloc(sizeof(Node)); n->data = val; n->next = NULL; return n; } // 头插法：每步 O(1)，最终链表是输入序列的逆序 Node* insertHead(Node* head, int val) { Node* n = createNode(val); n->next = head; return n; } // 尾插法：需要 tail 指针，最终链表保持输入顺序 Node* insertTail(Node* head, Node** tail, int val) { Node* n = createNode(val); if (head == NULL) { head = n; } else { (*tail)->next = n; } *tail = n; return head; }

逻辑说明：头插法每次把新节点的 next 指向当前 head，再把 head 移到新节点，所以遍历结果的顺序和输入完全相反。单链表原地逆置就是按头插法的思路，一遍遍历加插入，不需要额外开数组。尾插法必须记录 tail，否则每次都要从头遍历到尾，插入退化成 O(n)。

参数说明：insertTail 的 tail 是二级指针，因为函数内部要修改 tail 指向的节点。很多人在这一步栽跟头，传一级指针进函数，跑完 tail 还是老值，根源是 C 语言的值传递，后面第 5 章单独展开。

2.3 双向链表插入删除：四个指针的先后顺序

双向链表每个节点有 prior 和 next。在 a 和 b 之间插入 p，需要操作四根指针，顺序错了就断链。

#include <stdio.h> #include <stdlib.h> typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode; // 在节点 a 后面插入节点 p void insertAfter(DNode* a, DNode* p) { p->next = a->next; // 第 1 步：p 先指向原后继 if (a->next != NULL) { a->next->prior = p; // 第 2 步：原后继的 prior 指回 p } a->next = p; // 第 3 步：a 的 next 指向 p p->prior = a; // 第 4 步：p 的 prior 指向 a }

逻辑说明：第 1 步和第 2 步必须在 a->next 被改写前完成。如果先执行 a->next = p，原来那个后继节点就找不到了，第 2 步操作的就不是原后继，链表直接断掉。删除节点同理，先让前驱的 next 指向后继、后继的 prior 指向前驱，再考虑 free 当前节点。

参数说明：insertAfter 默认 p 已经初始化，且 p 当前不在任何链表中。如果 p 之前挂在另一个链表里，需要先把它摘除，否则会出现两个链表共享一个节点，free 时造成重复释放。

3. 栈、队列与二叉树：递归和指针操作的结合部

栈和队列是限制存取位置的线性表，树是第一个非线性结构。C 语言里它们共同的难点在于判空条件、循环下标和递归调用栈的消耗。这三块在考试题里的出场率非常高，代码量不大但边界陷阱密集。

3.1 链式栈的 push 和 pop：中缀转后缀的骨架

栈分顺序栈和链式栈。顺序栈数组大小要提前定，链式栈节点动态分配，适合深度不确定的场景。

#include <stdio.h> #include <stdlib.h> typedef struct StackNode { char data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; } LinkedStack; void push(LinkedStack *s, char c) { StackNode *n = (StackNode*)malloc(sizeof(StackNode)); n->data = c; n->next = s->top; s->top = n; } int pop(LinkedStack *s, char *out) { if (s->top == NULL) { return 0; // 栈空 } StackNode *tmp = s->top; *out = tmp->data; s->top = tmp->next; free(tmp); return 1; }

逻辑说明：push 是把新节点的 next 指向当前栈顶，然后 top 走到新节点；pop 先把栈顶值取出来，top 下移，再 free 原栈顶。pop 用 int 返回成功与否，避免栈空时拿到无效的 out。中缀转后缀、括号匹配的题，核心就是用栈暂存运算符，遇到优先级低的运算符时把栈里优先级高的先弹出去。

参数说明：s 是指向链栈结构的指针。判空只看 top == NULL，不需要 base 指针。如果你在单片机这类 RAM 很小的环境里大量 push，每个 malloc 都会消耗堆空间并产生碎片，这就是“单片机c语言没有堆栈吗”这种问题背后的现实来源——MCU 的栈区本来就小，递归一深就溢出了。

3.2 循环队列：front 和 rear 的边界判断

顺序队列的致命问题是假溢出：rear 到数组末尾时，前面还有空位但数组“感觉”满了。解决方式是取模。

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int front; int rear; } CircularQueue; int isFull(CircularQueue *q) { return (q->rear + 1) % MAXSIZE == q->front; } int isEmpty(CircularQueue *q) { return q->front == q->rear; } int enqueue(CircularQueue *q, int val) { if (isFull(q)) { return 0; } q->data[q->rear] = val; q->rear = (q->rear + 1) % MAXSIZE; return 1; } int dequeue(CircularQueue *q, int *out) { if (isEmpty(q)) { return 0; } *out = q->data[q->front]; q->front = (q->front + 1) % MAXSIZE; return 1; }

逻辑说明：循环队列通过 (rear+1) % MAXSIZE 把 rear 从数组末尾绕回开头。判断队满用的是“牺牲一个存储单元”的方案，即 (rear+1)%MAXSIZE == front 就认为满，实际最多存 MAXSIZE-1 个元素。队空直接用 front == rear。这两条边界条件就是循环队列考试题的全部考点。

参数说明：MAXSIZE 是数组物理长度。如果你想让队列真正用满 MAXSIZE，必须加一个 size 字段记录当前元素个数，否则空和满都会表现为 front == rear，这是最常见的困惑点。BFS 遍历二叉树或图时用队列也是这套结构，只是 data 换成节点指针。

3.3 二叉树的递归遍历与非递归：调用栈是底层逻辑

二叉树节点定义和遍历代码很简短，但很多人看得懂递归，自己写就懵。核心是抓住“空树就是递归基”。

#include <stdio.h> #include <stdlib.h> typedef struct BTNode { int data; struct BTNode *left; struct BTNode *right; } BTNode; void preOrder(BTNode *root) { if (root == NULL) { return; } printf("%d ", root->data); // 先访问根 preOrder(root->left); // 再遍历左子树 preOrder(root->right); // 最后遍历右子树 } void inOrder(BTNode *root) { if (root == NULL) { return; } inOrder(root->left); printf("%d ", root->data); inOrder(root->right); } void postOrder(BTNode *root) { if (root == NULL) { return; } postOrder(root->left); postOrder(root->right); printf("%d ", root->data); }

逻辑说明：三种遍历的差别只有一条 printf 的位置。先序在递归左子树之前打印，中序在左子树递归完之后打印，后序在两个子树都处理完才打印。非递归版本本质上是用显式栈模拟这些递归调用返回的位置。考研常考“用栈实现中序遍历”，原理是先把根和整条左链入栈，左到底就出栈访问，再转向右子树。

参数说明：root == NULL 时的 return 就是递归基，缺少它函数会无限递归直到栈溢出。前面说的 MCU“没有堆栈”疑问，本质就是递归深度耗尽栈空间。工程上你可以用队列和循环代替递归，或者把递归改成非递归遍历来规避。

3.4 哈夫曼树与编码：每次选两个最小权值

哈夫曼树每次从集合里取两个最小权值节点合并，重复 n-1 次，最后带权路径长度最小。C 实现里最简单的选择方式就是两轮比较。

#include <stdio.h> #include <stdlib.h> #define INF 10000 // 在 weights 中选两个最小下标，跳过 used 标记的节点 void selectTwo(int *weights, int *used, int n, int *min1, int *min2) { int m1 = INF, m2 = INF; *min1 = *min2 = -1; for (int i = 0; i < n; i++) { if (used[i]) continue; if (weights[i] < m1) { m2 = m1; *min2 = *min1; m1 = weights[i]; *min1 = i; } else if (weights[i] < m2) { m2 = weights[i]; *min2 = i; } } }

逻辑说明：selectTwo 维护一个最小值和一个次小值。每轮选完以后，把两个旧节点标记为 used，把合并后的新权值写回数组，继续下一轮。整个过程执行 n-1 次。这里 INF 是兜底哨兵值，保证空位不会参选。

参数说明：n 是叶子节点数量，哈夫曼树总节点数固定是 2n-1。这个性质考试常考，题目告诉你叶子有 100 个，树的总节点一定是 199。用数组实现哈夫曼树比指针省事，节点间关系用数组下标表达即可，王道数据结构教材里也是这套思路。

4. 图与排序与查找：邻接表、快速排序和 KMP 的三个硬骨头

图的遍历、快速排序、KMP 三块内容，是数据结构里最容易“觉得会了但一写就出错”的部分。问题都集中在边界条件：图的 visited 标记时机、快排 partition 的左右指针、KMP 的 next 数组回退语义。

4.1 图的邻接表存储：BFS 用队列，DFS 用递归

邻接表是“顶点数组 + 每条边一个链表节点”。BFS 需要队列记录待访问顶点，DFS 可以借助递归访问未访问的相邻顶点。

#include <stdio.h> #include <stdlib.h> #define MAXV 100 typedef struct EdgeNode { int adjvex; // 邻接点的下标 struct EdgeNode *next; } EdgeNode; typedef struct { int data; // 顶点数据 EdgeNode *firstEdge; // 第一条边 } VertexNode; typedef struct { VertexNode vertices[MAXV]; int numVertices, numEdges; } Graph; void DFS(Graph *g, int v, int *visited) { visited[v] = 1; printf("%d ", v); for (EdgeNode *e = g->vertices[v].firstEdge; e != NULL; e = e->next) { if (!visited[e->adjvex]) { DFS(g, e->adjvex, visited); } } }

逻辑说明：visited 数组在进入节点时立刻置 1，防止在环上绕圈。DFS 沿一条边递归到底再返回，BFS 则用队列把当前顶点的所有邻居先访问完，再往下一层推进。BFS 实现就是把 DFS 的递归换成“入队、出队、邻居入队”三步。

参数说明：邻接表适合稀疏图，邻接矩阵适合稠密图。稀疏图用矩阵会浪费大量空间，但判断两点是否直接相连只要查一个下标。时间复杂度和空间复杂度的分析题里，邻接表和邻接矩阵的差别主要就是这一条。

4.2 快速排序：partition 的边界条件决定生死

快速排序是面试手撕代码出场率最高的排序算法。C 语言实现里最典型的是 Hoare 分区，两个指针从两端往中间移动。

#include <stdio.h> void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } int partition(int *arr, int low, int high) { int pivot = arr[low]; int i = low, j = high; while (i < j) { while (i < j && arr[j] >= pivot) j--; if (i < j) { arr[i] = arr[j]; i++; } while (i < j && arr[i] <= pivot) i++; if (i < j) { arr[j] = arr[i]; j--; } } arr[i] = pivot; return i; } void quickSort(int *arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }

逻辑说明：partition 固定取 low 位置的值为基准 pivot。j 从右往左找比 pivot 小的值填到左边空位，i 从左往右找比 pivot 大的值填到右边空位，最后 i 和 j 相遇的位置就是 pivot 的最终位置。quickSort 递归处理左右两段。注意两个内层 while 都带 i < j 条件，少了它 j 会一路越过 i，数组被覆盖出界，这是快排最常见的段错误来源。

参数说明：这个写法把 pivot 存到临时变量，用“挖坑填数”避免每步都 swap。如果 pivot 选在中间位置，需要先和 low 交换再开始移动。尾递归优化版本会把短边递归、长边循环，那是工程优化，考试手撕用基础版就够。和冒泡排序比，快排每轮不是简单把最大值沉底，而是同时确定一个元素的最终位置，平均复杂度降到 O(n log n)。数据结构排序算法这块，快排是最值得先写熟的一个。

4.3 KMP 算法：next 数组的计算一个字母都不能错

KMP 是那种看懂了觉得很简单、自己写就翻车的算法。核心是 next 数组，表示匹配失败时模式串要回退到的位置。

#include <stdio.h> #include <string.h> void getNext(const char *p, int *next) { int m = strlen(p); int j = 0, k = -1; next[0] = -1; while (j < m - 1) { if (k == -1 || p[j] == p[k]) { j++; k++; next[j] = k; } else { k = next[k]; } } } int kmpSearch(const char *s, const char *p) { int i = 0, j = 0; int n = strlen(s), m = strlen(p); int next[100]; getNext(p, next); while (i < n && j < m) { if (j == -1 || s[i] == p[j]) { i++; j++; } else { j = next[j]; } } if (j == m) { return i - j; // 匹配起始位置 } return -1; }

逻辑说明：getNext 里初始 k = -1、next[0] = -1。k == -1 表示没有公共前后缀，此时模式串直接移到开头。匹配时失配就令 j = next[j]，主串下标 i 不回退，这是 KMP 相比朴素匹配省时间的原因。当 j == -1 时也走 i++; j++，代表模式串开头和主串当前字符都匹配不上，主串前进一个字符。

参数说明：next 数组有不同语义版本。这里用的是“失配时模式串从位置 next[j] 重新比较”，next[0] = -1。王道408教材和不少考试用的是 next[0] = 0 那一版，两种只差一位。换版本时必须保证 getNext 和 kmpSearch 用同一套语义，否则结果一定错。

5. C语言数据结构避坑指南：指针传参、内存泄漏和输入缓冲的实测记录

这一章是我实际调试数据结构和算法代码时踩过、翻车过的记录，每一条都按“现象 → 原因 → 解决”写清楚，可以直接对照排查。

5.1 指针参数传不进去：值传递陷阱

现象：在函数里给链表头节点赋值、malloc 之后函数返回，调用方打印 head 还是 NULL。 原因：C 语言参数是值传递。head 指针本身也只是个变量，传进函数的是它的拷贝；函数里修改 head 修改的是拷贝，调用方的 head 变量没有变化。 解决：需要修改指针变量本身时，传二级指针。典型场景是头插法的头节点更新，以及“让栈顶变化”的函数。

// 错误：传一级指针，函数内修改 head 无效 void initList(Node *head, int val) { head = (Node*)malloc(sizeof(Node)); head->data = val; head->next = NULL; } // 正确：传二级指针 void initListCorrect(Node **head, int val) { *head = (Node*)malloc(sizeof(Node)); (*head)->data = val; (*head)->next = NULL; }

逻辑说明：正确版本里 *head = malloc 修改的是调用方那个指针变量本身，函数返回后 head 地址有效。如果只是修改指针指向的内容，比如 p->data = 100，一级指针就够了，因为 p 指向的对象是同一个。判断标准很简单：函数内是否要改变指针变量本身的值，要改就上二级指针。

5.2 malloc 与 free 不配对：内存泄漏的客观存在

现象：程序跑起来没问题，连续运行多次后内存占用只涨不降；用 valgrind 一查，整堆“definitely lost”。 原因：分配了节点但忘了释放，或者 free 链表头节点时把其余节点链搞断，剩下节点成了孤儿。最常见的写法是循环里每次 malloc 新对象，跳出循环时没有把所有节点逐个 free。 解决：养成习惯，写完 insert 马上写配套的销毁函数。释放单向链表时必须先把 next 存下来再 free 当前节点，否则 free 之后 next 字段已不可访问。

void freeList(Node *head) { Node *cur = head; while (cur != NULL) { Node *tmp = cur->next; free(cur); cur = tmp; } }

逻辑说明：tmp 先保存下一跳，free 之后再移动 cur。如果先 free(cur) 再 cur = cur->next，访问的是已释放内存，属于未定义行为，大多数情况下程序会跑飞或崩溃。双链表释放还要注意先摘除前驱后继关系，避免重复释放同一块内存。

5.3 scanf 和 getchar：回车符是隐藏的坑

现象：用 scanf("%c", &c) 读字符，预期输入 a 然后 b，结果读到的是换行符，程序总少读一个字符。 原因：scanf 的 %c 不跳过空白字符，前面输入数字后回车会残留在输入缓冲里，被 %c 直接读走。 解决：在 %c 前加一个空格，或者用 getchar() 把缓冲里的回车吃掉。字符串逆序、字符统计这类题经常被它卡住。

char a, b; scanf("%c %c", &a, &b); // %c 前面留空格，跳过空白字符

逻辑说明：scanf 的 %c 前加空格，会让它跳过包括换行在内的所有空白字符，这样 b 拿到的才是真正的字符。用 getchar() 清缓冲要小心它会阻塞等待输入，有些程序卡死就是因为在等一个永远不来的回车。

5.4 递归深度过大导致栈溢出

现象：二叉树退化成链表之后，递归遍历直接段错误，甚至程序没反应就退出。 原因：递归每次调用都在调用栈上压一帧，深度达到几百上千层时栈空间耗尽。前面说的“单片机c语言没有堆栈吗”这类疑问，本质就是栈区太小，递归深度一高就爆。 解决：改用显式栈或队列做非递归遍历。考试里不让用递归时，这套写法必须手熟。

void preOrderNoRec(BTNode *root) { BTNode *stack[100]; int top = -1; if (root != NULL) { stack[++top] = root; } while (top >= 0) { BTNode *node = stack[top--]; printf("%d ", node->data); if (node->right != NULL) { stack[++top] = node->right; } if (node->left != NULL) { stack[++top] = node->left; } } }

逻辑说明：栈里先压右子树再压左子树，出栈时左子树先被访问，正好模拟先序递归的顺序。这样把函数递归调用变成了循环里的显式压栈，深度不再受系统调用栈限制。如果树特别深，stack 数组大小也要跟着调大，或者改成链式栈。

6. 把数据结构代码跑起来：gdb、valgrind 和随机化验证

写数据结构的最大错觉是“代码看起来对”。真正跑起来，段错误、输出多一个空格、排序结果不对，各种问题全冒出来。我的习惯是每写完一个数据结构，立刻用三件套验证。

6.1 gdb：打断点看链表节点和指针

编译时加 -g 保留调试符号，然后进 gdb 打断点，直接 print 指针指向的结构体。

gcc -g -o list list.c gdb ./list break printList run print head->data print head->next->data

gdb 的 print 能直接看到链表节点里的字段值。链表断链问题，用 print head->next 就能看出哪一跳断了。比瞎改代码加日志快得多。

6.2 valgrind 和随机化用例：让内存问题和边界问题现形

内存问题用 valgrind 跑一遍：

valgrind --leak-check=full --show-leak-kinds=all ./list

malloc 出来的节点没释放、free 之后又访问，valgrind 会逐行报出 “definitely lost” 和 “Invalid read”。排序算法多用随机数据验证：顺序数组、逆序数组、大量重复元素各跑一遍。快速排序碰到全等数组会反复递归原地打转，直到栈溢出，这是隐藏最深的边界问题。排序和查找这类算法，用随机输入验证正确性，比对着答案看代码可靠得多。

有一回我调链表头插法，纸上推演完全没问题，一跑就段错误。最后是 gdb 打印每次循环后的 head 和节点地址，发现少了一次 p = p->next 的更新。从那以后，我每次写完链表、树、图，都强制自己用 gdb 加 valgrind 走一遍，已经成了条件反射。希望帮到你。

本文还有配套的精品资源，点击获取