数据结构实验指导书-（精品）.doc

数据结构实验指导书-（精品）.doc数据结构实验指导书
实验的目的、内容和要求
一、 实验目的与要求
通过上机实验加深对课程内容的理解，提高软件设计、编写及程序调试的能力。
上机前要做好准备工作，包括程序框图、数据结构以及算法。
按时实验。
服从实验室老师的安排。
独立实验，有问题可以讨论，但不得翻版。
遵守实验室的各项纪律。
要求所编的程序能正确运行，并提交实验报告。
二、 实验内容
线性表基本操作:熟练掌握线性表的基本操作，及在两种存储结构上的实现。要求顺 序表的数据域是整型数值，完成顺序表的初始化、插入、删除等操作，插入时不允许重复 的值插入表中。要求单链表的数据域是字符串，完成单链表的初始化、插入、删除、逆向 等操作。
栈操作:采用顺序存储结构，完成建栈、数据元素入栈与出栈、判断栈空、判断栈满 等操作。
二叉树操作:采用二叉链表作为存储结构，完成二叉树的建立，先序、中序和后序以 及按层次遍历的操作，求所有叶子及结点总数的操作等。
图的遍历操作:可采用邻接矩阵或邻接表作为存储结构，完成有向图和无向图的DFS 和BFS操作。
数据查找:实现顺序查找、折半查找及二叉排序树上的查找算法，比较它们的查找速 度。实验时所输入的数据可按有序和随机产生去组织。
排序:实现直接插入、冒泡、直接选择、快速、堆、归并等排序算法，比较各种排序 算法的速度。
第 3, 5, 7, 9, 11, 13, 14, 15 周周二，实验楼 0711
四、实验报告要求
（1）报告内容包括：
实验名称
实验目的
实验内容
问题描述
问题分析
函数说明
程序流程图
重要算法解释
使用说明
调试报告
心得体会
实验报告的基本要求为：
需求分析:陈述程序设计的任务，强调程序要做什么，明确规定：①输入的形式和 输入值的范围；②输出的形式；③程序所能达到的功能；④测试数据：包括正确的输入输出 结果和错误的输入及其输出结果。
概要设计:说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。
详细设计:提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
调试分析:①调试过程中所遇到的问题及解决方法；②算法的时空分析；③经验与 体会。
用户使用说明:说明如何使用你的程序，详细列出每一步操作步骤。
测试结果:列出对于给定的输入所产生的输出结果。若可能，测试随输入规模的增 长所用算法的实际运行时间的变化。
必须打印。
实验1线性表基本操作(4学时)
实验目的
掌握使用C++上机调试线性表的基本方法。
熟练掌握线性表的基本操作，及在两种存储结构上的实现。
熟悉顺序表的基本操作，完成顺序表的初始化、插入、删除等操作，插入时不允许 重复的值插入表中。
熟悉对单链表的一些基本操作，完成单链表的初始化、插入、删除等操作。
实验内容
实现顺序表的定义和操作。该程序包括顺序表结构类型以及对顺序表操作的具体的 函数定义。
/*定义顺序表的最大长度为MAXSIZE */
#define MAXSIZE 50
/*定义DataType为int类型*/
typedef int DataType;
/*顺序表的类型*/
typedef struct list
{
DataType vec[MAXSIZE];
int len; //顺序表的长度
} SeqList;
，并在头文件中给出顺序表的函数及常量的定 义。
/*初始化顺序表*/
SeqList* Create();
/*清除顺序表*/
void Destroy(SeqList *L);
/*顺序表元素信息打印输出*/
void Print (SeqList *L);
/*判断顺序表是否为空*/
bool IsEmpty(SeqList *L);
/*判断顺序表是否为满*/
bool IsFull(SeqList *L);
/*向顺序表中添加数据*/
void Append(SeqList DataType data);
/*获取顺序表的长度*/
int GetLength(SeqList *L);
/*删除顺序表中指定位置的元素*/
bool Delete(SeqList int pos);
/*在顺序表的指定位置中的添加元素*/
bool Insert(SeqList int pos, DataType data);
int &iMax);
T &data);
int &pos);int &pos,const T &data);
//*VS C++函数定义
void Create(const void Destroy();
void Print