数据结构课程设计实验报告

《数据结构课程设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件111班18号赵庆珍《数据结构》课程设计任务书学期：12-13-1班级：软件111一、设计目的《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基

2、本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在三周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题说明：课程设计题目主要分为两大类：，主要是验证性题，少数是简单的综合性题，侧重考查学生对数据结构课程中重要数据结构和算法的理解与掌握程度，相对较简

3、单；本类题目选题要求：要求个人所选题目必须独立完成；原则上不得参考别人的程序，若个人能力有限必须参考，参考成分不得超过30%，其中参考部分自己必须能消化吸收，否则视为无效；为培养学生分析问题、解决问题的实际动手能力和团队协作能力，鼓励有能力的学生尽可能选作难度较高的题目，故仅选作一星题目的学生，无论完成多少题目，原则上最高分不超出70分；仅选作一星和二星题目的学生，无论完成多少题目，原则上最高分不超出85分注意：上述题目，可以相互讨论，但严禁搭便车，杜绝拷贝或分享别人的劳动果实，坚决杜绝让别人代做。一经发现、核实，无论是拷贝者或是被拷贝者的成绩均

4、视为不及格，情节严重者将交由学工办通报批评并受到相应的纪律处分。53软件111班18号赵庆珍选题说明：一个*的题代表满分10分，出色完成者方可得满分，下同；两个*的代表满分15分，三个*的题代表满分30分，四个*的题代表60分。验收时将根据实际选做题目的分值和数量以及实现程序的完善性可以适当加减分；同学们在选题时，要结合个人实际情况，力争多做，必须保证所选题目总分应该在100分以上，保障及格。第一题（一）设计内容简介散列表的设计与实现（**）任务：设计散列表实现电话号码查找系统。要求：（1)设每个记录有下列数据项：用户名、电话号码、地址；（2)从

5、键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表；（3)采用一定的方法解决冲突；（4)查找并显示给定电话号码的记录；选作内容：（1)系统功能的完善；（2)设计不同的散列函数，比较冲突率；（3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。（二）算法设计说明此算法要用散列表实现，里面必须涉及到哈希表的建立，整个程序要实现的功能有：添加用户信息；读取所有用户信息；以姓名建立哈希表；以电话号码建立哈希表；查找并显示给定用户名的记录；查找并显示给定电话号码的记录；清屏以及保存功能。定义电话本记录数量（MAXSI

6、ZE）、表长（HASHSIZE）、姓名长度(MAX_SIZE)以及结构体typedefstruct的内容，构造两个哈希函数hash1和hash2。解决冲突的办法，姓名用折叠法处理，电话号码取其整型长度，hash1是用姓名建立的哈希函数，hash2是用电话号码建立的哈希函数，两个哈希函数都是用除留余数法实现。处理冲突的函数，采用二次探测法。（三）测试结果1.程序的主界面，包含程序的各个功能：53软件111班18号赵庆珍2.添加用户信息的测试结果：3.用哈希数查找第一个用户的信息：（四）分析与探讨这道题主要解决在查找用户时解决冲突。利用哈希表。程序的

7、功能像添加用户信息，读取所有用户信息，清屏以及保存功能，都很容易实现，而像以姓名建立哈希表；以电话号码建立哈希表；查找并显示给定用户名的记录；查找并显示给定电话号码的记录这些就比较难点。要想实现这些，必须了解关于散列表的一些基本定义和原理。以姓名建立哈希表的主要函数：voidCreateHash1(HashTable*H,Record*a){for(i=0;ielem[pp]!=NULL)53软件111班18号赵庆珍{pp=collision(p

8、,c);if(pp<0){cout<<"第"<elem[pp]=&(a[i