简介：这份数据结构课程设计项目面向高校计算机相关专业学生及C语言进阶学习者，围绕单链表、栈、队列、二叉树与图五种结构，通过多级菜单集成创建、插入、删除、查找、遍历等基本操作，并延伸到一元多项式、表达式求值、客房分配、二叉排序树、拓扑排序等典型应用，适合课设参考、实验验收准备与知识串联复习。压缩包共28个文件，约500KB，以C/C++头文件和源文件为核心，配合Visual Studio解决方案、工程配置及编译中间文件，便于直接打开运行和按模块拆解。已有1716人学习下载，作为课程设计案例具备一定参考价值。读者可据此梳理五种结构的接口设计、菜单集成与模块组织方式，理解工程配置和调试产物的对应关系，并在此基础上替换应用案例或扩展功能，减少从零搭建课设框架的时间。
1. 数据结构课程设计（C语言实现）：从一份源码包到可改可跑的练手底座
课程设计周前一天，某开发者从下载包里翻出这份 C语言实现的数据结构课程设计，第一反应是“能跑就行”，结果打开源码发现所有函数都挤在 main.c 里，加一个链表节点要翻三百行。它给出的是一套拆开的结构：线性表、栈与队列、二叉树、图以及排序查找放在独立的头文件和源文件里，Makefile 把编译串成一条命令，示例数据从命令行参数或 data 目录读入。
适合两类人：刚学完数据结构、要交课程设计但不想从零搭工程的学生，以及工作几年后想回头把 C 语言指针和边界条件再摸一遍的开发者。整套代码不依赖第三方库，gcc 加 make 就能编译，改起来也不需要先读懂整个仓库。
2. 工程结构拆解：头文件、源文件与 Makefile 怎么排
先看目录。课程设计最容易翻车的地方不是算法写错，而是工程没分层，改一处牵动全身。常见做法是按“声明、实现、入口、测试、数据”五块切：
course-design-c/ ├── Makefile ├── README.md ├── include/ │ ├── list.h │ ├── stack_queue.h │ ├── tree.h │ ├── graph.h │ └── sort.h ├── src/ │ ├── list.c │ ├── stack_queue.c │ ├── tree.c │ ├── graph.c │ ├── sort.c │ └── main.c ├── tests/ │ ├── test_list.c │ ├── test_tree.c │ └── test_graph.c └── data/ └── edges.txtinclude 里只放结构体定义、宏常量和函数声明，让调用方看头文件就知道接口长什么样；src 里放具体实现；main.c 只做命令行参数解析和演示流程，不写算法；tests 里每个测试文件是独立可执行程序，只链接它要测的那个实现文件，比如 test_list.c 只链 src/list.c，这样不会和 main.c 撞入口；data 目录放邻接矩阵或边表的输入样例。
2.1 头文件该写什么、不该写什么
新手最容易把头文件写成第二个源文件：直接在 list.h 里把函数体写了，然后 list.c 又写一遍，链接时立刻报 multiple definition。我一般会在头文件里只保留三样东西：类型定义、宏、函数原型。像下面这样：
#ifndef LIST_H #define LIST_H #include <stddef.h> typedef struct { int *data; size_t size; size_t cap; } SeqList; /* 返回值约定：0 成功，-1 参数错误，-2 内存不足 */ int seqlist_init(SeqList *list, size_t cap); int seqlist_push_back(SeqList *list, int value); int seqlist_insert(SeqList *list, size_t pos, int value); int seqlist_erase(SeqList *list, size_t pos); void seqlist_destroy(SeqList *list); #endif#ifndef这一组是三行保护，防止同一个头文件被重复包含。#include <stddef.h>是给size_t用的，别在头文件里随手 include 一堆用不到的库，编译变慢还是小事，循环依赖才是真麻烦。函数原型上的返回值注释很重要，C 语言没有异常，调用方只能靠返回码判断，提前写清楚能省掉后面大量猜测。
2.2 Makefile：一条命令把工程编出来
课程设计项目文件不多，手写 gcc 命令也能过，但一旦加了测试文件就会漏。用 Makefile 的好处是源文件列表由通配符自动收集，新增 .c 文件不用改编译命令：
CC = gcc CFLAGS = -Wall -Wextra -std=c11 -g -O0 -Iinclude SRC = $(wildcard src/*.c) OBJ = $(SRC:.c=.o) TARGET = app all: $(TARGET) $(TARGET): $(OBJ) $(CC) $(CFLAGS) -o $@ $^ %.o: %.c $(CC) $(CFLAGS) -c $< -o $@ test_list: tests/test_list.c src/list.c $(CC) $(CFLAGS) -o $@ $^ clean: rm -f $(OBJ) $(TARGET) test_list .PHONY: all cleanCFLAGS里每一项都有用：-Wall -Wextra打开常用警告，能在编译期拦住大部分未初始化变量和类型不匹配；-std=c11固定语言标准，避免不同机器上默认标准不一样；-g保留调试符号，后面用 gdb 看崩溃位置靠它；-O0关掉优化，调试时变量的值不会被优化器藏起来；-Iinclude让#include "list.h"能找到头文件。$(wildcard src/*.c)收集所有源文件，$(SRC:.c=.o)把后缀替换成 .o。$@是目标名，$^是所有依赖，$<是第一个依赖。
编出来之后跑演示：
make clean make ./app list ./app graph data/edges.txtclean目标先删旧产物，避免上次编译失败留下的 .o 文件混进来。./app的第一个参数是子命令，第二个参数是可选的数据文件路径。main.c 里就按这个约定解析：
#include <stdio.h> #include <string.h> #include "list.h" int main(int argc, char **argv) { if (argc < 2) { fprintf(stderr, "usage: %s <list|graph> [file]\n", argv[0]); return 1; } if (strcmp(argv[1], "list") == 0) { SeqList list; if (seqlist_init(&list, 4) != 0) return 2; for (int i = 1; i <= 5; i++) seqlist_push_back(&list, i); for (size_t i = 0; i < list.size; i++) printf("%d ", list.data[i]); printf("\n"); seqlist_destroy(&list); /* 有 init 就必须有 destroy */ } return 0; }argv[1]是子命令字符串，argv[2]是文件路径。缺少参数时打印 usage 并返回 1，这种习惯在课程设计答辩时很加分，评审一眼能看出入口做了异常处理。seqlist_init返回非 0 时直接退出，因为后面所有操作都依赖初始化成功。
3. 线性结构核心实现：顺序表、链表、栈与队列的接口约定
线性结构是整个课程设计的地基。顺序表和链表写顺了，后面的树、图、排序都是在这套内存管理习惯上搭起来的。这一章把四个结构的实现拆开讲，重点放在边界检查、扩容和释放上。
3.1 顺序表与单链表：内存分配与边界检查
顺序表的核心是动态数组。初始化时给一个初始容量，插入时容量不够就翻倍，删除时把后面的元素整体前移。实现放在 src/list.c：
#include "list.h" #include <stdlib.h> #include <string.h> int seqlist_init(SeqList *list, size_t cap) { if (list == NULL || cap == 0) return -1; list->data = (int *)malloc(cap * sizeof(int)); if (list->data == NULL) return -2; list->size = 0; list->cap = cap; return 0; } static int seqlist_grow(SeqList *list) { /* 翻倍前先判断会不会溢出 size_t */ if (list->cap > (size_t)-1 / 2 / sizeof(int)) return -2; size_t new_cap = list->cap * 2; int *new_data = (int *)realloc(list->data, new_cap * sizeof(int)); if (new_data == NULL) return -2; /* 失败时原指针仍然有效 */ list->data = new_data; list->cap = new_cap; return 0; } int seqlist_push_back(SeqList *list, int value) { if (list == NULL) return -1; if (list->size == list->cap) { int rc = seqlist_grow(list); if (rc != 0) return rc; } list->data[list->size++] = value; return 0; } int seqlist_insert(SeqList *list, size_t pos, int value) { if (list == NULL || pos > list->size) return -1; if (list->size == list->cap) { int rc = seqlist_grow(list); if (rc != 0) return rc; } /* 从 pos 开始整体后移一位，必须从后往前拷贝 */ memmove(&list->data[pos + 1], &list->data[pos], (list->size - pos) * sizeof(int)); list->data[pos] = value; list->size++; return 0; } void seqlist_destroy(SeqList *list) { if (list == NULL) return; free(list->data); list->data = NULL; list->size = 0; list->cap = 0; }参数说明：seqlist_init的cap是初始容量，传 0 直接拒绝；seqlist_push_back不设上限，扩容失败返回 -2，此时原数据仍在，调用方可以降级处理；seqlist_insert的pos允许等于size，表示插在末尾，大于size属于越界。memmove而不是memcpy，是因为源区间和目标区间重叠，memcpy在重叠时行为未定义。seqlist_destroy里把指针置空，是为了让重复调用 destroy 不会二次释放崩溃，这是血泪经验。
单链表这边，我一般会带一个哨兵节点。不带哨兵时删头节点要单独写一段 if，带哨兵后所有插入删除逻辑统一：
#include <stdlib.h> typedef struct ListNode { int value; struct ListNode *next; } ListNode; ListNode *list_create(void) { ListNode *head = (ListNode *)malloc(sizeof(ListNode)); if (head == NULL) return NULL; head->next = NULL; /* 哨兵节点，value 不参与业务 */ return head; } int list_insert_after(ListNode *node, int value) { if (node == NULL) return -1; ListNode *new_node = (ListNode *)malloc(sizeof(ListNode)); if (new_node == NULL) return -2; new_node->value = value; new_node->next = node->next; /* 先接后 */ node->next = new_node; /* 再断前 */ return 0; } void list_destroy(ListNode *head) { while (head != NULL) { ListNode *next = head->next; free(head); head = next; } }list_insert_after的两个赋值顺序不能反：先让新节点指向原来的后继，再把前驱指向新节点。反过来的话，node->next已经被覆盖，新节点会指向自己，遍历直接死循环。list_destroy先保存next再free，因为 free 之后就不能再从节点里读字段了。
3.2 栈与队列：数组和链式两种落地
栈用数组写最简单，top表示下一个可写位置：
#define STACK_CAP 64 typedef struct { int data[STACK_CAP]; int top; } Stack; void stack_init(Stack *s) { s->top = 0; } int stack_push(Stack *s, int value) { if (s->top >= STACK_CAP) return -1; /* 栈满 */ s->data[s->top++] = value; return 0; } int stack_pop(Stack *s, int *out) { if (s->top <= 0) return -1; /* 栈空 */ *out = s->data[--s->top]; return 0; }top指向下一个空位，所以压栈是“先写后加”，出栈是“先减后读”。stack_pop用出参out把值带出来，返回码只表示成功失败，这样空栈时调用方不会拿到一个随机值。固定容量 64 是课程设计的常见简化，元素超过 64 个就要改宏或者换成动态扩容。
队列用循环数组，空一格来判断满，这样不用额外计数器：
typedef struct { int *data; int front; int rear; int cap; /* 实际分配 cap + 1 个位置 */ } Queue; int queue_init(Queue *q, int cap) { q->data = (int *)malloc((cap + 1) * sizeof(int)); if (q->data == NULL) return -2; q->front = 0; q->rear = 0; q->cap = cap + 1; return 0; } int queue_push(Queue *q, int value) { int next = (q->rear + 1) % q->cap; if (next == q->front) return -1; /* 队满 */ q->data[q->rear] = value; q->rear = next; return 0; } int queue_pop(Queue *q, int *out) { if (q->front == q->rear) return -1; /* 队空 */ *out = q->data[q->front]; q->front = (q->front + 1) % q->cap; return 0; }queue_init的cap是业务容量，内部多分配一格作为空位，q->cap存的是分配格数。判满用(rear + 1) % cap == front，判空用front == rear，两个条件不会打架。取模运算在元素很多时是性能热点，课程设计规模用不着优化，先保证逻辑对。
4. 树与图模块：二叉树遍历、邻接矩阵与最短路入口
树和图是课程设计里代码量最大的两块，也是最容易在答辩时被问“你的非递归遍历怎么写的”“图的无穷大怎么表示”的地方。这一章把树和图各拆一个核心实现出来。
4.1 二叉树的递归与非递归遍历
二叉搜索树的插入天然递归，新值与根比较，小往左、大往右：
#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int value; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode *tree_insert(TreeNode *root, int value) { if (root == NULL) { TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); if (node == NULL) return NULL; node->value = value; node->left = NULL; node->right = NULL; return node; } if (value < root->value) root->left = tree_insert(root->left, value); else if (value > root->value) root->right = tree_insert(root->right, value); return root; /* 相等时不做插入，避免重复值破坏树结构 */ }参数说明：返回新根指针，内存不足时返回 NULL，调用方必须检查。相等值直接跳过，这是课程设计里比“允许重复”更容易讲清楚的做法，要支持重复给节点加一个count字段就行。
非递归中序遍历用显式栈把递归调用栈模拟出来：
void inorder_iter(TreeNode *root) { TreeNode *stack[64]; int top = 0; TreeNode *cur = root; while (cur != NULL || top > 0) { while (cur != NULL) { stack[top++] = cur; /* 一路向左压栈 */ cur = cur->left; } cur = stack[--top]; /* 弹栈访问 */ printf("%d ", cur->value); cur = cur->right; /* 转向右子树 */ } }cur是当前走到的节点，内层 while 一直走到最左，外层弹栈访问后转向右子树。栈用固定数组 64，树退化成链时深度会超过 64，这是固定栈的典型翻车点；要么把 64 调大，要么用动态数组，答辩前最好自己造一棵偏斜的树测一下。
4.2 图的邻接矩阵与最短路入口
课程设计的图大多用邻接矩阵，节点数不大，写起来直观：
#include <limits.h> #define MAXV 64 #define INF 0x3f3f3f3f typedef struct { int n; int edge[MAXV][MAXV]; } Graph; void graph_init(Graph *g, int n) { g->n = n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g->edge[i][j] = (i == j) ? 0 : INF; } void graph_add_edge(Graph *g, int u, int v, int w) { if (u < 0 || v < 0 || u >= g->n || v >= g->n) return; g->edge[u][v] = w; g->edge[v][u] = w; /* 有向图删掉这一行 */ } void dijkstra(const Graph *g, int src, int dist[]) { int visited[MAXV] = {0}; for (int i = 0; i < g->n; i++) dist[i] = g->edge[src][i]; dist[src] = 0; visited[src] = 1; for (int k = 1; k < g->n; k++) { int u = -1, best = INF; for (int i = 0; i < g->n; i++) if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; } if (u == -1) break; /* 剩余节点不可达 */ visited[u] = 1; for (int v = 0; v < g->n; v++) if (!visited[v] && g->edge[u][v] != INF && dist[u] + g->edge[u][v] < dist[v]) dist[v] = dist[u] + g->edge[u][v]; } }INF用0x3f3f3f3f而不是INT_MAX，因为两个INF相加会溢出成负数，松弛判断直接失效；0x3f3f3f3f + 0x3f3f3f3f还在 int 范围内。dist数组由调用方分配，长度至少为g->n，Dijkstra 结束后它就是源点到各点的最短距离，不可达的点仍然是INF。graph_add_edge里带了下标检查，传错节点编号时直接忽略，不会写坏内存。
5. 常见问题排查：跑不起来、结果不对、内存泄漏怎么定位
这一章是我自己踩过、也见过别人踩的五个坑，按现象、原因、解决写。
5.1 链接报 multiple definition ofseqlist_init
现象：编译阶段都过了，链接时提示multiple definition of 'seqlist_init'。
原因：函数体写在了 list.h 里，或者 Makefile 的测试目标用了wildcard src/*.c，把带 main 的 src/main.c 也链进了测试程序，两个 main 撞在一起。
解决：头文件只留原型，实现归 .c；测试目标显式指定源文件，比如test_list: tests/test_list.c src/list.c，不要图省事用通配符。
5.2 realloc 之后程序随机崩溃
现象：往顺序表里插几十个元素后段错误，gdb 里栈帧显示的地址很怪。
原因：扩容时realloc可能把整块内存搬到新地址，代码某处还缓存了旧的list->data指针，扩容后再写就是往已释放的内存里写。
解决：所有对数据的访问都走list->data，不在局部变量里长期保存；seqlist_grow里先判空再赋值，扩容失败返回错误码而不是继续用旧指针。
5.3 循环队列跑到 cap - 1 个元素就满了
现象：初始化容量 10，只放了 9 个元素就入队失败。
原因：空一格判满的约定下，实际可用容量就是cap，也就是分配了cap + 1格时只能存cap个，这是设计选择不是 bug，但初始化和判满的逻辑必须一致。
解决：初始化时分配cap + 1并在结构体里记录cap + 1，判满用(rear + 1) % cap == front；如果业务要求正好cap个，就给 Queue 加一个count字段，用计数判空判满。
5.4 Dijkstra 输出负数或 0
现象：不可达节点打印出来是负数，或者松弛后的距离明显不对。
原因：INF定义成INT_MAX，做dist[u] + edge[u][v]时溢出成负数，随后负数被当作更短距离写入dist。
解决：#define INF 0x3f3f3f3f，两个 INF 相加不会溢出；松弛前先用g->edge[u][v] != INF把不可达边挡掉。
5.5 Windows 下 make clean 报 rm 不是内部命令
现象：在命令提示符里执行make clean，提示rm不是可识别的命令。
原因：Makefile 里写的rm -f是 POSIX shell 命令，命令提示符不认。
解决：用 MSYS2 或 MinGW 提供的 make 环境执行，或者给 clean 加分支，Windows 下用del /Q，或者干脆把编译和清理都放进 WSL 里跑。跨平台问题别硬扛，环境统一最省时间。
6. 二次开发改造：加一个模块、补测试、把课程设计改成可复用组件
拿到这套代码之后，最自然的二次开发是加一个哈希表模块。步骤不复杂，但顺序很重要：先写 include/hash.h 定义接口和返回码约定，再写 src/hash.c，最后在 Makefile 的SRC通配符下自动被收进去，不需要改编译规则。
我一般会把元素类型先抽出来：
/* include/hash.h 片段 */ #ifndef HASH_H #define HASH_H #include <stddef.h> typedef int HashKey; typedef struct HashNode { HashKey key; int value; struct HashNode *next; /* 链地址法解决冲突 */ } HashNode; typedef struct { HashNode **buckets; size_t bucket_count; size_t size; } HashMap; int hashmap_init(HashMap *map, size_t bucket_count); int hashmap_put(HashMap *map, HashKey key, int value); int hashmap_get(const HashMap *map, HashKey key, int *out); void hashmap_destroy(HashMap *map); #endif这里把HashKey用typedef单独命名，是为了以后从int换成char *时只改一处，而不是全仓库搜int key。课程设计规模用int够了，但接口留出这层抽象，二次开发时不用推倒重来。
补测试比加功能更值得先做。tests 目录里每个测试文件自带 main，直接用断言跑：
/* tests/test_list.c 片段 */ #include <assert.h> #include "list.h" int main(void) { SeqList list; assert(seqlist_init(&list, 2) == 0); for (int i = 0; i < 100; i++) assert(seqlist_push_back(&list, i) == 0); assert(list.size == 100); assert(seqlist_insert(&list, 0, -1) == 0); assert(list.data[0] == -1); seqlist_destroy(&list); return 0; }assert失败会直接 abort 并打印行号，比肉眼看输出可靠得多。把测试目标写进 Makefile，提交前固定跑一遍。再进一步可以开内存检查：
gcc -std=c11 -g -fsanitize=address,undefined -Iinclude src/*.c -o app_san ./app_san graph data/edges.txt-fsanitize=address会抓越界读写和释放后使用，-fsanitize=undefined抓整数溢出和空指针解引用。课程设计里这两个问题最隐蔽，答辩前跑一次能省掉现场演示崩溃的尴尬。
从那以后我每次新增模块，都强制先补一个最小测试文件再写实现，哪怕只测 init 和 destroy 两个函数。测试先行的习惯比多写一个算法更值钱。希望这套拆法能帮到你。
本文还有配套的精品资源，点击获取
