数据结构实验指导

1、目录实验说明 . 2实验要求 . 3实验 1 线性表的顺序存储结构的实现及其应用. 4实验 2 线性表的链式存储结构的实现及其应用. 9实验 3 栈和队列的存储结构的实现 16实验 4 树和二叉树的存储结构的实现 17实验 5 图的存储结构的实现 18实验 6 图的简单应用 19实验 7 查找算法的实现 20实验 8 排序算法的实现 21实验说明A. 每班学习委员或班长在 上机实验前一周 到软件学院教务 室(创新大楼西楼 4 楼教务室)购买上机实验报告B. 上机实验报告封面 上要写完整：班级、姓名、指导老师姓名， 学期、报告日期等 。C. 其它1) 本学期上机实验一共 16 学时，大家需要完成

2、 8 个实验。2) 上机前写好预习报告 (即上机报告中调试分析之前的内容) ，准备 好程序和测试数据。3) 报告要简洁明了， 一个实验报告只有 3 页，书写时字体大小不要太大，以免 写不下。4) 请按照指定时间完成上机报告，上机报告于 课程结束后上 交存 档，缺交上机报告达三分之一者取消考试资格。5) 请大家认真完成上机任务及上机报告， 严禁抄袭 。有任何问题可 以及时跟任课教师联系！6) 希望在愉快的环境中完成本学期的学习， 请大家积极配合！ 谢谢！实验要求一、实验步骤1问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、 设计要求和 约束以及基本数据特性，数据元素之间

3、的关系等。2. 数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案（必须连同算法一起考虑 ） ，确定主要的数据结构（可以采用抽象数据类型描述）及全局变量。对引 入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。3. 算法设计算法设计分概要设计和详细设计。 概要设计着重解决程序的模块设计问题， 这包括考虑 如何把被开发的问题程序自顶向下分解成若干顺序模块， 并决定模块的接口， 即模块间的相 互关系以及模块之间的信息交换问题。 概要设计可以由模块的功能说明和模块之间的调用关 系图完成。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言

4、描述。4. 测试用例设计准备典型测试数据和测试方案， 测试数据要有代表性、 敏感性， 测试方案包括模块测试 和模块集成测试。5. 上机调试对程序进行编译， 纠正程序中可能出现的语法错误。 测试前， 先运行一遍程序看看究竟 将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪， 包括打印执行路径或输出中间变量值等手段。二、实验报告每次上机实验前，应该写好预习报告。 预习报告 包括如下内容：（1）问题描述：简述题目要做什么。（2）设计部分：包括抽象数据类型描述，其他各个模块的功能说明，模块之间的调用 关系图，存储结构的定义、基本操作的实现、其他模块的算法等。（3）测试用例

5、设计每次实验结束后， 在预习报告的基础上撰写完整的实验报告。 实验报告 应包括如下内容：（1）、（ 2）同预习报告（3）调试报告：调试过程中遇到的问题以及如何解决；对设计和编码的讨论和分析。（4）测试结果。根据预习报告中设计的测试用例进行程序测试，可以贴相应的运行结 果截图。（5）算法分析与改进：重要算法的时间复杂度和空间复杂度分析；算法改进的设想。（ 6）总结和体会所有实验做完后，上交上机实验源程序（ .h ， .cpp ）、可执行文件（ .Exe ）和相应的 运行结果截图。 源程序要加注释。 如果题目规定了测试数据， 则截图结果要包含这些测试数 据和运行输出，当然还可以含有其它测试数据和运

6、行输出（有时需要多组数据）。实验 1 线性表的顺序存储结构的实现及其应用实验目的1 熟悉 C 语言的上机环境，掌握使用 VC 环境上机调试程序的基本方法；2 会定义线性表的顺序存储结构。3 熟悉对顺序表的一些基本操作和具体的函数定义。4 理解利用基本操作进行一些实际的应用型程序设计。实验要求1 独立完成。2 程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1、基础题： 编写应用程序（填空） ，实现可以在顺序表中插入任意给定数据类型数据的功能 （定义为 ElemType 抽象数据类型）。要求在主函数中定义顺序表并对该顺序表插 入若干个整数类型的数据（正整数） ，对它们求和并输出。请把

7、主函数设计为一 个文件 SqList.cpp ，其余函数设计为另一个文件 SqList.h 。 请填空完成以下给出的源代码并调试通过。（ 1） 文件 SqList.h:typedef struct ListElemType *elem;int length;SqList;void InitList（SqList &L） / 构造一个空的顺序表void ClearList(SqList &L) / 清空线性表，不销毁int ListLength (SqList L) / 求线性表长度bool ListInsert (SqList &L, int i , ElemType e) / 在线性表 L

8、中第 i 个数据元素之前插入新数据元素 e ElemType GetElem（SqList L, int i） /在线性表 L 中求序号为 i 的元素，该元素作为函数返回值(2) 文件 SqList.cpp :#include vstdio.h#include typedef ElemType;II填空 1#define MAXSize 10#include SqList.hvoid main(void)SqList myList;int i=1, x, sum=0, n;InitList ();II填空 2scanf( %d ”, &x);while ( x!= -1 )if (Listin

9、sert (myList, i, )=false) II填空 3printf(错误!n);return ;i+;scanf( %d ”, &x);n = ListLength (myList);for (i=1; iv=n; i+)II求所有数据元素的和x=GetElem(myList, i);sum =+ x;II填空 4printf(%dn , sum);ClearList(myList);2. 应用题(1) 编写函数 bool DeleteElem(SqList &L, int min, int max)实现从顺序表中删 除其值在给定值min和max之间(min 输入“工程名称”和存储“

10、位置”一一 “确定”。2.默认创建“一个空工程”一一 “完成”一一 “确定”Win32 Cwscle Appkalrcini -1 共 1 爭址姐恵创建汁么直聖审控制台程序？ t空工稍Er 一个向卑的程序IS）一HeIIc, Wfirldr 程序何一牛支持wrc的稈田时V上一步完成麟 1Win32 XnMilEApml测no將芸创建一 新的以下规格的工骨架；* Efnply ehule- ppIieMan.* Ns IIHc will be gMed r 制血 d t I be RoleeL工程目录:F他M确M取消3. “文件”菜单 “新建” “文件” “C/C+ Header File”一

11、输入文件名SqList.h （默认为.h类型，可省去.h） “确定”4. “文件”菜单一一 “新建”一一 “文件” 一一 “ C+ Source File”输入文件名SqList.cpp （默认为.cpp类型，可省去.cpp）站工作区旬qr： 1工窄 likG3Saurce Files国 SqLlsLcpp-ziflesderFiles 岡Sql臥h _ _I nsnur “确定”。文件迟龟也J4AjiS | Gf Q 0 | 毎略 | ：|Glabals)*|All gl5打开FileView双击SqList.h，完成头文件的编写。SqList.h主要含结构体的定 义和函数的实现。ttdef

12、ine MANSizt 50 ttdefine OUERFLO -2 typedef struct ListElemType elem;int 丄emgth;JSqList;uaid InitList(SqList &L)1 初始化线性表L ,elen=new ElenTjjpeMAXSize;if(!L.elem) exit(OUERFLOU);L _length=0；int ListLength (SqList L) 求线性表长度 return(L.length);bool Listinsert (SqList &L, int i ElenType e)在第i个位置向线性表插入一个元素ai

13、nt ji；if (i L_length+1) return False;/插入位置不合法iF (L.length = HAKSize) return false;for(j-L.length; j-i;-j)L-elemj = L.elemj-1; /摘入位置及之后的元素右移 L .eleini-1 = 9;+*L-lengtH;/ 表长増return true;ElenType GetElenfSqList L, int i) 在线性表L中求序号为i的元素，该元素作为函数返回值if(iL.lengtri) printFC i不注口叮范围内T ； exlt(OUERFLOW)；returnf

14、L elemi-1);uoid ClearList(SqList &L) -6打开FileView双击SqList.cpp,完成源文件的编写和填空。SqList.cpp主要含 mai n()函数的实现。闔亟! B 7.编译运行。实验 2 线性表的链式存储结构的实现及其应用实验目的1 掌握线性表的建立、插入、删除等基本操作的编程实现，进一步编程实现查找、排序等 操作，存储结果采用顺序表存储结构。2 理解利用基本操作进行一些实际的应用型程序设计。实验要求1 可以依次完成主要功能来体现功能的正确性，也可以用菜单管理完成大部分功能，要求 可以重复运行。2 准备好测试数据，程序调试正确，有执行结果。3

15、程序是自己开发的，在界面上注明 * 原创；参考或改写他人的，注明 * 参考他人版。实验内容(基础题必做，应用题任选 1 个)1、基础题： 线性表基本操作的实现 (演示单链表的 创建、插入、删除、查找、输出等操 作)，通过简单实例测试各基本操作函数算法的正确性。基本操作函数如下：Status InitList(LinkList &L)/初始化只含有头结点的空的单链表，返回函数状态值 void PrintList(LinkList L)void DestroyList(LinkList &L) void ClearList(LinkList &L) bool ListEmpty(LinkList

16、L) int ListLength(LinkList L)/销毁单链表/清空单链表，仅保留头结点/判断是否为空链表/返回单链表的长度/遍历函数，顺序输出单链表中的各元素的值Status GetElem(LinkList L,int i,ElemType &e) /用参数 e 返回单链表 L 中第 i 个元素的值Status ListInsert(LinkList &L,int i,ElemType e)/在单链表 L 的第 i 个数据元素之前插入数据元素 eStatus ListDelete(LinkList &L,int i,ElemType &e) /删除单链表 L 中第 i 个结点，并用

17、 e 返回其值 int LocateElem(LinkList L,ElemType e)/返回 e 元素在单链表 L 中的位序，若不存在，返回 02、应用题：(1) 将一个已知的单链表进行逆置运算，如(a1,a2,a)变为(an,a2,a1。(2) 求集合A、B的并集C。(3) 归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。实验步骤参考:“ wi n32 Con sole“确定”。2.默认创建“一个空工程”一一 “完成” “确定”WinM CansDlc Application籽曲削理一亍竊的-Z_稈肾第-t Emply cnnsale upplir:西llnib+ Hu l

18、iffi-will beur added iu Uie- projcti.丄程目录:FUInkLiul1打开Visual C+6.0,，文件”菜单“新建”“工程”- Applicatio n ” 输入“工程名称”和存储“位置” 3. “文件”菜单_ “新建” _ “文件”_ 输入文件名LinkList.h （默认为.h类型，可省去.h）“C/C+ Header File ” “确定”文井 工程I工怔区|其它文特|.菱|Adlvc SrrviEr PageijHIHL Pap匕 *Miicrn Filef KOll Script File光拯文件刎萤因文忤 Q文本文件 円啜翩A 爭贷源欖拽Lin

19、ULisI-丈件容脚：|LlrakLI$teiici：|FlinldLlB4P甌到丁程|6|；I * 1：4. “文件”菜单一一 “新建”一一 “文件” 一一 “ C+ Source File”输入文件名LinkList.cpp （默认为.cpp类型，可省去.cpp） “确定”程工隹区適旺t辽工.-.O LinkListfilfes-Source Files 世1 LinkList3 Hca 倉 LinkListh i ResnurnTft&5. 打开FileView双击LinkList.h，完成头文件的编写。LinkList.h主要含结构体的 定义和函数的实现。typedef struct

20、LNode定又单锂表鉛点突型ElemType data:struct LNode *next;LHode,aLinkList;int InitLiSt(LinkLiSt &L)初始化只含有头结点敢空的单链表 L= LNode; 创建头结点 if(L=NULL)next=NULL;return 1:uoid DestroyList(LirikList &L)销毀单嶺表LinkList p; while (L)next; delete p;L=HIJLL；uoid ClearList(LinkList &L)清空单链表，仅標留头结点LlnkList p; whilc(L-next)p=L-next

21、; L-next=p-next; delete p;int ListLength(LinkList L)返回单链表的长度LinkL1st p=L:int 1=6;while (p-next* = NULL)数到最石一个结点为止next；return i;uold PrintList(LinkList L)顺序输岀单链表中的各元素LinkList p=L-next; while (p*=NULL) coutdatanext; coutpndl;bool ListEmptj|(LinkList L)判断是否为空链表 if(L-next=NULL) return true； elsereturn f

22、alse;int GetEleR(LinkList L ,int i rElenType &e)用E返回单链表L中第i个元素的值if(inext;int j=1;while (ji & p怙NULL)next;j+；if p=HULL) ji旦p为空指针了，即i超岀?1.-n范围了 return 0;elsedata; return 1;int LocateElenCLinkList L jElemTpee)返回元素在单链表L中的位序，若不存在，返回*LinkList p-L-next;int n=1;uhlle (p!=NULL & p-data*=e)next;n+ ； (P-NULL)直

23、到最后也没找到等于元素e的结点returnf 0);elsereturn(n);int List Insert(LinkList &L,int i,ElenType e)在单链表L的第i个数据元素之前插入数据元素Ereturn 0;int j;社1号位置插入时，U号位置是塢位置LinkList p=Lwhile (ji-1 & p?=NULL)/寻找第i-1 个结点next; j*；if (p=NULL)未找到第iY个结点，即i超岀了时return 8;else找到第i 个结点Pw new LNode;创建新结点三1F(S=NULL)data=e; s-next=pnext; p-next-s

24、;return 1:将堀入到P之后irrt List Delete (Link List &Lfint i.ElenType &e)删除单链表L中第i个结点，并用已返回其值return 0;LinkList p=L,q；int j=0；亦ill& (p-next)T-NULL)/寻找第i7个结点，且第iT号元素不是最后一个元素p=p-next; i + + Iif (p-next)=NULL) return 0;else/硃找到第IT个结点，即i超岀了 仁1q=p-next； p-next-q-next;/从单链表中刪除 e=q-data; delete q; return 1;q.指向要删墮

25、的结点 点释放q结点6打开FileView双击LinkList.cpp，完成源文件的编写。LinkList.cpp主要含 main() 函数的实现。Itinciude iostreanhchar ElemTupe;/示例程序数据元素的类型设走为字符型Itinclude TinkList .h*uoid main()LinkList h;ElemTipe e;int i-;位序int t=0;国|织返回值 cout(1)初始化单链Rhn-；InitList(h);coutC2)卑链表为,(ListEnptyCh)?空y 非空 M)endl;cout-(3)fem字母舷h 以W结束：endl;加R

26、e; 紺遴二E;号位置开 WAuhile ( eT-tt* )Listlnsert(li ,i ,e);cine;C0UtW输出单链表些二PrintList(h); 査看结果cQut*(5)单链表 h 长度=*ListLength(h)endI;cout(5)单链表 h%(ListEnipt 叭 fl)?空”：非空)endl;cout(6)GetElem(Lfife)函薮，请输入i的fi,Bendl;cini;t=GetElen(h,i,e):_iF(t) coutai(6)链表hftti,*i-个元素=,-eendl;else cout-(6)单密表h的第匕“个元素不存在VT;cout *(

27、7)测试LocateElemfL.e)函数，请输入e的值endl; cine: t=LocateEleni(h ,e);if(t) coutM(7)7L素“的位置-Mlendl;else cout,(7)7f.MeSiListInsert(L pi pe)函数，请输入i的值和e的值endl; coutit输入i的值：飞cinii;cout-请输人e的值：；cime;cout(8)在第i个元素位置上插入Xe 元素:七 t=Listlnsert(h,i,e);if(t) coutlfifielse couti;cout(18)删除h的第L个元素：t = ListDelete(h ,i Te);if

28、(t) coutfifi功Welse cout,WfnB,;cout(H)ffiS 单链表 hf；PrintList(h); 查看结果 c(hiix“(12)释放单链表 nrr； DestroyList(h);H j気塾的值画数，诰输入的值Uc O寺前出单fil表h二&b hClUljTLisltDii- lieteCL. zL4Piec；s mnsp kesF to cent nueaJoic： dr qS城和出埜错翹b CCE、華钮恚h KfT-75单罪空ljt；Cnt:Flnni出数，请输入丄的值实验目的1 掌握栈的存储结构及基本操作。2 掌握队列的存储结构及基本操作。3 通过具体的应用

29、实例，进一步熟悉和掌握栈和队列的实际应用。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容（基础题必做，应用题任选）1. 基础题：（1）按照教材中抽象数据类型栈的定义，采用顺序存储结构（用动态数组） 或链式存储结构，编写主函数演示顺序栈 /链栈的基本操作。（2）按照教材中抽象数据类型队列的定义，采用顺序存储结构（循环队列） 或链式存储结构，编写主函数演示循环队列 /链队列的基本操作。2. 应用题：（1）算符优先算法为表达式求值 （2）舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一 队，跳舞开始时， 依次从男队和女队的队头上各出一人配成舞伴， 若两队初始人 数不相同

30、，则较长的那一队中未配对者等待下一轮舞曲。 设计一个函数 partner（） ， 模拟上述舞伴配对问题。基本要求：1） 由键盘输入数据，每对数据包括姓名和性别；2） 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称 和队头者的姓名；1 熟悉二叉树结点的结构和对二叉树的基本操作。2 掌握对二叉树每一种操作的具体实现。3 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。4 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。实验要求1 独立完成；2 程序调试正确，有执行结果。实验内容(基础题必做，应用题任选)1. 基础题： 按照教材中抽象数据类型二叉树的定义

31、，采用二叉链表存储结构，编写主函 数演示二叉树的基本操作，如：说明： 二叉树的基本操作可包括：(1) void InitBT ( BTreeNode *&BT )/初始化二叉树 BT(2) void CreateBT ( BTreeNode *&BT, char *a )/根据字符串 a 所给出二叉树的描述，建立二叉链表存储结构(3) int EmptyBT ( BTreeNode *BT)/检查二叉树 BT 是否为空，空返回 1，否则返回 0(4) int DepthBT ( BTreeNode *BT)/求二叉树 BT 的深度并返回该值(5) int FindBT ( BTreeNode

32、*BT, ElemType x)PreOrder ( BTreeNode *BT) InOrder ( BTreeNode *BT) PostOrder ( BTreeNode *BT) LevelOrder ( BTreeNode *BT )LeafCount (BTreeNode *BT , int & count)(6) void(7) void(8) void(9) void (10) void 点个数/查找二叉树 BT 中值为 x 的结点，若查找成功返回 1，否则返回 0 /先序遍历二叉树 BT /中序遍历二叉树 BT /后序遍历二叉树 BT /按层次遍历二叉树 BT/求二叉树 b

33、的叶子结(11) int NodeCount (BTreeNode *BT) /求二叉树 BT 的总结点个数(12) void ClearBTree ( BTreeNode *&BT )/清除二叉树 BT2应用题(1) 输入 n 个叶子结点的权值，根据 Huffman 算法，构造一棵哈夫曼树。(2) 家谱管理：本题目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人 信息、插入家族成员、删除家族成员等功能。1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法， 复习栈和队列的应用。实验要求1. 独立完成；2. 程序调试正确，有执行结果。实验内容1、基础题(至少做一个)(1)图的邻接矩阵定义及实现：定义图的邻接矩阵存储结构，并编写图的初始化、建立图、深度优先 /广度 优先输出图、输出图的每个顶点的度等基本操作实现函数。 以下图为例，建立一 个验证操作实现的主函数进行测试。(2)图的邻接表的定义及实现：定义图的邻接表存储结构，并编写图的初始化、建立图、深度优先 /广度优 先输出图、输出图的每个顶点的度等基本操作实现函