简介本资源是面向高校计算机专业学生及算法初学者的数据结构实战训练包聚焦SWUSTOJ平台80道经典题目覆盖数组、链表、栈、队列、树、图、哈希表、排序查找、动态规划等核心知识点有效解决理论学习后缺乏系统编码实践的痛点。压缩包共86个文件含83个可编译运行的C源码.cpp与3个配套可执行程序.exe涵盖二叉树遍历与判定、图的DFS/BFS、最小生成树、哈希冲突处理、堆排序、括号匹配、约瑟夫问题等典型题型代码结构清晰、注释完整便于调试与理解。资源大小仅449KB轻量易下载已有609人学习使用。读者可直接导入IDE编译运行获得从输入输出规范、边界条件处理到时间复杂度优化的全流程参考特别适合课程设计、期末复习与OJ刷题能力提升。1. 这不是题库是西南科技大学OJ数据结构真题的「可执行解题手册」如果你正在刷SWUSTOJ的数据结构题目却卡在“编译通过但样例不通过”“本地能跑线上WA”“递归深度超限”“指针野访问段错误”上——这份80道代码压缩包本质是一份带完整运行环境、输入输出契约、边界处理逻辑的「可复现解题手册」。它不只给出AC代码更暴露了西南科大OJ评测系统的真实约束比如利用先序遍历创建的二叉树要求输入格式为含空结点标记如#的字符串循环队列必须严格按MAXSIZE-1有效容量实现哈希表开放定址法需明确定义探测序列与装填因子阈值。这些细节在严蔚敏《数据结构C语言版》习题集里不会写但在真实OJ环境中决定生死。它适合两类人一是刚学完链表/栈/二叉树基础需要对照标准实现反向验证自己代码逻辑漏洞的初学者二是准备华为OD、银行科技岗等技术笔试需快速建立“题目→数据结构选型→边界编码→OJ适配”闭环的求职者。所有代码均以C编写无第三方依赖g 7.5 可直接编译且每道题命名直指核心操作如逆置单链表.cpp避免抽象命名带来的理解成本。2. 从输入解析到结构构建二叉树类题目中的三重契约西南科大OJ对二叉树题目的输入输出有明确契约脱离该契约的代码即使逻辑正确也会被判错。本节以输出利用先序遍历创建的二叉树的中序遍历序列.cpp为例拆解其输入解析、树构建、遍历输出三个环节的强制约定。2.1 输入格式的隐式规则与健壮解析OJ输入并非标准二叉树数组表示而是带空结点标记的先序字符串序列例如ABD##E##CF##G##。其中#代表空结点##表示某结点左右子树均为空。关键在于输入流读取时不能简单用cin ch因为存在连续#和字母混排需逐字符读取并跳过空白符。#include iostream #include string #include stack using namespace std; struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} }; // 关键逐字符读取跳过空格、换行等分隔符 char getNextChar() { char ch; while (cin.get(ch)) { if (ch ! ch ! \n ch ! \t) return ch; } return #; } TreeNode* buildTree() { char ch getNextChar(); if (ch #) return nullptr; TreeNode* root new TreeNode(ch); root-left buildTree(); // 递归构建左子树 root-right buildTree(); // 递归构建右子树 return root; }提示getNextChar()函数是OJ适配核心。若使用cin ch遇到ABD##E##时会将#作为分隔符吞掉导致后续读取错位。必须用cin.get()逐字抓取显式过滤空白符。2.2 树构建过程中的内存管理与递归终止条件构建过程采用经典先序递归但需注意两点硬性约束空结点必须返回nullptr而非new TreeNode(#)—— 否则中序遍历时会输出非法字符每个new TreeNode必须有对应delete逻辑虽OJ不检查内存泄漏但本地调试时避免堆污染。以下为安全构建与释放模板void deleteTree(TreeNode* root) { if (!root) return; deleteTree(root-left); deleteTree(root-right); delete root; } // 在main中调用 int main() { TreeNode* root buildTree(); // ... 执行中序遍历 deleteTree(root); // 必须释放否则Valgrind报内存泄露 return 0; }2.2.1 中序遍历的非递归实现与栈空间控制OJ对栈深度有限制通常≤10000深度过大的递归遍历易触发Runtime Error: Segmentation fault。因此中序遍历推荐使用显式栈模拟void inorderIterative(TreeNode* root) { stackTreeNode* stk; TreeNode* curr root; while (curr || !stk.empty()) { while (curr) { // 一路向左压栈 stk.push(curr); curr curr-left; } curr stk.top(); // 访问栈顶 cout curr-val; stk.pop(); curr curr-right; // 转向右子树 } cout endl; }注意此实现时间复杂度O(n)空间复杂度O(h)h为树高比递归更可控。若题目要求输出空格分隔如A B D E C F G需在cout curr-val后加 但末尾多一个空格会被OJ判为PEPresentation Error需用vector暂存后统一输出。2.3 输出格式的精确匹配空格、换行与特殊字符OJ判题严格比对输出流包括末尾换行。中序遍历序列要求输出为无空格连续字符串如BDAECFG而非带空格分隔。若误输出B D A E C F G\n将直接WA。验证方法将程序输出重定向到文件用diff -b对比标准答案# 编译并生成输出 g -o inorder inorder.cpp ./inorder input.txt output.txt # 与标准答案比对忽略空格差异 diff -b output.txt expected_answer.txt参数说明OJ常见陷阱input.txt包含ABD##E##CF##G##的纯文本文件文件末尾多空行导致getNextChar()阻塞expected_answer.txt对应中序结果BDAECFG答案末尾无换行但代码cout endl多输出\ndiff -b忽略空格、制表符、换行符差异若答案含空格而代码无则-b仍报错需用-w3. 链表与栈的底层操作从指针操作到OJ边界防御链表和栈是OJ高频考点但学生常因指针误操作或边界未覆盖而失败。本节以逆置单链表.cpp和利用栈完成后缀表达式的计算.cpp为例揭示OJ环境下的指针安全规范与栈操作容错设计。3.1 单链表逆置的三种实现及其OJ适配性分析SWUSTOJ要求链表节点结构体为struct ListNode { int data; ListNode* next; ListNode(int x) : data(x), next(nullptr) {} };3.1.1 迭代法最安全的OJ首选方案递归法在链表长度1000时易栈溢出迭代法无此风险且逻辑清晰ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* nextTemp curr-next; // 保存下一节点 curr-next prev; // 反转当前指针 prev curr; // 移动prev curr nextTemp; // 移动curr } return prev; // 新头结点 }关键参数说明nextTemp必须在curr-next prev前保存否则链表断裂。OJ测试用例包含空链表head nullptr、单节点链表head-next nullptr此代码天然支持。3.1.2 递归法仅限小规模数据的演示方案虽简洁但有风险仅作理解用ListNode* reverseListRecursive(ListNode* head) { if (!head || !head-next) return head; // 边界空或单节点 ListNode* newHead reverseListRecursive(head-next); head-next-next head; // 反转连接 head-next nullptr; // 断开原连接 return newHead; }注意OJ对递归深度限制通常为1000若测试用例含10000节点链表此函数必RE。生产环境禁用。3.2 后缀表达式计算中的栈操作与异常防御后缀表达式如3 4 2 *需计算为14。OJ输入为空格分隔的字符串需分割后逐项处理。关键防御点操作数栈溢出、除零、非法字符。#include sstream #include cctype int evalRPN(const string tokens) { stacklong long stk; // 用long long防int溢出 istringstream iss(tokens); string token; while (iss token) { if (token || token - || token * || token /) { if (stk.size() 2) throw runtime_error(Invalid expression); long long b stk.top(); stk.pop(); long long a stk.top(); stk.pop(); if (token ) stk.push(a b); else if (token -) stk.push(a - b); else if (token *) stk.push(a * b); else if (token /) { if (b 0) throw runtime_error(Division by zero); stk.push(a / b); // 截断除法符合OJ要求 } } else { // 安全转换检查是否为数字含负号 bool isNum true; for (char c : token) { if (!isdigit(c) c ! -) { isNum false; break; } } if (!isNum) throw runtime_error(Invalid token: token); stk.push(stoll(token)); } } if (stk.size() ! 1) throw runtime_error(Invalid expression); return (int)stk.top(); }3.2.1 输入分割的健壮性处理OJ输入可能含多余空格如3 4 2 *istringstream自动跳过连续空格比手动find_first_of( )更可靠。若用getline(iss, token, )遇多个空格会读入空字符串导致stoll()崩溃。3.2.2 数值范围与类型选择题目未限定操作数范围但OJ测试用例含2^31级大数。int在乘法时易溢出如100000 * 100000故栈元素用long long最终结果再转int。除法使用a / b而非a / (double)b因OJ要求整数截断7/23非3.5。4. 图与哈希表的工程化实现邻接表构建与冲突解决策略图论与哈希表是OJ中后期难点涉及动态内存分配与复杂逻辑。本节聚焦邻接表到邻接矩阵.cpp和哈希表链地址法处理冲突.cpp解析其工程化实现要点。4.1 邻接表转邻接矩阵顶点编号映射与稀疏优化SWUSTOJ图题输入格式为首行n mn顶点数m边数随后m行u v wu→v有权重w。邻接表存储需先建立顶点到索引的映射因输入顶点名可能为字母如A B 10或数字1 2 5而邻接矩阵需固定大小二维数组。#include unordered_map #include vector #include algorithm struct Graph { unordered_mapstring, int name2idx; // 顶点名→索引映射 vectorvectorint matrix; // 邻接矩阵-1表示无边 int n; // 顶点数 Graph(int maxN) : n(maxN) { matrix vectorvectorint(maxN, vectorint(maxN, -1)); } void addEdge(const string u, const string v, int w) { if (name2idx.find(u) name2idx.end()) { name2idx[u] name2idx.size(); } if (name2idx.find(v) name2idx.end()) { name2idx[v] name2idx.size(); } int i name2idx[u], j name2idx[v]; if (i n j n) matrix[i][j] w; } void printMatrix() { for (int i 0; i n; i) { for (int j 0; j n; j) { if (j 0) cout ; cout matrix[i][j]; } cout endl; } } };提示name2idx.size()动态增长但matrix初始化时需预估最大顶点数OJ通常≤100。若实际顶点数超maxNmatrix[i][j]越界访问将导致RE。安全做法是先扫描输入获取真实顶点数再构造Graph。4.2 链地址法哈希表桶数组与链表节点的内存协同哈希表题目要求实现插入、查找、删除冲突用链地址法每个桶是链表。关键设计点桶数组大小需为质数降低冲突率OJ常用997链表节点需包含key和value因题目可能要求根据key查value删除操作必须处理头结点与中间节点两种情况。const int TABLE_SIZE 997; struct HashNode { string key; int value; HashNode* next; HashNode(const string k, int v) : key(k), value(v), next(nullptr) {} }; class HashMap { private: vectorHashNode* buckets; int hash(const string key) { int h 0; for (char c : key) h (h * 31 c) % TABLE_SIZE; return (h TABLE_SIZE) % TABLE_SIZE; // 保证非负 } public: HashMap() : buckets(TABLE_SIZE, nullptr) {} void put(const string key, int value) { int idx hash(key); HashNode* curr buckets[idx]; // 查找是否存在key while (curr) { if (curr-key key) { curr-value value; // 更新值 return; } curr curr-next; } // 头插法插入新节点 HashNode* newNode new HashNode(key, value); newNode-next buckets[idx]; buckets[idx] newNode; } int get(const string key) { int idx hash(key); HashNode* curr buckets[idx]; while (curr) { if (curr-key key) return curr-value; curr curr-next; } return -1; // 未找到 } void remove(const string key) { int idx hash(key); HashNode* curr buckets[idx]; HashNode* prev nullptr; while (curr) { if (curr-key key) { if (prev nullptr) { // 删除头结点 buckets[idx] curr-next; } else { // 删除中间节点 prev-next curr-next; } delete curr; return; } prev curr; curr curr-next; } } };4.2.1 哈希函数的选择与冲突率控制使用h (h * 31 c) % TABLE_SIZE是Java String哈希的经典实现比简单sum ASCII % TABLE_SIZE分布更均匀。TABLE_SIZE 997质数可减少同余冲突。若OJ测试用例含大量相似字符串如a, aa, aaa此哈希函数仍可能聚集此时需改用std::hashstringC11。4.2.2 内存泄漏防护与析构函数上述代码未提供析构函数OJ不检查内存但本地调试需补充~HashMap() { for (int i 0; i TABLE_SIZE; i) { HashNode* curr buckets[i]; while (curr) { HashNode* next curr-next; delete curr; curr next; } } }5. OJ实战调试技巧用gdb定位段错误与Valgrind检测内存违规当代码在本地通过但OJ报Runtime Error90%源于内存违规。本节提供两套可立即上手的调试方案直击Segmentation fault与Invalid read/write。5.1 gdb动态调试精准捕获野指针与越界访问以单链表的删除操作的实现.cpp为例若删除不存在的节点导致崩溃用gdb定位# 编译时加调试信息 g -g -o delete_node delete_node.cpp # 启动gdb并加载输入文件 gdb ./delete_node (gdb) run input.txt # 程序崩溃后查看调用栈 (gdb) bt # 输出类似 # #0 0x0000000000400a12 in deleteNode (head0x0, pos1) at delete_node.cpp:25 # #1 0x0000000000400b5c in main () at delete_node.cpp:50 # 查看崩溃行变量值 (gdb) frame 0 (gdb) print head # $1 (ListNode *) 0x0 (gdb) print pos # $2 1关键技巧btbacktrace显示崩溃位置frame 0进入最内层函数print检查指针是否为nullptr。若head为0x0而代码执行head-next即确认空指针解引用。5.2 Valgrind内存检测发现隐藏的越界与泄漏Valgrind可检测malloc/new未配对free/delete以及数组越界# 编译时禁用优化-O0确保行号准确 g -O0 -g -o tree tree.cpp # 运行Valgrind valgrind --leak-checkfull --show-leak-kindsall ./tree input.txt # 典型输出 # 12345 Invalid write of size 4 # 12345 at 0x400A2F: buildTree() (tree.cpp:45) # 12345 by 0x400B1C: main (tree.cpp:88) # 12345 Address 0x5a1c044 is 0 bytes after a block of size 4 allocd # 12345 at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) # 12345 by 0x400A1A: buildTree() (tree.cpp:42)此输出明确指出第45行对刚分配的4字节内存进行了越界写0 bytes after根源在第42行malloc尺寸不足。OJ环境无Valgrind但本地检测可提前规避90%的RE。5.3 OJ特供调试法输出中间状态到stderr当无法使用gdb/Valgrind时如在线IDE用cerr输出关键变量OJ不捕获stderr不影响判题// 在关键指针操作前插入 cerr [DEBUG] curr curr , curr-next (curr ? curr-next : nullptr) endl; // 或输出链表当前状态 void printList(ListNode* head) { cerr [LIST] ; while (head) { cerr head-data -; head head-next; } cerr null endl; }运行后查看OJ的运行信息页非输出页可看到cerr内容快速定位空指针或环形链表。本文还有配套的精品资源点击获取