简介严蔚敏《数据结构C语言版第2版》算法设计题答案与书中算法源码是一份面向高校计算机类专业学生及考研读者的学习资源。全部源码基于CLion开发并以CMake方式组织按说明部署后即可直接运行作者结合原书算法进行了优化逐条修正参考答案中的错误并对可能触发bug的边界条件、不同实现方法、优化思路与执行过程给出详细注释便于对照理解。压缩包整体约3.14MB内容以算法源代码与答案说明文档为主适合在复习链表、栈与队列、树、图、排序与查找等章节时配合阅读。已有1220人学习下载另附五本经典算法/数据结构书籍的获取链接存放在ReadMe.txt中可作为扩展阅读。1. 严蔚敏这本书的C语言算法源码为什么不能拿来就抄很多人第一次拿到《数据结构C语言版》第2版第一反应是把书上的算法源码和习题答案抄进实验报告里。我也抄过结果抄完还是一脸懵教材代码不是完整工程Status、ElemType、InitList这些宏和类型全书四处出现没有一个统一的头文件。算法设计题答案往往只给关键步骤真正到机器上跑链表初始化、队列判满这些细节立刻翻车。《数据结构》和《算法》是两个层面看书是理解思路把严蔚敏这本书里的C语言算法源码逐行跑成一个能编译的工程才是把“数据结构与算法”变成自己能力的过程。这篇笔记写给正在写数据结构实验报告、准备期末复习或考研408的人目标是让你能把书上的源码变成能编译能测试的C程序同时把算法设计题答案从“背”变成“写”。2. 把教材算法源码变成可编译工程目录结构、公共头文件与最小运行骨架2.1 为什么教材源码不能直接编译严蔚敏第2版里的代码风格和现在的工程代码差别很大。书中为了版面紧凑经常省掉类型定义和函数原型比如顺序表章节会写Status ListInsert_Sq(SqList *L, int i, ElemType e)但Status你要往前翻好几页才能看到它是typedef int Status;。ElemType更是全书没有统一有的章节是int有的章节是学生结构体甚至图、树章节里的VertexType也另成一套。这是《数据结构c语言版》教材的老传统它展示的是逻辑不是交付代码。很多人在网盘里找“严蔚敏数据结构c语言版pdf”或“数据结构严蔚敏c语言版pdf”拿到的电子书里代码同样是片段。我曾试过把第2章的顺序表代码整体复制到一个.c文件里直接编译报错超过20条主要就是三类缺少宏定义、缺少头文件、函数参数类型不一致。踩过这个坑之后我的习惯是不碰原书的排版自己造一个公共基础层再往上叠算法代码。这一层做得好不好直接决定后面每一个算法设计题答案能不能跑通。2.2 建立公共头文件Status、ElemType 与基本宏我先把这本书所有代码里反复出现的符号统一收进一个ds_base.h这个文件不需要很复杂能把编译跑通就行。下面这份是我自己一直在用的最小版本针对期末复习和实验报告足够#ifndef DS_BASE_H #define DS_BASE_H #include stdio.h #include stdlib.h #include string.h #include limits.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; /* 函数返回值状态 */ typedef int ElemType; /* 元素类型可按题目改成结构体 */ #define MAXSIZE 100 /* 顺序表 / 循环队列的容量 */ #endif这里把函数返回状态统一成Status把存储元素统一成ElemType下面是参数说明。ElemType这行决定你后面所有算法能处理什么数据我做实验报告时把它改过两次一次改成char *一次改成自定义学生结构体改完之后所有函数的形参不用动只要改赋值语句。MAXSIZE是顺序表和循环队列共用的容量做题保持100就够测大数据排序时再单独在你的测试文件里重新#define不要改动头文件默认值防止改了这里影响另一道题。提示头文件末尾的#endif不能丢C语言预处理器的#ifndef只在第一次包含时生效漏掉会让重复包含变得不可控。这个公共头文件是你自己的“后悔药”。书上的源码大概率不会给你这套基础定义但你有了它后面任何一道算法设计题都能快速套进一个统一工程而不是每个题目都重新发明一套Status。2.3 给顺序表补上最小运行骨架有了公共头文件下一步是把书里的顺序表代码片段整理成能编译的.c文件。“整理”不是改算法而是补三件事为SqList结构体补完整定义、为每个函数补前置声明、在main里按“初始化-插入-打印-删除-销毁”的顺序调用。下面是一个能跑的骨架#include ds_base.h /* 顺序表结构体严书中用SqList命名 */ typedef struct { ElemType *elem; int length; int listsize; } SqList; /* 函数前置声明 */ Status InitList_Sq(SqList *L); Status ListInsert_Sq(SqList *L, int i, ElemType e); Status ListDelete_Sq(SqList *L, int i, ElemType *e); void ListTraverse(SqList *L); /* 初始化 */ Status InitList_Sq(SqList *L) { L-elem (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); if (L-elem NULL) { return OVERFLOW; /* 内存不够 */ } L-length 0; L-listsize MAXSIZE; return OK; } /* 在第i个位置插入元素 */ Status ListInsert_Sq(SqList *L, int i, ElemType e) { if (i 1 || i L-length 1) { return ERROR; } if (L-length L-listsize) { return ERROR; /* 简易版不做扩容 */ } for (int j L-length; j i; j--) { L-elem[j] L-elem[j - 1]; } L-elem[i - 1] e; L-length; return OK; } /* 删除第i个元素用e带回删除的值 */ Status ListDelete_Sq(SqList *L, int i, ElemType *e) { if (i 1 || i L-length) { return ERROR; } *e L-elem[i - 1]; for (int j i; j L-length; j) { L-elem[j - 1] L-elem[j]; } L-length--; return OK; } void ListTraverse(SqList *L) { for (int i 0; i L-length; i) { printf(%d , L-elem[i]); } printf(\n); } int main(void) { SqList list; ElemType deletedValue; InitList_Sq(list); for (int i 1; i 5; i) { ListInsert_Sq(list, i, i * 10); } ListTraverse(list); ListDelete_Sq(list, 3, deletedValue); printf(deleted value %d\n, deletedValue); ListTraverse(list); free(list.elem); /* 不要漏掉 */ return 0; }这段代码的逻辑要点有两个。第一插入时元素后移的下标边界是L-length i往回走到i - 1这个边界是顺序表算法里最容易写错的地方写错一次就是数组越界或者丢失元素。第二ElemType *e这个形参用来把删除的值带回到调用方这正是C语言指针的典型用法。很多刚写完数据结构实验报告的人在这里卡住不理解为什么删除要传指针答案是函数参数按值传递不带地址就无法把结果带出去。main末尾的free(list.elem)也是必须的教材代码从不管内存释放但你连续初始化几个表之后再看内存占用就知道这个习惯多重要。我把这个骨架跑通之后再翻书里的归并、逆置、删除重复元素这些题会发现它们的实现都建立在这三件套上插入、删除、取元素。所以第二章做的工程不只是让样例跑起来而是后面每一道算法题答案的可执行测试平台。3. 算法设计题答案的实战写法线性表、栈队列、树、图、排序的5类高频题把算法设计题答案当背诵材料是最亏的复习方式。看到一个“删除顺序表中所有值为x的元素”就去背一遍考试时换一个边界就懵比如改成“把值为x的元素全部移到表尾”。所以这一章不按题目背按题型拆每一类给一个能编译的代码片段和一组边界参数。这五类在数据结构知识点总结里也是固定主线数据结构与算法的主干就是线性结构、树形结构、图形结构和排序查找。3.1 线性表删除重复元素的原地算法线性表是这本书遇到的第一大类算法设计题最常见要求是不开新数组原地删除有序顺序表中的重复元素。做法是快慢指针快指针遍历慢指针维护“已保留”部分的末尾。这道题常见变体是“无序表去重”那要先排序或者用额外标记数组但考试更常考有序表。下面是能跑的完整版本配两组测试数组#include ds_base.h int removeDuplicates(int arr[], int n) { if (n 0) { return 0; /* 空表直接返回 */ } int slow 0; /* slow指向已整理部分的最后一个下标 */ for (int fast 1; fast n; fast) { if (arr[fast] ! arr[slow]) { slow; arr[slow] arr[fast]; /* 把新元素搬到保留区后 */ } } return slow 1; /* 新表长度 */ } int main(void) { int testA[9] {1, 1, 2, 3, 3, 3, 4, 5, 5}; int testB[9] {1, 2, 3, 4, 5, 6, 7, 8, 9}; int lenA removeDuplicates(testA, 9); for (int i 0; i lenA; i) { printf(%d , testA[i]); } printf(\n); int lenB removeDuplicates(testB, 9); for (int i 0; i lenB; i) { printf(%d , testB[i]); } printf(\n); return 0; }这里slow和fast的下标语义决定整个算法对不对fast永远指向当前元素slow永远指向不重复序列的最后一个下标。只有arr[fast] ! arr[slow]时才递增slow并搬移连续的重复区间被整体跳过。时间复杂度O(n)只遍历一趟空间复杂度O(1)。这个思路在考研408真题里反复出现王道408的复习资料里也把这道题放在顺序表章节的第一梯队。3.2 栈与队列括号匹配的栈实现栈队列章节的算法设计题中括号匹配出现率最高因为考的就是栈的后进先出特性。标准流程是左括号入栈右括号看栈顶是否匹配匹配则弹出不匹配直接返回错误最后看栈空不空。下面是一个能在普通C环境跑通的版本栈用固定数组实现#include ds_base.h #define STACK_SIZE 100 typedef struct { char data[STACK_SIZE]; int top; /* top指向栈顶元素下标空栈为-1 */ } CharStack; void initStack(CharStack *s) { s-top -1; } int push(CharStack *s, char c) { if (s-top STACK_SIZE - 1) { return ERROR; } s-data[s-top] c; return OK; } int pop(CharStack *s, char *c) { if (s-top 0) { return ERROR; } *c s-data[s-top--]; return OK; } int isMatchingPair(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } int checkBrackets(const char *expr) { CharStack stack; initStack(stack); for (const char *p expr; *p ! \0; p) { if (*p ( || *p [ || *p {) { push(stack, *p); } else if (*p ) || *p ] || *p }) { char topChar; if (pop(stack, topChar) ERROR) { return ERROR; /* 右括号多了 */ } if (!isMatchingPair(topChar, *p)) { return ERROR; /* 类型不匹配 */ } } } return (stack.top -1) ? OK : ERROR; /* 左括号多了 */ } int main(void) { const char *s1 {[()()]}; const char *s2 {[(])}; const char *s3 ((()); printf(%s - %d\n, s1, checkBrackets(s1)); printf(%s - %d\n, s2, checkBrackets(s2)); printf(%s - %d\n, s3, checkBrackets(s3)); return 0; }代码里的top初始化为-1判空条件是top 0判满条件是top STACK_SIZE - 1这三处约定必须前后一致否则会出现“栈明明空了还能弹出数据”的错觉。括号匹配有一个很多答案不强调的细节不是拿右括号去整个栈里找匹配而是只比较栈顶元素。栈顶代表“最近一个尚未匹配的左括号”它不匹配说明嵌套关系已经破掉。这道题把栈的特性和函数调用栈的思维打通了理解了它后面树的非递归遍历会轻松很多。3.3 二叉树统计叶子节点数的递归写法树章节的算法设计题递归题几乎必考。第2版书的二叉树定义是BiTree指针加BiTNode结构体统计叶子数的递归式是“空树返回0左右孩子都空返回1否则返回左右子树叶子数之和”。翻译成C语言时边界判断的顺序比代码本身更重要#include ds_base.h typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; int countLeaves(BiTree root) { if (root NULL) { return 0; } if (root-lchild NULL root-rchild NULL) { return 1; } return countLeaves(root-lchild) countLeaves(root-rchild); }这个三行递归的边界顺序有讲究先判空再判叶子最后递归。如果把叶子判断放判空之前空指针解引用直接崩溃如果一进来就递归叶子节点会被当成内部节点继续向下访问空的左右孩子永远返回0。BiTree本身是BiTNode *的别名所以形参BiTree root本质是一个指针递归传入root-lchild时传的也是指针不需要额外的。树有关的题目只要递归函数能先写清楚“边界条件”后面通常只是翻译数学表达式。3.4 图邻接表的深度优先搜索骨架图的算法设计题在期末复习里出现频率不低但很多人被前置的邻接表结构体吓住。严蔚敏这本书给出的图结构体里包含顶点表、边表和访问标记数组单是补全定义就要写几十行。实际考试时如果只要求“写出DFS的递归函数”给出递归核心就行如果是实验报告才需要放进完整工程。下面给一个以邻接表为基础的最小DFS#include ds_base.h typedef struct ArcNode { int adjvex; /* 邻接点下标 */ struct ArcNode *next; } ArcNode; typedef struct VNode { char data; ArcNode *firstarc; } VNode, AdjList[10]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; void DFS(ALGraph *G, int v, int visited[]) { visited[v] 1; printf(%c , G-vertices[v].data); for (ArcNode *p G-vertices[v].firstarc; p ! NULL; p p-next) { int w p-adjvex; if (visited[w] 0) { DFS(G, w, visited); } } }这段代码的visited数组必须由调用方创建并清零递归函数自身不做清零因为一张图可能要多次遍历。参数上G-vertices[v].firstarc的链式遍历和链表操作完全一样区别只是节点里存的是邻接点下标adjvex。图算法题里DFS是很多问题的基础比如连通分量判断、拓扑排序的前驱遍历、用贪心思想写最小生成树都是在visited标记的基础上改。注意DFS不保证最短路径这个问题我在避坑章会专门讲。3.5 排序快速排序与归并排序的边界参数排序章节是数据结构排序算法里期末和面试最爱考的地方算法设计题答案里快速排序几乎是必写的。书上快速排序的核心是Partition下面用首元素做枢轴两侧交替填坑最后把枢轴放回low所指位置int Partition(int arr[], int low, int high) { int pivot arr[low]; while (low high) { while (low high arr[high] pivot) { high--; } arr[low] arr[high]; while (low high arr[low] pivot) { low; } arr[high] arr[low]; } arr[low] pivot; return low; } void QuickSort(int arr[], int low, int high) { if (low high) { int pivotIndex Partition(arr, low, high); QuickSort(arr, low, pivotIndex - 1); QuickSort(arr, pivotIndex 1, high); } }Partition里两个内层while必须都带low high条件否则两侧指针可能互相穿过这是快速排序数组越界的常见根因。相等元素处理上右边用、左边用相等的元素不会无限交换但分区可能不均衡快排本身就不是稳定排序这一点在答题时如果有空间值得主动写出。归并排序算法和它互补归并稳定但需要O(n)辅助空间递归边界是左半区[low, mid]、右半区[mid 1, high]漏掉那个1会直接导致死循环或越界。堆排序算法是另一套体系它依赖完全二叉树的数组表示建堆时从最后一个非叶子节点开始下沉如果题里说“要求O(1)辅助空间的稳定排序”那是个陷阱因为目前不存在同时满足这两个条件的比较排序。做算法设计题时建议先写清楚输入输出的类型和边界再动手写函数。很多算法与数据结构知识点归纳把题目按“线性表、栈队列、树、图、排序查找”五类分这五类在严蔚敏书中正好是第二章到第十一章的主线。按这个顺序练至少能保证每一类都有一份能跑的模板兜底。4. 递归与指针陷阱严蔚敏书里KMP、二叉树与快排的复现要点4.1 二级指针链表初始化为什么总是失败严蔚敏这本书里链表部分的参数写法是有历史包袱的。早期版本用LinkList *L第2版很多地方又改成了LinkList L读者自己抄代码时一会儿L一会儿L编译能过运行时链表永远是空。我在这里把最可靠的约定写一下当函数需要在链表头插入新节点时形参用LinkList *head当函数只是遍历或查找时形参用LinkList head。如果你只传一个链头指针进去函数内部给头节点赋了新值调用方的指针变量在函数返回后依然保持原样这是C语言参数按值传递的基本性质。#include ds_base.h typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; /* 头插法需要二级指针 */ int insertHead(LinkList *head, ElemType value) { LinkList newNode (LinkList)malloc(sizeof(LNode)); if (newNode NULL) { return OVERFLOW; } newNode-data value; newNode-next *head; *head newNode; return OK; } /* 遍历查找一级指针即可 */ int searchValue(LinkList head, ElemType value) { for (LinkList p head; p ! NULL; p p-next) { if (p-data value) { return OK; } } return ERROR; } int main(void) { LinkList head NULL; insertHead(head, 10); insertHead(head, 20); searchValue(head, 20); return 0; }参数说明insertHead(LinkList *head, ...)里的head是“指向头指针的指针”函数内写*head newNode才是修改调用方的头指针。调用时必须写insertHead(head, 10)漏掉编译器的警告通常只是“不兼容的指针类型”但运行结果会完全不对。当年我在数据结构学习阶段反复被这个细节折磨后来靠一句话记住函数要修改一个变量就传这个变量的地址要修改一个指针变量就传指针变量的地址。这比背任何“链表初始化模板”都管用。4.2 KMP算法next数组推导与匹配函数KMP算法是严蔚敏这本书里最考验概念理解的章节之一。很多复习资料只给匹配函数不给next数组怎么来的于是背了答案还是不会默写。先把next数组含义说清next[j]表示模式串第j位失配时模式串应回退到第next[j]位继续比较。不同教材下标起点不同下面代码用从0开始的下标习惯和书对照时看到1到2个位置的偏移是正常的#include ds_base.h #include string.h void getNext(const char *pattern, int next[]) { int i 0; int j -1; int len (int)strlen(pattern); next[0] -1; while (i len - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; } else { j next[j]; /* 回退KMP的精髓 */ } } } int kmpSearch(const char *text, const char *pattern) { int i 0; int j 0; int n (int)strlen(text); int m (int)strlen(pattern); int next[256]; getNext(pattern, next); while (i n j m) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; } } if (j m) { return i - j; } return -1; }这段代码里最难懂的是getNext中的j next[j]。它处理的情况是你想扩展“最长公共前后缀”但当前字符不匹配于是回退到一个更短的公共前缀继续比。比如模式串ABABC算到某一位时pattern[i]和pattern[j]不相等j回退到next[j]再试。实际写算法设计题答案时能写出KMP匹配过程通常能拿大部分分能把next数组的递推写对才是区分点。建议把next数组的推导过程在草稿纸上画两遍不要只盯着代码看。4.3 二叉树递归转非递归用栈模拟系统调用树章节常有一道变形题叫“不用递归实现中序遍历”。判定标准是看你能不能理解递归背后的调用栈。做法是用显式栈保存节点指针模拟系统栈的压入和弹出。中序非递归遍历的流程最清晰先反复向左走并把节点入栈走不动就弹栈输出再转向右子树。#include ds_base.h typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; typedef struct { BiTree data[100]; int top; } Stack; void inorderNoRecursion(BiTree root) { Stack stack; stack.top -1; BiTree current root; while (current ! NULL || stack.top 0) { while (current ! NULL) { stack.data[stack.top] current; /* 沿左子树入栈 */ current current-lchild; } if (stack.top 0) { current stack.data[stack.top--]; printf(%d , current-data); current current-rchild; /* 转向右子树 */ } } }这个写法里每个节点被压栈一次、弹出一次整体复杂度O(n)。和递归版本对比递归版本把栈藏在系统调用栈里这个版本把栈明着写出来。我做实验报告时把两种写法对照着画过一遍调用树之后非递归遍历就再也不用背模板了。同理快速排序的递归转非递归也可以用手动栈保存low和high来完成思路上和二叉树完全一致都是“把递归的隐含状态显式化”。如果你能自己写出这个转换说明你对递归的掌握已经不是背答案的水平。5. 教材源码与算法题答案的避坑清单5个复现时的翻车现场下面这些坑来自我啃这本书和做实验报告时的真实记录每一条都按“现象、原因、解决”展开。能避开这些复现速度至少快一倍。5.1 抄书代码缺少类型定义和大括号现象把书里的代码片段复制成单个.c文件编译报expected ; before }或unknown type name Status甚至有经验的编译报错连成一片根本看不出第一处错在哪。原因教材为了版面省略了类型定义、宏定义和函数尾部的部分写法答案代码往往只给核心循环体。第2版不是一份可以交付的完整C工程。解决先把#include ds_base.h放进每个文件把Status、OK、ERROR这些符号全部从公共头文件里拿再按“结构体定义—函数声明—函数实现—main测试”四段重组代码。重组时优先保函数体其次是参数列表最后才是宏定义。这样补大括号的工程量会小很多。5.2 边界条件写错插入位置和快排分区越界现象顺序表插入、快速排序、归并排序这类代码一运行就段错误或者不报错但输出结果乱掉。原因边界条件写错。顺序表插入循环for (j L-length; j i; j--)如果写成j i最后一个待移动位置漏掉数组元素错位。快排里内层while少了low high限制指针会穿透。解决动手前先用小数据在纸上走一遍。比如length5、第1个位置插入时j从5走到1还是从5走到2拿笔画一次就清楚。养成习惯后每写一个带下标的循环都问自己一句这个下标是闭区间还是开区间排序算法里高频翻车点几乎全是区间定义没统一。5.3 ElemType 和 Status 的跨章冲突现象把第2章的线性表代码、第9章的哈希表代码放进同一个工程编译警告刷屏甚至运行时读到错误数据。原因全书各章对ElemType、Status的定义不统一有的章节还额外定义了VertexType、KeyType。直接合并文件类型名冲突基本不可避免。解决一个工程只允许一个ElemType。不同章的数据类型不同就分开编译成多个可执行文件不要试图在一个main里全测。如果确实需要在一个工程里处理多种类型可以用typedef struct Student ...作为全局ElemType但这样整本书的代码都要适配改动量很大对做作业来说不值得。5.4 循环队列判空判满写反现象队列的算法题总是多入队一个元素或者明明没满却报队满出队后立即入队又算错。原因以牺牲一个存储单元为代价的写法中判空是front rear判满是(rear 1) % MAXSIZE front。两个条件搞混结果就是入队和出队的判断全部错位。解决先确认本道题采用的是“少用一个存储单元”的约定front指向队首元素rear指向队尾的下一个位置。判空、判满分别写成独立函数两个都测试。测试输入用三组空队列、填满MAXSIZE-1个元素、刚出队一个立刻入队一个。数据结构期末复习做简答题时这三个用例能直接帮你暴露理解上的偏差。5.5 用DFS求最短路径换个图就错现象图的最短路径题用DFS写小图测试是对的换个稍大的图结果不对但又说不出哪里错。原因DFS求出来的是“一条可达路径”不是“最短路径”。深度优先先深入第一次访问到目标时并不保证经过的边数最少。带权图更是如此DFS和最短路径没有任何保证关系。解决判断题目问的是“可达性”还是“最短值”。可达性用DFS或BFS都行无权图最短路径用BFS带权图非负用Dijkstra有负权边考虑贝尔曼-福德算法。不要试图给DFS加“剪枝算法”来硬改成最短路那是两个问题。笔试手撕代码时先把适用条件写出来再动手写算法能避免最伤的一类误用。5.6 scanf读字符时换行符残留现象写括号匹配或字符串逆序题目时有几组输入会“吞掉”后一次输入的字符。热词“c语言变量用%d输入一个字符后的值”反映的是同一个坑前面输入数字后按下的回车被后面的%c读走了。原因scanf(%c, ch)会把缓冲区里的换行符\n当作有效字符读入。这会让按字符读入的算法题在第二次输入开始集体翻车。解决读单个字符用scanf( %c, ch)前面的空格让scanf先跳过空白字符。处理单行字符串优先用fgets比如char line[128]; fgets(line, sizeof(line), stdin);它会把整行读进来再逐字符处理缓冲区不用担心残留换行。网上很多“字符串逆序c语言pta”的题目错误根源就是直接对fgets读进来的字符串做逆序时把末尾的\n和\0也一起翻了。6. 跑分验证与测试用例如何确认算法题答案没有白写算法题代码跑通一遍只能说明“这个输入下没崩”不说明算法实现是对的。我现在的习惯是为每个算法准备三组测试数据最短0个或1个元素、最怪全是相同元素、全部逆序、交替相等、最大接近容量上限。比如顺序表去重必须测[1,1,1]和[1,2,3]前者检验慢指针能不能正确停在最后后者检验没有重复元素时是否误删。排序算法要多测一个“已经有序”的输入因为快速排序在有序输入下如果不做优化会退化到O(n^2)这是数据结构排序算法复习资料里反复强调的边界。输入期望输出主要检查点空表[]长度0判空分支是否遗漏全重复[1,1,1]长度1慢指针推进逻辑无重复[1,2,3]长度3是否误删元素逆序[5,4,3,2,1]排序正确快排分区边界验证复杂度时用clock()包裹排序调用对比一个冒泡排序c语言实现和归并排序算法实现在十万条随机数据上的运行时间。如果归并排序没有明显快于冒泡通常是大坑比如每层递归都重新malloc辅助数组那时间全耗在内存分配上。把时间打印出来比单独测返回值更能暴露问题。数据量也别一上来就十万先一千、再一万逐步加哪一步突然慢出数量级哪一步就能看到复杂度拐点。我现在的习惯是每个算法设计题答案旁边都留一个main测试骨架里面只存三件事——输入数据、预期输出、实际输出。它们都在同一个文件里一年后再看还能一分钟跑起来。先写出每一步的中间状态打印再删掉调试输出这个简单的流程帮我抓住了很多书上答案没展开的边界。希望帮到你。本文还有配套的精品资源点击获取
