搜索
《数据结构》实验指导书高级语言、数据结构与算法课程组绍兴文理学院教务处二零一三年二月版1目录数据结构实验步骤、规范的要求与建议----------------------------------2数据结构实验时间安排---------------------------------------------------3数据结构实验报告示例---------------------------------------------------4实验一、大整数加法------------------------------------------------------10实验二、栈序列匹配-----------------------------------------------------14实验三、二叉排序树-----------------------------------------------------17实验四、最小生成树-----------------------------------------------------21附录：VC有关操作的提示-----------------------------------------------272数据结构实验步骤、规范的要求与建议从以往教学实验的经验来看，在初学阶段严格按实验步骤的要求去做，有助于养成良好的程序编制风格，培养严谨、科学、高效的工作方式。经常发现很多学生抱怨说，化了两个小时才找出一个错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自己。有的学生不屑于按实验步骤去做，甚至对于实验步骤的要求看都不看一遍，认为那是浪费时间，这是极其有害的。有的学生甚至主要是抄袭别人的，以应付检查，这是学习上的堕落，是很危险的！实验题目配合课程的进度，请同学们务必自己独立完成。为了锻炼自己的应用各种不同的数据结构的能力，尽可能的多做一些题目是非常必要的。在完成各种不同题目的过程中，加深对数据结构的理解和把握，提高编程和实践能力，从而帮助你在更高的角度解决各种应用问题。按实验步骤进行实验，不但可以培养科学化的工作作风，而且还能有效地避免错误，提高实验效率，达到实验目的。具体的要求如下：1、问题分析与系统的结构设计：充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数据结构和功能模块为中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个子程序(过程或函数)的规格说明，列出它们之间的调用关系，可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。2、详细设计和编码详细设计的目的是对子程序(过程或函数)的进一步求精。可以用IF、WHILE等伪代码等自然语言写出算法的框架，以避免陷入细节。在编码时，可以对详细设计的结果进一步求精，用高级语言表示出来。也可以直接用高级语言来描述算法。程序的每一行最好不超过60个字符。每个子程序(或过程、函数)通常不要太长，以不超过40行为宜。子程序(或过程、函数)包含的程序行数太多，易于造成理解的困难。控制循环和判断等语句的连续嵌套的深度。程序的目的性必须明确。对每一段程序完成的作用，除非常明显的除外，尽可能加以注释。这会对程序的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。3、上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联调。调试正确后将源程序和运行结果加以输出。4、实验报告的书写(1)需求分析问题描述，求解的问题是什么。包括实验的任务、输入、输出、功能、测试数据等。(2)概要设计3设计思想：存储结构、主要的算法思想。设计表示：主程序、子程序(过程或函数)的规格说明，通过调用关系图表示它们之间的调用关系。(3)详细设计数据类型。主程序和其他模块的算法或算法框架。(4)调试分析问题是如何解决的，讨论与分析、改进设想、经验与体会、时空复杂度等。至少写三点。(5)测试结果列出你的测试结果，包括输入的测试数据和输出的结果。测试数据应该完整和严格，必要时用多组数据进行测试。(6)用户手册：使用说明。即说明你的程序在什么环境下运行，怎么运行等。(7)附录源程序文件名，实验结束时源程序的电子稿要归档。数据结构与算法实验时间安排(32学时)数据结构与算法实验时间安排(16学时)实验内容学时数起止周实验一大整数相加161—8实验二栈序列匹配89—12实验三二叉排序树813—16实验四最小生成树实验内容学时数起止周实验一大整数相加161—8实验二栈序列匹配89—12实验三二叉排序树813—16实验四最小生成树实验内容学时数起止周实验一大整数相加81—8实验二栈序列匹配49—12实验三二叉排序树413—16实验四最小生成树实验内容学时数起止周实验一大整数相加161—8实验二栈序列匹配89—12实验三二叉排序树813—16实验四最小生成树4数据结构实验报告示例约瑟夫环一、需求分析1、实验任务是用循环单链表(不带头结点)来实现约瑟夫环。循环单链表的结点结构中包含环内代表人的编号和密码。2、对于输入的人数(n)和n个密码，建立不带头结点的单循环链表。3、对于密码m，从相对的第一个人开始报到第m个人，输出相对于开始报数的第m个人的信息。4、输出过程及输出完n个人的信息，即实现了约瑟夫环的功能。5、测试数据m的初值设为6；(1)对于n=7，7个人的密码依次为：3，1，7，2，4，8，4进行测试。(2)对于从键盘输入的n和n个人的密码进行测试。二、概要设计1、数据类型(1)n个人的编号和密码的数据元素结构typedefstruct//用于接收数据的输入{intnum;intm;}data;(2)单向循环链表结点结构typedefstructnode{intnum;intm;node*next;}node,*link;2、算法思想(1)输入n个人的密码，分别和依次按1到n的编号，输入到一个结构体数组，以便为建立单循环链表作数据准备；(2)根据结构体数组中的数据，建立单循环链表；(3)由得到的单向循环链表，根据约瑟夫问题的要求，构造约瑟夫函数，该函数中设置2个指针p和q，p指向当前报数的结点，q指向p结点后面的结点，开始时，q应指向单向循环链表的最后一个结点。对于出列的人(结点)，在该函数中输出其编号。该函数被主函数5调用。(4)在主函数中设置结构体数组，调用输入模块，把输入的n个人的密码和依次按1到n的编号，存储到一个结构体数组，然后调用建立有n个结点构成的单向循环链表的函数，最后调用约瑟夫函数，实现约瑟夫问题的求解。3、各子模块(1)输入数据模块该模块中输入n及n个人的编号和密码，依次存储于data类型的结构体数组；(2)建立单循环链表模块该模块中根据结构数组中的数据，建立不带头结点的单循环链表，其结点中的数据是人的编号和密码；(3)约瑟夫问题求解模块该模块中根据单向循环链表，从第一个人(结点)开始报数，报到密码m时(初始密码m可为6)该(人)结点出列，并输出相应的信息和得到新的密码，为下一次报数做准备，直至每个人(结点)全部出列，输出的信息即为约瑟夫问题的求解。4、主模块及与子模块的调用关系(1)主模块设置data类型的结构体数组和有关变量，然后依次调用输入数据模块、建立单循环链表模块和约瑟夫问题求解模块。(2)各模块之间的调用关系主程序模块输入数据模块建立单循环链表模块约瑟夫问题求解模块三、详细设计1、数据结构typedefstruct{intnum;intm;}data;typedefstructnode{intnum;intm;structnode*next;}node,*link;62、输入数据模块(用源代码也可以，但以伪代码比较好,下同)voidinputdata(intn，dataman[]){输入n；fori=0ton-1{输入密码m;mani.num←i+1;mani.d←m;}}3、建立单循环链表模块voidcreatelinklist(intn,dataman[],link&l){linkl,p,q;l←newnode;l-num=←man0.num;l-m←man0.m;q=l;fori=1ton-1{p=←newnode;p-num=←mani.num;p-m←mani.m;q-next←p;q←p;}q-next←l;}4、约瑟夫问题求解模块voidjoseph(linkl,intn){linkq,p,s;m=6;7q←l-next;while(q-next≠l)q←q-next;p←l;fori=0ton-1//重复n次{forj=1tom-1//找第m个人{q←p;p←p-next;}s←p;q-next←p-next;p←p-next;outputs-num;m←s-m;deletes;}}5、主程序模块voidmain(){linkl;intn;dataman[100];inputn;inputdata(n，man);createlinklist(n,man,l);joseph(l,n);}四、调试分析1、由于建立的是带头结点的单循环链表，导致输出的结果许多是错的，删除头结点，即建立的是不带头结点的单循环链表解决。2、由于开始时没有指针指向要开始报数结点后的指针，导致当开始密码是1时不能删除第一个结点，出现输出乱的现象，经检查发现该错误，采用在joseph函数的开始就扫描单循环链表，使指针其指向单循环链表的最后一个结点，以便需要时能删除第一个结点，也就是8说，在数结点时后面要跟一个指针，以便当数到要删除那个结点时，通过对后面跟着的指针所指结点的操作能删除数到的结点，这样就解决了这个问题。这一点也提醒我们，单恋表中的操作，要删除结点，必须有指向其“前驱”结点的指针，否则是不能删除要删除的结点的。3、由于先删除了结点空间，没有把被删结点中的密码保存，出现得到的密码不是被删结点的密码，而是被删结点下一个结点的密码，导致输出的信息不正确，修改成在删除结点空间前先保存其密码而解决。4、算法的时间复杂度设约瑟夫问题中的人数为n,则建立单链表的时间复杂度是Ο(n)，约瑟夫问题的求解模块中，要n次出列人，而每次出列人要走m个结点，设密码的平均值为m，则约瑟夫问题求解模块的时间复杂度为Ο(n×m)。所以算法的时间复杂度为○(n)。五、测试结果第一组：Input73172484Output614723第二组：Input10529683114710Output69724531810测试通过。六、用户使用说明1、本程序的运行环境为windows操作系统下命令执行方式，执行文件为：exp1.exe；也可在VC集成环境下执行。2、运行程序后输入人数n后，按提示依次输入n个密码即可。输出的是约瑟夫问题的求解过程中出列人的编号。见下图。9七、附录源程序文件名清单：exp1.cpp。实验结束后上交。10实验一、大整数加法一、问题描述给定两个非负整数A和B,计算出A+B的值。整数A和B的位数可能超过整数类型数据能存储的范围。要求计算并输出A+B的值。二、基本要求1、正确输入两个大整数；2利用两个单链表存储结构存储两个大整数；3对存储于单链表的两个大整数，根据数据加法的要求，通过对链表的操作，使两个大整数的和存储于单链表，并考虑尽量使用原单链表存储空间；4输出两个大整数的和，即输出和单链表中的内容。三、测试数据第一组999999999999999999991第二组123456789876543219876543212345678987654321第三组888888888888888888888888888888886666666666666666666666666666666666666666四、实现提示1、算法思路(1)正确输入两个整数，由于其整数位数可能超过整数数据类型可以存储的范围，所以要用字符串的数据