简介这份资源是湖南科技大学计算机科学与工程学院第二学期数据结构课程设计报告面向正在修读数据结构课程、需要完成课设或复盘算法实验的本科生。报告以docx文档形式呈现压缩包内共1个文件约234KB内容按项目名称、内容与目的、项目分析与总体设计、数据结构和算法实现、算法分析、项目小结等模块组织目录结构清晰。报告覆盖复杂度分析、Josephus问题、单词检查、后缀表达式求值、二叉树创建与文本显示、表达式树创建与输出、24点游戏、推箱子游戏等经典题目并给出顺序表、二叉排序树、Hash表、循环链表、栈与队列、广度与深度优先搜索等多种实现思路。已有581人学习下载适合需要参考完整课设框架、算法分析写法与实验报告排版的读者也可作为数据结构期末复习与算法入门的辅助材料。1. 从一份课设文档说起数据结构到底要落地哪些东西每年到了期末总有一批同学被一份叫“湖南科技大学数据结构课设.docx”的文件卡住。文件名看着平平无奇打开之后往往是四五道大题约瑟夫环、线性表操作、二叉排序树、表达式求值、排序算法对比。很多人第一反应是去搜“数据结构c语言版答案”或者翻出严蔚敏那本教材对着目录找代码。但真正动手才发现课设不是把书上的伪代码抄一遍就能过的——它要求你从零搭出可编译、可运行、能演示、能讲清楚时间复杂度的完整程序。这份课设的本质是一次对线性表、栈、树、排序这几类核心结构的集中实战。它不考你背概念考的是你能不能把“逻辑结构”翻译成“存储结构”再用C语言把操作函数一个个写出来。适合谁看正在做课设的本科生、准备408数据结构代码题的考研人、以及想用C语言把基础结构重新捋一遍的开发者。下面我按课设里最常见的几个模块把选型理由、实现步骤和参数设置拆开讲尽量让每一段都能直接对应到你文档里的那道题。2. 约瑟夫环与线性表从数组到循环链表的选型与实现2.1 为什么约瑟夫环优先用循环链表而不是数组约瑟夫环的经典描述是n个人围成一圈从第k个人开始报数报到m的人出列然后从下一个人继续报数直到所有人出列。课设里通常要求输出出列顺序。用数组做不是不行但每次删除一个人都要移动后续元素时间复杂度是O(n²)。更麻烦的是“圈”的语义——数组下标走到末尾要手动取模回到0边界判断容易写错。循环链表天然就是一个圈删除节点只需要改两个指针出列操作的时间复杂度是O(1)整体O(n·m)只花在报数遍历上。我一般会先跟学生确认课设是否要求“不带头结点的循环链表”。湖南科技大学这份文档里线性表部分往往要求带头结点但约瑟夫环单独成题时不带头结点更直观。下面给的是不带头结点的版本n个人依次插入尾节点的next指向首节点。#include stdio.h #include stdlib.h typedef struct Node { int id; // 人的编号从1开始 struct Node *next; } Node; // 创建n个人的循环链表返回首节点 Node* createCircle(int n) { if (n 0) return NULL; Node *head (Node*)malloc(sizeof(Node)); head-id 1; head-next head; // 先自己成环 Node *tail head; for (int i 2; i n; i) { Node *p (Node*)malloc(sizeof(Node)); p-id i; p-next head; // 新节点指向首节点 tail-next p; // 旧尾节点指向新节点 tail p; // 更新尾节点 } return head; } // 从start开始报数报到m出列打印出列顺序 void josephus(Node *head, int k, int m) { if (!head) return; Node *prev head; while (prev-next ! head) prev prev-next; // prev指向head的前驱 // 先移动到第k个人 for (int i 1; i k; i) { prev head; head head-next; } while (head-next ! head) { // 只剩一个节点时停止 for (int i 1; i m; i) { prev head; head head-next; } printf(%d , head-id); prev-next head-next; // 删除head free(head); head prev-next; // 从下一个人继续 } printf(%d\n, head-id); free(head); } int main() { int n 8, k 3, m 4; Node *head createCircle(n); josephus(head, k, m); return 0; }这段代码里createCircle用尾插法建环tail始终指向最后一个节点保证新节点插入后环不断。josephus里prev的作用是记录待删除节点的前驱因为单链表删除必须知道前一个节点。报数循环for (int i 1; i m; i)走m-1步此时head正好指向第m个人。参数k表示从第几个人开始报数m是报数上限。如果课设要求从第1个人开始把k设为1即可。注意free(head)之后不要再访问head-id必须先保存head-next再释放。很多同学在这里翻车程序跑着跑着就段错误。2.2 线性表课设题的通用骨架顺序表与链表的操作对照课设里的线性表题目通常要求实现插入、删除、查找、遍历、求长度、合并两个有序表。顺序表和链表各写一套然后对比。顺序表用数组加length字段链表用带头结点的单链表。顺序表插入的核心是判断pos合法性然后把pos之后的元素整体后移一位。链表插入则是找到pos-1位置的节点改指针。删除同理。查找和遍历两者逻辑一致只是访问方式不同。我建议把公共操作抽成函数指针或者宏但课设通常要求分开写那就老老实实写两套。关键参数是pos的取值范围顺序表是1 pos length1链表是1 pos length1但链表找pos-1时如果pos1前驱就是头结点。这个边界在课设答辩时经常被问到。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; // 顺序表插入在pos位置插入xpos从1开始 int seqInsert(SeqList *L, int pos, int x) { if (pos 1 || pos L-length 1) return 0; // 位置非法 if (L-length MAXSIZE) return 0; // 表满 for (int i L-length; i pos; i--) { L-data[i] L-data[i - 1]; // 后移 } L-data[pos - 1] x; L-length; return 1; }顺序表插入的时间复杂度是O(n)因为平均要移动一半元素。链表插入是O(1)不考虑查找前驱的时间但查找第pos个位置是O(n)。课设报告里通常要求写出这两种结构在不同操作下的时间复杂度对比表下面这个表可以直接用。操作顺序表带头结点单链表按位查找O(1)O(n)按值查找O(n)O(n)插入O(n)O(n)含查找前驱删除O(n)O(n)含查找前驱求长度O(1)O(n)需遍历提示如果课设要求“合并两个有序顺序表”用双指针从后往前填可以避免额外空间但需要第一个表有足够容量。从前往后填则需要新数组空间换时间。2.3 约瑟夫环的边界参数与调试方法约瑟夫环最容易出错的地方是k和m的边界。如果k1表示从首节点开始报数上面的代码里for (int i 1; i k; i)不会执行head仍指向首节点正确。如果m1表示每次报数到1就出列for (int i 1; i m; i)也不执行直接删除当前head然后head prev-next。但此时prev还是head的前驱删除后prev-next已经指向新head所以head prev-next是对的。调试时建议先用n5, k1, m2手动推一遍出列顺序2, 4, 1, 5, 3。如果程序输出不是这个就在while循环里加printf打印当前head-id和prev-id看指针有没有走错。另一个常见问题是建环时忘了把尾节点指向首节点导致prev-next ! head永远成立死循环。如果课设要求用数组模拟那就开一个visited数组标记出列用count累计报数index循环取模。数组版代码短但删除语义不如链表直观答辩时容易被问“为什么不用链表”。3. 栈与队列表达式求值和合法出栈序列判定3.1 用栈实现中缀表达式转后缀并求值课设里栈的题目通常有两类一是括号匹配二是表达式求值。表达式求值一般要求先转后缀再计算。中缀转后缀的规则是遇到操作数直接输出遇到左括号入栈遇到右括号弹栈直到左括号遇到运算符如果栈顶运算符优先级不低于当前运算符就弹栈输出然后当前运算符入栈。优先级表和-为1*和/为2(为0。下面用两个栈实现一个存操作数一个存运算符直接边转边算省去输出后缀的步骤。#include ctype.h #include string.h #define MAX 100 int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; // 左括号 } // 从栈顶取两个操作数计算结果压回操作数栈 void apply(int *num, int *topNum, char *op, int *topOp) { int b num[(*topNum)--]; int a num[(*topNum)--]; char o op[(*topOp)--]; int r 0; switch (o) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r a / b; break; } num[(*topNum)] r; } int evaluate(char *s) { int num[MAX], topNum -1; char op[MAX], topOp -1; for (int i 0; s[i]; i) { if (isdigit(s[i])) { int val 0; while (isdigit(s[i])) { val val * 10 (s[i] - 0); i; } i--; num[topNum] val; } else if (s[i] () { op[topOp] (; } else if (s[i] )) { while (topOp 0 op[topOp] ! () { apply(num, topNum, op, topOp); } topOp--; // 弹出左括号 } else { // 运算符 while (topOp 0 priority(op[topOp]) priority(s[i])) { apply(num, topNum, op, topOp); } op[topOp] s[i]; } } while (topOp 0) { apply(num, topNum, op, topOp); } return num[topNum]; }这段代码里num和op是两个独立栈topNum和topOp分别指向栈顶。apply函数从num弹出两个数注意先弹的是右操作数b后弹的是左操作数a因为栈是后进先出。evaluate主循环里遇到数字要连续读取多位所以用while (isdigit(s[i]))累加然后i--抵消外层for的i。遇到右括号时弹运算符直到左括号但左括号本身不参与计算最后topOp--把它弹掉。参数方面输入字符串不能有空格所有数字按整数处理。如果课设要求支持浮点数把int改成doubleisdigit换成strtod。如果要求支持多位数和负数负数需要在转后缀前特殊处理或者用#标记。注意priority函数里左括号返回0所以当栈顶是左括号时priority(op[topOp]) priority(s[i])不成立不会误弹左括号。这个细节很多同学写错导致括号匹配失败。3.2 合法出栈序列判定的模拟法另一道高频题是给定入栈序列1,2,3,...,n判断某个出栈序列是否合法。比如入栈1,2,3,4,5出栈4,5,3,2,1合法出栈4,3,5,1,2不合法。判定方法是模拟用一个栈按入栈序列依次压栈每次压栈后检查栈顶是否等于出栈序列当前元素如果相等就弹出出栈序列指针后移继续检查栈顶。最后如果栈空且出栈序列走完就是合法。int check(int *in, int *out, int n) { int stack[MAX], top -1; int j 0; // out的下标 for (int i 0; i n; i) { stack[top] in[i]; // 入栈 while (top 0 stack[top] out[j]) { top--; // 弹出 j; } } return (top -1 j n); }in是入栈序列out是待判定的出栈序列n是长度。j始终指向out中下一个待匹配的元素。每次压栈后只要栈顶等于out[j]就弹出并j。循环结束后如果栈空且jn说明出栈序列合法。这个算法的时间复杂度是O(n)因为每个元素最多入栈一次、出栈一次。空间复杂度O(n)。课设里如果要求输出所有合法出栈序列那就需要用回溯但通常只要求判定一个序列模拟法足够。提示如果入栈序列不是1到n而是任意整数模拟法同样适用只要in和out是同一组数的排列。判定前可以先检查两个序列的元素是否一致不一致直接返回0。3.3 栈的两种存储方式在课设中的取舍栈可以用顺序栈或链栈。顺序栈用数组加top指针操作简单但容量固定。链栈用单链表头插法入栈头删法出栈容量不限但每个节点多一个指针开销。课设里如果题目没有明确要求我一般建议用顺序栈因为代码短、调试方便。表达式求值里两个栈都是顺序栈MAX设100足够应付课设数据。如果要求“栈的容量动态增长”那就用链栈或者顺序栈加realloc。链栈的入栈和出栈typedef struct StackNode { int data; struct StackNode *next; } StackNode; void push(StackNode **top, int x) { StackNode *p (StackNode*)malloc(sizeof(StackNode)); p-data x; p-next *top; *top p; } int pop(StackNode **top, int *x) { if (*top NULL) return 0; StackNode *p *top; *x p-data; *top p-next; free(p); return 1; }链栈的top是指向栈顶节点的指针入栈时新节点next指向原栈顶然后更新top。出栈时保存栈顶数据top后移释放原节点。注意pop返回0表示栈空调用方需要检查。顺序栈和链栈在课设报告里通常要求对比。顺序栈的push和pop是O(1)链栈也是O(1)但链栈有malloc和free的开销。如果课设要求“共享栈”那就是两个顺序栈共用一个数组从两端向中间增长top1从-1开始top2从MAX开始相遇时满。4. 二叉排序树插入、删除与遍历的完整实现4.1 二叉排序树的插入与查找为什么递归最省事二叉排序树BST的性质是左子树所有节点小于根右子树所有节点大于根。插入和查找都可以用递归因为递归天然匹配“在左子树或右子树继续”的逻辑。插入的递归写法如果当前节点为空创建新节点返回如果x小于当前节点值递归插入左子树如果x大于当前节点值递归插入右子树如果相等通常不插入课设可能要求统计重复次数那就加一个count字段。typedef struct BSTNode { int data; struct BSTNode *left, *right; } BSTNode; BSTNode* insert(BSTNode *root, int x) { if (root NULL) { BSTNode *p (BSTNode*)malloc(sizeof(BSTNode)); p-data x; p-left p-right NULL; return p; } if (x root-data) { root-left insert(root-left, x); } else if (x root-data) { root-right insert(root-right, x); } // x root-data 时不插入 return root; } BSTNode* search(BSTNode *root, int x) { if (root NULL || root-data x) return root; if (x root-data) return search(root-left, x); return search(root-right, x); }insert返回新的子树根节点所以调用时是root insert(root, x)。递归的终止条件是root NULL此时创建新节点。search返回找到的节点指针找不到返回NULL。递归的缺点是当树退化成链表时递归深度等于节点数可能栈溢出。课设数据量小通常不会。如果要求非递归就用while循环用parent记录父节点找到空位后挂上去。注意如果课设要求“插入时不允许重复”上面的代码已经满足。如果要求“重复时插入到右子树”或“统计重复次数”需要修改x root-data分支。4.2 删除节点的三种情况与代码实现BST删除是最容易写错的部分。删除节点p分三种情况p是叶子节点直接删除父节点对应指针置空。p只有一个孩子用孩子替代p父节点对应指针指向孩子。p有两个孩子找左子树最大节点或右子树最小节点替代p的值然后删除那个替代节点。递归删除的代码BSTNode* deleteNode(BSTNode *root, int x) { if (root NULL) return NULL; if (x root-data) { root-left deleteNode(root-left, x); } else if (x root-data) { root-right deleteNode(root-right, x); } else { // 找到要删除的节点 if (root-left NULL) { BSTNode *r root-right; free(root); return r; } if (root-right NULL) { BSTNode *l root-left; free(root); return l; } // 两个孩子找左子树最大节点 BSTNode *maxLeft root-left; while (maxLeft-right ! NULL) maxLeft maxLeft-right; root-data maxLeft-data; // 值替换 root-left deleteNode(root-left, maxLeft-data); // 删除替代节点 } return root; }deleteNode返回新的子树根节点。当root只有一个孩子时保存孩子指针释放root返回孩子。当root有两个孩子时找左子树最大节点maxLeft把它的值赋给root然后递归删除maxLeft。因为maxLeft是左子树最大节点它一定没有右孩子所以递归删除时只会走“一个孩子或叶子”的分支。参数x是要删除的值。如果树中不存在x递归到NULL返回NULL原树不变。课设里通常要求删除后仍然保持BST性质这个实现满足。提示找左子树最大节点时while (maxLeft-right ! NULL)循环结束后maxLeft指向最大节点。如果左子树没有右孩子maxLeft就是root-left本身。4.3 中序遍历验证BST与课设报告里的复杂度分析BST的中序遍历输出一定是有序序列。课设里通常要求写中序遍历用来验证插入和删除操作是否正确。中序遍历递归写法void inorder(BSTNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); inorder(root-right); }先左子树再根再右子树。如果输出不是升序说明BST性质被破坏通常是删除操作写错了。课设报告里要求分析BST的查找、插入、删除时间复杂度。平均情况下树高为O(log n)所以操作是O(log n)。最坏情况下插入有序序列会退化成单支树树高O(n)操作变成O(n)。为了避免退化可以用平衡二叉树AVL或红黑树但课设通常不要求。操作平均时间复杂度最坏时间复杂度查找O(log n)O(n)插入O(log n)O(n)删除O(log n)O(n)中序遍历O(n)O(n)如果课设要求“统计BST的节点数、叶子数、高度”可以写三个递归函数。节点数空返回0否则1左右。叶子数空返回0左右都空返回1否则左右。高度空返回0否则1max(左,右)。5. 排序算法对比课设里怎么选、怎么测、怎么讲清楚5.1 直接插入、冒泡、快速、堆排序的实现要点课设里的排序题通常要求实现至少四种排序并对比运行时间。直接插入排序适合小规模或基本有序的数据冒泡排序稳定但慢快速排序平均最快但不稳定堆排序稳定O(n log n)且原地。直接插入排序的核心是维护一个有序区每次把当前元素插入到有序区合适位置void insertSort(int *a, int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }key保存当前待插入元素j从i-1往前找比key大的元素后移。循环结束后a[j1]就是key的位置。时间复杂度O(n²)空间O(1)稳定。快速排序用分治法选一个基准把小于基准的放左边大于的放右边然后递归int partition(int *a, int low, int high) { int pivot a[low]; while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; while (low high a[low] pivot) low; a[high] a[low]; } a[low] pivot; return low; } void quickSort(int *a, int low, int high) { if (low high) { int mid partition(a, low, high); quickSort(a, low, mid - 1); quickSort(a, mid 1, high); } }partition把a[low]作为基准先从右往左找比基准小的填到左边再从左往右找比基准大的填到右边最后把基准放到low位置。返回low作为分界点。快速排序平均O(n log n)最坏O(n²)当基准总是最小或最大不稳定。堆排序需要先建大顶堆然后每次把堆顶和末尾交换调整堆void heapify(int *a, int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { int t a[i]; a[i] a[largest]; a[largest] t; heapify(a, n, largest); } } void heapSort(int *a, int n) { for (int i n / 2 - 1; i 0; i--) heapify(a, n, i); for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; heapify(a, i, 0); } }heapify维护以i为根的子树是大顶堆。建堆从最后一个非叶子节点n/2-1开始往前调整。排序时每次把堆顶a[0]和当前末尾a[i]交换然后对前i个元素重新heapify。堆排序O(n log n)原地不稳定。5.2 用随机数测试四种排序的运行时间课设报告里通常要求生成随机数分别用四种排序跑记录时间。C语言用clock()函数#include time.h #include stdlib.h void testSort(int n) { int *a (int*)malloc(n * sizeof(int)); int *b (int*)malloc(n * sizeof(int)); srand(time(NULL)); for (int i 0; i n; i) a[i] rand() % 10000; clock_t start, end; memcpy(b, a, n * sizeof(int)); start clock(); insertSort(b, n); end clock(); printf(insertSort: %.3f ms\n, (double)(end - start) * 1000 / CLOCKS_PER_SEC); memcpy(b, a, n * sizeof(int)); start clock(); quickSort(b, 0, n - 1); end clock(); printf(quickSort: %.3f ms\n, (double)(end - start) * 1000 / CLOCKS_PER_SEC); // 同理测冒泡和堆排序 free(a); free(b); }clock()返回CPU时钟周期数CLOCKS_PER_SEC是每秒周期数相减除以它得到秒数乘1000得到毫秒。每次测试前用memcpy把原数组复制到b保证四种排序处理相同数据。n可以取1000、5000、10000、50000观察增长趋势。注意rand() % 10000生成的随机数范围小快速排序遇到大量重复元素时性能会下降。如果要更真实用rand()直接赋值或者用rand() 15 | rand()扩大范围。5.3 排序算法对比表与课设答辩常见追问课设答辩时老师通常会问为什么快速排序最坏是O(n²)堆排序为什么不稳定直接插入排序在什么情况下最好下面这个表可以帮你快速回答。排序算法平均时间最坏时间空间稳定性适用场景直接插入O(n²)O(n²)O(1)稳定小规模或基本有序冒泡O(n²)O(n²)O(1)稳定教学演示快速O(n log n)O(n²)O(log n)不稳定大规模随机数据堆O(n log n)O(n log n)O(1)不稳定要求最坏O(n log n)快速排序最坏O(n²)是因为每次选的基准都是当前区间的最大或最小值分区极度不平衡。避免方法是随机选基准或三数取中。堆排序不稳定是因为交换堆顶和末尾时可能改变相同元素的相对顺序。直接插入排序在数据已经有序时内层while不执行时间复杂度降到O(n)。如果课设要求“外部排序”或“多路归并”那是另一个话题通常不在基础课设范围内。把上面四种写清楚加上运行时间对比图排序部分就能拿满分。6. 课设调试与报告撰写的几个私藏习惯做课设最怕的不是写不出代码而是写完了跑不对或者跑对了讲不清。我自己的习惯是每写完一个模块立刻写一个最小main函数单独测试不要等所有模块拼在一起才编译。比如约瑟夫环写完后先用n5, k1, m2跑一遍手动核对输出。BST写完后插入5,3,7,2,4,6,8中序遍历应该是2,3,4,5,6,7,8。排序写完后用n10的小数组打印排序前后结果确认无误再上大规模随机数。第二个习惯是给每个函数写一行注释说明参数含义和返回值。课设报告里老师会看代码注释清楚能省很多解释。比如josephus(Node *head, int k, int m)注释写“head为不带头结点循环链表首节点k为起始报数位置m为出列报数”。这样答辩时被问到直接指注释就行。第三个习惯是报告里的复杂度分析不要只写大O要写推导过程。比如快速排序平均O(n log n)因为每次分区大约分成两半递归深度log n每层比较n次。最坏O(n²)因为每次分区只减少一个元素递归深度n。堆排序建堆O(n)每次调整O(log n)共n-1次所以O(n log n)。这些推导写在报告里比只写结论更有说服力。最后一个习惯是留一份“后悔药”所有代码提交前把可运行版本单独复制一份到U盘或云盘。课设答辩现场经常有人改代码改崩了或者老师要求现场改一个参数有备份就能快速回滚。我见过太多同学因为最后一步改错导致演示失败。希望帮到你。本文还有配套的精品资源点击获取
