1、算法与数据结构实验指导书算法与数据结构实验指导书（适用于计算机科学与技术）目录前言 1实验一、线性表基本操作的实现 2实验二、集合的并、交、差运算 7实验三、二叉树的基本操作的实现 12实验四、哈夫曼编/译码器 16前言算法与数据结构是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。算法与数据结构是一门理论和实践相结合的课程，它在整
2、个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。实验一 线性表基本操作的实现姓名_ 座号 _ _ 级本科_专业 _班 日期: 【实验课程名称】算法与数据结构【实验项目名称】线性表基本操作的实现【实验目的】1掌握线性表顺序存储基本操作；2掌握线性表链式存储基本操作；3学会设计实验数据验证程序。【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】1 线性表顺序存储基本操作存储结构定义：#de
3、fine 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已存在。操
4、作结果：若 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
5、)初始条件：线性表 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
6、 )初始条件：线性表 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。2 线性表链式存储基
7、本操作存储结构定义：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
8、 )初始条件：线性表 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 已存在，com
9、pare( ) 是元素判定函数。操作结果：返回 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 的值。
10、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 操作
11、说明：实验二 集合的并、交和差运算姓名_ 座号 _ _ 级本科_专业 _班 日期: 【实验课程名称】算法与数据结构【实验项目名称】集合的并、交和差运算【实验目的】1掌握有序链表的基本操作；2掌握集合的基本操作；3学会采用抽象数据分层设计程序。【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】（1）本演示程序中，集合的元素限定为小写字母字符a.z,集合的大小n27.集合输入的形式为一个以“回车符”为结束标志的字符串顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。（2）演示程序以用户和计算机的对话形式执行，
12、即在计算机终端上显示“提示信息”之后，由用户在键盘输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。（3）程序执行的命令包括：1）构造集合1；2）构造集合2；3）求并集；4）求交集；5）求差集；6）结束。“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。为实现上述程序功能，应以有序链表表示集合。为次，需要两个抽象数据类型：有序表和集合。1有序链表的基本操作存储结构定义：typedef struct LinkType head,tail; /分别指向线形表的头结点和尾结点 Int size; /指示链表当前的长度OrderedList;实现的
13、基本操作：InitList(&L)操作结果：构造一个空的的有序表L。DestroyList(&L)初试条件：有序表L已存在。操作结果：销毁有序表L。ListLength (L)初试条件：有序表L已存在。结果操作：返回有序表L的长度。ListEmpty (L)初试条件：有序表L已存在。结果操作：若有序L为空表，则返回True,否则返回False,GetElem(L,pos)初试条件：有序表L已存在。结果操作：1posLength(L),则返回表中第pos个数据元素LocateElem (L,e，&q)初试条件：有序表L已存在。结果操作：若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置
14、，并返回函数值TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回 函数值FALSEAppend (&L,e)初试条件：有序表L已存在。结果操作：在有序表L的末尾插入元素eInsertAfter(&L,q,e)初试条件：有序表L已存在， q指示L中一个元素结果操作：在有序表L中q指示的元素之后插入元素eListTraverse(q,visit()初试条件：有序表L已存在， q指示L中一个元素结果操作：依次对L中q指示的元素开始的每个元素调用函数visit()2集合的基本操作存储结构定义：typedef OrderedList OrderedSet;实现的基本操作：CreateSet( &
15、T,Str)初始条件：Str为字符串操作结果：生成一个由Str中小写字母构成的集合TDestroySet( &T)初始条件：集合T已存在操作结果：销毁集合T的结构Union(&T,S1,S2)初始条件：集合 S1和S2存在操作结果：生成一个由S1和S2的 并集 构成的集合TIntersection( &T,S1,S2)初始条件：集合 S1和S2存在操作结果：生成一个由S1和S2的 交集 构成的集合TDifference(&T,S1,S2)初始条件：集合 S1和S2存在操作结果：生成一个由S1和S2的 差集 构成的集合TPrintSet(T)初始条件：集合 S1和S2存在操作结果：按字母次序顺序
16、显示集合T的全部元素 3主程序：（1）主程序模块：void main() do 接受命令；处理命令； while （“命令”=“退出”）；（2）集合单元模块实现集合的抽象数据类型；（3）有序表单元模块实现有序表的抽象数据类型；（4）结点结构单元模块定义有序表的结点结构各模块之间的调用关系如下： 主程序模块 集合单元模块 有序表单元模块 结点结构单元模块【测试数据及实验结果】（1）Set1=”magazine”, Set2=”paper”, Set1Set2=”aegimnprz”, Set1Set2=”ae”, Set1-Set2=”gimnz”。（2）Set1=”012oper4a6tion
17、89”, Set2=”error data”,Set1Set2=”adeinoprt”, Set1Set2=”aeort”, Set1-Set2=”inp”。【实验小结】1为什么要选择有序链表存储结构？2分析你的集合并、交、差运算算法的时间复杂度。【源代码说明】1文件名：2操作说明：实验三 二叉树基本操作的实现姓名_ 座号 _ _ 级本科_专业 _班 日期: 【实验课程名称】算法与数据结构【实验项目名称】二叉树基本操作的实现【实验目的】1掌握二叉树的存储结构定义；2掌握二叉树基本操作；3学会设计实验数据验证算法【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】
18、1二叉树的二叉链表存储结构定义：typedef struct BiTNode /结点定义 TElemType data; struct BiTNode * lchild, * rchild; BiTNode,*BiTree;实现的基本操作：InitBiTree(&T);操作结果：构造空二叉树 T。CreateBiTree(&T, definition);初始条件：definition 给出二叉树 T 的定义。操作结果：按 definition 构造二叉树 T。DestroyBiTree(&T);初始条件：二叉树 T 存在。操作结果：销毁二叉树 T。BiTreeEmpty(T);初始条件：二叉树
19、 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 无左孩
20、子，则返回空。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 是对结点操作的应用函
21、数。操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。InOrderTraverse(T, vsit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。PostOrderTraverse(T, visit();初始条件：二叉树T存在，visit 是对结点操作的应用函数。操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。LevelOrderTraver
22、se(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 不相交且右子树为
23、空。操作结果：根据 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掌握哈夫
24、曼编码、译码的实现；2学会设计一个完整的编/译码系统【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】1. 初始化：（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存入文件hfmTree.txt中。. 编码：（Edcoding）。利用建好的哈夫曼树（如不在内存则从文件hamTree.txt中读入），对文件TobeTran.txt中的正文进行编码，然后将结果存入文件CodeFile.txt 中。3. 译码：（Decoding）。利用已建好的哈夫曼树将文件CodeFile.txt中的代码进行译码，结果存入文件T
25、extFile.txt中。4. 打印代码文件（Print）。将文件CodeFile.txt以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。5. 打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据及实验结果】（1）利用教科书例6-2中的数据调试程序。（2）利用下表给出的字符集合频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161【实验小结】【源代码说明】1文件名：2操作说明：
