数据结构上机实验与课程设计指导书.doc

I 数据结构上机实验数据结构上机实验 与课程设计指导书与课程设计指导书 第一版 林 琳 王新胜 编著 施化吉 主审 计算机科学与通信工程学院计算机科学系 江苏大学印刷厂 2004 7 II 前前 言言 数据结构是计算科学科学与技术专业的一门重要的专业基础课程 当用计 算机来解决实际问题时 就要涉及到数据的表示及数据的处理 而数据表示及 数据处理正是数据结构课程的主要研究对象 通过这两方面内容的学习 为后 续课程 特别是软件方面的课程打下了厚实的知识基础 同时也提供了必要的 技能训练 因此 数据结构课程在计算机科学与技术专业中具有举足轻重的作 用 数据结构主要研究数据的逻辑结构及其基本操作在计算机中的表示和实现 数据结构不仅是计算机专业的核心课程 而且已成为其他理工科专业的热门选 修课 课程的教学要求之一是训练学生进行复杂课程设计的技能和培养良好的 程序设计习惯 其重要程度不亚于知识传授 因此 在数据结构的整个教学过 程中 完成上机实习是一个至关重要的环节 为了帮助读者学好这门课程 我 们编写了这本实验指导书 编 者 2004 年 7 月于江苏大学 III 实验要求实验要求 1 每位同学准备一个实验本 上机前作好充分的准备工作 预习本次实 验的内容 事先熟悉与实验有关的软硬件环境 编写好程序代码 供 上机时使用 2 实验时遵守实验室的规章制度 爱护实验设备 不得私自将使用的计 算机加密码 影响其他同学的上机 原则上每人固定实验设备 由始 而终地进行实验 对于实验设备出现的问题 要及时向指导老师汇报 3 统一以以下格式命名本人的实验文件 班级班级 学号学号 实验题号实验题号 扩展名扩展名 例 计 021 班学号为 03 的学生第四个实验的文件名为 j02103 4 cj02103 4 c 4 最终的实验报告按照要求书写 或打印 按时上交 仔细记录实验中 的数据 源程序 实验结果 对于实验过程中出现的问题或疑惑要一 并书写 并作为重点加以思考 5 编程序过程中要注意多存盘 避免由于死机等原因造成不必要的重复 录入 6 编程序时要注意将常用的功能单独组成函数以供调用 避免重复录入 IV 目目 录录 实验一实验一 单链表操作单链表操作 1 实验二实验二 二叉树操作二叉树操作 3 实验三实验三 图的操作图的操作 5 实验四实验四 查找操作查找操作 7 实验五实验五 内部排序操作内部排序操作 8 课课程程设计设计 9 参考文献参考文献 15 附 课程设计实习报告的书写格式附 课程设计实习报告的书写格式 16 1 实验一实验一 单链表操作 一 实验内容一 实验内容 单链表的创建 插入 删除和查找 二 实验目的二 实验目的 1 熟悉用 tc 进行程序设计的方法 2 掌握单链表的基本操作 插入 删除 查找等运算 三 实验题目三 实验题目 本实验要求实现以下功能 1 从键盘输入顺序任意的 5 个整数 生成第一个有序单链表 将该链表输出显示 2 再从键盘输入顺序任意的 5 个整数 生成第二个有序单链表 将该链表输出显示 3 将这两个有序单链表合并成一个有序单链表 要求使用两个单链表的原有空间进 行合并 将生成的有序单链表输出显示 测试数据 输入第一组整数 23 45 11 78 34 输出的排序单链表应为 11 23 34 45 78 输入第二组整数 90 13 45 66 10 输出的排序单链表应为 10 13 45 66 90 合并两个单链表 输出排好序的结果应为 10 11 13 23 34 45 45 66 78 90 2 四 实验报告四 实验报告 1 实验题目 2 程序中使用的数据结构及符号说明 3 流程图 4 打印一份源程序并附上注释 5 打印程序运行时的初值和运行结果 3 实验二实验二 二叉树操作二叉树操作 一 实验内容一 实验内容 二叉树的建立 二叉树的遍历 二 实验目的二 实验目的 1 进一步掌握指针变量的使用 2 掌握二叉树的结构特征 以及各种存储结构的特点及使用范围 3 掌握用指针类型描述 访问和处理二叉树的运算 4 掌握栈或队列的使用 三 实验题目三 实验题目 本实验要求实现以下功能 1 按前序次序建立一颗二叉树 以 表示空 2 中序 后序遍历该二叉树 输出遍历序列 3 求出该二叉树的深度并输出 或求出该二叉树的叶子数目并输出 4 试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅助存储结构实 现二叉树的层次遍历算法 测试数据 输入以下字符串 建立二叉树 ABC DE G F 输出中序遍历序列应为 CBEGDFA 输出后序遍历序列应为 CGEFDBA 输出二叉树的深度应为 5 输出二叉树的叶子数目应为 3 4 四 实验报告四 实验报告 1 实验题目 2 程序中使用的数据结构及符号说明 3 打印一份源程序并附上注释 4 打印程序运行时的初值和运行结果 画出该二叉树的形态 上次做了个实验 也费了很长时间才作完 希望能和大家分享分享 题目 1 按前序次序建立一颗二叉树 以 表示空 2 中序 后序遍历该二叉树 输出遍历序列 3 求出该二叉树的深度并输出 或求出该二叉树的叶子数目并输出 测试数据 输入以下字符串 建立二叉树 ABC DE G F 输出中序遍历序列应为 CBEGDFA 输出后序遍历序列应为 CGEFDBA 输出二叉树深度为 5 输出二叉树叶子数目 3 5 在 vc6 0 下可以实现 include using namespace std class bintreelist class binode private binode lchild rchild char data public binode char adata binode alchild NULL biode arcnhild NULL data adata lchild alchild rchild archild friend class bintreelist class bintreelist private binode root public 6 bintreelist root new binode binode getroot return root void creatbintreelist binode start void midorder binode start void afterorder binode start int level binode start int leaf binode start void free binode start include bintreelisthead h void bintreelist creatbintreelist binode start char T cin T start data T if T return start lchild new binode start rchild new binode creatbintreelist start lchild creatbintreelist start rchild void bintreelist midorder binode start 7 if start NULL start data return midorder start lchild cout data rchild void bintreelist afterorder binode start if start NULL start data return afterorder start lchild afterorder start rchild cout data data start NULL return 0 if start lchild data int A level start lchild int B level start rchild if A B return A 1 else return B 1 int bintreelist leaf binode start if start NULL start data return 0 8 if start lchild data return leaf start lchild leaf start rchild void bintreelist free binode start if start NULL return binode A start lchild B start rchild delete start free A free B include bintreelisthead h int main bintreelist one cout please input the preorder datas one creatbintreelist one getroot cout the middle travel order is one midorder one getroot cout endl cout the post travel order is one afterorder one getroot 9 cout endl cout level num one level one getroot endl cout leaf num one leaf one getroot endl one free one getroot return 1 程序自己写的 不过在 void creatbintreelist binode start 这边 我想改成 void creatbintreelist binode start 然后把定义部分也改用另种方法 为什么把指 针传过去时说不能将 类型