数据结构课程设计实验指导书20100104

《数据结构课程设计实验指导书20100104》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计指导书东华大学计算机科学与技术学院2010年1月13目录1.前言12顺序表与链表52.1实验内容52.2实现提示63树和二叉树83.1实验内容83.2实现提示84图104.1实验内容104.2实现提示115查找和排序125.1问题描述125.2问题分析125.3实现提示13131.前言《数据结构》是计算机科学与技术专业的一门核心专业基础课程，它主要介绍线性结构、树型结构和图型结构的存储实现与基本操作，尤其是查找与排序算法的实现，并分析相应算法的时间、空间效率。其主要任务是培养学生的算法设计能力及

2、良好的程序设计习惯。通过学习，要求学生掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案、设计出简洁、高效、实用的算法，并为后续课程的学习及软件开发打下良好的基础。为了更好地配合数据结构课程的实践，特编写此课程设计指导书。1.1指导思想本次课程设计的指导思想是：1、学习获取知识的方法；2、提高发现问题、分析问题和解决实际问题的能力；3、加强创新意识和创新精神；4、加强团队的分工与合作；5、掌握面向实际背景思考问题的方法。1.2设计任务本次课程设计任务主要分为个人任务和小组任务两种。个人基本任务

3、：完成第2章以及第3章中的设计任务，其中选做题不是必须完成的任务。小组任务：13完成第4章和第5章的设计任务，其中选做题不是必须完成的任务。1.1要求1、每项目小组人员为3~5名。2、每项目小组提交一份课程设计报告，内容包括：课题名称，课题参加人员名单和分工，课题的目的，课题内容，需求分析、概要设计、主要代码分析、测试结果、课题特色和创新之处、收获与体会、使用说明。3、每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会

4、。无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。1.2参考进度第1天，布置任务。第1、2、3天，完成第2章任务第4、5、6天，开始第3章任务。第7到10天，完成小组任务。1.3成绩评定采用小组考核和个人考核两级考核方法。1、小组考核（1）圆满完成第4章和第5章的全部内容的小组成绩为优。13（2）第4章选做题任务未完成的小组成绩为良。（3）未通过验收的项目为不及格。1、个人考核：全部完成并经过良好测试才能评优。个人未完成选做题任务的为良；个人只完成所有个人任务的一半以上的为及格；

5、个人成绩的评定还受项目组成绩影响。2、小组成绩折算成个人成绩方法：小组交实验报告时同时交一份成员贡献表，表格式如下：学号姓名贡献度101张三120102李四90103王五90104钱六100（总计）400上表中，如果成员数为4，则贡献度总和为400。如果小组成绩为80分，则折算到个人的成绩如下：张三：80*120/100=96分李四：80*90/100=72分王五：80*90/100=72分钱六：80*100/100=80分13如果某小组无此表格，则每个成员的贡献度按100计算。如果某小组的贡献度平均值大于10

6、0，则降低组长的贡献度，使得平均值为100。1.1注意事项：1、迟到3次或缺席一次，成绩下降一个档次，迟到6次或缺席2次，成绩再下降一个档次，依次类推。2、上机时发现玩游戏一次，成绩下降一个档次，玩游戏二次，成绩再下降一个档次，依次类推。3、课程设计开始前，各班的同学在班内自由组合，形成小组，每小组自行推荐小组长一人，在课程设计开始的第一天上交组长名单、小组组员名单，名单上注明班级、学号、姓名。1.2参考书目[1]严蔚敏等著，数据结构（C语言版），清华大学出版社132顺序表与链表2.1实验内容1、顺序表的应用(

7、1)．对于顺序存储的线性表，请实现以下功能：1）实现二路归并排序算法。2）实现希尔排序算法。3）实现快速排序算法。4）实现堆排序算法。(2)．已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。要求：线性表元素个数n很大，而值为item的数据元素个数很少，要求移动元素个数尽量少；删除后的数组元素与原数组元素不必保持顺序一致。(3)．编写一个主函数,调试上述算法。2、链表的应用(1)．假设有两个按元素值递增次序排列的线性表A

8、和B，均以单链表形式存储，里面的大部分元素对应相等，请删除一些元素（A中有而B中没有，或B中有而A中没有），使得两个有序表中保留下来的元素对应相等。比如，A中元素为（1,3,5,8,10,13,18），B中元素为（1,3,6,8,9,10,13,15），则删除元素后A、B里的元素为（1,3,8,10,13）。(2)．猴子选大王。n只猴子围成一圈，从1到m报数，报m的猴子出局。余下的猴子