数据结构课程设计通讯录、电话号码查询系统

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

电

通

话

讯

号

录

码

查

询

系

统

学院保）：

班级：

学生姓名：学号.

指导教师：_______________

2012年12月17日到2013年1月2日

一、课程设计概述：

本次数据结构课程设计共完成两个题：电话号码查询系统、通讯录。

使用语言：C

编译环境：VC6.0

二、课程设计题目一

［实验内容］

电话号码查询系统

［问题描述］

设计散列表实现电话号码查找系统。

［需求分析］

(1)设每个记录有下列数据项：电话号码、用户名、地址；

(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；

(3)采用一定的方法解决冲突；

(4)查找并显示给定电话号码的记录；

(5)查找并显示给定用户名的记录。

整个系统必须满足系统功能要求；设计不同的散列函数，比较冲突率；在散列函数确定

的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。

［概要设计］

voidgetin(Record*a)//键盘输入联系人的信息

voidShowlnformation(Record*a)//显示输入的用户信息

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

voidCreateHash(HashTable*H1Record*a)//建表若哈希地址冲突，进行冲突处理

voidSearchHash(HashTable*H,int&c)//在通讯录里查找关键字

voidSave()〃保存

voidmain_menu()

［存储结构］

typedefstruct{〃记录

NAname;

NAtel;

NAadd;

}Record;

typedefstruct{//哈希表

Record*elemLHASHSIZE］;〃数据元素存储基址

intcount;〃当前数据元素个数

intsize;〃当前容量

JHashTable;

［流程图］

voidmain_menu()

voidgetinvoidvoidvoidStatus

ShowlnformationCreateHashSearchHashcollision

[详细设计]

#include<iostream>//cout,cin语句的头文件#include<stdlib.h>〃清屏函数头文件：使用

#include<string>〃字符串头文件csl时调用system

#include<stdio.h>

#include<fstream>

#defineMAXSIZE100〃电话薄记录的数量

#defineMAX_SIZE50//用户名、电话号码、地址的最大长度

#defineHASHSIZE400//定义表长

#defineSUCCESS1〃查找

#defineUNSUCCESS-1

#defineLENsizeof(HashTable)//哈希表的长度

usingnamespacestd;

typedefintStatus;//typedef用来定义类型的别名。此处用status作为int别名，目的表达int

变量是一个状态变量。

typedefcharNA[MAX_SIZE];//NA作为char的另！J名

typedefstruct{〃自定义一个记录用户名、电话号码、联系地址的结构体的别名

record

NAn

ame,tel,add,way;}Record;

Recorda[HASHSIZE];

typedefstruct{儆列表

Record*elem[HASHSIZE];〃数据元素存储地址

intcount;〃数据元素个数

intsize;〃容量

JHashTable;

Statuseq(NAx,NAy)

{〃关键字比较，相等返回SUCCESS;否则返回UNSUCCESS

Nstrcmp(x,y)==0)〃2个字符串的大小比较s仁s2»strcmp(s1,s2)==0;s1>s2,

strcmp(s1Ss2)==1;s1<s2,strcmp(s1,s2)==-1;

returnSUCCESS;

else

returnUNSUCCESS;

StatusNUM_BER;〃记录的个数

voidgetin(Record*a){//键盘输入联系人的信息，Record*调用Record函数：a是参数

coutvv”请输入要添加的联系人的个数：\nM;cin»NUM_BER;

inti;for(i=0;i<NUM_BER;i++){

coutvv”请输入第"vvi+1vv”个记录的用户名:\n";cin»a[i].name;

coutvv”请输入第”vvi+1vv”个记录的电话号码:\nn;cin»a[i].tel;

coutvv”请输入第”vvi+1vv”个记录的地址:\n";cin»a[i].add;

}}voidShowlnformation(Record*a)〃显示输入的用户信息

(

inti;

for(i=O;i<NUM_BER;i++)

cout«"\nM"vvi+1vv”个用户信息：\n姓名："vva[i].namevv”\n电话号码：

w«a[i].tel«An联系地址："«a[i].add«^n............\n";

}

longfold(NAs)//人名的折叠处理：将关键字分割成位数相同的几部分，最后一部分位数可以不同，

然后取这几部分的叠加和(去除进位)作为散列地址

(

char*p;

longsum=0;

NAss;

strcpy(ss,s);〃复制字符串，不改变原字符串的大小写

strupr(ss);//将字符串ss转换为大写形式

P=ss;

while(*p!='\0')

sum+=*p++;

returnsum;

}

intHashi(NAstr){//哈希函数

longn;

intm;

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

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

returnm;〃并返回模值

intHash2(NAstr){//哈希函数

longn;

intm;

n=atoi(str);//把字符串转换成整型数.m=n%HASHSIZE;//用除留余数法构造哈希函数

returnm;〃并返回模值

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

inti,q;

i=c/2+1;

while(i<HASHSIZE){

if(c%2==0){

C++；

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

if(q>=0)returnq;

elsei=c/2+1;

)

else{

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

C++；

if(q>=0)returnq;

elsei=c/2+1;

}

}

returnUNSUCCESS;

}

intsearchHash(HashTable*&H,NAkey,int&p,int&cJntway)

if(way==1){p=Hash1(key);

while(H->elem[p]!=NULL&&!eq(key,H->elem[p]->name))〃若哈希地址冲突，进行冲突

处理

collision(p,++c);if(eq(key,H->elem[p]->name))return1;

elsereturn0;

}

else

(

p=Hash2(key);

while(H->elem[p]!=NULL&&!eq(key,H->elem[p]->tel))//若哈希地址冲突，进

行冲突处理

collision(p,++c);

if(eq(key,H->elem[p]->tel))

return1;

else

return0;

)

//建表，若哈希地址冲突，进行冲突处理voidCreateHash(HashTable*H,Record*a)

cout«"\n======建立散列表=======

cout«"\n(1).以姓名建立散列表(再散列法解决冲突)

cout«"\n⑵.以电话号码建立散歹!J表(再散歹U法解决冲突)

J

cout«H\n☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

COUtw”请输入选择:"；

intnum,i,p=-1,c;

cin»num;

for(i=0;i<NUM_BER;i++){

c=0;

if(num==1){

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

while(H->elem[p]!=NULL&&!eq(a[i].name,H->elem[p]->name))〃若哈希地址冲突»进行

冲突处理

collision(p,++c);

)

else{

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

while(H->elem[p]!=NULL&&!eq(a[i].tel,H->elem[p]->tel))//若哈希地址冲突，进行冲突

处理

collision(p,++c);

)

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

H->count++;

coutvv"第“vvi+1vv”个记录冲突次数为"vvcvv”。\n”；〃需要显示冲突次数时输出

)

cout«"\n建表完成!\n此哈希表容量为ZvHASHSIZEvv”，当前表内存储的记录个数为

,,«H->count«".\n,';

)

〃查找用户名和电话号码的记录；

voidSearchHash(HashTable*H,int&c){//在通讯录里查找关键字，若查找成功，显示信息

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

NAtype;

intp;

cout«'*\n======查找并显示用户信息记录=======

coutvv'n⑴.查找并显示给定用户名的记录

cout«"\n⑵.查找并显示给定电话号码的记录

J

cout«"\n☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"；

coutvv”请输入选择:"intnum;

cin»num;

switch(num){

case1:

coutvv'n请输入要查找的用户名：\n”;cin»type;

searchHash(H,type,p,c,1);

if(eq(type,H->elem[p]->name)==1){

coukv'n查找成功！以下是您需要要查找的信息：\n\n"；

coutvv"姓名："«H->elem[p]->name«^n电话号码："«H->elem[p]->tel«"\n

联系地址："vvH->elem[p]->addvv"\rT;

)

else

cout«"\n对不起，该用户不存在\n";

break;

case2:

cout«"\n请输人要查找电话号码：\nM;cin»type;

searchHash(H,type,p,c,2);

if(eq(type,H->elem[p]->tel)==1){cout«n\n查找成功！以下是您需要要查找的信息：

\n\n";

cout«H姓名："vvH-elemlpJ,namevvQn电话号码：M«H->elem[p]->tel«"\n联系地

址："vvH・>elem[p]->addvv'*\rr；

}

else

cout«H\n对不起，该用户不存在\n";

break;

default:cout«"输入错误，请重新输入

voidSave(){〃保存

ifstreamin;

ofstreamout;out.open("123.txt'*);

printf("\n保存成功!");

for(inti=0;i<NUM_BER;i++){

out«"姓名："vva[i].namevv"\n电话号码："vva[i].telvv”\n联系地址

"«a[i].add«"\n";

)

return;

}

voidmain_menu()

(

intc,flag=1;////定义一个布尔型变量flag并初始化为真(true)HashTable*H;

H=(HashTable*)malloc(LEN);

for(inti=O;i<HASHSIZE;i++)

H->elem[i]=NULL;

H->size=HASHSIZE;H->count=0;

while(1){//while使电话查询系统执行后返回主菜单的界面system("cls");

cout«*'\n======V(A3。/欢迎使用电话号码查找系统=======

coutvv'M(1).添加用户信息"；

coutvv'M(2).读取所有用户信息"；

cout«n\n(3).建立散列表(再散列法解决冲突)”；

cout«^n(4).查找并显示给定用户的记录"；

coutvv'n(5).保存

cout«,r\n(6).退出

cout«An提示：进行4操作前请先进行3操作.否则无法查找成功!"；

cout«,r\n☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"；

cout«^n\n请选择：

intnum;

cin»num;

switch(num){

case1:

getin(a);

system("pause")；

break;

case2:

Showlnformation(a);

system("pause");

break;

case3:

CreateHash(H,a);/*建立散列表7

system("pauseM);

break;

case4:

c=0;

SearchHash(H,c);

system("pause");

break;

case5:

Save();

system("pause");

break;

case6:

return;

break;

default:

cout«"输入错误，请重新输入

cout«"\n";

intmain(intargc,char*argv[])

main_menu();

〃执行结束后清屏，显示主菜单

return0;

}［调试分析］

问题一：

现象：每次执行后，系统界面不自动清屏？

原因：执行每个选项后，没有清屏操作的代码。解决办法：将CLS放到switch函数体

后面，执行选项后，执行清屏操作

问题二：

现象：进行查找的时候，总是查找失败！！！

原因：查找前没有建立散列表。解决办法：先建立散列表，再查找。

［运行结果及分析］

c**C:\Docu>entsandSettings\Ad>inistrator\LocalSettings\Te*p\Rar$DIaO...日日X

欢

uL3/迎使3

息

加

户

添

信

信

读

户

有

21取

斡

爨

建

列

语

第

31.文

定

示

查

显

给

并

4].找

.保

.存

51退

.&

61田

遣

媪

5一

一

☆'

清选择：2

渤个

户信

息

用:

姓

娟

稻

智

话

屯O8

矍

肥

系

联18

S重

请按任意键继续..•

搜狗拼音半:zJ

K*C:\DocuaentsandSettingsVAdainistrator\LocalSettings\TeBp\Rar$DIaO...□|x

—

一感

信息

2矍

取

另

镯

咐

3班

立

并

示

己

定

录

4用

找

5存

6出

一

撮

行

-患

磔

.卷找成功，

☆☆☆介

☆'☆☆☆

诜择3

I•以姓名iijft列

2一以电话年码挈隹立..................

☆☆右☆☆石■

☆☆☆☆☆$☆☆☆☆☆☆笫1_个记录冲突次数为0

建表完成？

魁爵IT•当前表内甸记录俾汕

狗拼音半:

*C:\Docu>entsandSettings\Ad>inistrator\LocalSettings\TeBp\Rar$DIaO..

1:

5.保存

6).退出

提不：进行4操作前请先进行3操作•否则无法查找成功?

请选择：4

奏

(-一--

用

——

哈

己

■显H

翁

々

急

二

言

々

内

哈

为

显

一

查§

三

工

各

々

召

杳

☆☆白

贵

。-请输入选择汽

\j

/2

VI

/3

\(

\/4

/

XI5

6

/:是

一

性选才仝：5

保存成功?请按任意键继续・••

搜狗拼音半:

品*C:ADocuMentsandSettingsV\d>inistrator\LocalSettings\Teii!p\Rar$DIaO...|

_____________)一覆加用力佶息—

一覆卓所有甩户信息

羲立羲4羸|列出%立散列解决口［41一查找并显示给定用户的记录

(6)

提$进仃4操作前状进行3操作.否则土法直找成功！召寿召☆合

客玄玄矗金☆☆岳☆渥☆金承

请选择；6

|PressNnykeytocontinue

I搜狗拼音半:

课程设计题目二

［实验内容］

通讯录

［问题描述］

管理通讯信息，包含姓名(name)、出生日期(birthday)、城市(city)、职业

(profession)、电话(tel)、00号(qq)等°

［需求分析］

1'输入信息。

2、显示信息。

3、分别以姓名、城市、出生日期、电话或QQ作为关键字查找。

4、删除信息。

5、存盘，将数据保存在文件phonefile中，以便下次可以继续上述工作。

测试数据：自己设计，不少于30人。

［概要设计］

voidTeleNumber::ReadFile(istream&in)〃从文件依次将标准输入流中的数据读入到变

量name，….中

voidTeleNumber::input()〃信息数据输入

voidTeleNumber::display()//调用telenumber中的display函数输出信息

voidTeleMessage::Remove()〃删除

voidTeleMessage::Show()int

main()

［存储结构］

此程序的存储结构是单链表

voidTeleMessage::lnsert()〃插入

IEnd-^innutn：〃尾指针指向input,从单链表尾部插入信息

End=End->Next;coutvvendlvv”插人〃尾节点指向下一个节点

成功"vvendl;

［流程图］

intmain()

voidTeleNumbe匚:input()voidTeleMessage::Remove()void

TeleMessage::Show()

［详细设计］

#includeviostream>〃对标准输入输出文件的操作，后面有命名空间，不能用viostream.h>»

否则出错

#include<fstream>//是对文件操作

#include<string>

#include<stdlib.h>

usingnamespacestd;

intnum;

structTeleNumber〃用struct结构体来存放不同类型的数据*函数

(

charname［20］;〃姓名，字符必须注明长度

intphoneNumber;//电话号码

intbirthday;〃出生日期

charcity［30］;〃城市

TeleNumber*Next;

voidReadFile(istream&in);//

voidinput();〃信息输入的函数

voiddisplay；〃信息输出的函数

}；

voidTeleNumber::ReadFile(istream&in)〃从文件依次将标准输入流中的数据读人到变量

name，…•中

{in»name»phoneNumber»birthday»city;

)

voidTeleNumber::input()//信息数据输入

{coutvv”请输入姓名"vvendl;

End->Next=newTeleNumber;〃尾节点指向下一个数据节点，开辟一个新的节点

cin»name;

coutvv”请输入电话号码"vvendl;

cin»phoneNumber;

coutvv”请输入出生日期“wendl;

cin»birthday;

coutvv”请输入城市"vvendl;

cin»city;

)

voidTeleNumber::display()〃调用telenumber中的display函数输出信息

{cout«M姓名:',«name«*\t,«H固定号码:'*«phoneNumber«'\f«M出生日

期："vvbirthdayvv'\t'vv"城市:M«city«endl;

classTeleMessage//建造一个类，表示信息功能的类

{public:

TeleMessage();//构造数据结构

-TeleMessage();void〃析构函数，用来释放单链表

Save();〃数据保存到文件

TeleNumber*Search(char*);//定义一个查找数据的指针

voidlnsert();voidRemove();〃插入函数的定义在后面，这里要先声明

voidChange();voidShow();//删除

private:〃更改

//显示

TeleNumber*End,*Head;

ifstreamin;

〃定义结构体的头尾指针

ofstreamout;

〃定义从文件中读入数据

};TeleMessage::TeleMessage()

〃定义将数据写到文件中

{Head=newTeleNumber;

〃定义信息类中的信息函数

Head->Next=newTeleNumber;

//头插法建立单链表

End=Head->Next;//head指向一个新分配的节点

指向下一个节点，直到指向尾节点〃对结构体遍历，头节点指针依次

in.open(MTeleNumber.text'*);

)〃使屏幕暂停，而不是直接闪过〃打开外存文件，读人数据

TeleMessage::-TeleMessage()

〃释放单链表

{TeleNumber*temp;

〃定义一个数据指针temp

while(Head->Next!=End)

〃当头节点指向的下一个指针不是尾节点

{temp=Head->Next;

〃数据指针指向头节点指向的下一个节点

Head=Head->Next;delete

〃头结点依次指向头结点的下一个节点

temp;

〃删除数据指针指向的节点数据

deleteHead,End;

//删除头尾指针

voidTeleMessage::Save()

{out.openCTeleNumber.txt");数据写入外存文件中

for(TeleNumber//保存文件

*p=Head->Next;p!=End;p=p->Next)〃建止外停文i牛TeleNumber.txt'把

out«p->name«"\t"«p->phoneNumber«"\t"«p->birthday«"\t"«p->city«endl;//将数据存至！1夕卜

存文件里

out.close();〃定义一个数据指针p,使p依次指向头结点指向的下一个指针，直到p指

向尾节点，依次写入每个节点的信息

cout«"保存成功！"<<endl;

voidTeleMessage::lnsert()〃插入

{End->input();〃尾指针指向input,从单链表尾部插入

信息

End・>Next=newTeleNumber;〃尾节点指向下一个数据节点，开辟一个新的节点

八、、

End=End->Next;〃尾节点指向下一个节点coutvvendkv”插入成功M«endl;

voidTeleMessage::Remove()//删除

{charname[20];

TeleNumber*p=newTeleNumber,*temp=NULL;//定义一个数据指针，指向新的数据»定义一个

数据指针temp,指向空函数

coutvv”请输入要删除人的姓名:M«endl;cin»name;

if((p=Search(name)))〃如果找到了要删除的节点

{if(Head->Next==p){

Head->Next=p->Next;//利用头指针，将要删除的数据拉出来，这个是经过找很多人写出来的。

首先非常感谢百度知友和校友

»

temp=p;〃使指针temp指向p指向的要删除的节点

p=p->Next;//摘链：使p指向p指向的下一个节点的下一个节点

deletetemp;//删除temp指向的节点

cout«"删除成功!"«endl;

I

else

{coukv”没有找至!!r«endl;

।

TeleNumber*TeleMessage::Search(char*name)〃定义信息类中查找函数指针

{for(TeleNumber*p=Head->Next;p!=End;p=p->Next)〃定义一个数据指针p指向头节点指向的下一个

节点，头节点没有数据，数据从头节点的下一个节点开始存储，P进行遍历

操作，直到指向尾节点

if(!strcmp(p->name,name))//strcmp作用是俩个变量相减，如果p所指向的name和要查找

的name相同，则strcmp值为0，非1

{p->display();

returnp;

else

cout«M查无此人"«endl;

return0;systemrcis");

voidTeleMessage::Show()

{for(TeleNumber*p=Head->Next;p!=End;p=p->Next)

p->display();

।

intmain()

{boolflag=true;〃定义一个布尔型变量flag并初始化为真(true),只认识真(true)和假(false)，

1和0，也就是成立和不成立的简单判断。

TeleMessagetele;

charname[20];

while(flag)〃如果flag为真

system(MclsH);

coutvv',=：=====通讯录====="vvendl;

coutvv”1.增加信息Mvvendl;

coutvv”2.显示信息Mvvendl;

coutvv”3.查找号码Mvvendl;

coutvv"4.删除信息"vvendl;

coutvv"5.保存信息nvvendl;

coutvv',6.退出系统Mvvendl;

cout«M-----------------------------------------------------M«endl;

coutvv”请选择："；cin»num;

switch(num)

{case1:tele.lnsert();break;

case2:tele.Show();break;

case3:coutvv”请输入姓名"vvendl;

cin»name;

tele.Search(name);break;

case4:tele.Remove();break;

case5:tele.Save();break;

case6:coutvv”谢谢使用!Mvvendl/eturn0;break;//return0表示退出系统default：

coutvv”输入错误，请重新输入r；coutvvM\nM;

।

system("pause");

}}

[调试分析]

问题一：

现象：执行查找时，运行出错。

原因：定义查找时，出错了，经过调试if语句，运行成功

问题二：

现象：按0，系统不退出

原因：输入0后，系统执行的是break＞而不是return0.

问题三：

现象：删除操作时，系统显示俩排相同的信息

原因：定义删除函数时，一个for，一个if导致删除执行了俩次。解决办法是for消掉

[运行结果及分析]

^^D:\36诟盘'作业'歙据结构作业\Deb“\通讯录・=••del

1增加信息

2显示信息

3箕码

4S

信息

氟退出系统

清输入电话号码

]]一

嘴输入纸市

品-D:\360云盘'作业数振结构作业XDebugA通讯录.eie.E°I

史

储

鬲

一

辛

•

Y

民

可

J：■S同22城中:也

：f-C■"B2阅城市：=q

c<.D:\360云盘'作业'数据结构作业\Debug\通讯录.exe-I°l

髓

西

增

Fl值f

1加

2显^M

不o

查

l码

3找p

删

^息

4%g

保

信

5息

退

统