高校数据结构课程实验指导手册

高校数据结构课程实验指导手册2.递归遍历：前序（根-左-右）：`voidpreorder(TreeNode*root){if(root){cout<<root->val;preorder(root->left);preorder(root->right);}}`中序、后序类似，仅调整输出位置。3.非递归遍历（栈实现）：前序非递归：根节点入栈→弹出并输出→右子节点入栈→左子节点入栈（利用栈“后进先出”，保证左子树先处理）。应用：BST的中序遍历是升序序列，可用于验证树的合法性；哈夫曼树构建时，每次选取权值最小的两个节点合并。实验四：图的存储与最短路径实验目标掌握邻接矩阵、邻接表的存储方式，实现Dijkstra、Floyd算法，分析稀疏图/稠密图的结构选择。实践步骤1.邻接矩阵（二维数组）：定义`intgraph[V][V]`（V为顶点数，建议设为100以内），`graph[i][j]`表示顶点i到j的权值（无穷大表示不可达，如`1e9`）。初始化时，`graph[i][i]=0`（自环权值为0），其余设为无穷大。2.Dijkstra算法（单源最短路径）：维护`dist[]`数组（记录源点到各点的最短距离）、`visited[]`数组（标记是否确定最短路径）。步骤：初始化`dist[src]=0`→循环V次，每次选`dist`最小且未访问的节点u→更新u的邻接节点v的`dist[v]=min(dist[v],dist[u]+graph[u][v])`。3.应用拓展：用邻接表（链表/vector数组）存储社交网络关系，统计每个用户的“六度人脉”（BFS层数）。实验常见问题与解决方案内存相关问题内存泄漏：C/C++中`new`/`malloc`后未`delete`/`free`，可借助Valgrind工具检测，或在析构函数中统一释放（如链表的`~LinkedList()`遍历删除所有节点）。野指针：指针未初始化或指向已释放内存，建议使用智能指针（C++11的`unique_ptr`/`shared_ptr`），或在指针赋值后立即置`nullptr`。算法逻辑错误链表操作断链：删除节点时，需先保存`next`指针（如`Node*temp=cur->next;cur->next=temp->next;deletetemp;`）。递归栈溢出：如二叉树遍历深度过深（数百层），改用非递归实现（栈/队列模拟递归）。性能优化建议数组扩容策略：顺序表扩容时，每次扩大为原容量的1.5倍（避免频繁扩容的时间开销）。图的存储选择：稀疏图（边数远小于V²）用邻接表，稠密图用邻接矩阵，减少空间浪费。实验报告撰写规范一份完整的实验报告应包含以下部分：1.实验目的：明确本次实验要解决的问题（如“实现链表的增删操作，分析时间复杂度”）。2.实验原理：简述数据结构的定义、算法的核心思想（如“Dijkstra算法基于贪心策略，每次确定一个顶点的最短路径”）。3.实验步骤：分模块描述代码实现（附关键代码片段，标注功能），如“顺序表扩容函数：当length等于capacity时，新建容量为原1.5倍的数组，拷贝元素后释放原数组”。4.实验结果：截图运行界面（如测试用例的输出）、性能对比表（如顺序表/链表插入100次的时间）。5.分析与总结：对比理论复杂度与实际运行效率，反思优化方向（如“链表插入效率高于顺序表，但随机访问性能差，适合频繁增删的场景”）。拓展与进阶方向1.算法优化：实现红黑树（平衡BST）、并查集的路径压缩优化、Kruskal算法的并查集实现。2.工程实践：用哈希表（如C++的`unordered_map`）实现词频统计，用Trie树（前缀树）实现敏感词过滤。3.竞赛与科研：参与ACM竞赛的算法题（如LeetCode的“数据结构”专题），或研究“区块链中的默克尔树”“推荐系统中的图神经网络”等交叉领域应用。附录：提供常用代码模板（如链表反转、快速排序的分治实现），帮助学生快速上手实验。通过系统的实验训练