2010数据结构实验指导书48分析.doc

《数据结构B》实验指导书 电子工程学院 数据结构与算法分析教学小组编 前 言 《数据结构B》是电子工程学院测控技术与仪器和电子信息科学与技术专业的专业必修课。由于教科书选材的变动，原来使用的数据结构实验指导书与授课内容关联不够密切。为了能更好的将理论教学和实验教学结合在在一起，我们调整了实验内容的安排，加大了实验的实践力度，并重新编写了实验指导书。要学好数据结构这门课，加强算法的设计并上机加以实现是非常重要的，希望同学们充分利用实验条件，认真完成实验，从实验得到相应的锻炼和培养。另外，仅仅依靠本实验教材中的实验想达到透彻理解数据结构的相关算法和实现是远远不够的，有条件有兴趣的学生可以针对学习和实践中出现的问题主动地思考和设计算法，编写程序，进一步提高自己分析问题和解决问题的能力。 希望同学们在使用本实验指示书及进行实验的过程中，对本实验指导书中的不足之处提出建议，使《数据结构B》课程的教学得到不断的改进和提高。 本实验指导书在编写过程中，参考了原来的电子工程系的数据结构实验指导书、计算机系的实验指导书。 由于编者水平有限，难免有不足之处，敬请批评指正。 电子工程学院数据结构与算法分析教学小组 2008年4月 目 录 实验说明及要求 3 实验一 线性表 4 实验二 栈 6 实验三 队列 8 实验四 树 10 实验五 散列表 14 实验六 排序 2 实验七 查找 5 实验八 图 8 综合设计考核 11 附录1 在Visual Studio.net 2003中建立、编译和运行程序 12 附录2 使用教材提供的参考文件的方法 17 附录3 如何设置编译器生成C代码 20 参考文献 21 实验说明及要求 一 实验说明 《数据结构B》实验是为了辅助《数据结构B》n（n=0）个数据元素组成的有限序列。线性表中的数据元素可以是各种各样的，但同一线性表中的数据元素必须有相同的属性，因此是属于同一数据类型的。 在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续存储单元依次存储线性表中的元素。其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。一般地，线性表的顺序存储结构可用一个一维数组结构来描述。用这种方法存储的线性表简称为顺序表。线性表的链式存储结构（也称链表）的特点是用一组任意的存储单元存储线性表中的数据元素，不要求逻辑上相邻的元素在物理位置上也相邻。链表中的结点可用C语言中的结构数据类型来描述，也可以用C++语言中类来实现。链表中的结点只有一个链域的链表称为单链表。循环链表则是一种首尾相接的链表。 对线性表首先要掌握作为抽象数据类型（ADT）的那些基本操作，其次才是具体实现的细节。 实验要求（课题一必做，课题二选做） 实验课题一： a、（C++语言实现）： 使用教材参考代码中给出的线性表类构造一个表，查找表内是否有某元素，如果有则交换该元素和它相邻的下一元素的位置； （2和3中选一个即可）为链表类List增加一个成员函数reverse，使其具备能倒置链表中元素的功能。写好的表倒置函数的时间复杂度应该是?(n)； 为List链表实现增加逆转迭代器类（reverse iterators），并增加方法rbegin和rend，具体要求参见教科书109页习题3.16。 b、?(n)。 课题一的具体实验内容 1、构造元素类型为整型的线性表，将以下元素插入分别插入线性表： 34 56 20 9 15 5 2、查找表中是否存在元素20，实现元素20与元素9的交换； 3、按照课题要求编写函数，实现线性表元素34 56 9 20 15 5的倒置，即倒置后的表应为 5 15 20 9 56 34 。 *实验课题二：约瑟夫（Josephus）问题的求解（循环链表的使用，使用C和C++语言均可）。 假设有编号为1，2，……，n的n个人围坐成一圈，约定从编号为k（n=k=1）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。 1、给定一个8个人的圈（n=8）6 2 7 4 3 5 1 8 。 实验步骤： 在“F:\DataStru\”目录下面创建自己以自己学号作为名字的文件夹。自己所有的实验程序均放在该文件夹下面。 创建项目，文件保存到第1步说的目录。 每台计算机的教材参考代码在“E：DataStru\”，先解压至“F:\DataStru\”。 通过“工