号码系统查询.docx
《号码系统查询.docx》由会员分享,可在线阅读,更多相关《号码系统查询.docx(18页珍藏版)》请在冰点文库上搜索。
![号码系统查询.docx](https://file1.bingdoc.com/fileroot1/2023-6/8/91e1f80d-d95d-4a77-8708-7ad99467ceac/91e1f80d-d95d-4a77-8708-7ad99467ceac1.gif)
号码系统查询
湖南人文科技学院运算机科学技术系
课程设计说明书
课程名称:
数据结构
课程代码:
408024
题目:
号码查询系统
年级/专业/班:
学生姓名:
学号:
指导教师:
开题时间:
2020年12月21日
完成时间:
2020年1月1日
摘要
哈希表最大的优势,确实是把数据的存储和查找消耗的时刻大大降低,几乎能够看成是常数时刻;而代价仅仅是消耗比较多的内存。
但是在当前可利用内存愈来愈多的情形下,用空间换时刻的做法是值得的。
另外,编码比较容易也是它的特点之一。
哈希表又叫做散列表,分为"开散列"和"闭散列"。
本次课程设计是为用户解决关于号码的存储,查询,和添加删除。
用户能够通过键盘输入用户信息进行存储,然后在通过哈希表提供的2种查询方式进行用户信息查询。
关键词:
哈希表;散列函数;冲突处置
Abstract
Hashtableofthebiggestadvantagesisthatthedatastorageandsearchtimesignificantlyreducedconsumption,almostcanberegardedasconstanttime;whilethepriceisjustconsumingmoreandmorememory.However,inthecurrentavailablememory,anincreasingnumberofcases,thepracticeofusingspacefortimeisworthit.Inaddition,thecodeisalsorelativelyeasytooneofitscharacteristics.Hashtableisalsocalledahashtableisdividedinto“openhash”and“closedhashing”.
Thiscourseisdesignedtosolveonthephonenumbersforuserstostore,query,andaddremove.Userscanenteruserinformationviathekeyboardisstored,andthenthroughthehashtableprovidedbythetwokindsofwaystosearchforuserinformationquery.
Keywords:
hashtable;hashfunction;ConflictManagement.
《数据结构》课程设计
----号码查询系统
一、引言
随着我国进一步的开放,咱们需要扩大国际交流,增强学习国外的先进体会。
把握国际的领先技术是咱们的首要任务。
运算机技术进展异样迅速,内容更新专门快,咱们对运算机的了解程度也直接阻碍了我国的现代化和信息化的程度。
《数据结构》是运算机程序设计的重要理论技术基础,它不仅是运算机学科的核心课程,而且是其他理工专业的热点选修课。
数据结构研究的是世界上所有非数值量的信息结构及其处置方式,它不仅是运算机科学与技术相关专业十分重要的核心课程,也是应用数学、治理科学、环境计划等很多专业的一门重要基础课。
所有的运算机系统软件和应用软件都要用到各类类型的数据结构。
因此,关于所有想更好地运用运算机来解决实际问题得人们而言,仅把握几种运算机程序设计语言是难以应付众多复杂的课题的。
要想有效地利用运算机、充分发挥运算机的性能,还必需学习和把握好数据结构的有关知识。
打好《数据结构》这门课程的扎实基础,关于学习运算机专业的其他课程,如操作系统、编译原理、数据库治理系统、软件工程、人工智能等都是十分有利的。
本课程设计要求实现号码的查询。
一样的查找方式有各式各样的缺点,可是哈希表不同,哈希表是一种通过捐躯空间来提高效率的方式,理论上,有足够的空间的话,哈希表和他的函数几乎能不通过任何比较一次性就能够取得结果。
为了实现查询功能,用到了关于哈希表的存储结构和链表结构,而且通过链地址法解决哈希表冲突。
课程设计要求用哈希表实现功能,第一要解决哈希表的存储冲突问题,对不同的关键字可能取得同一个哈希地址,这种现象称为冲突。
在以住,咱们都以为冲突只能尽可能地少,而不能完全地幸免。
关于那个问题,通过一番对照和试探,决定采纳链地址法解决冲突。
成立一个链表,将冲突的关键字都存入同一个链表,同时将每一个链表的头指针存入另一个链表。
二、设计目的与任务
一、课程设计的目的
通过课程设计,使咱们巩固所学知识、培育咱们动手能力。
咱们用数据结构设计一个完整的应用程序,综合应用所学知识完成软件的分析、设计、调试和总结,提高咱们对数据结构综合应用能力和解决问题的能力。
灵活应用所学数据结构知识,独立完成问题分析。
初步把握软件开发进程的问题分析、系统设计、程序编码、测试等方式。
训练用系统的观点和软件开发一样标准进行软件开发。
提高综合运用所学的理论知识和方式独立分析和解决问题的能力。
同时增加了咱们之间的团队合作精神!
加倍也体会到以后在工作中团队合作的重要性和必要性!
二、课程设计的任务
问题描述:
利用哈希表实现号码的查找功能,要求输入号码或用户姓名能够查找出用户信息。
而且能加入新的用户。
设计散列表实现查询系统。
三、设计方案
一、需求分析
1)设每一个记录有以下数据项:
号码、用户名、地址;
2)从键盘输入各记录,别离以号码和用户名为关键字成立散列表;
3)采纳必然的方式解决冲突;
4)查找并显示给定的号码的记录;
5)查找并显示给定用户名的记录;
二、概要设计
1)哈希表数据类型(ADT)如下:
ADTnode
{数据对象:
name,address,num;
数据关系:
name为用户姓名,address为用户地址,num为用户号码;
大体操作:
(1)voidhash(charA[])
程序功能:
关于key的哈希函数,函数值为key的值
(2)node*input()
程序功能:
输入一个节点的值
(3)intapend()
程序功能:
将节点添加到哈希表
(4)voidcreate()
程序功能:
新建一个哈希表
(5)voidfind(charA[])
程序功能:
通过线索查找用户
}
2)存储结构
structnode
{
charname[8],address[20];//姓名,地址存储字符组
charnum[11];//号码存储字符组
node*next;//后继元素地址
};
3)流程图
开始
输入b
b是1?
2
2,输入数据入key2
1,输入数据入key
从姓名列表查询
从号码列表查询
输出搜索结果
结束
3、详细设计
在本次课程设计中,咱们用到了哈希表那个重要的数据结构,在实现程序功能的时候,很多地址都涉及哈希表,另外咱们用到了链表,在程序顶用到了许多链表的操作,比如成立,添加,删除等操作。
在对程序进行整体设计时,咱们选用了哈希表表这种数据结构来存贮数据,哈希表查找迅速,理论上空间足够大的话,能够不需比较直接找到目标因此比较适合本程序的要求。
重要程序段如下:
1)以号码和姓名为关键字的哈希函数
voidhash(charnum[11])
{
inti=3;
key=(int)num[2];
while(num[i]!
=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20;
}
同意传来的号码和姓名,第一判定号码和姓名是不是为空。
不为空那么将号码和姓名的每位转化为整型进行累加,然后用用除留取余法取得关键码。
2)输入函数
node*input()
{
node*temp;
temp=(structnode*)malloc(sizeof(structnode));
temp=newnode;
temp->next=NULL;
cout<<"输入姓名:
"<cin>>temp->name;
cout<<"输入地址:
"<cin>>temp->address;
cout<<"输入:
"<cin>>temp->num;
returntemp;
}
成立一个新结点,将结点的下个结点置空。
输入姓名,地址,后返回结点。
3)添加新结点
intapend()
{
node*newphone;
node*newname;
newphone=input();
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next=phone[key]->next;
phone[key]->next=newphone;
newname->next=nam[key2]->next;
nam[key2]->next=newname;
return0;
}
成立一个新的结点和姓名结点,挪用输入函数。
将结点的地址赋给姓名结点,使它们拥有一样的值,别离挪用以号码和以姓名为关键字的哈希函数。
然后将结点插入到表中。
4)初始化号码表
voidcreate()
{
inti;
phone=newpnode[20];
for(i=0;i<20;i++)
{
phone[i]=newnode;
phone[i]->next=NULL;
}
}
为号码表申请20个元素,为表中每一个元素申请空间,将其数据元素置空。
5)查找函数
voidfind(charnum[11])
{
inti=0;
hash(num);
node*q=phone[key]->next;
while(q!
=NULL)
{
if(strcmp(num,q->num)==0)
{
cout<name<<"_"<address<<"_"<num<i=1;
}
q=q->next;
}
if(!
i)cout<<"无此记录"<}
依照号码查找用户信息,num[11]为用户需要查询的号码,挪用哈希函数,取得关键码,然后进行判定。
声明一个操纵变量,若是找到记录那么将其赋1,不然为0。
6)保留用户信息
{
inti;
node*p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
fstreamiiout("out.txt",ios:
:
out);
iiout<name<<"_"<address<<"_"<num<p=p->next;
}
}
}
。
4、程序清单
#include
#include"string.h"
#include"fstream"
#defineNULL0
unsignedintkey;
unsignedintkey2;
int*p;
structnode//建节点
{charname[8],address[20];charnum[11];node*next;};
typedefnode*pnode;
typedefnode*mingzi;
node**phone;
node**nam;
node*a;
usingnamespacestd;//利用名称空间
voidhash(charnum[11])//哈希函数
{inti=1;key=(int)num[2];while(num[i]!
=NULL)
{key+=(int)num[i];i++;}
key=key%20;
}
voidhash2(charname[8])//哈希函数
{inti=1;key2=(int)name[0];
while(name[i]!
=NULL)
{key2+=(int)name[i];i++;}
key2=key2%20;
}
node*input()//输入节点
{node*temp;temp=newnode;temp->next=NULL;
cout<<"输入姓名:
"<>temp->name;
cout<<"输入地址:
"<>temp->address;
cout<<"输入:
"<>temp->num;
returntemp;
}
intapend()//添加节点
{node*newphone;node*newname;newphone=input();
newname=newphone;newphone->next=NULL;newname->next=NULL;
hash(newphone->num);hash2(newname->name);
newphone->next=phone[key]->next;phone[key]->next=newphone;
newname->next=nam[key2]->next;nam[key2]->next=newname;
return0;
}
voidcreate()//新建节点
{inti;phone=newpnode[20];
for(i=0;i<20;i++)
{phone[i]=newnode;phone[i]->next=NULL;}
}
voidcreate2()//新建节点
{inti;nam=newmingzi[20];
for(i=0;i<20;i++)
{nam[i]=newnode;nam[i]->next=NULL;}
}
voidfind(charnum[11])//查找用户信息
{inti=0;
hash(num);node*q=phone[key]->next;
while(q!
=NULL)
{if(strcmp(num,q->num)==0)
{cout<name<<"_"<address<<"_"<num<q=q->next;
}
if(!
i)cout<<"无此记录"<}
voidfind2(charname[8])//查找用户信息
{inti=0;
hash2(name);node*q=nam[key2]->next;
while(q!
=NULL)
{if(strcmp(name,q->name)==0)
{cout<name<<"_"<address<<"_"<num<q=q->next;
}
if(!
i)cout<<"无此记录"<}
voidsave()//保留用户信息
{inti;node*p;
for(i=0;i<20;i++)
{p=phone[i]->next;
while(p)
{fstreamiiout("out.txt",ios:
:
out);
iiout<name<<"_"<address<<"_"<num<p=p->next;
}
}
}
voidmenu()
{
charnum[11];
charname[8];
intsel;
cout<<"---------------------------------------------------"<cout<<"|菜单|"<cout<<"|1.添加记录|"<cout<<"|2.查找记录|"<cout<<"|3.清空记录|"<cout<<"|4.保留记录|"<cout<<"|5.退出系统|"<cout<<"---------------------------------------------------"<cout<<"请输入操作:
(1--5)";cin>>sel;
switch(sel)
{case1:
{cout<<"请输入要添加的内容:
"<apend();menu();break;}
case2:
{cout<<"1号码查询,2姓名查询"<intb;
cin>>b;
if(b==1)
{cout<<"请输入号码:
"<>num;
cout<<"输出查找的信息:
"<}
else
{cout<<"请输入姓名:
"<>name;
cout<<"输出查找的信息:
"<menu();break;
}
}
case3:
{cout<<"列表已清空;"<create2();menu();break;
}
case4:
{cout<<"通信录已保留:
"<menu();break;
}
case5:
cout<<"谢谢!
"<//break;
}
}
intmain()
{create();create2();menu();return0;}
四、调试分析与体会
本次课程设计的实例尽管比较简单,程序设计也不是很复杂。
可是在程序的编写和调试进程中,咱们仍是碰到了一些问题。
这些问题有些完满是自己的粗心造成的,有的却是一些由于咱们自身的知识面不广造成的。
这些问题提示咱们:
在做情形的时候专门是在做研究性的课题的时候必然要胆大心细。
同时也告知咱们:
在科学的世界里咱们要尽力的学习,取得更多的知识。
测试环境:
WindowsXP环境
一、问题一:
如何成立适当的哈希函数来减少冲突?
现象:
冲突较多,找不到插入位置。
缘故:
成立的哈希函数产生的关键码相同,哈希函数不合理。
二、问题2:
如何查找到相同记录的数据?
现象:
查找不到相同记录的元素,查找完一个就终止了。
缘故:
当查找完一个元素时,函数就终止了,并无继续查找。
五、运行结果
第一直接运行程序,运行结果如图1所示。
图1程序直接运行成效图
程序直接运行,挪用菜单
运行添加记录程序,运行结果如图2所示。
图2添加记录
输入1,选择添加记录,然后依照提示,输入用户姓名,地址,,输入完成后,程序自动挪用菜单。
运行查找记录程序,运行结果如图3所示。
图3查找记录
按提示输入2,显现2个选择,第一选择1号码查询,按提示输入要查询的号码,程序搜索记录并输出符合要求的记录,接着挪用菜单。
再次选择查找记录,这次选择2姓名查找,然后按提示输入要查询的姓名,程序输出符合要求的记录并再次挪用菜单。
六、结论
通过这次的课程设计,咱们关于号码查询系统有了更深刻的明白得,巩固了数据结构课学到的知识。
在编程的具体进程中,了解的一些关于哈希表的知识和存储结构。
通过本次课程设计,咱们了解到了课程设计的要求与方式,学会了程序设计的大体步骤,且进一步提高了团队合作的意识。
同时,我们也感觉到,一个优秀的程序,不单单只是能够运行,更应该具有较高的效率,合理的结构,良好的可读性和必然的容错性。
其中超级重要的一点是,我们以为整个课程设计是一个团队的工作,一个人要完成所有的工作是超级困难和耗时的,必需发挥团队的团结协作精神,提高工作效率和工作质量,团结协作是咱们本次课程设计取得成功的一项尤其重要的保证。
在以后的学习中我们也会加倍注意方方面面能力的和谐和进展。
七、致谢
感激我们的指导教师教师,谢谢他在我们的课程设计进程中提出了指导性的方案和架构,并指引我们阅读相关的资料和书籍,使我们在不熟悉的领域中仍能迅速把握新的方式和技术。
感激校领导给咱们这次宝贵的锻炼机遇,让咱们能更好的明白得和实践数据结构编程,让咱们对数据结构编程有了更深刻的认知,对已学知识有了更进一步的巩固。
也谢谢我的同窗与咱们一路合作,一起完成了那个课程设计。
八、参考文献
[1]严蔚敏.数据结构(C语言版)[M].北京:
清华大学出版社,1997.
[2]朱占立.数据结构(第二版)[M].西安:
西安交通大学出版社,2000.
[3]麦中凡.C++程序设计语言教程[M].北京:
北京航空航天大学出版社,1995.
[4]杜慧、李哲英、骆丽,MCTL系统中成立任务流集合的研究[J],北方工业大学学报,2004Vol.16No.1.
[5].2007Vol.20No.5
课程设计任务书及成绩评定
课落款称:
号码查询系统
完成者:
王宇波龙佳魏钧宇
肖龙午肖旭
一、设计的目的与要求:
1)灵活应用所学数据结构知识,独立完成问题分析。
2)初步把握软件开发进程的问题分析、系统设计、程序编码、测试等方式。
3)训练用系统的观点和软件开发一样标准进行软件开发。
4)提高综合运用所学的理论知识和方式独立分析和解决问题的能力。
二、设计进度及完成情形
日期
内容
2009.
分析问题,找出所要解决问题的关键
2009.—2009.
总体设计,找出解决方案
2009.—2009.
详细设计,列出解决步骤
2009.—2009.
程序编码
2009.—2009.
程序调试,修改加以完善
2009.—2009.
书写文档
3、成绩评定:
设计成绩:
(教师填写)
指导教师:
(签