电话号码系统查询

电话号码系统查询 湖南人文科技学院计算机科学技术系 课程说明书 课 程 名 称: 数据结构 课 程 代 码: 408024 目: 电话号码查询系统 年级/专业/班: 学 生 姓 名: 学 号: 指 导 教 师: 开 题 时 间: 2009 年 12 月 21 日 完 成 时 间: 2010 年 1 月 1 日 目 录 摘 要 ....................................................... 1 一、引 言 ................................................... 2 二、设计目的与任务 ........................................... 2 1、课程设计的目的 ......................................... 2 2、课程设计的任务 ......................................... 3 三、设计方案 ................................................. 3 1、需求分析 ............................................... 3 2、概要设计 ............................................... 3 3、详细设计 ............................................... 4 4、程序清单 ............................................... 7 四、调试分析与体会 .......................................... 10 五、运行结果 ................................................ 10 六、结 论 .................................................. 12 七、致 谢 .................................................. 12 八、参考文献 ................................................ 12 摘 要 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是 常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下， 用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。哈希表又叫做散 列表，分为"开散列" 和"闭散列"。 本次课程设计是为用户解决关于电话号码的存储，查询，以及添加删除。用户可以通 过键盘输入用户信息进行存储，然后在通过哈希表提供的2种查询方式进行用户信息查 询。 关键词:哈希表;散列函数;冲突处理 Abstract Hash table of the biggest advantages is that the data storage and search time significantly reduced consumption, almost can be regarded as constant time; while the price is just consuming more and more memory. However, in the current available memory, an increasing number of cases, the practice of using space for time is worth it. In addition, the code is also relatively easy to one of its characteristics. Hash table is also called a hash table is divided into “open hash” and “closed hashing”. This course is designed to solve on the phone numbers for users to store, query, and add remove. Users can enter user information via the keyboard is stored, and then through the hash table provided by the two kinds of ways to search for user information query. Keywords: hash table; hash function; Conflict Management. 1 《数据结构》课程设计 ----电话号码查询系统 一、引 言 随着我国进一步的开放，我们需要扩大国际交流，加强学习国外的先进经验。掌握国际的领先技术是我们的首要任务。计算机技术发展异常迅速，内容更新很快，我们对计算机的了解程度也直接影响了我国的现代化和信息化的程度。《数据结构》是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且是其他理工专业的热门选修课。数据结构研究的是世界上所有非数值量的信息结构及其处理方法，它不仅是计算机科学与技术相关专业十分重要的核心课程，也是应用数学、管理科学、环境规划等很多专业的一门重要基础课。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，对于所有想更好地运用计算机来解决实际问题得人们而言，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好《数据结构》这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。 本课程设计要求实现电话号码的查询。一般的查找方法有各式各样的缺点，但是哈希表不同，哈希表是一种通过牺牲空间来提高效率的方法，理论上，有足够的空间的话，哈希表和他的函数几乎能不经过任何比较一次性就能得到结果。为了实现查询功能，用到了关于哈希表的存储结构和链表结构，并且通过链地址法解决哈希表冲突。 课程设计要求用哈希表实现功能，首先要解决哈希表的存储冲突问题，对不同的关键字可能得到同一个哈希地址,这种现象称为冲突。在以住,我们都认为冲突只能尽可能地少,而不能完全地避免。对于这个问题，经过一番对比和思考，决定采用链地址法解决冲突。建立一个链表，将冲突的关键字都存入同一个链表，同时将每个链表的头指针存入另一个链表。 二、设计目的与任务 1、课程设计的目的 通过课程设计，使我们巩固所学知识、培养我们动手能力。我们用数据结构设计一个 2 完整的应用程序，综合应用所学知识完成软件的分析、设计、调试和总结，提高我们对数据结构综合应用能力和解决问题的能力。灵活应用所学数据结构知识，独立完成问题分析。 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等方法。训练用系统的观点和软件开发一般规范进行软件开发。提高综合运用所学的理论知识和方法独立分析和解决问题的能力。同时增加了我们之间的团队合作精神～更加也体会到以后在工作中团队合作的重要性和必要性～ 2、课程设计的任务 问题描述: 使用哈希表实现电话号码的查找功能，要求输入电话号码或者用户姓名可以查找出用户信息。并且能加入新的用户。设计散列表实现电话查询系统。 三、设计方案 1、需求分析 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表; 3) 采用一定的方法解决冲突; 4) 查找并显示给定的电话号码的记录; 5) 查找并显示给定用户名的记录; 2、概要设计 1) 哈希表数据类型(ADT)如下: ADT node { 数据对象:name,address,num; 数据关系:name为用户姓名,address为用户地址,num为用户电话号码; 基本操作: (1) void hash(char A[]) 程序功能:关于key的哈希函数，函数值为key的值 (2) node* input() 程序功能:输入一个节点的值 (3) int apend() 程序功能:将节点添加到哈希表 (4) void create() 3 程序功能:新建一个哈希表 (5) void find(char A[]) 程序功能:通过线索查找用户 } 2) 存储结构 struct node { char name[8],address[20]; //姓名，地址存储字符组 char num[11]; //电话号码存储字符组 node * next; //后继元素地址 }; 3) 流程图 开始 输入b b是1 ,2 1，输入数据2，输入数据 入key 入key2 从号码列表查询 从姓名列表查询 输出搜索结果 结 束 3、详细设计 在本次课程设计中，我们用到了哈希表这个重要的数据结构，在实现程序功能的时候， 很多地方都涉及哈希表，另外我们用到了链表，在程序中用到了许多链表的操作，比如建 4 立，添加，删除等操作。在对程序进行整体设计时，我们选用了哈希表表这种数据结构来 存贮数据，哈希表查找迅速，理论上空间足够大的话，可以不需比较直接找到目标所以比 较适合本程序的要求。重要程序段如下: 1) 以电话号码和姓名为关键字的哈希函数 void hash(char num[11]) { int i = 3; key=(int)num[2]; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } 接受传来的电话号码和姓名，首先判断电话号码和姓名是否为空。不为空则将号码和 姓名的每位转化为整型进行累加，然后用用除留取余法获得关键码。 2) 输入函数 node* input() { node *temp; temp=(struct node *)malloc(sizeof(struct node)); temp = new node; temp->next=NULL; cout<<"输入姓名:"<>temp->name; cout<<"输入地址:"<>temp->address; cout<<"输入电话:"<>temp->num; return temp; } 建立一个新结点，将结点的下个结点置空。输入姓名，地址，电话后返回结点 。 3) 添加新结点 int apend() { node *newphone; node *newname; newphone=input(); newname=newphone; 5 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; return 0; } 建立一个新的电话结点和姓名结点，调用输入函数。将电话结点的地址赋给姓名结点， 使它们拥有同样的值，分别调用以电话号码和以姓名为关键字的哈希函数。然后将结点插 入到表中。 4) 初始化电话号码表 void create() { int i; phone=new pnode[20]; for(i=0;i<20;i++) { phone[i]=new node; phone[i]->next=NULL; } } 为电话号码表申请20个元素，为表中每个元素申请空间，将其数据元素置空。 5) 查找函数 void find(char num[11]) { int i=0; hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) { cout<name<<"_" <address<<"_"<num<next; } if(!i) cout<<"无此记录"<next; while(p) { fstream iiout("out.txt", ios::out); iiout<name<<"_"<address<<"_"<num<next; } } } 保存用户信息,将信息保存到out.txt这个文档下。 4、程序清单 #include #include "string.h" #include "fstream" #define NULL 0 unsigned int key; unsigned int key2; int *p; struct node //建节点 { char name[8],address[20]; char num[11]; node * next; }; typedef node* pnode; typedef node* mingzi; node **phone; node **nam; node *a; using namespace std; //使用名称空间 void hash(char num[11]) //哈希函数 { int i = 1; key=(int)num[2]; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } 7 void hash2(char name[8]) //哈希函数 { int i = 1; key2=(int)name[0]; while(name[i]!=NULL) { key2+=(int)name[i]; i++; } key2=key2%20; } node* input() //输入节点 { node *temp; temp = new node; temp->next=NULL; cout<<"输入姓名:"<>temp->name; cout<<"输入地址:"<>temp->address; cout<<"输入电话:"<>temp->num; return temp; } int apend() //添加节点 { 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; return 0; } void create() //新建节点 { int i; phone=new pnode[20]; for(i=0;i<20;i++) { phone[i]=new node; phone[i]->next=NULL; } } void create2() //新建节点 { int i; nam=new mingzi[20]; for(i=0;i<20;i++) { nam[i]=new node; nam[i]->next=NULL; } } void find(char num[11]) //查找用户信息 { int i=0; hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) { cout<name<<"_" <address<<"_"<num<next; } if(!i) cout<<"无此记录"<next; while(q!= NULL) { if(strcmp(name,q->name)==0) 8 { cout<name<<"_" <address<<"_"<num<next; } if(!i) cout<<"无此记录"<next; while(p) { fstream iiout("out.txt", ios::out); iiout<name<<"_"<address<<"_"<num<next; } } } void menu() { char num[11]; char name[8]; int sel; cout<<" ---------------------------------------------------"<>sel; switch(sel) { case 1: { cout<<"请输入要添加的内容:"<>b; if(b==1) { cout<<"请输入电话号码:"<>num; cout<<"输出查找的信息:"<>name; 9 cout<<"输出查找的信息:"<