《算法与数据结构》实验指导书.doc

算法与数据结构吴景岚 王润鸿 编撰闽江学院计算机实验教学中心印制1目录前言1实验一 顺序表基本操作的实现2实验二 链表基本操作的实现4实验三 串基本操作的实现6实验四 二叉树基本操作的实现8实验五 图基本操作的实现11前言数据结构是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。数据结构是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。实验一 顺序表基本操作的实现专业： 班级： 学号： 姓名： 实验地点： 实验时间： 指导教师： 【实验课程名称】算法与数据结构【实验项目名称】顺序表基本操作的实现一、 实验目的1掌握线性表顺序存储基本操作；2学会设计实验数据验证程序。二、 实验仪器及环境计算机，window xp操作系统，VC+6.0三、 实验内容及步骤线性表顺序存储基本操作存储结构定义：#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量typedef struct ElemType *elem; /存储空间基址 int length； /当前长度 int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位）SqList；实现的基本操作：InitList( &L )操作结果：构造一个空的线性表 L 。DestroyList( &L )初始条件：线性表 L 已存在。操作结果：销毁线性表 L 。ListEmpty( L )初始条件：线性表L已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。ListLength( L )初始条件：线性表 L 已存在。操作结果：返回 L 中元素个数。PriorElem( L, cur_e, &pre_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。NextElem( L, cur_e, &next_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义。GetElem( L, i, &e )初始条件：线性表 L 已存在，1iLengthList(L)。操作结果：用 e 返回 L 中第 i 个元素的值。LocateElem( L, e, compare( ) )初始条件：线性表 L 已存在，compare( ) 是元素判定函数。操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L, visit( )初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。操作结果：依次对 L 的每个元素调用函数 visit( )。一旦 visit( ) 失败，则操作失败。ClearList( &L )初始条件：线性表 L 已存在。操作结果：将 L 重置为空表。PutElem( &L, i, &e )初始条件：线性表L已存在，1iLengthList(L)。操作结果：L 中第 i 个元素赋值同 e 的值。ListInsert( &L, i, e )初始条件：线性表 L 已存在，1iLengthList(L)+1。操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。ListDelete( &L, i, &e )初始条件：线性表 L 已存在且非空，1iLengthList(L)。操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。四、 实验记录 (自己设计测试数据验证算法的正确性)五、 实验小结六、 思考题1. 线性表的顺序存储有何优缺点？2. 各举一两个例子说明求解什么样的问题用顺序存储较好。【源代码说明】1 文件名：2 操作说明：实验二 链表基本操作的实现专业： 班级： 学号： 姓名： 实验地点： 实验时间： 指导教师： 【实验课程名称】算法与数据结构【实验项目名称】链表基本操作的实现一、 实验目的1掌握线性表链式存储基本操作；2学会设计实验数据验证程序。二、 实验仪器及环境计算机，window xp操作系统，VC+6.0三、 实验内容及步骤线性表链式存储基本操作存储结构定义：typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;实现的基本操作：InitList( &L )操作结果：构造一个空的线性表 L 。DestroyList( &L )初始条件：线性表 L 已存在。操作结果：销毁线性表 L 。ListEmpty( L )初始条件：线性表L已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。ListLength( L )初始条件：线性表 L 已存在。操作结果：返回 L 中元素个数。PriorElem( L, cur_e, &pre_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。NextElem( L, cur_e, &next_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义。GetElem( L, i, &e )初始条件：线性表 L 已存在，1iLengthList(L)。操作结果：用 e 返回 L 中第 i 个元素的值。LocateElem( L, e, compare( ) )初始条件：线性表 L 已存在，compare( ) 是元素判定函数。操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L, visit( )初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。操作结果：依次对 L 的每个元素调用函数 visit( )。一旦 visit( ) 失败，则操作失败。ClearList( &L )初始条件：线性表 L 已存在。操作结果：将 L 重置为空表。PutElem( &L, i, &e )初始条件：线性表L已存在，1iLengthList(L)。操作结果：L 中第 i 个元素赋值同 e 的值。ListInsert( &L, i, e )初始条件：线性表 L 已存在，1iLengthList(L)+1。操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。ListDelete( &L, i, &e )初始条件：线性表 L 已存在且非空，1iLengthList(L)。操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。四、 实验记录(自己设计测试数据验证算法的正确性)五、 实验小结六、 思考题1. 线性表的链式存储有何优缺点？2. 各举一两个例子说明求解什么样的问题用链式存储较好。【源代码说明】1 文件名：2 操作说明：实验三 串基本操作的实现专业： 班级： 学号： 姓名： 实验地点： 实验时间： 指导教师： 【实验课程名称】算法与数据结构【实验项目名称】串基本操作的实现一、 实验目的1 理解定长顺序串的存储结构及基本操作的定义；2 掌握定长顺序串的基本操作；3 学会设计实验数据验证程序。二、 实验环境计算机，window xp操作系统，VC+6.0三、 实验内容1. 存储结构定义：define MAXSTRLEN 255 /串的长度最大为255typedef unsigned char SStringMAXSTRLEN+1; /0号单元存放串的长度，其最大值刚好是2552. 实现的基本操作： StrAssign (&T, chars)初始条件：chars 是串常量。操作结果：赋于串T的值为 chars。StrCopy (&T, S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。 DestroyString (&S)初始条件：串 S 存在。操作结果：串 S 被销毁。 StrEmpty (S)初始条件：串 S 存在。操作结果：若 S 为空串，则返回 TRUE，否则返回 FALSE。 StrCompare (S, T)初始条件：串 S 和 T 存在。操作结果：若ST，则返回值=0；若S=T，则返回值0；若ST，则返回值0。StrLength (S)初始条件：串 S 存在。操作结果：返回串 S 序列中的字符个数，即串的长度。ClearString (&S)初始条件：串 S 存在。操作结果：将 S 清为空串。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 SubString (&Sub, S, pos, len) 初始条件：串S存在，1posStrLength(S)且0lenStrLength(S)-pos+1。 操作结果：用 Sub 返回串S的第 pos 个字符起长度为 len 的子串。 Index (S, T, pos) 初始条件：串S和T存在，T 是非空串，1posStrLength(S)。 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。 Replace (&S, T, V) 初始条件：串 S，T 和 V 存在，T 是非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert (&S, pos, T) 初始条件：串 S 和 T 存在，1posStrLength(S)1。 操作结果：在串 S 的第 pos 个字符之前插入串 T。 StrDelete (&S, pos, len) 初始条件：串 S 存在，1posStrLength(S)-len+1。 操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串。四、 测试及实验结果(1) 建立如下字符串S1:“输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归。”(2) 输出S1;(3) 查找“二叉树”出现的位序;(4) 将文中的”顺序”改为”次序”；(5) 建立如下字符串S2:例如用“”或用“-1”表示字符序列或正整数序列空结点。(6) 将S1串与S2串连接成S串;(7) 输出S串的值与串的长度；(8) 删除S1串和S2串；五、 实验小结六、 思考题定长顺序串的存储结构与c语言中用字符指针存储字符串相比有何优点？【源代码说明】1 文件名：2 操作说明：实验四 二叉树基本操作的实现专业： 班级： 学号： 姓名： 实验地点： 实验时间： 指导教师： 【实验课程名称】算法与数据结构【实验项目名称】二叉树基本操作的实现一、 实验目的1 理解二叉树概念及其存储结构；2掌握采用二叉链储存结构的二叉树基本操作；3学会设计实验数据验证程序。二、 实验环境计算机，window xp操作系统，VC+6.0三、 实验内容1. 存储结构定义： typedef struct BiTNode /结点定义 TElemType data; struct BiTNode * lchild, * rchild; BiTNode,*BiTree;2. 实现的基本操作： InitBiTree(&T);操作结果：构造空二叉树 T。 CreateBiTree(&T, definition);初始条件：definition 给出二叉树 T 的定义。操作结果：按 definition 构造二叉树 T。 DestroyBiTree(&T);初始条件：二叉树 T 存在。操作结果：销毁二叉树 T。 BiTreeEmpty(T);初始条件：二叉树 T 存在。操作结果：若T为空二叉树，则返回 TRUE，否则返回 FALSE。 BiTreeDepth(T);初始条件：二叉树 T 存在。操作结果：返回 T 的深度。 Root(T);初始条件：二叉树 T 存在。操作结果：返回 T 的根。 Value(T, e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的值。 Parent(T, e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回空。 LeftChild(T, e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的左孩子。若 e 无左孩子，则返回空。 RightChild(T, e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的右孩子。若 e 无右孩子，则返回空。 LeftSibling(T, e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟，则返回空。 RightSibling(T, e);初始条件：二叉树 T 存在，e 是 T 的结点。操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回空。 PreOrderTraverse(T, visit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 InOrderTraverse(T, vsit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。 PostOrderTraverse(T, visit();初始条件：二叉树T存在，visit 是对结点操作的应用函数。操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 LevelOrderTraverse(T, visit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 ClearBiTree(&T);初始条件：二叉树 T 存在。操作结果：将二叉树 T 清为空树。 Assign(&T, &e, value);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：结点 e 赋值为 value。 InsertChild(&T, p, LR, c);初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成为 c 的右子树。 DeleteChild(&T, p, LR);初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。四、 测试数据及实验结果(参照前几个实验的测试方法自己设计测试数据验证算法的正确性)五、 实验小结六、 思考题1举例说明什么样的二叉树采用顺序存储，什么样的二叉树采用二叉链存储。2总结编程调试过程中遇到的问题，你采取的解决方案。若未能测试通过所有操作，请分析原因。【源代码说明】1 文件名：2 操作说明：实验五 图基本操作的实现专业： 班级： 学号： 姓名： 实验地点： 实验时间： 指导教师： 【实验课程名称】算法与数据结构【实验项目名称】图基本操作的实现一、 实验目的1 理解图的存储结构；2掌握邻接矩阵储存结构的图基本操作；3学会设计实验数据验证程序。二、 实验环境计算机，window xp操作系统，VC+6.0三、 实验内容1. 存储结构定义： #define INFINITY INT_MAX; / 最大值#define MAX_VERTEX_NUM 20;/ 最大顶点个数typedef enum DG, DN, AG, AN GraphKind;/ 类型标志有向图,有向网,无向图,无向网typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。对无权图，用1或0 /表示相邻否；对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct / 图的定义VertexType vexsMAX_VERTEX_NUM; / 顶点信息AdjMatrix arcs; / 表示顶点之间关系的二维数组int vexnum, arcnum; / 图的当前顶点数和弧(边)数GraphKind kind; / 图的种类标志 MGraph;2. 实现的基本操作： CreateGraph(&G, V, VR);初始条件：V 是图的顶点集，VR 是图中弧的集合。操作结果：按 V 和 VR 的定义构造图 G。 DesstroyGraph(&G);初始条件：图 G 存在。操作结果：销毁图 G。 LocateVex(G, u);初始条件：图 G 存在，u 和 G 中顶点有相同特征。操作结果：若 G 中存在和 u 相同的顶点，则返回该顶点在图中位置；否则返回其它信息。 GetVex(G, v);初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：返回 v 的值。FirstAdjVex(G, v);初始条件：图 G 存在，v 是 G 中某个顶点。操作结果：返回 v 的第一个邻接点。若该顶点在