课程设计任务书
2010 ~2010 学年第 1 学期
学生姓名:吴浪专业班级: 09网络工程
指导教师刘志远工作部门:计算机学院
一、课程设计题目哈希表及其应用
二、课程设计内容
建立一个小型信息管理系统(可以是图书、人事、学生、物资、商品等任何信息管理系统)。要求:
1.使用哈希查找表存储信息;
2.实现查找、插入、删除、统计、输出等功能;
三、进度安排
1.初步完成总体设计,搭好框架;
2.完成最低要求:尝试使用多种哈希函数和冲突解决方法,并通过实际运行测试给出自己的评价
四、基本要求
1.界面友好,函数功能要划分好
2.程序要加必要的注释
3.要提供程序测试方案
教研室主任签名:
年月日
1 概述 (4)
2 设计目的 (4)
3 设计功能说明 (4)
4 详细设计说明 (5)
5 流程图 (5)
6 程序代码 (6)
7 程序运行结果 (15)
8 总结 (19)
参考文献 (19)
成绩评定表 (20)
3 / 20
数据结构是一门理论性强、思维抽象、难度较大的课程,是基础课和专业课之间的桥梁,只有进行实际操作,将理论应用于实际中,才能确实掌握书中的知识点。通过课程设计,不仅可以加深学生对数据结构基本概念的了解,巩固学习成果,还能够提高实际动手能力。为学生后继课程的学习打下良好的基础。
2 设计目的
《数据结构》课程设计是在教学实践基础上进行的一次大型实验,也是对该课程所学理论知识的深化和提高。因此,要求学生能综合应用所学知识,设计与制造出具有较复杂功能的应用系统,并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想,并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。
1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法,能够较熟练地完成程序的设计和调试。
2.培养学生综合运用所学知识独立完成程序课题的能力。
3.培养学生勇于探索、严谨推理、实事求是、有错必改,用实践来检验理论,全方位考虑问题等科学技术人员应具有的素质。
4.提高学生对工作认真负责、一丝不苟,对同学团结友爱,协作攻关的基本素质。
5.培养学生从资料文献、科学实验中获得知识的能力,提高学生从别人经验中找到解决问题的新途径的悟性,初步培养工程意识和创新能力。
6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。
3 设计功能分析
本设计的功能如下:
1、利用哈希函数来实现一个小型信息管理系统,其中信息包含用户名,地址,电话等。
2、能添加用户信息,并能保存该信息。
3、查询管理系统中的信息:可通过姓名查找,也可通过电话查找等两种方式。
4、能散列管理系统中的信息,保存信息等功能。
4 详细设计说明
哈希表是一种重要的存储方式,也是一种常见的检索方法。其基本思想是将关系码的值作为自变量,通过一定的函数关系计算出对应的函数值,把这个数值解释为结点的存储地址,将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。
(1) 假定每个记录有下列数据项:用户名、电话号码、地址。
(2) 初始记录为空,通过不断添加记录,并保存到数据文件telphone.txt
中。
(3) 分别采用线性和平方探测解决冲突。
(4) 查找并显示给定电话号码的记录;查找并显示给定用户
名的记录。
5 / 20
6 程序代码
#include
#include
#include
#include
using namespace std;
#define Maxsize 57
struct record
{char name[20];
char tel[20];
char add[20];};
typedef record *precord;
struct HashTable
{ int elem[Maxsize]; //存放数组a[]的下标
int count;};
typedef HashTable * pHashTable;
int Number; //统计当前数组a[]中的记录总数
void Getdata(precord a) //从文件telphone.txt中读取数据存放到数组a[] { Number=0;
ifstream infile("telphone.txt",ios::in|ios::binary);
if(!infile) {cout<<"文件打开失败!\n"; exit(1);}
while(!infile.eof() && infile.get()!=EOF) //文件不为空并且文件指针没有指到结束符
{infile.seekg(Number*sizeof(a[Number]),ios::beg); //定位文件指针infile.read((char *)&a[Number],sizeof(a[Number]));
Number++;}
infile.close();}
void Add(precord a) //添加记录
{ int i,num;
cout<<"当前文件内已有"< cout<<"请输入添加的个数:"; cin>>num; ofstream ofile("telphone.txt",ios::app); if(!ofile) {cout<<"文件打开失败!"; exit(1);} for(i=0;i {cout<<"请输入第"< cout<<"请输入第"< cout<<"请输入第"< ofile.seekp(ios::end); ofile.write((char *)&a[Number],sizeof(a[Number])); Number++;} ofile.close();} void Print(precord a) //显示所有记录 { int i; for(i=0;i {cout<<" 姓名:"< cout<<" 电话:"< cout<<" 地址:"< } int Hash(char str[]) //除留取余 { long val=0;char p[20],*p1; strcpy(p,str); p1=p; while(*p1!='\0') val=val+*p1++; //将字符串中的所有字符对应的ASCII值相加return(val%Maxsize); } int derter; //线性增量 int Line_Sollution(int address) //采用线性探测解决冲突 7 / 20 { derter++; if(derter==Maxsize) return(-1); else return((address+derter)%Maxsize); } int n; int Square_Sollution(int address) //采用平方探测法解决冲突 { int j;derter++; if(derter==Maxsize) return -1; n=n*(-1); j=(int(pow((float)derter,2))*n+address)%Maxsize; return(j);} void Init_Hash(pHashTable h) //初始化哈希表 { int i; for(i=0;i h->elem[i]=-1; } int menu; void Creathash_Name(pHashTable h,precord a)//以员工姓名为关键字创建哈希表 {cout<<" ------------------------------------------------------------------------\n"; cout<<" 1----以线性探测建表\n"; cout<<" 2----以平方探测建表\n"; cout<<" ------------------------------------------------------------------------\n"; int i,address; cout<<"请选择:"; cin>>menu; Init_Hash(h); for(i=0;i { derter=0;n=-1; address=Hash(a[i].name); while(h->elem[address]!=-1) {if(menu==1) address=Line_Sollution(address); else address=Square_Sollution(address); if(address==-1) break;} if(address!=-1) { h->elem[address]=i; h->count++;} } cout<<"姓名哈希表已成功建立!\n"; } void Search_Name(pHashTable h,precord a) //查找并显示指定姓名的记录{ cout<<"请输入要查找的姓名:"; char nam[20];int address,i=1; cin>>nam; address=Hash(nam); derter=0;n=-1; while(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)!=0) { if(menu==1) address=Line_Sollution(address); else address=Square_Sollution(address); i++; if(address==-1) break;} if(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)==0) { cout<<"你要查找的信息为:\n"; cout<<" 姓名:"<elem[address]].name< cout<<" 电话:"<elem[address]].tel< cout<<" 地址:"<elem[address]].add< cout<<"比较次数为"< else cout<<"无此姓名,查找失败!"; } 9 / 20 void Creathash_tel(pHashTable h,precord a) //以电话号为关键字创建哈希表 {cout<<" ---------------------------------------------------------\n"; cout<<" 1----以线性探测建表\n"; cout<<" 2----以平方探测建表\n"; cout<<" ---------------------------------------------------------\n"; int i,address; cout<<"请选择:"; cin>>menu; Init_Hash(h); for(i=0;i { derter=0;n=-1; address=Hash(a[i].tel); while(h->elem[address]!=-1) {if(menu==1) address=Line_Sollution(address); else address=Square_Sollution(address); if(address==-1) break;} if(address!=-1) { h->elem[address]=i; h->count++;} } cout<<"电话号码哈希表已成功建立!\n";} void Search_tel(pHashTable h,precord a)//查找并显示指定电话号的记录{ cout<<"请输入要查找的电话:"; char telphone[20];int address,i=1; //i统计比较次数 cin>>telphone; address=Hash(telphone); derter=0; n=-1; //初始化线性增量 while(h->elem[address]!=-1&& strcmp(telphone,a[h->elem[address]].tel)!=0) { if(menu==1) address=Line_Sollution(address); else address=Square_Sollution(address); i++; if(address==-1) break;} if(h->elem[address]!=-1 && strcmp(telphone,a[h->elem[address]].tel)==0) { cout<<"你要查找的信息为:\n"; cout<<" 姓名:"<elem[address]].name< cout<<" 电话:"<elem[address]].tel<