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

数据结构编撰闽江学院计算机实验教学中心印制i目录前言1实验一、线性表基本操作的实现2实验二、集合的并、交、差运算8实验三、二叉树的基本操作的实现12实验四、哈夫曼编/译码器1617前言数据结构是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。数据结构是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。实验一、线性表基本操作的实现 实验目的1掌握线性表顺序存储基本操作；2掌握线性表链式存储基本操作；3学会设计实验数据验证程序。实验环境计算机，window xp操作系统，vc+6.0实验内容1 线性表顺序存储基本操作存储结构定义：#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。2 线性表链式存储基本操作存储结构定义：typedef struct lnode /结点类型 elemtype data; struct lnode *next;*link,*position;typedef struct /链表类型link head,tail;int len;linklist;实现的基本操作：makenode(&p,e)操作结果：分配由p指向的值为e的结点，并返回ok；若分配失败，返回errorfreenode(p)操作结果：释放p所指结点initlist( &l )操作结果：构造一个空的线性表 l 。destroylist( &l )初始条件：线性表 l 已存在。操作结果：销毁线性表 l 。clearlist( &l )初始条件：线性表 l 已存在。操作结果：将 l 重置为空表，并释放结点空间。insfirst（l，s）初始条件：线性表 l 已存在。操作结果：将s所指结点插入在第一个结点之前。delfirst（l，&q）初始条件：线性表 l 已存在。操作结果：删除链表中的第一个结点并以q返回。append（ &l，s）初始条件：线性表 l 已存在。操作结果：将s所指的一串结点链接到l的最后一个结点之后，并改变l的尾指针。 remove(&l,&q)初始条件：线性表 l 已存在。操作结果：删除l的尾结点以q返回，并改变l的尾指针。insbefore（&l，&p,s）初始条件：线性表 l 已存在,p指向其中一个结点。操作结果：将s所指结点插入在p所指结点之前，并将p指向新插入的结点。insafer（&l，&p,s）初始条件：线性表 l 已存在,p指向其中一个结点。操作结果：将s所指结点插入在p所指结点之后，并将p指向新插入的结点。 setcurelem(&p,e)初始条件：p指向链表中某个结点。操作结果：用e更新p所指结点元素的值。getcurelem( p )初始条件：p指向链表中某个结点。操作结果：返回p所指结点元素的值。listempty( l )初始条件：线性表l已存在。操作结果：若 l 为空表，则返回 true，否则返回 false。listlength( l )初始条件：线性表 l 已存在。操作结果：返回 l 中元素个数。gethead（l）初始条件：线性表 l 已存在。操作结果：返回 l 中头结点的位置。getlast（l）初始条件：线性表 l 已存在。操作结果：返回 l 中最后一个结点的位置。priorpos( l，p )初始条件：线性表 l 已存在，p指向其中一个结点。操作结果：返回p所指结点的直接前驱的位置，若无前驱，返回null。nextpos( l，p )初始条件：线性表 l 已存在，p指向其中一个结点。操作结果：返回p所指结点的直接后继的位置，若无后继，返回null。locatepos（l，i，&p）初始条件：线性表 l 已存在。操作结果：用p带回l中第i个结点的位置并返回ok，若i值不合法，返回errorl。locateelem( l, e, compare( ) )初始条件：线性表 l 已存在，compare( ) 是元素判定函数。操作结果：返回 l 中第1个与 e 满足关系 compare( ) 的元素的位序。若这样的元素不存在，则返回值为null。listtraverse(l, visit( )初始条件：线性表 l 已存在，visit( ) 为元素的访问函数。操作结果：依次对 l 的每个元素调用函数 visit( )。一旦visit( ) 失败，则操作失败。3. 测试数据及实验结果(自己设计测试数据验证算法的正确性)相关练习1. 线性表的顺序存储和链式存储各有何优缺点？2. 各举一两个例子说明求解什么样的问题用顺序存储，什么样的问题用链式存储较好。 实验二、集合的并、交、差运算 实验目的1掌握有序链表的基本操作；2掌握集合的基本操作；3学会采用抽象数据分层设计程序。实验环境计算机，window xp操作系统，vc+6.0实验内容（1）本演示程序中，集合的元素限定为小写字母字符a.z,集合的大小n27.集合输入的形式为一个以“回车符”为结束标志的字符串顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。（2）演示程序以用户和计算机的对话形式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。（3）程序执行的命令包括：1）构造集合1；2）构造集合2；3）求并集；4）求交集；5）求差集；6）结束。“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。为实现上述程序功能，应以有序链表表示集合。为次，需要两个抽象数据类型：有序表和集合。1有序链表的基本操作存储结构定义：typedef struct linktype head,tail; /分别指向线形表的头结点和尾结点 int size; /指示链表当前的长度orderedlist;实现的基本操作：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的元素的位置，并返回函数值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( &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存在操作结果：按字母次序顺序显示集合t的全部元素 3主程序：（1）主程序模块：void main() do 接受命令；处理命令； while （“命令”=“退出”）；（2）集合单元模块实现集合的抽象数据类型；（3）有序表单元模块实现有序表的抽象数据类型；（4）结点结构单元模块定义有序表的结点结构各模块之间的调用关系如下： 主程序模块 集合单元模块 有序表单元模块 结点结构单元模块测试数据及实验结果（1）set1=”magazine”, set2=”paper”, set1set2=”aegimnprz”, set1set2=”ae”, set1-set2=”gimnz”。（2）set1=”012oper4a6tion89”, set2=”error data”,set1set2=”adeinoprt”, set1set2=”aeort”, set1-set2=”inp”。相关练习1为什么要选择有序链表存储结构？2分析你的集合并、交、差运算算法的时间复杂度。实验三、二叉树的基本操作的实现 实验目的1掌握二叉树的存储结构定义；2掌握二叉树基本操作；3学会设计实验数据验证算法实验环境计算机，window xp操作系统，vc+6.0实验内容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);初始条件：二叉树 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 所指结点的左或右子树。3. 测试数据及实验结果(自己设计测试数据验证算法的正确性)相关练习1举例说明什么样的二叉树采用顺序存储，什么样的二叉树采用二叉链存储。2总结编程调试过程中遇到的问题，你采取的解决方案。若未能测试通过所有操作