数据结构课程设计.docx

资源描述

数据结构课程设计.docx

《数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计.docx（27页珍藏版）》请在冰点文库上搜索。

数据结构课程设计.docx

数据结构课程设计

计算机科学与技术学院

课程设计报告

课程名称数据结构课程设计

专业：

软件工程

班级：

11级3班

学号：

201113138103

姓名：

李青龙

指导老师：

袁嵩

计算机科学与技术学院课程设计成绩单

课程名称：

数据结构课程设计指导教师：

姓名

李青龙

性别

男

学号

201113138103

班级

软件1103

综合成绩

成绩等级

程序运行情况

（占总成绩20%）

□能正确运行□基本能正确运行□能运行但结果不完善

（20分）（15分）（10分）

程序功能的完善程度

（占总成绩10%）

□完善□基本完善□不完善

（10分）（8分）（5分）

程序结构的合理性

（占总成绩10%）

□合理□基本合理□不太合理

（10分）（8分）（5分）

对问题的答辩情况

（占总成绩40%）

□概念正确有创新□能正确回答所有问题□基本能正确回答

（40分）（35分）（30分）

□部分问题回答概念不清晰

（20分）

学生的工作态度与独立工作能力

（占总成绩10%）

□工作态度认真能独立完成任务□工作态度认真但独立性较差

（10分）（8分）

□工作态度基本认真但缺乏独立性

（5分）

设计报告的规范性

（占总成绩10%）

□符合规范□基本符合规范□规范性较差

（10分）（8分）（5分）

优秀：

90分~100分良好：

80分~89分中等：

70~79分及格：

60~69分不及格0分~59分

武汉科技大学计算机科学与技术学院制表

题目一通讯录

[问题描述]

1）通过键盘建立通讯录，每条记录至少包括2个数据项：

姓名、电话号码；

2）对通讯录进行插入、删除、修改和查找；

3）通过姓名查找，必须实现精确查找和模糊查找，例如输入“张”，则显示第一个姓张的朋友，然后可以选择“下一个”，鼓励思路创新，提供其他多种查找方式，例如拼音查找等；

4）也可以根据电话号码或部分电话号码进行精确查找和模糊查找；

5）自行定义数据结构，可以选择性的将顺序查找、折半查找、索引查找、树型查找、哈希表等灵活运用其中，完成多方式查找功能。

[解题思路]

由于题目要求通讯录能增、删、改、查，所以选择用线性链表这一存储结构比较好操作。

又由于存放的数据至少包含两个数据，因此节点类型应该为结构体。

题目要求实现精确查找和模糊查找，可以利用string类中的strcmp（）函数实现。

查找类型为顺序查找。

[算法描述]

[程序设计]

//data数据类型定义

structElemType

{

stringname;

stringnum;

};

//线性表的单链表存储结构

structLNode

{

ElemTypedata;

LNode*next;

};

typedefLNode*LinkList;//另一种定义LinkList的方法

voidBuild（LinkListL,ElemTypee）//新建联系人并插入链表

{

inti;

cout<<"请输入姓名：

cin>>e.name;

cout<<"*--*--*--*--*--*"<

cout<<"请输入电话号码：

cin>>e.num;

cout<<"*--*--*--*--*--*"<

i=Locate（L,e.name,e.num）;

if（i!

=0）{

intj=ListInsert（L,i,e）;//调用ListInsert（）函数

printf（"新建成功！

请选择操作项：

\n"）;

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

}

else{

cout<<"请选择操作项：

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

}

voidDelete（LinkListL）//删除联系人

{

stringname;

cout<<"请输入要删除的联系人姓名：

cin>>name;

cout<<"*--*--*--*--*--*"<

inti=GetId（L,name）;

if（i!

=0）{

intx=ListDelete（L,i）;//调用ListDelete（）函数

cout<<"删除成功！

请选择操作项：

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

}

else{

cout<<"对不起，输入的联系人不存在！

printf（"请选择操作项：

\n"）;

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

}

intModify（LinkListL）//修改联系人信息

{

stringname;

cout<<"请输入要修改的联系人姓名：

cin>>name;

cout<<"*--*--*--*--*--*"<

inti=GetId（L,name）;//调用GetId（）函数，在链表中找到要修改的位置

while（i==0）{

cout<<"输入联系人不存在，是否继续？

YESN:

NO"<

stringa;

cin>>a;

cout<<"*--*--*--*--*--*"<

while（a!

="Y"&&a!

="N"）{

cout<<"无效选项，请从新输入：

cin>>a;

cout<<"*--*--*--*--*--*"<

}

if（a=="Y"）{

cout<<"请输入要修改的联系人姓名：

cin>>name;

cout<<"*--*--*--*--*--*"<

i=GetId（L,name）;

}

elseif（a=="N"）{

cout<<"未修改！

printf（"请选择操作项：

\n"）;

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

return0;

}

intj=Alter（L,i,name）;//调用Alter（）函数，在链表中修改联系人信息

printf（"请选择操作项：

\n"）;

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

return0;

}

intAlter（LinkListL,inti,stringName）//修改name所在节点信息

{

intj=0;

stringname,num;

ElemTypee;

LinkListp=L,q=L;

while（p->next&&j

{

p=p->next;

j++;

}

if（!

p->next||j>i-1）//更改位置不合理

returnERROR;

cout<<"请输入更改后的联系人信息：

cout<<"姓名：

cin>>name;

cout<<"*--*--*--*--*--*"<

cout<<"电话号码：

cin>>num;

cout<<"*--*--*--*--*--*"<

intk=Exist（L,name）;

if（name==Name）

k=1;

while（k==0）{

cout<<"更改后姓名与原信息有同名项！

是否继续？

YESN:

NO"<

stringa;

cin>>a;

cout<<"*--*--*--*--*--*"<

while（a!

="Y"&&a!

="N"）{

cout<<"无效选项，请从新输入：

cin>>a;

}

if（a=="Y"）{

cout<<"请从新输入更改后的联系人信息：

cout<<"姓名：

cin>>name;

cout<<"*--*--*--*--*--*"<

cout<<"电话号码：

cin>>num;

cout<<"*--*--*--*--*--*"<

k=Exist（L,name）;

}

elseif（a=="N"）{

cout<<"未修改！

return0;

}

e.name=name;

e.num=num;

p->next=p->next->next;

ints=1;

stringa,b;

if（q->next）{

s=1;

a=q->next->data.name;

b=name;

intl=strcmp（a.c_str（）,b.c_str（））;

if（l<0）{

s++;

}

q=q->next;

while（l<0&&（q->next））{

a=q->next->data.name;

b=name;

l=strcmp（a.c_str（）,b.c_str（））;

if（l<0）

s++;

q=q->next;

}

intm=ListInsert（L,s,e）;

cout<<"修改成功！

return1;

}

voidSearch（LinkListL）//用关键字查询联系人，包括模糊查找和精确查找

{

stringkeyword;

cout<<"请输入检索关键字：

cin>>keyword;

cout<<"*--*--*--*--*--*"<

intn=keyword.length（）;

LinkListp=L;

stringNa[100],Nu[100];

intr=0,j=1;

while（p->next）{

intm=p->next->data.name.length（）;

intk=m-n+1;

intpos=0;

while（k>0）{

inti=p->next->datapare（pos,n,keyword）;

if（i==0）{

Na[r]=p->next->data.name;

Nu[r]=p->next->data.num;

++r;

break;

}

k--;

pos++;

}

p=p->next;

}

if（r==0）

cout<<"查询结果为空"<

else{

cout<

while（j<=r）{

cout<

j++;

}

//精确查询

cout<

YESN:

NO"<

stringa;

cin>>a;

cout<<"*--*--*--*--*--*"<

while（a!

="Y"&&a!

="N"）{

cout<<"无效选项，请从新输入：

cin>>a;

cout<<"*--*--*--*--*--*"<

}

if（a=="Y"）{

charb[100];

inti;

cout<<"请输入精确查找联系人序号：

cin>>b;

cout<<"*--*--*--*--*--*"<

chartemp[100];

itoa（r,temp,10）;

intn=strcmp（b,temp）;

if（n<=0）

n=0;

while（Charge（b）||b[0]=='0'||n）{

cout<<"无效选项！

请从新输入：

cin>>b;

cout<<"*--*--*--*--*--*"<

}

i=atoi（b）;

cout<

}

cout<<"查询完成！

请选择操作项：

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

}

voidScan（LinkListL）//浏览通讯录信息

{

LinkListq=L;

if（!

（q->next））

cout<<"通讯录信息为空！

else

cout<

while（q->next）{

cout<<"姓名：

"<next->data.name<<'\t'<<"电话号码：

"<next->data.num<

q=q->next;

}

printf（"请选择操作项：

\n"）;

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

}

//主函数

voidmain（）

{

ElemTypee;

LinkListL;

stringn;

inti=InitList（L）;

LinkListq=L;

cout<<"通讯录已启动，请选择操作项：

cout<<"1.新建2.删除3.修改4.查询5.浏览6.退出"<

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

cin>>n;

cout<<"*--*--*--*--*--*"<

while（n!

="6"）{

if（n=="1"）{Build（L,e）;cin>>n;cout<<"*--*--*--*--*--*"<

elseif（n=="2"）{Delete（L）;cin>>n;cout<<"*--*--*--*--*--*"<

elseif（n=="3"）{inti=Modify（L）;cin>>n;cout<<"*--*--*--*--*--*"<

elseif（n=="4"）{Search（L）;cin>>n;cout<<"*--*--*--*--*--*"<

elseif（n=="5"）{Scan（L）;cin>>n;cout<<"*--*--*--*--*--*"<

else{cout<<"无效选项！

请从新输入：

"<>n;cout<<"*--*--*--*--*--*"<

}

cout<<"*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*"<

cout<<"通讯录已退出！

}

[测试结果]

程序开始运行，提示用户输入对应序号选择操作项

选择操作项1，新建联系人

选择操作项2，删除联系人，若输入联系人不存在，删除失败

若输入联系人存在，删除成功

选择操作项3，修改联系人信息，若输入联系人不存在，修改失败

若修改后的联系人与原有信息有同名项，修改失败

修改成功实例

选择操作项4，进入查询

查询分为模糊查询与精确查询

选择操作项5，浏览当前通讯录信息

选择操作项6，退出程序

[总结]

[心得体会]

做完该通讯录的课程设计之后自己对汉字的编码有了更加深入的了解，对数据结构的操作，选取有了整体的认识及提高。

在做通讯录时遇到了些棘手的问题，但通过自己的不懈努力终于将问题解决，使自己独立解决问题的能力有所提高。

这次课程设计可以说是对自己很好的锻炼。

本程序在查询部分并不完善，查询方法还有待优化，查询方式过于单一，数据较少还可以，数据多了就反应太慢。

题目二【便利店选址】

[问题描述]

某小区决定在小区内部建一家便利店，现小区内部共有八栋楼，它们的地理坐标分别为：

（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。

为了方便更多的住户购物，要求实现总体最优，请问便利店应该建立在哪里？

[解题思路]

本题目通过建立数学模型后可以转换为二元函数求最值问题，其中f（x,y）表示为距离*权重的累加，只要找到点使得f（x）最小则该点时最优解！

[算法描述]

本题采用PSO粒子群算法找到最优解

PSO算法描述如下：

a）.初始化一群微粒（群体规模为m），包括随机的位置和速度；

b）.评价每个微粒的适应度；

c）.对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；

d）.对每个微粒，将它的适应值和全局所经历最好位置gbest的作比较，如果较好，则重新设置gbest的索引号；

e）.根据方程

（1）变化微粒的速度和位置；

f）.如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到b）。

[程序设计]

#include

usingnamespacestd;

#definesize30

typedefstruct

{

doublex;

doubley;

}point;

pointloc_house[8]={{10,20},

{30,34},{19,25},{38,49.1},{9,38.1},{2,34},{5,8},{29,48}};

doubleweight[8]={30,45,28,8,36,16,78,56};

//以下是pso所需变量的定义

intiteration=100;//迭代次数

//intsize=100;//种群数量

doublew;

doublew_max=1.7,w_min=-1.7;

doublebest_in_history=100000;//全局历史最优值

doublemax_v=0.3;//最大速度限制

doublebest_fitness=100000;//最优适应值

doublepop_matrix[size][8];

doublec1=2;

doublec2=2;

doublex_max=100;

doubley_max=100;

doublex_min=0;

doubley_min=0;

doublegbest_x;//全局最优值X

doublegbest_y;//全局最优值y

voidinit（）;

voidcal_fitness（）;

voidupdate_pos（）;

voidupdate_v（）;

voidfind_best_fit（）;

doubledist（pointp1,pointp2）;

intmain（）

{

//第一步进行初始化

init（）;

time_tt;

srand（unsigned（time（&t）））;

//进入迭代循环

for（inti=0;i

{

w=w_max-（w_max-w_min）*（i

展开阅读全文