数据结构实验指导书-2014解读.doc

《数据结构》 实验指导书 计算机专业实验中心 2014年9月目 录 实验一、线性表的实现及操作（一） 5 实验二、线性表的实现及操作（二） 8 实验三、线性表的应用 13 实验四、二叉树的实现及操作 14 实验五、二叉树的应用 19 实验六、图的遍历操作 20 实验七、图的应用 27 《数据结构》上机实验的内容和要求 通过上机实验加深对课程内容的理解，增加感性认识，提高程序设计、开发及调试能力。 序号 实 验 名 称 内 容 提 要 每组 人数 实验 时数 实验 要求 实验 类别 ） 1 线性表的实现及操作（一）、删除基本操作1 2 必做 设计 15分 2 线性表的实现及操作（二）的、删除基本操作 1 15分 3 线性表的应用 约瑟夫环问题或者长整数相加 1 2 选作 综合 10分 4 二叉树的实现及 二叉树的基本操作：树的 1 2 必 20分 5 二叉树的应用 赫夫曼树 1 2 选作 综合 10分 6 图的遍历 图的：深度优先和广度优先1 2 必 设计 20分 7 图的应用 最短路径算法： 1 2 选作 综合 10分 8 算法性能测试和答疑涉及到的算法进行性能测试、实验所的问题进行总结和答疑 2 本实验指导书适用于16学时《》具体内容如下： 其中，内容为程序代码。这部分撰写实验报告总分。第为根据自己的选作。三个实验要求学生利用所学的理论知识实际问题实验报告实验。此实验适用于实验课， 实验报告要求 请按照实验教师要求，按时提交实验报告电子版文件。 实验报告格式可个性化定义，内容包括但不限于以下内容： 题目、姓名、、班级（） 输入的形式和输出值的范围； 输出的形式； 程序所能达到的功能； 测试数据：包括正确的输入输出结果和错误的输入及输出结果。 概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。 详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。 调试分析： 调试过程中所遇到的问题及解决方法； 算法的时空分析； 经验与体会。 用户使用说明：说明如何使用你设计的程序，详细列出每一步操作步骤。（如果程序简单，可略去）总结实验一、线性表的实现及操作（一）C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算 二、实验要求 给定一段程序代码，代码所完成的功能为：）一个线性表）输入数据元素1（）（）显示当前线性表中的数据元素。假设线性表的数据元素个数在最坏情况下不会超过，要求使用顺序表。中有3错误的地方，，逻辑错误，对书中的代码仔细分析后，要求同学们修改错误的代码，上机调试得到正确的运行结果。 #include stdio.h #define MaxSize 100 typedef int DataType; typedef struct { DataType list[MaxSize]; int size; } SeqList; void ListInitiate(SeqList *L) /*初始化顺序表L*/ { L-size = 0; /*定义初始数据元素个数*/ } int ListLength(SeqList L) /*返回顺序表L的当前数据元素个数*/ { return L.size; } int ListInsert(SeqList *L, int i, DataType x) /*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/ /*插入成功返回1，插入失败返回0*/ { int j; if(L-size = MaxSize) { printf(顺序表已满无法插入! \n); return 0; } else if(i 0 || i L-size ) { printf(参数i不合法! \n); return 0; } else { //此段程序有一处错误 return 1; } } int ListDelete(SeqList *L, int i, DataType *x) /*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/ /*删除成功返回1，删除失败返回0*/ { int j; if(L-size = 0) { printf(顺序表已空无数据元素可删! \n); return 0; } else if(i 0 || i L-size-1) { printf(参数i不合法); return 0; } else {//此段程序有一处