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

《数据结构实验指导书-2014.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》实验指导书计算机专业实验中心2014年9月27目录实验一、线性表的实现及操作（一）5实验二、线性表的实现及操作（二）8实验三、线性表的应用13实验四、二叉树的实现及操作14实验五、二叉树的应用19实验六、图的遍历操作20实验七、图的应用2727《数据结构》上机实验的内容和要求通过上机实验加深对课程内容的理解，增加感性认识，提高程序设计、开发及调试能力。序号实验名称内容提要每组人数实验时数实验要求实验类别分值（总100分）1线性表的实现及操作（一）顺序表建立、插入、删除等基本操作12必做设计15分2线性表的实现及操作（二）单

2、链表的建立、插入、删除等基本操作12必做设计15分3线性表的应用约瑟夫环问题或者长整数相加的设计与实现12选作综合10分4二叉树的实现及操作二叉树的基本操作：树的建立、前序、中序、后序遍历12必做设计20分5二叉树的应用赫夫曼树12选作综合10分6图的遍历图的遍历：深度优先和广度优先12必做设计20分7图的应用最短路径算法：Dijkstra算法和Floyd算法12选作综合10分8算法性能测试、总结和答疑对实验课涉及到的算法进行性能测试、对实验所遇到的问题进行总结和答疑12本实验指导书适用于16学时《数据结构》实验课，实验项目具体内容如

3、下：其中，第1、2、4、6实验项目为设计性实验，的其内容为程序代码分析与调试，要求每位同学在每次实验课结束前通过检查。这部分实验应撰写1份实验报告，总分70分。第3、5、7实验项目为综合应用性实验，学生根据自己的兴趣和基础选作。这三个实验要求学生利用所学的理论知识解决实际问题，每一个实验应撰写一份实验报告，每个实验10分。此实验指导书也适用于8学时《数据结构》实验课，要求完成第1、2、4、6实验项目。实验报告要求请按照实验教师要求，按时提交实验报告电子版文件。实验报告格式可个性化定义，内容包括但不限于以下内容：1、题目、姓名、学号、班

4、级（首页）2、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（1）输入的形式和输出值的范围；（2）输出的形式；（3）程序所能达到的功能；（4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。271、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。2、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。3、调试分析：（1）调试过程中所遇到的问题及解决方法；（2）算法的时空分析；（3）经验与体会。4、用户使用说明：说明如何使用你设计的程序，详细列出每一步操作步骤。（如果程序操作简

5、单，可略去）5、测试结果：列出对于给定的输入所产生的输出结果。（若有可能，测试随输入规模的增长所用算法的实际运行时间的变化）8、总结27实验一、线性表的实现及操作（一）一、实验目的了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。二、实验要求给定一段程序代码，程序代码所完成的功能为：（1）建立一个线性表；（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；（3）删除数据元素5；（4）

6、依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。三、程序代码#include#defineMaxSize100typedefintDataType;typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;voidListInitiate(SeqList*L)/*初始化顺序表L*/{L

7、->size=0;/*定义初始数据元素个数*/}intListLength(SeqListL)/*返回顺序表L的当前数据元素个数*/{returnL.size;}intListInsert(SeqList*L,inti,DataTypex)/*在顺序表L的位置i（0≤i≤size）前插入数据元素值x*//*插入成功返回1，插入失败返回0*/27{intj;if(L->size>=MaxSize){printf("顺序表已满无法插入!");return0;}elseif(i<0

8、

9、i>L->size){printf("参数i不合法!

10、");return0;}else{//此段程序有一处错误for(j=L->size;j>i;j--)L->list[j]=L->list[j];/*为插入做准备*/L->list[i]=x;/*插入*/L->size