数据结构实验指导书软件.docx

数据结构实验指导书软件.docx

《数据结构实验指导书软件.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导书软件.docx（9页珍藏版）》请在冰点文库上搜索。

数据结构实验指导书软件

《数据结构》实验指导书

（本实验指导书尚未定稿，因此会经常改进，建议大家每次上机前重新下载，由于尚未定稿，可能存在错误，发现后请标注颜色发给lbd@，非常感谢）

一、实验要求

1、采用良好的编程风格；关键操作要有注释。

2、程序能够运行，并能严格按要求输出结果。

3、自己编写完成实验，不可以拷贝别人程序，测试程序具有查重功能。

4、因采用程序进行测试，因此对输出格式要求严格，格式不对也会被判测试不通过。

输出数据时，每个数之间用“，”隔开，中间不要含空格，参考样例在需要的地方换行，输出开始有“Output”字样，输出结束有“End”字样。

详细格式要求参考每个实验的格式样例。

二、开发工具

1、MicrosoftVisualC++

2、EclipseIDEForC++

三、实验周数

9周*2小时

四、评分标准

在规定时间之前完成并提交到实验平台，测试通过，该实验计10分，在规定时间之后完成，计6分。

五、指导书下载地址

Ftp服务器地址：

211.87.224.23，用户/密码：

db/dbsystem

六、作业提交步骤及办法

七、

1、每次上机，登入系统进行注册，注册过程代替点名。

登入网址：

http:

//211.87.224.23:

8080/testplat/logonDialog.jsp

账号密码：

学号/123

登入成功后如果不能够看到实验平台画面，可以输入下面网址：

http:

//211.87.224.23:

8080/testplat/index.jsp，就可以进入实验平台了。

2、源程序文件名采用test01_ID.cpp，test01代表实验一（下面相同），ID代表本人学号（下面相同），例如学号为201000300001的学生的第一个实验源程序文件名为test01_201000300001.cpp。

程序编译后创建一个test01_ID.exe文件。

3、作业自测通过后，在实验平台上，将test01_ID.cpp文件上传到相应实验源代码，将test01_ID.exe文件上传到相应实验的目标代码，然后提交实验，等待10秒后，执行【刷新】，查看实验状态：

1）上传源代码：

已经正确上传完源代码。

2）上传目标代码：

已经正确上传目标代码。

3）提交试验：

已经提交实验，等待后台测试目标代码。

如果保持该状态超过1分钟，说明后台出现错误，请通知实验指导教师。

4）按时完成：

程序在要求时间内完成实验。

5）超时完成：

程序在要求时间后完成实验。

6）运行错误：

上传的目标代码可能不能正确运行，再一次提交实验进行尝试，如果仍然没有解决问题，进一步测试你的程序能够正确运行，是否按要求的格式输入数据。

7）结果错误：

程序运行后输出的结果和答案不一致，也就是你的程序存在逻辑错误，需要你进一步修改调试。

8）正在查重：

后台已经开始查重。

如果保持该状态超过1分钟，说明后台出现错误，请通知实验指导教师。

9）正在测试：

后台已经开始测试目标代码。

如果保持该状态超过1分钟，说明后台出现错误，请通知实验指导教师。

10）涉嫌抄袭：

你的程序有抄袭嫌疑，如果确实本人编写，请联系指导教师进行人工核对。

否则，重新自己动手完成实验。

11）文件名错误：

源程序文件名采用test01_ID.cpp，目标文件名称采用test01_ID.exe。

12）文件太小：

源程序有效代码太少，低于20行。

如果你的程序确实低于20行代码，请联系指导教师。

4、如果没有通过，根据提示继续调试你的程序直到通过。

实验一递归练习

一、要求完成时间

实验开始后的第二周之前完成

二、实验目的

1、熟悉开发工具的使用。

2、掌握递归的实现思想。

三、实验内容

1、输入2-10个大于0的正整数，如果输入0作为结束。

2、输出这几个整数的全排列，每个数之间用半角“，”隔开，中间不要有空格，每个排列单独一行。

四、输入输出请严格按下面要求的格式实现

实验二排序算法

一、要求完成时间

实验开始后的第三周之前完成

二、实验目的

掌握各种排序方法的实现思想。

三、实验内容

1、输入2-10个不为零的正整数，遇到0，代表输入结束。

2、数字选择排序方法，1-冒泡排序、2-插入排序、3-基数排序。

3、使用所选排序方法的排序，结果输出所用方法以及结果，每个数之间用“，”隔开，中间不要有空格。

4、输入输出请严格按下面要求的格式实现

实验三线性表操作

一、要求完成时间

实验开始后的第五周之前完成

二、实验目的

1、掌握线性表的基本操作：

插入、删除、查找。

2、掌握链表遍历器的使用方法。

3、

三、实验内容

1、创建线性表类。

线性表的存储结构使用链表。

2、完成表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。

3、输入n个不为零的整数作为节点元素值，遇到0代表输入结束（不创建元素值为0的节点），创建链表。

输出整个链表。

4、输入一个整数，将该数作为一个元素值插入表首位置。

输出整个链表。

5、输入一个整数，在链表中进行搜索，输出其在链表中的位置。

如果不存在输出0。

6、再一次输入一个整数，在链表中进行搜索，输出其在链表中的位置。

如果不存在输出0。

7、使用链表遍历器实现链表的反序输出。

8、再一次输入n个不为零的整数作为节点元素值，遇到0代表输入结束（不创建元素值为0的节点），创建另外一个链表，输出整个链表。

9、使用链表遍历器实现上面两个链表的合并，输出合并后的链表。

四、输入输出请严格按下面要求的格式实现

实验四堆栈的应用

一、要求完成时间

实验开始后的第六周之前完成

二、实验目的

掌握堆栈的使用。

三、实验内容

1、输入一个数学表达式（假定表达式输入格式合法），计算表达式结果并输出。

2、数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“（、）”构成，例如2+3*（4+5）–6/4。

四、输入输出请严格按下面要求的格式实现

实验五二叉树操作

一、要求完成时间

实验开始后的第七周之前完成

二、实验目的

掌握二叉树的基本概念，链表描述方法；遍历方法。

三、实验内容

1、创建二叉树类。

二叉树的存储结构使用链表。

2、提供操作:

前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。

3、对建立好的二叉树，执行上述各操作。

4、接收键盘录入的二叉树前序序列和中序序列（各元素各不相同），输出该二叉树的后序序列。

四、输入输出请严格按下面要求的格式实现

实验六堆和搜索树

一、要求完成时间

实验开始后的第八周之前完成

二、实验目的

掌握堆和搜索树的基本概念，插入、删除方法。

三、实验内容

1、创建最大堆类，最大堆的存储结构使用链表。

2、提供操作:

堆的插入、堆的删除。

堆的初始化。

Huffman树的构造。

二叉搜索树的构造。

3、接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。

4、堆排序。

四、输入输出请严格按下面要求的格式实现

实验七图的操作

一、要求完成时间

实验开始后的第九周之前完成

二、实验目的

掌握图的基本概念，描述方法；遍历方法。

三、实验内容

1、创建图类。

二叉树的存储结构使用邻接矩阵。

2、提供操作:

遍历、BFS、DFS

3、对建立好的图，执行上述各操作。

4、输出最短路径。

5、输出最小生成树。

四、输入输出请严格按下面要求的格式实现