数据结构课程设计计信系教师通信录查询系统

《数据结构》课程设计报告

目录

1.需求分析..................................................................................................................... 1

1.1问题描述.......................................................................................................... 1 1.2需求分析.......................................................................................................... 1 2.概要设计..................................................................................................................... 2

2.1设计的内容...................................................................................................... 2 2.2设计的数据结构选择..................................................................................... 2

2.2.1.开放定址法........................................................................................... 4 2.2.2.链地址法............................................................................................... 5

3.详细设计..................................................................................................................... 6

3.1.涉及的知识点.................................................................................................. 6 3.2.详细的设计思路.............................................................................................. 6

3.2.1算法的基本思路描述........................................................................... 6 3.2.2 算法的设计.......................................................................................... 6 3.2.3程序的总流程图................................................................................... 7

4.编码............................................................................................................................. 9

4.1常量的定义...................................................................................................... 9 4.2数据结构定义.................................................................................................. 9 5.各个模块功能上机测试........................................................................................... 12

5.1口令测试（进入系统的条件）.................................................................... 20 5.2录入计信系各教师的信息............................................................................ 21 5.3显示系统中教师的信息................................................................................ 21 5.4查找教师的信息（以姓名）........................................................................ 22 5.5查找教师的信息（以电话号码）................................................................ 23 5.6删除教师的信息............................................................................................ 23 5.7修改教师的信息............................................................................................ 24 6.小结........................................................................................................................... 24 参考文献...................................................................................................................... 25

《数据结构》课程设计报告

1.需求分析

1.1问题描述

本程序要完成一个实现计算机与信息工程系教师通信录查询系统，能够完成教师信息的录入、查找、删除、增添功能。要求采用散列表实现计信系教师查询系统，并考虑解决散列冲突的方法。

通过对任务的分配，实现本程序需要解决以下几个问题： ?设每个记录有下列数据项：电话号码、用户名、地址；

? 从键盘输入各记录，分别以电话号码、姓名为关键字建立散列表； ? 采用二次探测再散列法解决冲突； ?查找并显示给定电话号码的记录； ?查找并显示给定姓名的记录；

?对教师信息进行相关添、删、修等操作； ?通信录信息文件保存；

?要求人机界面友好，使用图形化界面；

1.2需求分析

（1）程序所需要达到的功能：是通过创建哈希表，实现通信录的创建，并通过哈希表的插入和查找使通信录可以进行姓名、电话、地址的添加和相应的查找。 （2）输入的形式和输入值的范围：姓名地址均使用汉语拼音全拼形式，电话使用数字，记录的添加不会超过系教师的总人数。

（3）输出的形式：若输出整个哈希表内容，则按照哈希表的每一项所对应输入内容后，将整个记录表直接输出；若单个查找，则只会出现查找时对应的记录内容。

（4）测试数据：输入的记录个数应该小于设定的教师的记录数量（<20），输入的记录姓名的汉语拼音的长度也应小于设定的姓名的最大长度(<20)，只要在规定的输入范围内输入都能得到想要的结果。

1

《数据结构》课程设计报告

2.概要设计

2.1设计的内容

Menu()的功能： 显示提示选单。 Key()的功能： 口令测试。 Create()的功能： 创建新的通讯录。

Search()的功能： 查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通 讯录中没有此人的信息，并返回选单。

Alter()的功能： 修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。

Delete()的功能： 删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。

List()的功能： 显示通讯录中的所有记录。

Save()的功能： 保存通讯录中的所有记录到指定文件中。

2.2设计的数据结构选择

存储教师的记录时，若在存储位置和其关键字之间建立某种确定的对应关系?,使得每个关键字和存储结构中一个唯一的存储位置相对应，那么在进行查找时，根据这个对应关系?就可以找到给定值K的像?(K）。若存储结构中存在关键字和K相?等的记录，则必定在f（K）的存储位置上，由此不需要进行比较便可直接找到所查记录。这个对应关系?称为哈希（Hash）函数或散列函数。按照以上思路建立的表称为哈希表或散列表。该程序设计主要考察散列表的建立、查找、删除和修改 ，系统的功能模块图如图1所示。

散列表一旦建立，进行查找时就可以用给定的关键字和建立散列表时所采用的哈希函数直接在给定的表中进行查找。然而，由于集合中各记录关键字的聚会可能在一个很大的范围内，所以，即使当集合中记录的个数不是很多时，也很难选取一个合适的哈希函数H能够保证对于任意不同的ki和kj。有H(Ki)?H(Kj)。

2

《数据结构》课程设计报告

当Ki?Kj，而H(Ki)?H(Kj)的现象称为冲突现象。当发生冲突时，必须采用适当的方法来解决冲突。

因此，构造哈希函数和建立解决冲突的方法是建立哈希表的两大任务。 选取一个合适的不大于哈希表长的正整数P，用P去除关键字K，所得的余数作为其哈希地址，即H（K）＝K mod P，这种方法称为除余法哈希函数。除余法是一种简单且行之有效的构造哈希函数的方法。实践证明，当P取小于哈希表长的最大质数时，产生哈希函数较好。所以本程序设计采用的是除余法哈希函数。

系统功能添加教师记录显示教师记录查找教师记录删除教师记录修改教师记录根据姓名查找根据电话号码以姓名创建哈希函数以电话号码创建哈希函数

图 1系统功能图

解决冲突的方法有两大类，即开放定址法和链地址法。

3

《数据结构》课程设计报告

2.2.1.开放定址法

开放定址法又分为线性探查法、二次探查法和双重散列法。开放定址法解决冲突的基本思想是：使用某种方法在散列表中形成一 个探查序列，沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点存入其中。假设散列表空间为T[0....m-1]，散列函数为H（key），开放定址法的一般形式为：其中为增量序列，m为散列表长。h0?H(key)hi?(H(key)?di)%m(0?i?m?1)，

为初始探查地址（假设d0＝0），后续的探查地址依次是h1,h2,...，hm?1。 （1）线性探查法

线性探查法的基本思想是：将散列表T[0...m-1]看成一个循环向量，若初始探查的地址为d（即H(key）=d），那么，后续探查地址的序列为：d+1,d+2,....,m-1,0,1,....,d-1。也就是说，探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1],....,T[m-1],此后又循环到T[0],T[1],...,T[d-1]。若当前探查单元为空，则将关键字key写入空单元；若不为空则继续后序地址探查，直到遇到空单元插入关键字，若探查到T[d-1]时仍未发现空单元，则插入失败（表满） （2）二次探查法

二次探查法的探查序列为：hi?(H(key)?i2)%m,0?i?m?1，也就是说，探查从地址d开始，先探查T[d],然后再依次探查T[d?12],T[d?22],....。 （3）双重散列法

双重散列法的探查序列为：hi?(H(key)?i*H1(key))%m(0?i?m?1),即探查序列为：d?H(key),(d?1*H1(key))%m,(d?2*H1(key))%m,....。

4

《数据结构》课程设计报告

2.2.2.链地址法

当存储结构是链表时，多采用链地址法。用链地址法处理冲突的办法是：把具有相同散列地址的关键字（同义词）值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0...m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到T[i]为指针的单链表中。T中各分量的初值应为空指针。链地址法解决冲突后创建的散列表如图2所示。

用链地址法处理冲突，虽然比开放地址法多占用一些存储空间用做链接指针，但它可以减少在插入和查找过程中同关键字的平均比较次数（平均查找长度）。这是因为，在链地址法中待比较的节点都是同义词节点，而且包含有非同义词结点，往往非同义词结点比同义词结点还要多。

图 2散列表

本程序采用二次探查再散列法解决冲突。

5

《数据结构》课程设计报告

3.详细设计

3.1.涉及的知识点

散列表的建立 散列表的查找 冲突的解决

3.2.详细的设计思路

3.2.1算法的基本思路描述

输入教师信息时会产生冲突，于是我们构建了二次探测函数来解决冲突，再者应把人名进行折叠处理，然后除留取余数法取得哈希模值，才能用于二次探索。建立好哈希表后，就要以人名和电话号码形式查找信息，就要构造两个函数，最后构建一个主函数起调用作用，将各个函数相互组合串联在一起，形成了具有某种功能的一个小系统。 3.2.2 算法的设计 数据结构的设计和说明:

在设计中运用到了两个结构体，Record结构体中主要包含三项，一个是姓名，电话号码和地址，另一个结构体中有数据元素存储地址，当前数据元素的个数和当前容量。在主函数中首先输出菜单界面，显示菜单界面供使用者选择要操作的序号。当操作者选择出序号后在，switch调用相应的函数。使用者只要根据提示进行操作即可。

1-添加教师信息2-读取所有教师信息 3-以姓名建立哈希表 4-以电话号码建立哈希表 5-查找并显示给定教师的记录 6-查找并显示给定电话号码的记录 7-删除教师的信息8-修改教师的信息9-清屏10-退出程序。

6

《数据结构》课程设计报告

3.2.3程序的总流程图

程序开始输入口令显示菜单输入操作码i录入指定输入个数的建立教师通信录i=1i=2显示教师的信息i=3以姓名为关键字来创建哈希函数i=4以电话号码为关键字来创建哈希函数i=5以姓名为关键字来查找教师信息i=6以电话号码为关键字来查找教师信息i=7删除教师的信息i=8修改教师的信息i=9清屏i=10退出程序结束图 3程序总流程图

7

《数据结构》课程设计报告

A：基本信息：

定义节点类型----typedef struct Record

定义哈希表节点类型----typedef struct HashTable 关键字比较----void eq()

人名的折叠处理，将名字转换成一个数值----void fold() 建立哈希函数----void Hash()

建立解决冲突的方法----void collision() B:显示菜单：

按照指定的长度建立通信录 显示通信录内所有教师信息 添、删、修教师信息

查找并显示给定教师姓名的记录 查找并显示给定电话号码的记录 显示信息并退出程序 C：根据选项实际操作

主函数void main()分别调用下面函数并对应输出 录入内存内容----void gein() 显示教师信息----void list() 创建哈希表----void createdHash1()

查找哈希表中的关键字----void Search_name()/Search_phonenumber() 删除教师的记录----void Delete() 修改教师的记录----void Alter()

8

《数据结构》课程设计报告

4.编码

4.1常量的定义

1.MAXSIZE 20：通讯录的大小

2.MAX_SIZE 20 ：通讯录中姓名、电话、地址的最大长度 HASHSIZE 53 ：创建哈希表的容量 SUCCESS 1 ：成功标志位 FAILURE -1 ：失败标志位

LEN sizeof(HashTable)：哈希表的长度

4.2数据结构定义

所用数据结构参考定义如下： （1）定义通信录节点结构体 typedef struct{ //每个教师记录

NA name; NA tel; NA add; }Record;

（2）定义哈希表节点结构体

typedef struct{ //哈希表

Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable;

9

《数据结构》课程设计报告

（3）关键字的比较

Status eq(NA x,NA y){//关键字比较，相等返回SUCCESS；否则返回FAILURE

if(strcmp(x,y)==0)

return SUCCESS; else return FAILURE;

}Status NUM_BER; //记录的个数

(4)对姓名的折叠处理

long fold(NA s){//人名的折叠处理

char *p; long sum=0; NA ss;

strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\\0') sum+=*p++;

printf(\//将字符串转换成一个int 型的值用于hash表的计算比较

return sum; }

（5）建立哈希函数（两个） int Hash1(NA str){ //哈希函数

long n; int m;

n=fold(str); //先将用户名进行折叠处理

m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数 return m; }

10

//并返回模值

《数据结构》课程设计报告

int Hash2(NA str){ //哈希函数

long n; int m;

n = atoi(str); //把字符串转换成整型数. m=n%HASHSIZE; return m; }

（6）解决冲突

Status collision(int p,int &c){ //冲突处理函数，采用二次探测再散列法解决冲突

int i,q; i=c/2+1; while(i

if(c%2==0){

c++;

q=(p+i*i)%HASHSIZE;

return q; //并返回模值

if(q>=0) else } else{

i=c/2+1;

q=(p-i*i)%HASHSIZE; c++; if(q>=0) Else } }

return FAILURE; }

11

return q;

i=c/2+1;

《数据结构》课程设计报告

（7）创建以姓名为关键字哈希表

void CreateHash1(HashTable* H,Record* a){ //建表，以人的姓名为关键字，建立相应的散列表

//若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp;

for(i=0;i

p=Hash1(a[i].name); pp=p;

while(H->elem[pp]!=NULL) { pp=collision(p,c); if(pp<0){

printf(\第%d记录无法解决冲突\需要显示冲突次数时输出 continue;

}//无法解决冲突，跳入下一循环 }

H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入 H->count++;

printf(\第%d个记录冲突次数为%d。\\n\需要显示冲突次数时输出 }

printf(\以教师姓名建散列表完成!\\n此哈希表容量为%d,当前表内存储的记录个数为%d.\\n\

benGetTime(); }

12

《数据结构》课程设计报告

(8)查找以姓名为关键字的哈希表（前提条件是步骤7要先创建好哈希函数） void Search_name(HashTable* H,int &c){//在通讯录里查找姓名关键字，若查找成功，显示信息

//c用来记录冲突次数,查找成功时显示冲突次数

benGetTime(); NA str;

printf(\请输入要查找记录的姓名：\\n\scanf(\int p,pp; p=Hash1(str); pp=p;

while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1)) pp=collision(p,c);

if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){

printf(\查找成功！\\n查找过程冲突次数为%d．以下是您需要要查找的信息：\\n\\n\printf(\

姓

名

:

%s\\n

电

话

号

码

：

%s\\n

联

系

地

址：%s\\n\}

else printf(\此人不存在，查找不成功!\\n\

benGetTime(); }

（9）创建以电话号码为关键字的哈希表

void CreateHash2(HashTable* H,Record* a){//建表，以电话号码为关键字，建立相应的散列表

//若哈希地址冲突，进行冲突处理

benGetTime(); int i,p=-1,c,pp; for(i=0;i

13

《数据结构》课程设计报告

p=Hash2(a[i].tel); pp=p;

while(H->elem[pp]!=NULL) { pp=collision(p,c); if(pp<0){

printf(\第%d记录无法解决冲突\需要显示冲突次数时输出 continue;

}//无法解决冲突，跳入下一循环 }

H->elem[pp]=&(a[i]);//求得哈希地址，将信息存入 H->count++;

printf(\第%d个记录冲突次数为%d。\\n\需要显示冲突次数时输出 }

printf(\以教师电话号码建散列表完成!\\n此哈希表容量为%d,当前表内存储的记录个数为%d.\\n\

benGetTime(); }

（10）查找以电话号码为关键字的哈希表（前提为步骤9要先创建好哈希函数） void Search_phonenumber(HashTable* H,int &c){//在通讯录里查找电话号码关键字，若查找成功，显示信息

//c用来记录冲突次数,查找成功时显示冲突次数

benGetTime(); NA tele;

printf(\请输入要查找记录的电话号码：\\n\scanf(\int p,pp; p=Hash2(tele); pp=p;

while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1)) pp=collision(p,c);

14

《数据结构》课程设计报告

if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1){

printf(\查找成功！\\n查找过程冲突次数为%d．以下是您需要要查找的信息：\\n\\n\ printf(\

姓

名

：

%s\\n

电

话

号

码

：

%s\\n

联

系

地

址：%s\\n\}

else printf(\此人不存在，查找不成功!\\n\

benGetTime(); }

（11）录入教师的记录（初始化） void getin(Record* a){//键盘输入各人的信息

printf(\输入要添加的个数：\\n\scanf(\int i;

for(i=0;i

printf(\请输入第%d个记录的用户名:\\n\ scanf(\

printf(\请输入%d个记录的电话号码:\\n\ scanf(\

printf(\请输入第%d个记录的地址:\\n\ scanf(\} }

15

《数据结构》课程设计报告

（12）显示输入的教师记录

void list(Record* a) //显示输入的用户信息 {

int i;

for( i=0;i

printf(\第%d个用户信息:\\n 姓名：%s\\n 电话号码：%s\\n 联系地址：%s\\n\ }

（13）删除指定电话号码的教师记录 void Delete(HashTable* H,int &c) { benGetTime(); NA tele;

printf(\请输入要删除记录的电话号码：\\n\ m++; scanf(\ int p,pp; p=Hash2(tele); pp=p;

while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1))

pp=collision(p,c);

if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1) { printf(\以下是您需要要删除的信息：\\n\\n\ printf(\姓名\\t电话号\\t\\t地址\\n\

printf(\ printf(\ printf(\ printf(\

(H->elem)[pp]->tel[0]='\\0'; printf(\删除成功!!!\

} else printf(\此人不存在，删除不成功!\\n\ benGetTime();

16

《数据结构》课程设计报告

}

（14）修改指定电话号码的教师记录

void Alter(HashTable* H,int &c) //在通讯录里修改某个老师信息 {

benGetTime(); NA tele;

printf(\请输入要修改记录的电话号码：\\n\ scanf(\ int p,pp; p=Hash2(tele);

pp=p;

while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1))

pp=collision(p,c);

if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1) {

printf(\以下是您需要修改的信息：\ printf(\

printf(\姓名\\t电话号\\t\\t地址\\n\

printf(\ printf(\ printf(\ (H->elem)[pp]->tel[0]='\\0';

printf(\请输入修改后记录的用户名:\\n\ scanf(\ printf(\请输入修改后记录的电话号码:\\n\ scanf(\ printf(\请输入修改后记录的地址:\\n\ scanf(\ printf(\修改成功!!!\ } else {

benGetTime();

17

《数据结构》课程设计报告

printf(\此人不存在，修改不成功!\\n\ } }

（15）主函数

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

int c,flag=1; HashTable *H;

H=(HashTable*)malloc(LEN); for(int i=0;ielem[i]=NULL; H->size=HASHSIZE; H->count=0;

Record a[MAXSIZE]; key(); while (1){

printf(\ printf(\┏〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┓*\ printf(\┃★ 欢迎进入计算机与信息工程系教师通讯查询系统★ ┃*\ printf(\┃【1】. 录入教师信息 ┃*\ printf(\┃ 【2】. 输出所有教师信息 ┃*\ printf(\┃ 【3】. 以姓名建立哈希表 ┃*\ printf(\┃ 【4】. 以电话号码建立哈希表 ┃*\ printf(\┃ 【5】. 查找并显示给定姓名的教师记录 ┃*\ printf(\┃ 【6】. 查找并显示给定电话号码的教师记录 ┃*\ printf(\┃ 【7】. 删除教师的记录 ┃*\ printf(\┃ 【8】. 修改教师的记录 ┃*\ printf(\┃ 【9】. 清屏 ┃*\ printf(\┃ 【0】. 保存 ┃*\ printf(\┃ 【10】. 退出程序 ┃*\

18

《数据结构》课程设计报告

printf(\温馨提示： ┃*\ printf(\Ⅰ.进行5操作前请先输出3 ┃*\ printf(\┃Ⅱ.进行6操作前请先输出4 ┃*\ printf(\┗〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┛*\ printf(\ printf(\

printf(\请输入你的操作>>>\ printf(\ int num;

scanf(\ switch(num){ case 1: getin(a);break; case 2:list(a);break;

case 3:CreateHash1(H,a);break;/* 以姓名建立哈希表 */ case 4:CreateHash2(H,a); break;/* 以电话号码建立哈希表 */ case 5:c=0;Search_name(H,c); break;

case 6:c=0;Search_phonenumber(H,c); break; case 7:c=0;Delete(H,c);break; case 8:c=0;Alter(H,c);break; case 9:Cls(a);break; case 0:Save();break; case 10: return 0;break;

default:printf(\你输错了，请重新输入!\ printf(\ } }

system(\return 0; }

19

《数据结构》课程设计报告

5.各个模块功能上机测试

5.1口令测试（进入系统的条件）

图 4通过输入口令进行测试进入系统

20

《数据结构》课程设计报告

5.2录入计信系各教师的信息

图 5首先输入要录入的个数，然后依次输入相应的用户名、电话号码和地址

5.3显示系统中教师的信息

图 6显示教师信息

21

《数据结构》课程设计报告

5.4查找教师的信息（以姓名）

图 7执行操作5之前要先操作3，因为要先创建哈希函数才能使用哈希表来进行查找功能。

22

《数据结构》课程设计报告

5.5查找教师的信息（以电话号码）

图 8查找教师信息

5.6删除教师的信息

图 9删除教师的信息，是以电话号码为线索

23

《数据结构》课程设计报告

5.7修改教师的信息

图 10修改教师的信息，是以电话号码为线索的

6.小结

通过这次课设，我学会了如何把数据结构的知识应用到实践当中，同时也进一步加深了对c/c++语言语法的应用，以及深刻的掌握了数据结构和c/c++语言的结合运用。在编程过程中，遇到了许多问题，在一次次的运行错误后，问题被一步步改正，也从中学到了许多知识。虽然我的程序还不够完善，还需加以改进以实现更多的功能，但是我会尽我最大的努力去完成它，我相信我会努力去把程序做的更加完美。

24

《数据结构》课程设计报告

参考文献

［1］王昆仑,李红等编著. 数据结构与算法. 北京:中国铁道出版社,2007. ［2］苏仕华等编著. 数据结构课程设计. 北京：机械工业出版社 ,2005. ［3］苏仕华编著. 数据结构与算法解析. 合肥:中国科学技术大学出版社,2004. ［4］郭嵩山等著. 国际大学生程序设计竞赛例题解. 北京:电子工业出版社,2008. ［5］刘大有,唐海鹰等编著. 数据结构. 北京:高等教育出版社,2001. ［6］徐孝凯编著.数据结构实用教程. 北京: 清华大学出版社,1999.

［7］严蔚敏,陈文博编著. 数据结构及算法教程. 北京: 清华大学出版社,2001.

25

本文来源：https://www.bwwdw.com/article/54b6.html