级数据结构课程设计报告Word下载.docx
《级数据结构课程设计报告Word下载.docx》由会员分享，可在线阅读，更多相关《级数据结构课程设计报告Word下载.docx（25页珍藏版）》请在冰点文库上搜索。
班级：
11级1班
学号：
1
姓名：
涂智明
指导老师：
袁嵩
题目一通讯录
一、问题描述
1）通过键盘建立通讯录，每条记录至少包括2个数据项：
姓名、电话号码；
2）对通讯录进行插入、删除、修改和查找；
3）通过姓名查找，必须实现精确查找和模糊查找，例如输入“张”，则显示第一个姓张的朋友，然后可以选择“下一个”，鼓励思路创新，提供其他多种查找方式，例如拼音查找等；
4）也可以根据电话号码或部分电话号码进行精确查找和模糊查找；
5）自行定义数据结构，可以选择性的将顺序查找、折半查找、索引查找、树型查找、哈希表等灵活运用其中，完成多方式查找功能。
二、解题思路
将一个用户的信息定义为一个结构体，使用链表存储用户信息。
每一个用户为一个节点。
通讯录功能设置为新建通讯录，新增联系人，查找联系人，修改联系人，删除联系人，保存通讯录，打开已有通讯录。
保存通讯录将通讯录以文本文件存到本地硬盘，在启动程序后，可选择打开已保存的通讯录。
三、算法描述
四、程序设计
typedefstructnode
{
intn;
charname[20];
chartel[20];
charadd[20];
charqq[15];
structnode*next;
}list;
用于存储联系人信息
voidenterdata（list*p0）;
用于数据输入
voidshow（list*head）;
显示已输入的信息
voidsave（list*head,FILE*fp）;
保存文件
voidload（list*&
head）;
载入已存储的文件
voidsearch（list*head）;
搜索联系人
voidchange（list*head）;
改变已有联系人信息
voiddel（list*&
删除已有联系人
voidcreate（list*&
创建新通讯录
voidinsert（list*&
插入一个联系人信息
程序源码：
#include"
stdafx.h"
#include<
iostream>
#include<
stdio.h>
malloc.h>
stdlib.h>
string>
#defineLENsizeof（list）
usingnamespacestd;
intn;
charname[20];
chartel[20];
charadd[20];
charqq[15];
structnode*next;
voidenterdata（list*p0）;
intmain（intargc,char*argv[]）
list*head=NULL;
FILE*fp=NULL;
intm;
//功能代号吗
do{
cout<
<
"
\t\t\t\t通讯录"
endl;
请选择您需要的功能：
################################################################################"
;
#\t\t1.显示所有联系人信息\t\t"
2.新建通讯录\t\t#"
#\t\t3.查找联系人\t\t\t"
4.修改联系人\t\t#"
#\t\t5.删除联系人\t\t\t"
6.增加联系人\t\t#"
#\t\t7.保存\t\t\t\t"
8.打开\t\t\t#"
#\t\t9.清屏\t\t\t\t"
0.退出\t\t\t#"
输入要执行的功能代号：
cin>
>
m;
switch（m）
{
case1:
show（head）;
break;
case2:
create（head）;
break;
case3:
search（head）;
case4:
change（head）;
case5:
del（head）;
case6:
insert（head）;
case7:
save（head,fp）;
printf（"
==保存成功==\n"
）;
case8:
load（head）;
case9:
system（"
cls"
}
}
while（m!
=0）;
return0;
}
//数据输入
voidenterdata（list*p0）
printf（"
名字:
"
gets（p0->
name）;
城市:
gets（p0->
add）;
电话:
tel）;
QQ:
qq）;
\n"
//显示列表
voidshow（list*head）
list*p;
//定义移动指针
inti;
char*menu[]={"
姓名"
"
地址"
电话"
"
QQ"
};
//,"
生日"
备注"
p=head;
--------------------------------------------------------------------\n"
for（i=0;
i<
4;
i++）
%-12s"
menu[i]）;
cout<
if（head!
=NULL）
while（p!
{
printf（"
p->
printf（"
p=p->
next;
}
else
不好意思,列表为空\n"
//保存
voidsave（list*head,FILE*fp）
list*p0;
//定义移动指针
p0=head;
fp=fopen（"
通讯录.txt"
wb+"
while（p0!
{
fprintf（fp,"
%s%s%s%s"
p0->
name,p0->
add,p0->
tel,p0->
p0=p0->
fclose（fp）;
//载入
head）
FILE*fp;
charch;
//存储从文件中读取的字符
charlujing[100];
list*p1,*p2;
//,*p3;
输入打开通讯录得路径：
例如：
c:
\\新建文件夹\\通讯录.txt\n请输入:
scanf（"
%s"
lujing）;
fp=fopen（lujing,"
r"
if（fp==NULL）
错误:
打不开文件或文件不在\n"
exit（0）;
ch=fgetc（fp）;
//判定通讯录是否为空
if（ch==EOF）
===通讯录空===\n"
p2=p1=head;
while（p1!
p2=p1;
p1=p1->
free（p2）;
head=NULL;
while（!
feof（fp））
p1=（list*）malloc（LEN）;
p1->
next=NULL;
fscanf（fp,"
%s%s%s%s"
p1->
name,p1->
add,p1->
tel,p1->
if（head==NULL）
head=p1;
p2=head;
else
p2->
next=p1;
\n通讯录打开成功\n"
//查找
voidsearch（list*head）
charcheck_name[20];
intj=0,m;
请输入要查找的姓名\n"
check_name）;
\n不好意思,列表为空\n"
p1=head;
=NULL）
{
if（strstr（p1->
name,check_name））//模糊查找用的strstr（）函数
姓名:
%s"
城市:
电话:
QQ:
是否是本条记录？
按1确定本条记录\t按其他数字键继续\n"
scanf（"
%d"
&
m）;
if（m==1）
break;
if（p1==NULL&
&
j==0）
\n没有%s的通讯信息\n"
//修改
voidchange（list*head）
charchange_name[20];
请输入要修改的姓名\n"
change_name）;
getchar（）;
=NULL&
strcmp（change_name,p1->
name）!
=0）
if（p1!
strcmp（change_name,p1->
name）==0）
enterdata（p1）;
save（head,fp）;
\n%s没有被找到\n"
change_name）;
//删除
//定义临时指针
chardelname[20];
//保存要删除人的姓名
//文件指针
请输入要删除人的姓名:
delname）;
\n====通讯录为空====\n"
//通讯录不为空时，把头指针赋值给p1
while（p1&
（i=strcmp（delname,p1->
name）））/*p1指向的不是所要找的结点，且p1不是最后一个结点*/
//保存前驱结点地址
if（i==0）
删除人为:
%s\n"
if（p1==head）
{
head=p1->
//若p1指向的是首结点，指第二个结点的地址给P1
else
p2->
next=p1->
//修改指针域
head->
n=head->
n-1;
刚刚删除的是:
free（p1）;
elseif（p1==NULL）
\n姓名为%s的通讯信息没有被找到！
//创建
list*p0,*p1,*p2;
//作为判断是否继续新建的条件
p0=（list*）malloc（LEN）;
p0->
head=p0;
请输入信息建立通讯录：
enterdata（p0）;
p2=p0;
是否继续按1输入，按0结束"
while（m）
getchar（）;
p1=（list*）malloc（LEN）;
p1->
n=head->
n+1;
//表长***********************************
是否继续按1输入，按0结束"
if（m==0）
//插入
list*p,*q;
while（p->
next）
p=p->
//遍历到最后一个结点
新建：
q=（list*）malloc（LEN）;
q->
enterdata（q）;
p->
next=q;
head->
==建立完成-注意保存==\n"
五、测试结果
题目二便利店选址
某小区决定在小区内部建一家便利店，现小区内部共有八栋楼，它们的地理坐标分别为：
（10，20）（30，34）（19，25）（38，49.1）（9，38.1）（2，34）（5，8）
（29，48）。
同时，其中的住户人数分别为：
30,45,28,8,36,16,78,56。
为了方便更多的住户购物，要求实现总体最优，请问便利店应该建立在哪里？
【提示】
1）便利店无论选址何处，八栋楼的居民均可直接到达，即八栋楼与便利店均相邻，且距离为直线距离；
2）八栋楼的居民人数为权重，应该方便大多数人，实现总体最优。
运用精确重心算法，求出小区的重心，将便利店建在重心处即可。
1.确定便利店地址初始位置（xd（0）,yd（0））。
2.计算出与（xd（0）,yd（0））相应的距离权重CT（0）。
3.将（xd（0）,yd（0））代入公式中，计算出便利店地址的改进位置（xd
（1）,yd
（1））。
4.计算出与（xd
（1）,yd
（1））相应的距离权重CT
（1）。
5.将CT
（1）与CT（0）进行比较，若CT
（1）＜CT（0），则返回步骤3，将（xd
（1）,yd
（1））代入公式中，计算出便利店地址第二次改进位置（xd
（2）,yd
（2））。
若CT
（1）≥CT（0），说明初始位置（xd（0）,yd（0））便是最优解。
6.如此反复迭代计算，直至CT（k+1）≥CT（k），求出（xd（k）,yd（k））这一最优解为止。
本程序中定义了四个函数分别是choosePostion（），sum1（），sum2（），comp（）；
sum1（）,sum2（）分别计算
，
，choosePostion（）计算
，comp（）返回两数字差值的绝对值；
math.h>
#defineM10000
doublex[M]={10,30,19,38,9,2,5,29},y[M]={20,34,25,49.1,38.1,34,8,48},r[M]={30,48,28,8,36,16,78,56},d[M];
voidchoosePostion（intn,doublem）;
voidmain（）{
inti,n;
doublemin;
输入楼的数量：
n）;
while（n==0）{
没有楼不能建超市!
请重新输入需要满足楼数：
输入各楼的坐标（x,y），住户\n"
n;
i++）{
第%d个：
坐标：
i+1）;
%lf,%lf"
x[i],&
y[i]）;
住户人数:
%lf"
r[i]）;
求最佳地址"
i=8;
请给出收敛的差值min:
scanf（"
min）;
choosePostion（i,min）;
doublesum1（intn,doublea[M],doubleb[M]）{
doubles=0,p=0;
s+=a[i]*b[i];
p+=b[i];
returns/p;
doublesum2（intn,doublea[M],doubleb[M]）{
s+=a[i]*b[i]/d[i];
p+=b[i]/d[i];
doublecomp（doublea,doubleb）{
if（a<
0）
return（-a-b）;
return（a-b）;
voidchoosePostion（intn,doublem）{
inti=1,j;
boolfind=false;
doublesum,a1,b1,a2,b2;
if（n==1）{
对于一个楼，便利店最佳选址即楼所在地址:
x=%lf,y=%lf\n"
x[0],y[0]）;
else{
a1=sum1（n,x,r）;
b1=sum1（n,y,r）;
while（find==false）{
a[%d]=%lf,b[%d]=%lf\n"
i,a1,i,b1）;
***********************:
\n"
for（j=0;
j<
j++）{
d[j]=（sqrt）（（x[j]-a1）*（x[j]-a1）+（y[j]-b1）*（y[j]-b1））;
printf（"
d[%d]:
%lf\t"
j+1,d[j]）;
}
sum=0;
sum+=d[j]*r[j];
当前距离权重%lf.\n"
sum）;
a2=sum2（n,x,r）;
b2=sum2（n,y,r）;
if（（
升级会员 