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

1、数据结构实验实验指导书华中师范大学信息技术系二00九年四月目 录目 录I概述1实验项目一 线性结构的实现1一实验目标1二实验内容1三实验要求11线性表的就地逆置12利用栈实现数制转换23利用队列判断字符序列是否“回文”2四实验报告规范3五实验报告样例3实验项目二 树结构的实现11实验目标11实验内容11实验要求11实验项目三 图结构的实现12实验目标12实验内容12实验要求12实验项目四 利用线性结构求解问题12实验目标12实验内容13实验要求131解约瑟夫环问题132表达式求值13实验项目五 利用非线性结构求解问题14实验目标14实验内容14实验要求141哈夫曼编码和译码142课程编排问题1

2、5概述实验是对学生的一种综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。本实验课程着眼于方法与应用的结合，通过实验使书本上的知识“活”起来，让学生能深化理解和灵活掌握教学内容，通过实验使学生掌握如何把课堂和书本中学到的知识用于解决实际问题的基本方法和技能，对学生进行软件设计的基本训练。为了达到上述目的，本课程安排了五个实验项目，每个项目训练重点在于基本的数据结构，而不强调面面俱到。每个实验题目提交的成果都是两个部分，一个是实验报告，一个是源程序文件。实验报告以word文档格式提交，源文件以.c或.cpp格式提交。本实验课程的所有实验项目都按照实验报告规范内容所表示的步骤完成

3、，请读者仔细阅读实验报告规范，明确实验的开展所要经历的基本过程。本实验课程的所有实验项目都按照实验报告规范内容所表示的步骤完成，请读者仔细阅读实验报告规范，明确实验的开展所要经历的基本过程。本实验课程的评价按照实验报告规范的各个项目进行评价。实验项目一 线性结构的实现一实验目标能够写出线性表、栈、队列等数据结构的描述；能够实现线性表、栈、队列等数据结构的存储结构；能够能够写出线性表、栈、队列、等数据结构基本操作的实现算法。二实验内容1 线性表的建立与实现实验题目：线性表的就地逆置2 栈的建立与实现实验题目：利用栈实现数制转换3 队列的建立与实现实验题目：利用队列判断字符序列是否“回文”三实验要

4、求1线性表的就地逆置问题描述： 利用线性表原有的存储空间将线性表 ( a1 , a2 , , an-1 , an ) 逆置为：(an ,an-1 , ,a2 ,a1 ) 基本要求： 编写程序，对由键盘输入的有n个元素的线性表，输出其逆置前和逆置后的所有元素 线性表的长度n也通过键盘输入 无论输入还是输出，要给出适当的提示信息 分别用静态顺序结构和单链表实现 测试数据： 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 实现提示： 程序运行后，首先提示输入线性表的长度，然后输入线性表的元素，接着输出线

5、性表的各元素，然后再输出逆置后的线性表的各元素。2利用栈实现数制转换问题描述：十进制数N和其他d 进制数的转换是计算机实现计算的基本问题。可以基于下列原理： N = (N div d)d + N mod d 解决此问题。本题目的问题是对于任意一个非负十进制整数，计算得到其等值的八进制数。基本要求： 编写程序，对由键盘输入的1个任意非负十进制整数n（n30000），输出与其等值的八进制数d。 无论输入还是输出，要给出适当的提示信息 分别用静态顺序栈和单链栈实现测试数据： n=1024 n=29475 n=32780实现提示：程序运行后，首先提示输入1个任意非负十进制整数n（n30000），然后对

6、于不符合要求的输入数据给予提示，并允许重新输入，接着输出这个数据n，然后再输出与n等值的八进制d。3利用队列判断字符序列是否“回文”问题描述：正读和反读都相同的字符序列为“回文”，例如“8”和“werttrew”是回文。本题目的问题是对与给定的一个字符序列，判断其是不是“回文”。基本要求： 编写程序，对由键盘输入的一个以#为结束符的字符序列，并输出。输出“yes”或“YES”表示输入的是回文；输出“no”或“NO”表示输入的不是回文 无论输入还是输出，要给出适当的提示信息 分别用循环队列和链队列实现测试数据： 7# wdxljpxdw# wenxueeeuxnew#实现提示：程序运行后，首先提

7、示输入1个以#为结束符的字符序列，然后输出这个序列，接着输出“yes”或“YES”表示这个序列是回文，或者输出“no”或“NO”表示这个序列不是回文。四实验报告规范每个实验题目写一份实验报告。实验报告规范将给出实验报告的项目和内容。1 开头 2分开头第1行给出实验项目号和项目名称，第2行写出实验题目，第3行给出给出班级、学号、姓名和完成日期 2 需求分析 20分以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：（1）程序所能达到的总体功能（2）输入的形式和输入值的范围（3）输出的形式（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果 3 概要设计 20分（1

8、）说明本程序中用到的数据结构，并给出其逻辑结构表示（2）对需求分析中给出的总体功能进行分解，以确定程序中的功能模块，并给出各功能模块之间的结构图（3）给出主控模块（对应主函数）的流程以及对应各功能模块的函数之间的层次（调用）关系图4 详细设计 20分（1）给出概要设计中的数据结构的存储结构描述（2）写出本程序中用到的数据结构基本操作的伪码算法（3）写出主函数和其他函数模块的伪码算法伪码算法的详细程度建议为：按照伪码算法可以在计算机键盘上直接输入高级程序设计语言程序（4）画出函数的调用关系图 5 调试分析 10分（1）调试过程中遇到的问题是如何解决的（2）算法的时空分析包括基本操作和其他算法的时

9、间复杂度和空间复杂度的分析和改进设想（3）对设计与实现的回顾、分析、讨论以及经验和体会等 6 使用说明 8分说明如何使用你编写的程序，详细列出每一步的操作步骤 7 测试结果 10分列出你的测试结果，包括输入的内容和格式以及输出的内容和格式。这里的测试数据应该完整和严格，最好多于需求分析中所列。 8 附录 10分带注释的源程序。也可以只列出提交的程序文件清单。注意：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写。 五实验报告样例实验项目一 线性结构的实现题目：编制程序，求两个集合的并集班级： 姓名 学号 完成日期 一.需求分析1.本程序的功能是对已知的集合 A 和 B，求其并集

10、，使 AAB，且 B 不再单独存在 。2.本程序中，集合的元素限定为字符，集合的大小最大限定为N（程序中通过常量定义其值）。集合输入的形式为一个以“回车符”为结束标志的字符串。集合的输出形式是用“，”号间隔的字符串。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二.概要设

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

12、出模块线性表的基本操作模块图1 各模块之间的调用关系void main ( )创建LA创建LB输出LA输出LB调用求集合并集的模块输出LA各模块之间的调用关系如图1所示。三.详细设计1. 线性表的静态顺序存储结构描述typedef char ElemType; struct lsqstr ElemType elemN; int length;typedef struct lsqstr SSqList;2. 线性表的7个基本操作算法void InitList ( SSqList &L ) /构造一个空的线性表 L.length=0; /空表长度为0int ListInsert ( SSqList

13、 & L,int i,ElemType e ) /在L中第i个位置之前插入新的数据元素e,L的长度加1if ( 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

14、UNDERFLOW;if ( i 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;int LocateE

15、lem (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

16、(iL.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

17、char :n,n); L_len= 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; L_len=ListLength(L); printf(list length:%dn,L_len); if(L_len) printf(list element:n);

18、 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); /从 L

19、B 中删除第1个数据元素并赋给 e if (!LocateElem(LA,e,equal) f=ListInsert(LA,+La_len,e); if(f!=1) printf(OVERFLOW!n); fflush(stdin); break; / 当LA中不存在和 e 值相同的数据元素时进行插入outputlistcreatelistInitListListLengthunion1ListInsertGetElemequalLocateElemListEmptyListDeletemain图2 各算法之间的调用关系 / while / union16. 主程序算法void main (

20、)createlist(LA); /创建LAcreatelist(LB); /创建LBoutputlist(LA); /输出LAoutputlist(LB); /输出LBunion1(LA,LB); /启动unionoutputlist(LA); /输出LA各算法之间的调用关系如图2所示。四.调试分析1.算法的时间复杂度（1）算法createlist的时间复杂度为O（ListLength(L)）。虽然在for循环中调用了线性表的基本操作ListInsert算法，该算法的时间复杂度为O（ListLength(L)），但在本算法中，每次插入的位置是最后，所以，ListInsert算法的时间复杂度在

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

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

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

24、 element:a,2,d,Merge the LA and LBoutput LAlist length:5list element:a,s,d,f,2,六.测试结果1.第1组数据： 集合A=a，s，d，f，元素个数为4；集合B=h，j，k，u，i，元素个数为5。 运行结果：create LAinput element number :n=4input 4 char :asdfcreate LBinput element number :n=5input 5 char :hjkuioutput LAlist length:4list element:a,s,d,f,output LBlis

25、t length:5list element:h,j,k,u,i,Merge the LA and LBoutput LAlist length:9list 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 LAinput element number :n=4input 4 char :asdfcreate LBinput element number :n=5input 5 char :hakfioutput LAlist length:4list element:

26、a,s,d,f,output LBlist length:5list element:h,a,k,f,i,Merge the LA and LBoutput LAlist length:7list element:a,s,d,f,h,k,i,3. 第3组数据：集合A=a，s，d，f，r，t，元素个数为6；集合B=a，1，f，k，4，i，8元素个数为7。 运行结果：create LAinput element number :n=6input 6 char :asdfrtcreate LBinput element number :n=7input 7 char :a1fk4i8output L

27、Alist length:6list element:a,s,d,f,r,t,output LBlist length:7list element:a,1,f,k,4,i,8,Merge the LA and LBOVERFLOW!output LAlist length:10list element:a,s,d,f,r,t,1,k,4,i,七.附录（这里给出带扩展名.cpp的源文件名即可）实验项目二 树结构的实现实验目标能够写出树结构的描述；能够实现树结构的存储结构；能够能够写出树结构基本操作的实现算法。实验内容利用“扩展先序遍历序列” 创建二叉树，并分别中序遍历和后序遍历该二叉树。实验要求

28、问题描述： 在二叉树的遍历序列中，用特定的元素表示空子树，就得到相应的扩展遍历序列。例如，若以.表示空子树，则下图中二叉树的“扩展先序遍历序列”为：AB.DF.G.C.E.H. 本题目的问题是，针对给出某二叉树的“扩展先序遍历序列”，创建该二叉树，并对该二叉树进行中序遍历和后序遍历，以得到该二叉树的中序序列和后序序列。基本要求： 编写程序，对由键盘输入的以n为结束符的“扩展先序遍历序列”，构建相应的二叉链表，并输出相应的中序序列和后序序列 无论输入还是输出，要给出适当的提示信息测试数据： AB.DF.G.C.E.H. HGE.B.FD.CA.实现提示： 程序运行后，首先提示连续键入“扩展先序遍

29、历序列”中的各个字符，最后以回车结束输入，然后提示并输出中序序列和后序序列。实验项目三 图结构的实现实验目标能够写出图结构的描述；能够实现图结构的存储结构；能够能够写出结构基本操作的实现算法。实验内容创建一个图，并确定每个顶点的度。实验要求问题描述：本题目的问题是，对给定的某图的顶点数目、边（弧）的数目和各边（弧）的信息，构建该图，并求出该图中每个顶点的度。基本要求： 编写程序，对由键盘输入的顶点数目v、边（弧）的数目e、图的性质f（为1是有向图，为0是无向图）以及各边（弧）的信息，构建相应图的邻接表，并输出相应图的每个顶点的度 无论输入还是输出，要给出适当的提示信息 与上述要求相同，改用数组

30、表示实现测试数据： v =5， e =6，f=0，各边为：（a，b），（a，c），（a，d），（c，e），（c，d），（c，b） v =6， e =11，f=1，各弧为：， ，实现提示：程序运行后，首先依次提示键入顶点数目v、边（弧）的数目e、图的性质f、各边（弧），然后提示并输出各个顶点的度数。实验项目四 利用线性结构求解问题实验目标能够针对一个具体问题建立相应的线性结构能实现线性结构的顺序存储结构和链式存储结构能够基于顺序存储结构和链式存储结构写出解决具体问题的算法和程序实验内容1 解约瑟夫环问题2 表达式求值实验要求1解约瑟夫环问题问题描述： 约瑟夫环问题的一种描述为：编号为1，2，.,

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

32、以及n个人的密码值，经过程序处理过程后依次输出出队人的编号 程序运行开始输入的密码顺序号为每个人的编号。一个人可由编号和密码两部分信息构成 上述测试数据得到的正确输出是：6，1，4，7，2，3，5 选做内容： 利用单链表实现该过程 2表达式求值问题描述：表达式计算是编译原理要处理的基本而重要的问题之一，也是栈的应用的一个典型例子。本题目的问题是，对给定的一个算术表达式，计算其值。基本要求： 编写程序，对以字符序列形式从键盘输入的语法正确、不含变量的一位整数四则混合运算的算术表达式，计算并输出其值 实现表达式求值的过程中要利用栈 对操作数多于一位要能给出提示，并能重新输入 无论输入还是输出，要给出适当的提示信息测试数据： 4*（8+4）/6-3 2*（6+2*（3+6*（6+6）实现提示：程序运行后，首先提示并键入符合要求的表达式，然后对不符合要求的操作数给予提示，并重新输入相应操作数，接着输出该表达式，后面跟一个“=”，然后在“=”后面输出该表达式的值。实验项目五 利用非线性结构求解问题实验目标能够针对一个具体问题建立相应的非线性结构能实现非线性结构的多种