《《数据结构》实验指导书(Java语言版).doc》由会员分享，可在线阅读，更多相关《《数据结构》实验指导书(Java语言版).doc（95页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程实验指导数据结构实验教学大纲课程代码：0806523006 开课学期：3开课专业：信息管理与信息系统总学时/实验学时：64/16总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉
2、及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。三、实验
3、方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。具体实验要求如下：1. 问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。2. 数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。3. 算法设计算法设计分概要和详细设计。概要设计着重解决程序的类的设计问题，这包括考虑如何把被开发的问题程序分解成若干个类，并决定类与类之间的关系。详细设计
4、则要决定每个类内部的具体算法，包括输入、处理和输出。4. 测试用例设计准备典型测试数据和测试方案。测试数据要有代表性、敏感性。测试方案包括单元测试和单元集成测试。5. 上机调试对程序进行编译，纠正程序中可能出现的语法错误。调试前，先运行一遍程序看看究竟将会发生什么。如果情况很糟，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。6. 程序性能分析在运行结果正确的前提下再分析程序中主要算法是否具有较好的时间复杂度和空间复杂度。如果没有，则通过改变数据结构或操作方法使编写的程序性能达到最佳。7. 实验总结每个实验完成后要认真书写实验报告，对程序运行的结构，
5、要认真分析，总结每次实验项目的体会与收获。四、报告与考核每个实验都要求学生根据上机内容写出实验报告，报告要求包括以下七个方面的内容：1实验目的；2实验内容；3实验要求；4算法设计；5详细程序清单；6程序运行结果；7实验心得体会。考核方式：每个实验项目根据以下两个方面进行考核：1指导教师随堂抽查学生的实验过程（包括实验预习、实验出勤、实验结果的测试），并根据抽查结果评定学生成绩，此成绩占此实验总成绩的70%；2学生编写课程实验报告，每位学生按照实验报告的内容和要求编写详细的实验报告上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占实验总成绩的30%。五、设备及器材材料配置硬件：奔
6、腾以上PC机软件：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境六、实验指导书及主要参考书1刘小晶.数据结构实验指导书(Java语言版)2 Robert Lafore著,计晓云等译. Java数据结构和算法(第二版)M. 北京：中国电力出版社,2004.3 Sartaj Sahni著,孔芳,高伟译. 数据结构、算法与应用(Java语言描述)M. 北京：中国水利水电出版社,2007.4 叶核亚. 数据结构(Java版)M. 北京：电子工业出版社，2004.5 邓俊辉. 数据结构与算法(Java语言描述)M. 北京：机械工业出版社，2006.6 朱战立. 数据结构- J
7、ava语言描述M. 北京：清华大学出版社，2005.7 张铭.数据结构与算法. 高教出版社.2008.68 张铭.数据结构与算法学习指导与习题解析. 高教出版社.20099 耿国华等 数据结构-C语言描述. 高教出版社.2005.710 刘怀亮. 数据结构(C语言描述) .冶金出版社.2005.211 刘怀亮. 数据结构(C语言描述)习题与实验指导导.冶金出版社.2005.212 蔡子经，施伯乐.数据结构教程.上海:复旦大学出版社.199413 严蔚敏,吴伟民.数据结构(C语言版).北京：清华大学出版社.1999；14 严蔚敏,吴伟民.数据结构题集(C语言版).北京：清华大学出版社.1999；
8、15 徐孝凯.数据结构课程实验.北京：清华大学出版社.2002； 16 孟佳娜,胡潇琨.算法与数据结构实验与习题.北京：机械工业出版社.2004.七、实验项目与内容提要序号实验名称目的要求、内容提要（限20字）每组人数实验学时实验类型必做选做所在实验分室1顺序表的基本操作熟悉并完成顺序表上基本操作的算法及其应用问题的编程实现。1个班2验证与设计必做2链表的基本操作熟悉并完成单链表和双向链表基本操作算法的编程实现。1个班2验证与设计必做3栈的基本操作熟悉并完成顺序栈和链栈基本操作算法及其应用问题的编程实现1个班2验证与设计必做4队列的基本操作熟悉并完成循环顺序队列和循环链队列基本操作算法及其应用
9、问题的编程实现。1个班2验证与设计必做5二叉树的操作熟悉并完成二叉树遍历算法及其应用问题的编程实现。1个班2验证与设计必做6静态查找表的查找操作熟悉并完成静态查找表上的顺序查找、二分查找和索引查找算法的编程实现1个班2验证与设计必做7二叉排序树的查找操作熟悉并完成在二叉排序树上进行查找、插入和删除操作的编程实现。1个班2验证与设计选做8哈希表上的查找操作熟悉并完成哈希表的建立、查找和插入操作的编程实现1个班2验证与设计选做9排序操作熟悉并完成几种主要排序操作的编程实现。1个班2验证与设计必做10图的遍历熟悉并完成图的遍历、最小生成树及其应用问题的编程实现1个班2验证与设计选做66实验B01:
10、顺序表的操作实验一、实验名称和性质所属课程数据结构实验名称顺序表的操作实验学时2实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握线性表的顺序存储结构的表示和实现方法。2掌握顺序表基本操作的算法实现。3了解顺序表的应用。三、实验内容1建立顺序表。2在顺序表上实现插入、删除和查找操作（验证性内容）。3删除有序顺序表中的重复元素（设计性内容）。4完成一个简单学生成绩管理系统的设计（应用性设计内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Netbeans 6.5以上或Eclipse、MyEclipse等编程环境下 。五、知识准备前期要求熟练掌
11、握了Java语言的编程规则、方法和顺序表的基本操作算法。六、验证性实验1实验要求编程实现如下功能：（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。（2）在顺序表的第i(0in)个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。（3）删除顺序表中第i(0in-1)个元素，并输出删除后的顺序表中各元素值。（4）在顺序表中查找值为x的数据元素初次出现的位置。如果查找成功，则返回该数据元素在顺序表中的位序号；如果查找失败，则返回-1。2. 实验相关原理线性表的顺序存储结构称为顺序表，线性表的顺序存储结构在线性表Jav
12、a接口的实现类中描述如下：public class SqList implements IListprivate Object listElem; / 线性表存储空间private int curLen; /线性表的当前长度 【核心算法提示】顺序表插入操作的基本步骤：要在当前的顺序表中的第i(0in, n为线性表的当前长度)个数据元素之前插入一个数据元素x，首先要判断插入位置i是否合法， i的合法值范围：1in+1，若是合法位置，就再判断顺序表是否满，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的当
13、前长度值增加1，否则抛出异常。顺序表删除操作的基本步骤：要删除当前顺序表中的第i(0in-1)个数据元素，首先仍然要判断i的合法性，i 的合法范围是0in-1，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的当前长度减1，否则抛出异常。顺序表查找操作的基本步骤：要在当前顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第0个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，如果所有数据元素都与x比较但都不相等，表明值为x的数据元素在顺序表中不存在，则返回-1值。【核心算法描述】在当前顺序表上的插入操作算法v
14、oid insert(int i, Object x) throws Exception if (curLen = listElem.length) / 判断顺序表是否已满 throw new Exception(顺序表已满); / 抛出异常 if (i curLen) / i不合法 throw new Exception(插入位置不合法);/ 抛出异常 for (int j = curLen; j i; j-) listElemj = listElemj - 1;/ 插入位置及其之后的所有数据元素后移一位 listElemi = x; / 插入x curLen+; / 表长加1 在当前顺序表上的删除操作算法void remove(int i) throws Exception if (i curLen - 1) / i不合法 throw new Exception(删除位置不合法);/ 抛出异常 for (int j = i; j curLen
