2022年《数据结构实验》 .pdf

《2022年《数据结构实验》 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构实验》 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验实验指导书华中师范大学信息技术系二 00 九年四月名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 17 页 -I 目录目录.I 概述 .1 项目一线性结构的实现.1 一实验目标 .1 二实验内容 .1 三实验要求 .1 1线性表的就地逆置.1 2利用栈实现数制转换.2 3利用队列判断字符序列是否“回文”.2 四实验报告规范.3 五实验报告样例.4 项目二树结构的实现 .11 实验目标 .11 实验内容 .11 实验要求 .11 项目三图结构的实现 .12 实验目标 .12 实验内容 .12 实验要求 .12 项目四利用线性结构求解问题.13 实验目标 .13 实验内容

2、 .13 实验要求 .13 1解约瑟夫环问题.13 2表达式求值.13 项目五利用非线性结构求解问题.14 实验目标 .14 实验内容 .14 实验要求 .14 1哈夫曼编码和译码.14 2课程编排问题.15 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 17 页 -1 概述实验是对学生的一种综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。本实验课程着眼于方法与应用的结合，通过实验使书本上的知识“活”起来，让学生能深化理解和灵活掌握教学内容，通过实验使学生掌握如何把课堂和书本中学到的知识用于解决实际问题的基本方法和技能，对学生进行软件设计的基本训练。为了达到

3、上述目的，本课程安排了五个实验项目，每个项目训练重点在于基本的数据结构，而不强调面面俱到。每个实验题目提交的成果都是两个部分，一个是实验报告，一个是源程序文件。实验报告以word 文档格式提交，源文件以.c 或.cpp 格式提交。本实验课程的所有实验项目都按照实验报告规范内容所表示的步骤完成，请读者仔细阅读实验报告规范，明确实验的开展所要经历的基本过程。本实验课程的所有实验项目都按照实验报告规范内容所表示的步骤完成，请读者仔细阅读实验报告规范，明确实验的开展所要经历的基本过程。本实验课程的评价按照实验报告规范的各个项目进行评价。项目一线性结构的实现一实验目标能够写出线性表、栈、队列等数据结构的

4、描述；能够实现线性表、栈、队列等数据结构的存储结构；能够能够写出线性表、栈、队列、等数据结构基本操作的实现算法。二实验内容1 线性表的建立与实现实验题目：线性表的就地逆置2 栈的建立与实现实验题目：利用栈实现数制转换3 队列的建立与实现实验题目：利用队列判断字符序列是否“回文”三实验要求1线性表的就地逆置问题描述：利用线性表原有的存储空间将线性表 (a1,a2,an-1,an)逆置为：(an,an-1,a2,a1)基本要求：编写程序，对由键盘输入的有n 个元素的线性表，输出其逆置前和逆置后的所有元素线性表的长度n 也通过键盘输入无论输入还是输出，要给出适当的提示信息名师资料总结-精品资料欢迎下

5、载-名师精心整理-第 3 页，共 17 页 -2 分别用静态顺序结构和单链表实现测试数据：n=11，线性表的n 个元素分别为：1，9，5，7，1，2，1，1，4，2，1 n=8，线性表的n 个元素分别为：8，6，1，9，2，5，0，1 实现提示：程序运行后，首先提示输入线性表的长度，然后输入线性表的元素，接着输出线性表的各元素，然后再输出逆置后的线性表的各元素。2利用栈实现数制转换问题描述：十进制数N和其他 d 进制数的转换是计算机实现计算的基本问题。可以基于下列原理：N=(N div d)d+N mod d 解决此问题。本题目的问题是对于任意一个非负十进制整数，计算得到其等值的八进制数。基本

6、要求：编写程序，对由键盘输入的1 个任意非负十进制整数n（n30000），输出与其等值的八进制数d。无论输入还是输出，要给出适当的提示信息分别用静态顺序栈和单链栈实现测试数据：n=1024 n=29475 n=32780 实现提示：程序运行后，首先提示输入1 个任意非负十进制整数n（n30000），然后对于不符合要求的输入数据给予提示，并允许重新输入，接着输出这个数据n，然后再输出与 n 等值的八进制d。3利用队列判断字符序列是否“回文”问题描述：正读和反读都相同的字符序列为“回文”，例如“860125521068”和“werttrew”是回文。本题目的问题是对与给定的一个字符序列，判断其是不

7、是“回文”。基本要求：编写程序，对由键盘输入的1 个以#为结束符的字符序列，并输出。输出“yes”或“YES”表示输入的是回文；输出“no”或“NO”表示输入的不是回文无论输入还是输出，要给出适当的提示信息分别用循环队列和链队列实现测试数据：751025520157#wdxljpxdw#名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 17 页 -3 实现提示：程序运行后，首先提示输入1 个以#为结束符的字符序列，然后输出这个序列，接着输出“yes”或“YES”表示这个序列是回文，或者输出“no”或“NO”表示这个序列不是回文。四实验报告规范每个实验题目写一份实验报告。实验报告规范

8、将给出实验报告的项目和内容。1 开头2 分开头第 1 行给出实验项目号和项目名称，第2 行写出实验题目，第3 行给出给出班级、学号、姓名和完成日期2 需求分析20 分以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：（1）程序所能达到的总体功能（2）输入的形式和输入值的范围（3）输出的形式（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果3 概要设计20 分（1）说明本程序中用到的数据结构，并给出其逻辑结构表示（2）对需求分析中给出的总体功能进行分解，以确定程序中的功能模块，并给出各功能模块之间的结构图（3）给出主控模块（对应主函数）的流程以及对应各功能模块

9、的函数之间的层次（调用）关系图4 详细设计20 分（1）给出概要设计中的数据结构的存储结构描述（2）写出本程序中用到的数据结构基本操作的伪码算法（3）写出主函数和其他函数模块的伪码算法伪码算法的详细程度建议为：按照伪码算法可以在计算机键盘上直接输入高级程序设计语言程序（4）画出函数的调用关系图5 调试分析10 分（1）调试过程中遇到的问题是如何解决的（2）算法的时空分析包括基本操作和其他算法的时间复杂度和空间复杂度的分析和改进设想（3）对设计与实现的回顾、分析、讨论以及经验和体会等6 使用说明8 分说明如何使用你编写的程序，详细列出每一步的操作步骤7 测试结果10 分列出你的测试结果，包括输入

10、的内容和格式以及输出的内容和格式。这里的测试数据应该完整和严格，最好多于需求分析中所列。8 附录10 分带注释的源程序。也可以只列出提交的程序文件清单。注意：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 17 页 -4 五实验报告样例项目一线性结构的实现题目：编制程序，求两个集合的并集班级：姓名学号完成日期一.需求分析1.本程序的功能是对已知的集合A 和 B，求其并集，使AAB，且 B 不再单独存在。2.本程序中，集合的元素限定为字符，集合的大小最大限定为N（程序中通过常量定义其值）。集合输入的形式为一个以“回车

11、符”为结束标志的字符串。集合的输出形式是用“，”号间隔的字符串。3.程序运行中通过对话方式完成数据的输入，即在屏幕上显示相应的“提示信息”后，在键盘上输入相应数据，数据输入完成后，输入的数据以及相应的运算结果显示在输入数据的后面。4.测试数据定义 N=10（1）集合 A=a，s，d，f，集合 B=h，j，k，u，i（2）集合 A=a，s，d，f，集合 B=h，a，k，f，i（3）集合 A=a，s，d，f，r，t，集合 B=a，1，f，k，4，i，8 二.概要设计1.本程序用线性表表示集合，即用线性表LA 和 LB 分别表示集合A 和集合 B，LA 和 LB 的元素分别为集合A 和 B 的元素。

12、LA=（a1，a2，an），aichar，n 为集合 A 的元素个数。LB=（b1，b2，bm），bichar，m 为集合 B 的元素个数。2.本程序包含六大模块：（1）主程序模块（2）存储结构模块 描述线性表的静态顺序结构类型（3）线性表的基本操作模块 实现线性表的7 个基本操作（4）线性表的创建模块 实现线性表的构造和元素的输入（5）线性表的输出模块 实现线性表元素的输出（6）求集合并集的模块 实现求用线性表表示的两个集合的并集操作3.主程序模块的流程图void main()创建 LA 创建 LB 输出 LA 输出 LB 调用求集合并集的模块输出 LA 各模块之间的调用关系如图1 所示。主

13、程序模块线性表创建模块求集合并集的模块线性表输出模块线性表的基本操作模图 1 各模块之间的调用关系名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -5 三.详细设计1.线性表的静态顺序存储结构描述typedef char ElemType;struct lsqstr ElemType elemN;int length;typedef struct lsqstr SSqList;2.线性表的7 个基本操作算法void InitList(SSqList&L)/构造一个空的线性表L.length=0;/空表长度为0 int ListInsert(SSqList&L,int i

14、,ElemType e)/在 L 中第 i 个位置之前插入新的数据元素e,L 的长度加1 if(i L.length+1)return ERROR;if(L.length=N)return OVERFLOW;for(j=L.length;j=i;j-)L.elemj=L.elemj-1;L.elemi-1=e;L.length=L.length+1;return OK;int ListDelete(SSqList&L,int i,ElemType&e)/删除 L 的第 i 个数据元素,并用 e 返回其值,L 的长度减 1 if(L.length=0)return UNDERFLOW;if(i

15、L.length)return ERROR;e=L.elemi-1;for(j=i+1;j=L.length;j+)L.elemj-2=L.elemj-1;L.length=L.length-1;return OK;int ListLength(SSqList L)/返回线性表L 中元素的个数return L.length;int ListEmpty(SSqList L)/若 L 为空表,则返回TRUE,否则返回FALSE if(L.length=0)return TRUE;else return FALSE;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 17 页 -6 int

16、 LocateElem(SSqList L,ElemType e,int(*compare)(ElemType,ElemType)/返回 L 中第 1 个与 e 满足关系compare()的元素的位序。若这/样的元素不存在,则返回值为0 i=1;while(i=L.length&!(*compare)(L.elemi-1,e)i+;if(i=L.length)return i;else return 0;int GetElem(SSqList L,int i,ElemType&e)/用 e 返回 L 中的第 i 个元素的值if(L.length=0)return UNDERFLOW;if(iL

17、.length)return ERROR;e=L.elemi-1;return OK;int equal(ElemType e1,ElemType e2)/若 e1 等于 e2,则返回 1;否则返回 0 return e1=e2?1:0;3.线性表的创建算法void createlist(SSqList&L)/构造并输入线性表L int n,i,L_len,f;char c;InitList(L);printf(input element number:n=);scanf(%d,&n);fflush(stdin);printf(n);printf(input%d char:n,n);L_len

18、=ListLength(L);for(i=1;i=n;i+)scanf(%c,&c);f=ListInsert(L,+L_len,c);if(f!=1)printf(OVERFLOW!n);fflush(stdin);break;4.线性表的输出算法void outputlist(SSqList L)/输出线性表L int L_len,i;ElemType e;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 17 页 -7 L_len=ListLength(L);printf(list length:%dn,L_len);if(L_len)printf(list element:

19、n);for(i=1;i=L_len;i+)GetElem(L,i,e);printf(%c,e);printf(n);5.求集合并集的算法void union1(SSqList&LA,SSqList&LB)/将所有在线性表LB 中但不在 LA 中的数据元素插入到LA 中,/算法执行之后,线性表LB 不再存在。int La_len,f;ElemType e;La_len=ListLength(LA);/求得线性表LA 的长度while(!ListEmpty(LB)/依次处理LB 中元素直至LB 为空表止 ListDelete(LB,1,e);/从 LB 中删除第 1 个数据元素并赋给e if(

20、!LocateElem(LA,e,equal)f=ListInsert(LA,+La_len,e);if(f!=1)printf(OVERFLOW!n);fflush(stdin);break;/当 LA 中不存在和e 值相同的数据元素时进行插入/while/union1 6.主程序算法void main()createlist(LA);/创建 LA createlist(LB);/创建 LB outputlist(LA);/输出 LA outputlist(LB);/输出 LB union1(LA,LB);/启动 union outputlist(LA);/输出 LA 各算法之间的调用关系如

21、图2 所示。四.调试分析outputliscreatelisInitLisListLengtunion1ListInsertGetEleequalLocateEleListEmptListDeletmain图 2 各算法之间的调用关系名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 17 页 -8 1.算法的时间复杂度（1）算法 createlist 的时间复杂度为O（ListLength(L)）。虽然在 for 循环中调用了线性表的基本操作ListInsert算法，该算法的时间复杂度为O（ListLength(L)），但在本算法中，每次插入的位置是最后，所以，ListInsert

22、算法的时间复杂度在createlist算法中变为O（1），所以算法createlist的时间复杂度为O（ListLength(L)）。（2）算法 outputlist 的时间复杂度为O（ListLength(L)）。（3）算法 union1 的时间复杂度为O（ListLength(LB)）2.问题分析和处理（1）程序运行中数据输入遇到这样的问题，就是在键入集合元素个数后接着要键入集合的各元素，而元素个数是整型数据，后面键入的元素是字符数据，于是，程序在接收元素的字符数据时将前面的整型数据的结束符回车当作集合的第一个元素接收了。解决这个问题就是要在键入了整型数据后要将缓冲区里的回车消除掉，于是在

23、程序的createlist 函数中使用了系统函数fflush(stdin)，该函数功能就是清除键盘缓冲区的内容。（2）输出线性表的元素时是用“，”号间隔，但没有考虑最后一个元素的后面应该没有逗号。屏幕上整个显示的内容格式不太清晰。（3）经验和体会（略）五.使用说明程序运行后，屏幕上将显示：create LA input element number:n=光标将停留在“=”号后面，这时，用户从键盘键入集合A 的元素个数然后回车。键入个数后屏幕上将在新一行显示：（假设键入的个数是4）input 4 char:光标停留在下一行的开头，这时，用户可从键盘键入集合A 的各字符，各字符间没有分隔符，最后以

24、回车表示输入结束。（假设键入的是asdf 回车）键入集合 A 的元素后，屏幕上将在新一行显示：create LB input element number:n=光标将停留在“=”号后面，这时，用户从键盘键入集合B 的元素个数然后回车。键入个数后屏幕上将在新一行显示：（假设键入的个数是3）input 3 char:光标停留在下一行的开头，这时，用户可从键盘键入集合B 的各字符，各字符间没有分隔符，最后以回车表示输入结束。（假设键入的是a2d 回车）键入集合 B 的元素后，屏幕上将从新一行起显示如下内容：output LA list length:4 list element:a,s,d,f,名师

25、资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 17 页 -9 output LB list length:3 list element:a,2,d,Merge the LA and LB output LA list length:5 list element:a,s,d,f,2,六.测试结果1.第 1 组数据：集合 A=a，s，d，f，元素个数为4；集合 B=h，j，k，u，i，元素个数为5。运行结果：create LA input element number:n=4 input 4 char:asdf create LB input element number:n=5 i

26、nput 5 char:hjkui output LA list length:4 list element:a,s,d,f,output LB list length:5 list element:h,j,k,u,i,Merge the LA and LB output LA list length:9 list element:a,s,d,f,h,j,k,u,i,2.第 2 组数据：集合 A=a，s，d，f，元素个数为4；集合 B=h，a，k，f，i，元素个数为5。运行结果：create LA input element number:n=4 input 4 char:asdf 名师资料总

27、结-精品资料欢迎下载-名师精心整理-第 11 页，共 17 页 -10 create LB input element number:n=5 input 5 char:hakfi output LA list length:4 list element:a,s,d,f,output LB list length:5 list element:h,a,k,f,i,Merge the LA and LB output LA list length:7 list element:a,s,d,f,h,k,i,3.第 3 组数据：集合 A=a，s，d，f，r，t，元素个数为6；集合 B=a，1，f，k，

28、4，i，8元素个数为7。运行结果：create LA input element number:n=6 input 6 char:asdfrt create LB input element number:n=7 input 7 char:a1fk4i8 output LA list length:6 list element:a,s,d,f,r,t,output LB list length:7 list element:a,1,f,k,4,i,8,Merge the LA and LB OVERFLOW!output LA list length:10 list element:a,s,d

29、,f,r,t,1,k,4,i,名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 17 页 -11 七.附录（这里给出带扩展名.cpp 的源文件名即可）项目二树结构的实现实验目标能够写出树结构的描述；能够实现树结构的存储结构；能够能够写出结构基本操作的实现算法。实验内容利用“扩展先序遍历序列”创建二叉树，并分别中序遍历和后序遍历该二叉树。实验要求问题描述：在二叉树的遍历序列中，用特定的元素表示空子树，就得到相应的扩展遍历序列。例如，若以.表示空子树，则下图中二叉树的“扩展先序遍历序列”为：AB.DF.G.C.E.H.本题目的问题是，针对给出某二叉树的“扩展先序遍历序列”，创建该二叉

30、树，并对该二叉树进行中序遍历和后序遍历，以得到该二叉树的中序序列和后序序列。基本要求：编写程序，对由键盘输入的以n为结束符的“扩展先序遍历序列”，构建相应的二叉链表，并输出相应的中序序列和后序序列无论输入还是输出，要给出适当的提示信息测试数据：AB.DF.G.C.E.H.名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -12 HGE.B.FD.CA.实现提示：程序运行后，首先提示连续键入“扩展先序遍历序列”中的各个字符，最后以回车结束输入，然后提示并输出中序序列和后序序列。项目三图结构的实现实验目标能够写出图结构的描述；能够实现图结构的存储结构；能够能够写出结构基本操

31、作的实现算法。实验内容创建一个图，并确定每个顶点的度。实验要求问题描述：本题目的问题是，对给定的某图的顶点数目、边（弧）的数目和各边（弧）的信息，构建该图，并求出该图中每个顶点的度。基本要求：编写程序，对由键盘输入的顶点数目v、边（弧）的数目e、图的性质f（为 1 是有向图，为0 是无向图）以及各边（弧）的信息，构建相应图的邻接表，并输出相应图的每个顶点的度无论输入还是输出，要给出适当的提示信息与上述要求相同，改用数组表示实现测试数据：v=5，e=6，f=0，各边为：（a，b），（a，c），（a，d），（c，e），（c，d），（c，b）v=6，e=11，f=1，各弧为：，实现提示：程序运行后，

32、首先依次提示键入顶点数目v、边（弧）的数目e、图的性质f、各边（弧），然后提示并输出各个顶点的度数。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 17 页 -13 项目四利用线性结构求解问题实验目标能够针对一个具体问题建立相应的线性结构能实现线性结构的顺序存储结构和链式存储结构能够基于顺序存储结构和链式存储结构写出解决具体问题的算法和程序实验内容1 解约瑟夫环问题2 表达式求值实验要求1解约瑟夫环问题问题描述：约瑟夫环问题的一种描述为：编号为1，2，.,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时

33、针方向自1 开始顺序报数，报到 m时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序基本要求：编写程序，对键盘输入的m 和 n 以及 n 个人的密码，按照问题描述要求的这n 个人的出队顺序输出各人的编号利用顺序表模拟实现该过程测试数据：m 的初值为20，n=7，7 个人的密码依次为：3，1，7，2，4，8，4 实现提示：程序运行后，首先提示输入初始报数上限值m，然后提示输入人数n 以及 n 个人的密码值，经过程序处理过程后依次输出出队人的编号程序运行开始输入的密码顺序号为每个人的编号。

34、一个人可由编号和密码两部分信息构成上述测试数据得到的正确输出是：6，1，4，7，2，3，5 选做内容：利用单链表实现该过程2表达式求值问题描述：名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 17 页 -14 表达式计算是编译原理要处理的基本而重要的问题之一，也是栈的应用的一个典型例子。本题目的问题是，对给定的一个算术表达式，计算其值。基本要求：编写程序，对以字符序列形式从键盘输入的语法正确、不含变量的一位整数四则混合运算的算术表达式，计算并输出其值实现表达式求值的过程中要利用栈对操作数多于一位要能给出提示，并能重新输入无论输入还是输出，要给出适当的提示信息测试数据：4*（8+

35、4）/6-3 2*（6+2*（3+6*（6+6）实现提示：程序运行后，首先提示并键入符合要求的表达式，然后对不符合要求的操作数给予提示，并重新输入相应操作数，接着输出该表达式，后面跟一个“=”，然后在“=”后面输出该表达式的值。项目五利用非线性结构求解问题实验目标能够针对一个具体问题建立相应的非线性结构能实现非线性结构的多种存储结构能够基于非线性结构的相应存储结构写出解决具体问题的算法和程序实验内容1 哈夫曼编码和译码2 课程编排问题实验要求1哈夫曼编码和译码问题描述：为了提高信道的利用率，缩短信息传输时间，通常都采用合适的码制和相应的系统对传送的数据进行编码和译码，在发送端通过一个编码系统对

36、待传原码序列进行编码，在接收端将传来的编码序列进行译码，将编码序列还原成原码序列。通过哈夫曼算法得到的编码和译码系统就是哈夫曼编码和译码系统。本题目的问题是，设计一个简易的编/译码系统，对给定的报文字符集和相应的频度进行哈夫曼编码，并对给定的原码报文形成编码报文，还对给定的编码报文译码成原码报文。名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -15 基本要求：编写程序，对从键盘输入的字符序列和相对应的频度数据建立哈夫曼树，建立各字符的编码表，并输出编码表（编码为01 序列）对从键盘输入的原码报文字符序列，输出对应的编码报文对从键盘输入的编码报文序列，输出对应的原码报

37、文序列哈夫曼树用二叉链表实现测试数据：字符序列：A B C D E F G H J K L M 空格频度：64 13 22 32 103 21 15 47 57 15 32 20 186 2课程编排问题问题描述：大学每个专业学生的学习是一个工程。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。本题目的问题是，对于已定的课程和这些课程之间的先修关系以及开课的学期数，给出一个课程的开课顺序。基本要求：编写程序，对文件输入的课程以及课程之间的先修关系，建立相应的AOV 网，并用二元组的形式输出到相应文件对文件输入的开课学期数，分别在屏幕上和文件里输出课程的开课顺序程序中能自动对开课数量的均衡性进行调整。测试数据：课程代号课程名称先修课程C1高等数学 C2程序设计基础 C3离散数学 C1,C2 C4数据结构 C3,C2 C5高级语言程序设计 C2 C6编译方法 C5,C4 C7操作系统 C4,C9 C8普通物理 C1C9计算机原理 C8实现提示：利用拓扑排序算法名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 17 页 -