设计哈希表实现电话号码查询系统C语言版(课程设计报告)

一﹑目的

通过课程设计，巩固和加深对结构体、文件、哈希表等理论知识的理解；掌握现实复杂问题的分析建模和解决方法，掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人动手能力，历练自身素质。

哈希表实现 查询系统是利用哈希表实现 系统的快速查询，程序实现哈希表建表和查表，并实现对没有查找到的内容进行记录。掌握哈希表的工作原理，熟悉建立哈希表、对哈希表冲突处理、哈希表查找等功能的实现，回顾文件读取、写入，回顾随机函数的作用。

二﹑需求分析

1.输入的形式和输入值的范围

数据输入分两种模式：一种是将原有数据记录在old.txt文档中，由程序读入；另一种是由程序随机生成，并储存在new.txt文档中。数据的格式为：##、 、家庭住址。 用户使用时显示菜单，用户输入菜单选项完成操作。

2.输出的形式

查找的结果显示在屏幕上。未被查找到的内容输出到out.txt文档中。在用户需要时，将哈希表显示在屏幕上。

3.程序所能达到的功能

根据用户的选择，从原有文档读入数据或随机生成数据，分别以##和 做为关键字生成哈希表。生成哈希表后用户可以根据相应关键字进行数据的查找，若查找到对应的数据则将数据输出到屏幕，若没有查找到对应的数据则将用户输入的查找内容输出到out.txt文档。在用户选择显示哈希表时，显示完整的哈希表。

程序使用文字菜单的友好界面。在数据输入时对输入内容进行范围控制。

4.初步测试计划

在old.txt文档中输入30条记录，令程序读入并分别以##和 做为关键字生成哈希表，查找记录中原有的记录，查看输出数据，查找记录中没有的记录查看回馈，查看整个哈希表的数据。

令程序随机生成记录，查看new.txt文档，分别以##和 做为关键字生成哈希表，查看整个哈希表的数据，分别查找原有和没有的记录，查看回馈。

三﹑概要设计

1 / 32

1.数据类型

定义结构体类型存储每条记录。 struct Data {

char name[sizename]; char phone[sizephone]; char address[sizeaddress]; bool used;

}*hash_data;

2各种函数说明：

int get_hashkey(char* str,int select)// 获得关键字 void show(int i)// 显示每条信息

void Store(char *str)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中

void Allshow()//输出哈希表中的记录

void Auto_file()//随机生成数据，并将数据保存在new.txt void Build_Hash(int HashType)//建立哈希表 void FindName()//根据##查找哈希表中的记录 void FindPhone()//根据 查找哈希表中的记录

四﹑详细设计

1.头文件与定义结构体类型

#include #include #include #include struct Data {

2 / 32

string name;// string phone;

string address;

}; Data *hash_data;

2.定义长度

#define sizehash 100 #define sizename 20 #define sizephone

15

#define sizeaddress 40

3.获取关键字函数

int get_hashkey(char* str,int select) { int Key=0, ReKey,m; char tmp[10];

for (int i=0;i}

Key%=sizehash; if (hash_data[Key].used) { m=Key; Key=-1; if (select==1) { for (i=0;i<10;i++)

{ 3 / 32

}

ReKey=(m+A[i])%sizehash; if (!hash_data[ReKey].used) { }

Key=ReKey; break;

}else if (select==2) {

ReKey=m;

for (i=0;i<100;i++)

{ ReKey=ReKey+1;

ReKey=ReKey%sizehash;

}

}

}

if (!hash_data[ReKey].used) { }

Key=ReKey; break;

}

return Key;

4.产生hash表

4 / 32

void Build_Hash(int HashType){ for (int i=0;iprintf( \"%s读取失败\\n\

fclose(reader); exit(1);

}

char s[100]; char seps[]=\" ,\\";

char *name;char* phone;char* address;

int HashKey;

while (!feof(reader)) { fgets(s,100,reader); if (strlen(s)>0)

{

name=strtok(s,seps);

phone=strtok(NULL,seps); address=strtok(NULL,seps); if (HashType==1) { HashKey=get_hashkey(name,HashType);

{

HashKey=get_hashkey(phone,HashType);

if (HashKey==-1)

5 / 32

}

}else if (HashType==2)

}

}

}

{

printf( \"哈希表过小或哈希碰撞过多\"); fclose(reader); exit(1);

}else{ }

strcpy(hash_data[HashKey].name,name); strcpy(hash_data[HashKey].phone,phone); strcpy(hash_data[HashKey].address,address); hash_data[HashKey].used=true;

fclose(reader);

5.在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中

void Store(char *str)//将查找失败记录添加到out.txt文件末尾 { }

FILE* pf=fopen(\"out.txt\以追加的方式写入 if (pf==NULL)//判断文件是否打开成功 {

printf( \"创建out.txt失败\\n\");

fclose(pf); }

fscanf(pf,\"%s\fclose(pf);

exit(1);

6 / 32

6.输出哈希表中的记录

void Allshow() { }

for (int i=0;iprintf(\"\\n\\n\");

if (hash_data[i].used) { }

show(i);

7.随机生成数据，并将数据保存在new.txt

void Auto_file() {

FILE* fp=fopen(\"new.txt\

writer.open(\"new.txt\");

if(fp==NULL) {

printf( \"创ä¡ä建¡§new.txt失º¡ì败㨹!\\n\\n\");

char s[100]={0}; }

fclose(fp); exit(1);

7 / 32

int k=0;

srand(time(0)); for (int i=0;i<50;i++) {

memset(s,0,100); k=0;

//随?机¨²产¨²生¦¨²用®?户¡ì名?

for (int j=0;j<8;j++,k++) { }

s[k]='a'+rand()%26;

//随?机¨²产¨²生¦¨²电Ì?话¡ã号?码? s[k++]='\';

for (j=0;j<12;j++,k++) { }

s[k]='0'+rand()%10;

//随?机¨²产¨²生¦¨²地Ì?址¡¤ s[k++]='\';

for (j=0;j<20;j++,k++) { }

s[k]='a'+rand()%26;

8 / 32

}

}

fprintf(fp,\"%s\if(i!=49) fprintf(fp,\"\\n\");

fclose(fp);

8.根据##查找哈希表中的记录

int Find_by_name(string name) {

int i=0; int j=1; int key; char*p;

for(key=0,p=&name[0];*p;p++)

key=key+*p;

key=key%43; while(1) {

if(sign[key]=='0'&&key<=42) {key++;j++;}

if(hash_data[key].name==name)

else { }

key=Handle_Random(key,i); j++; return key;

9 / 32

}

}

if(j==num)

return -1;

9.根据用户名查找记录

void FindName(){ }

char name[10]=\"\";

printf( \"请输入要查找的用户名：\"); scanf(\"%s\int i=Find(name,1); if (i==-1) {

printf( \"无此记录\\n\"); Store(name);

}else{ }

printf(\"\\n\\n\");

printf( \"查找结果：\\n\"); show(i);

10.根据 查找记录

void FindPhone(){

char phone[12]=\"\";

10 / 32

printf( \"请输入要查找的 ：\"); scanf(\"%s\int i=Find(phone,2); if (i==-1) {

printf( \"无此记!\\n\"); Store(phone);

}else{ }

printf(\"\\n\\n\"); }

printf( \"查找结果：\\n\"); show(i);

12.整个程序的流程图如下

void Build-Hash()

void show(int i) void FindName() void Allshow() void FindPhone() main() Auto-file()

void Build-Hash()

11 / 32

五﹑调试分析

1.测试环境

在Windows 7环境下的Visual C++ 6.0。

2.模块调试

随机生成数据时，对随机生成的内容的控制需要特别注意。要注意其字符组合模式，比如生成名字是应该只有字幕，生成 是应该只有数字，在随机生成是用ASCII码的规律解决。还要注意生成字符组合的长度限制，比如 应该是11位，这可以在循环语句中进行控制。在哈希含查找时要注意取余的除数的一致，这是哈希表成立的关键点。

3.复杂度分析

使用哈希表存储记录，在执行查找是可以快捷的进行查找。程序选用了除留余数法建立哈希函数，选用在哈希法和为随机探测再散列法。程序设定的哈希标长为50，文件数据长度为30，则哈希表的填装因子α为0.6，则查找成功时的平均查找长度为Snr≈-In〔1-0.6〕

查找不成功时的平均查找长度为Unr≈

12 / 32

六﹑测试结果

1菜单：

运行软件后会出现主菜单，然后可以根据上面的提示，选择相应操作。

13 / 32

2 以##或者查询old.txt文件中的数据：

按照提示输入##查找：第一步输入文件中没有的##kjhyuio查找结果显示无此记录。

第二步输入hefangfang就立刻显示出正确信息。 第三步显示以##为关键字建立的哈希表。 第四步输入0退出程序。

14 / 32

第二步输入文件中没有的1332455查找结果显示输入不正确。 第三步显示以为关键字建立的哈希表。 第四步输入0退出程序。

15 / 32

3 以##或者查询new.txt文件中的数据：

按照提示输入##查找：第一步输入文件中没有的##dbfgdswe查找结果显示无此记录。 第二步输入wfnfozvs就立刻显示出正确信息。 第三步显示以##为关键字建立的哈希表。 第四步输入0退出程序。

16 / 32

第二步输入20973726016查找结果显示正确信息。 第三步显示以为关键字建立的哈希表。 第四步输入0退出程序。

七﹑用户使用说明

17 / 32

本程序运行在Windows 7系统下。

程序为命令提示行文件，执行文件前请在程序同目录下的old.txt文件中输入原始数据。程序生成的文档文件也将存放在程序同目录下。 打开程序后请根据提示选择功能。

输入“1〞程序将使用程序同目录下的old.txt文件中的数据； 输入“2〞 程序将随机生成数据； 输入“0〞则会结束程序。

输入“1〞表明用##做为关键字进行查找； 输入“2〞 表明用 做为关键字进行查找；

用##〔 〕查找时

输入“1〞用户将需要输入##〔 〕进行查找； 输入“2〞程序将显示完整的哈希表； 输入“0〞则会结束程序。

用户输入##查找后，若有这条记录，程序将显示该条记录。

若未找到这条记录，则显示“没有找到这条记录！〞，同时将输入记录在程序同目录下的out.txt文件中。

选择随机生成随据，数据同时将输出在程序同目录下的new.txt文件中。

八﹑课程设计总结

1 编程前遇到一些小问题：

由于C语言我们现在学的比较浅，所以编程都是自己通过网上学习或者请教同学，对于文件应用方面我了解甚少，但是经过自己自行学习文件知识后，了解了文件方面相应的知识。开始时程序出现了一些问题，经过修改和完善，终于解决了每个问题，使程序新建或打开文件非常好。通过努力也把文件应运得很好。

18 / 32

2 心得：

通过此次课程设，我巩固和加深了对哈希表、文件等理论知识的理解；掌握现实复杂问题的分析建模和解决方法；也提高了对报告书写的规范性。

本次设计哈希表实现 查询系统课程设计，实现了用户通过##或者 查找自己建好的old.txt文件和系统自动生成的new.txt文件中的信息。

九﹑附录

源代码

#include #include #include #include

#define sizehash 100 #define sizename 20 #define sizephone 15 #define sizeaddress 40

struct Data {

char name[sizename]; char phone[sizephone]; char address[sizeaddress]; bool used;//表示该条记录已使用 }*hash_data;

int A[10]={1,6,11,16,21,26,31,36,41,46};//伪随机数

19 / 32

char *DataFile; void Auto_file() {

FILE* fp=fopen(\"new.txt\ //writer.open(\"new.txt\"); if(fp==NULL) {

printf( \"创建new.txt失败!\\n\\n\"); }

char s[100]={0}; int k=0;

srand(time(0)); for (int i=0;i<50;i++) {

memset(s,0,100);

k=0; fclose(fp); exit(1);

for (int j=0;j<8;j++,k++) { }

s[k++]='\'; s[k]='a'+rand()%26;

for (j=0;j<12;j++,k++) { }

s[k]='0'+rand()%10;

20 / 32

}

s[k++]='\';

for (j=0;j<20;j++,k++) { }

fprintf(fp,\"%s\if(i!=49) fprintf(fp,\"\\n\");

s[k]='a'+rand()%26;

fclose(fp); }

int get_hashkey(char* str,int select) {

int Key=0, ReKey,m; char tmp[10];

for (int i=0;iKey%=sizehash;

if (hash_data[Key].used) Key+=str[i];

{

m=Key; Key=-1; if (select==1) {

for (i=0;i<10;i++)

21 / 32

{ }

ReKey=(m+A[i])%sizehash; if (!hash_data[ReKey].used) { }

Key=ReKey; break;

}else if (select==2) {

ReKey=m;

for (i=0;i<100;i++)

{ ReKey=ReKey+1;

ReKey=ReKey%sizehash;

}

}

}

if (!hash_data[ReKey].used) { }

Key=ReKey; break;

return Key; }

22 / 32

void Build_Hash(int HashType)//产生hash表 {

for (int i=0;ihash_data[i].used=false;

FILE* reader=fopen(DataFile,\"r\"); if (reader==NULL) {

printf( \"%s读取失败\\n\

fclose(reader); exit(1);

}

char s[100]; char seps[]=\" ,\\";

char *name;char* phone;char* address; int HashKey;

while (!feof(reader)) { fgets(s,100,reader); if (strlen(s)>0)

{

name=strtok(s,seps);

phone=strtok(NULL,seps); address=strtok(NULL,seps); if (HashType==1) {

HashKey=get_hashkey(name,HashType);

{

23 / 32

}else if

(HashType==2) ê?\"); }

HashKey=get_hashkey(phone,HashType); }

if (HashKey==-1) {

printf( \"哈t希¡ê表À¨ª过y小?或¨°哈t希¡ê碰?撞Á2过y多¨¤！

}

fclose(reader); exit(1);

}else{ }

strcpy(hash_data[HashKey].name,name); strcpy(hash_data[HashKey].phone,phone); strcpy(hash_data[HashKey].address,address); hash_data[HashKey].used=true;

fclose(reader); }

void show(int i) {

printf( \"%s\%s\%s\\n\hash_data[i].address); }

void Allshow() {

for (int i=0;i24 / 32

{ }

printf(\"\\n\\n\"); }

int Find(char *str,int select) { int Key=0; int ReKey;

char tmp[10];int m;

for (int i=0;iKey%=sizehash;

if (!hash_data[Key].used) { }

if ((select==1 && strcmp(hash_data[Key].name,str)!=0)|| (select==2 && strcmp(hash_data[Key].phone,str)!=0 )) {

m=Key; Key=-1; return -1; Key+=str[i];

if (hash_data[i].used) { }

show(i);

25 / 32

if (select==1) {

for (i=0;i<10;i++) { }

ReKey=(m+A[i])%sizehash;

//if (pInfo[ReHashKey].name==str) if (strcmp(hash_data[ReKey].name,str)==0) { }

Key=ReKey; break;

}else if (select==2) {

ReKey=m;

for (i=0;i<100;i++)

{ ReKey=ReKey+1;

ReKey=ReKey%sizehash;

}

if (strcmp(hash_data[ReKey].phone,str)==0) { }

Key=ReKey; break;

26 / 32

}

return Key; }

void Store(char *str)//将查找失败记录添加到out.txt文件末尾 {

FILE* pf=fopen(\"out.txt\以追加的方式写入 if (pf==NULL)//判断文件是否打开成功 {

printf( \"创建out.txt失败\\n\"); }

fclose(pf); }

fscanf(pf,\"%s\ fclose(pf); }

void FindName()//根据用户名查找记录 {

char name[10]=\"\";

printf( \"请输入要查找的用户名：\"); scanf(\"%s\ int i=Find(name,1); if (i==-1) {

exit(1);

27 / 32

printf( \"无此记录\\n\"); Store(name);

}else{ }

printf(\"\\n\\n\"); }

void FindPhone()//根据 查找记录 {

char phone[12]=\"\";

printf( \"请输入要查找的 ：\"); scanf(\"%s\ int i=Find(phone,2); if (i==-1) {

printf( \"无此记!\\n\"); Store(phone);

printf( \"查找结果：\\n\"); show(i);

}else{ }

printf(\"\\n\\n\"); }

int main(int argc, char* argv[]) {

printf( \"查找结果：\\n\"); show(i);

28 / 32

hash_data=(Data*)malloc( sizeof(Data)*sizehash ); int choice=0; do{

int choice=0;

printf( \" *************************************\\n\");

printf( \" * *\\n\");

printf( \" * 1.*\\n\");

printf( \" * 2.*\\n\");

printf( \" * 0.*\\n\");

printf( \" *************************************\\n\"); printf( \"请输入您的选择：\\n\");

scanf(\"%d\ if (choice==1) {

DataFile=\"old.txt\";

}else if(choice==2) { Auto_file(); DataFile=\"new.txt\";

} else

{

29 / 32

请选择要查询的数据来源：原始数据old.txt 随机产生new.txt 退出程序

}

exit(1);

}

system(\"cls\");

while((choice!=1)&&(choice!=2)&&(choice!=0)); printf(\"你选择的查找文件是：\");

printf(\"%s\\n\

printf(\"****************************************************\\n\");

printf(\"* 请 选 择 查 找 方 式 *\\n\"); printf(\"* 1.根 据 姓 名 查 *\\n\"); printf(\"* 2.根 据 号 查 找 *\\n\");

printf(\"****************************************************\\n\");

printf(\"%s\\n\ do {

int choose;

printf( \"请输入您的选择：\\n\"); scanf(\"%d\ if(choice!=1&&choice!=2)

{ }

printf(\" 输入序号有误¨重新输入!!!\\n\");

}while((choice!=1)&&(choice!=2)); while(choice==1) {

Build_Hash(1);//by name

30 / 32

printf(\"****************************************************\\n\"); printf(\"* 请 选 择 功| 能 *\\n\"); printf(\"* 1 . 输 入 姓 名 查 找 数 据 *\\n\"); printf(\"* 2 . 显 示 哈 希 表 *\\n\");

printf(\"* 0 . 退 出 程 序 !!! *\\n\"); printf(\"****************************************************\\n\");

} }

while(choice==2) {

Build_Hash(2);//by phone

case 2:

Allshow(); break; case 0: exit(1);

int ch;

printf( \"请输入您的选择：\\n\"); scanf(\"%d\ switch(ch) { case 1:

FindName(); break;

printf(\"****************************************************\\n\"); printf(\"* 请选择 功 能 *\\n\");

printf(\"* 1 . 输 入 电 话 查 找 数 据 *\\n\");

31 / 32

printf(\"* 2 . 显 示 哈 希 表 *\\n\"); printf(\"* 0 . 退出程序!! *\\n\"); printf(\"****************************************************\\n\"); int ch;

printf( \"请输入您的选择：\\n\"); scanf(\"%d\ switch(ch) { case 1: FindPhone();

break;

case 2: Allshow();

break;

case 0:

exit(1);

} }

}

32 / 32