a数据结构实验指导书(09计本1.2)

《数据结构》实验指导书目录前言.............................................................................................................1实验一、线性表基本操作的实现............................................................2实验二、集合的并、交、差运算............................................................7实验三、二叉树的基本操作的实现......................................................12实验四、哈夫曼编/译码器....................................................................161前言《数据结构》是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。《数据结构》是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。2实验一线性表基本操作的实现姓名_________座号________级本科______________专业________班日期:【实验课程名称】数据结构【实验项目名称】线性表基本操作的实现【实验目的】1掌握线性表顺序存储基本操作；2掌握线性表链式存储基本操作；3学会设计实验数据验证程序。【实验仪器及环境】计算机，windowxp操作系统，VC++6.0【实验内容及步骤】1．线性表顺序存储基本操作存储结构定义：#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址intlength；//当前长度intlistsize;//当前分配的存储容量（以sizeof(ElemType)为单位）}SqList；实现的基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)3初始条件：线性表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已存在，1≤i≤LengthList(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已存在。4操作结果：将L重置为空表。PutElem(&L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)。操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。2．线性表链式存储基本操作存储结构定义：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;实现的基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。5ListLength(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已存在，1≤i≤LengthList(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已存在，1≤i≤LengthList(L)。操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)6初始条件：线性表L已存在，1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。【测试数据及实验结果】(自己设计测试数据验证算法的正确性)【实验小结】1.线性表的顺序存储和链式存储各有何优缺点？2.各举一两个例子说明求解什么样的问题用顺序存储，什么样的问题用链式存储较好。【源代码说明】1．文件名：2．操作说明：7实验二集合的并、交和差运算姓名_________座号________级本科______________专业________班日期:【实验课程名称】数据结构【实验项目名称】集合的并、交和差运算【实验目的】1掌握有序链表的基本操作；2掌握集合的基本操作；3学会采用抽象数据分层设计程序。【实验仪器及环境】计算机，windowxp操作系统，VC++6.0【实验内容及步骤】（1）本演示程序中，集合的元素限定为小写字母字符[‘a’.’z’],集合的大小n27.集合输入的形式为一个以“回车符”为结束标志的字符串顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。输出的运算结果字符串中将不含重复字符或非法字符。（2）演示程序以用户和计算机的对话形式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。（3）程序执行的命令包括：1）构造集合1；2）构造集合2；3）求并集；4）求交集；5）求差集；6）结束。“构造集合1”和“构造集合2”时，需以字符串的形式键入集合元素。为实现上述程序功能，应以有序链表表示集合。为次，需要两个抽象数据类型：有序表和集合。1有序链表的基本操作存储结构定义：8typedefstruct{LinkTypehead,tail;//分别指向线形表的头结点和尾结点Intsize;//指示链表当前的长度}OrderedList;实现的基本操作：InitList(&L)操作结果：构造一个空的的有序表L。DestroyList(&L)初试条件：有序表L已存在。操作结果：销毁有序表L。ListLength(L)初试条件：有序表L已存在。结果操作：返回有序表L的长度。ListEmpty(L)初试条件：有序表L已存在。结果操作：若有序L为空表，则返回True,否则返回False,GetElem(L,pos)初试条件：有序表L已存在。结果操作：1≤pos≤Length(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中一个元素9结果操作：在有序表L中q指示的元素之后插入元素eListTraverse(q,visit())初试条件：有序表L已存在，q指示L中一个元素结果操作：依次对L中q指示的元素开始的每个元素调用函数visit()2集合的基本操作存储结构定义：typedefOrderedListOrderedSet;实现的基本操作：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）主程序模块：10voidmain(){do{接受命令；处理命令；}while（“命令”=“退出”）；}（2）集合单元模块——实现集合的抽象数据类型；（3）有序表单元模块——实现有序表的抽象数据类型；（4）结点结构单元模块——定义有序表的结点结构‘各模块之间的调用关系如下：主程序模块↓集合单元模块↓有序表单元模块↓结点结构单元模块【测试数据及实验结果】（1）Set1=”magazine”,Set2=”paper”,Set1∪Set2=”aegimnprz”,Set1∩Set2=”ae”,Set1-Set2=”gimnz”。（2）Set1=”012oper4a6tion89”,Set2=”errordata”,Set1∪Set2=”adeinoprt”,Set1∩Set2=”aeort”,Set1-Set2=”inp”。【实验小结】1为什么要选择有序链表