数据结构课程设计.docx

1、数据结构课程设计 计算机科学与技术学院 课 程 设 计 报 告课程名称 数据结构课程设计专 业： 软 件 工 程 班 级： 11 级 3 班 学 号： 201113138103 姓 名： 李 青 龙 指导老师： 袁 嵩 计算机科学与技术学院课程设计成绩单课程名称：数据结构课程设计 指导教师： 姓名李青龙性别男学号201113138103班级软件1103综合成绩成绩等级程序运行情况（占总成绩20%）能正确运行 基本能正确运行 能运行但结果不完善（20分） （15分） （10分）程序功能的完善程度（占总成绩10%）完善 基本完善 不完善（10分） （8分） （5分）程序结构的合理性（占总成绩10%

2、）合理 基本合理 不太合理（10分） （8分） （5分）对问题的答辩情况（占总成绩40%）概念正确有创新 能正确回答所有问题 基本能正确回答（40分） （35分） （30分）部分问题回答概念不清晰（20分）学生的工作态度与独立工作能力（占总成绩10%）工作态度认真能独立完成任务 工作态度认真但独立性较差（10分） （8分）工作态度基本认真但缺乏独立性（5分）设计报告的规范性（占总成绩10%）符合规范 基本符合规范 规范性较差（10分） （8分） （5分）优秀：90分100分 良好：80分89分 中等：7079分 及格：6069分 不及格0分59分 武汉科技大学计算机科学与技术学院制表题目一 通

3、讯录问题描述1） 通过键盘建立通讯录，每条记录至少包括2个数据项：姓名、电话号码；2） 对通讯录进行插入、删除、修改和查找；3） 通过姓名查找，必须实现精确查找和模糊查找，例如输入“张”，则显示第一个姓张的朋友，然后可以选择“下一个”，鼓励思路创新，提供其他多种查找方式，例如拼音查找等；4） 也可以根据电话号码或部分电话号码进行精确查找和模糊查找；5） 自行定义数据结构，可以选择性的将顺序查找、折半查找、索引查找、树型查找、哈希表等灵活运用其中，完成多方式查找功能。解题思路由于题目要求通讯录能增、删、改、查，所以选择用线性链表这一存储结构比较好操作。又由于存放的数据至少包含两个数据，因此节点类

4、型应该为结构体。题目要求实现精确查找和模糊查找，可以利用string类中的strcmp（）函数实现。查找类型为顺序查找。算法描述程序设计/ data数据类型定义struct ElemType string name; string num;/ 线性表的单链表存储结构struct LNode ElemType data; LNode *next;typedef LNode *LinkList; / 另一种定义LinkList的方法void Build(LinkList L, ElemType e) /新建联系人并插入链表 int i; cout请输入姓名：e.name; cout*-*-*-*-

5、*-*endl; cout请输入电话号码：e.num; cout*-*-*-*-*-*endl; i=Locate(L,e.name,e.num); if(i!=0) int j=ListInsert(L,i,e); /调用ListInsert（）函数 printf(新建成功！请选择操作项：n); cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; else cout请选择操作项：endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-

6、*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; void Delete (LinkList L) /删除联系人 string name; cout请输入要删除的联系人姓名：name; cout*-*-*-*-*-*endl; int i=GetId(L,name); if(i!=0) int x=ListDelete(L,i) ; /调用ListDelete()函数 cout删除成功！请选择操作项：endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-

7、*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; else cout对不起，输入的联系人不存在！endl; /输入联系人不存在删除失败 printf(请选择操作项：n); cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; int Modify(LinkList L) /修改联系人信息 string name; cout请输入要修改的联系人姓名：name; cout*-*-*-*-*-*endl; int i=GetId(L,name)

8、; /调用GetId()函数，在链表中找到要修改的位置 while(i=0) cout输入联系人不存在，是否继续？endlY:YES N:NOa; cout*-*-*-*-*-*endl; while(a!=Y&a!=N) cout无效选项，请从新输入：a; cout*-*-*-*-*-*endl; if(a=Y) cout请输入要修改的联系人姓名：name; cout*-*-*-*-*-*endl; i=GetId(L,name); else if(a=N) cout未修改！endl; printf(请选择操作项：n); cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

9、-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; return 0; int j=Alter(L,i,name); /调用Alter()函数，在链表中修改联系人信息 printf(请选择操作项：n); cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*next&jnext; j+; if(!p-next|ji-1) / 更改位置不合理 return ERROR; cout请输入更改后的联系人信息：end

10、l; cout姓名：name; cout*-*-*-*-*-*endl; cout电话号码：num; cout*-*-*-*-*-*endl; int k=Exist(L,name); if(name=Name) k=1; while(k=0) cout更改后姓名与原信息有同名项！是否继续？endlY:YES N:NOa; cout*-*-*-*-*-*endl; while(a!=Y&a!=N) cout无效选项，请从新输入：a; if(a=Y) cout请从新输入更改后的联系人信息：endl; cout姓名：name; cout*-*-*-*-*-*endl; cout电话号码：num;

11、cout*-*-*-*-*-*endl; k=Exist(L,name); else if(a=N) cout未修改！next=p-next-next; int s=1; string a,b; if(q-next) s=1; a=q-next-data.name; b=name; int l=strcmp(a.c_str(),b.c_str(); if(lnext; while(lnext) a=q-next-data.name; b=name; l=strcmp(a.c_str(),b.c_str(); if(lnext; int m=ListInsert(L,s,e); cout修改成功

12、！endl; return 1;void Search(LinkList L) /用关键字查询联系人，包括模糊查找和精确查找 string keyword; cout请输入检索关键字：keyword; cout*-*-*-*-*-*next) int m=p-next-data .name.length(); int k=m-n+1; int pos=0; while(k0) int i=p-next-data pare(pos, n,keyword); if(i=0) Nar=p-next-data .name; Nur=p-next-data .num; +r; break; k-; po

13、s+; p=p-next ; if(r=0) cout查询结果为空endl; else coutendl查询结果如下：endlendl; while(j=r) coutj. Naj-1endl; j+; /精确查询 coutendl是否继续精确查询？endlY:YES N:NOa; cout*-*-*-*-*-*endl; while(a!=Y&a!=N) cout无效选项，请从新输入：a; cout*-*-*-*-*-*endl; if(a=Y) char b100; int i; cout请输入精确查找联系人序号：b; cout*-*-*-*-*-*endl; char temp100;

14、itoa(r,temp,10); int n=strcmp(b,temp); if(n=0) n=0; while(Charge(b)|b0=0|n) cout无效选项！请从新输入：b; cout*-*-*-*-*-*endl; i = atoi(b); coutendlendl姓名：Nai-1t电话号码：Nui-1endlendl; cout查询完成！请选择操作项：endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*next) cout通讯录信息为空！end

15、l; else coutendl以下是通讯录信息：endlnext) cout姓名：next-data.namet电话号码：next-data.numendlnext; printf(请选择操作项：n); cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;/主函数void main() ElemType e; LinkList L; string n; int i=InitList(L); LinkList q=L; cout通讯录已启动，请选择操作项：end

16、l; cout1.新建 2.删除 3.修改 4.查询 5.浏览 6.退出endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*n; cout*-*-*-*-*-*n; cout*-*-*-*-*-*n; cout*-*-*-*-*-*n; cout*-*-*-*-*-*n; cout*-*-*-*-*-*n; cout*-*-*-*-*-*endl; else cout无效选项！请从新输入：n; cout*-*-*-*-*-*endl; cout*-*-*-*-

17、*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl; cout通讯录已退出！endl;测试结果程序开始运行，提示用户输入对应序号选择操作项选择操作项1，新建联系人选择操作项2，删除联系人，若输入联系人不存在，删除失败若输入联系人存在，删除成功选择操作项3，修改联系人信息，若输入联系人不存在，修改失败若修改后的联系人与原有信息有同名项，修改失败修改成功实例选择操作项4，进入查询查询分为模糊查询与精确查询选择操作项5，浏览当前通讯录信息选择操作项6，退出程序总结心得体会 做完该通讯录的课程

18、设计之后自己对汉字的编码有了更加深入的了解，对数据结构的操作，选取有了整体的认识及提高。在做通讯录时遇到了些棘手的问题，但通过自己的不懈努力终于将问题解决，使自己独立解决问题的能力有所提高。这次课程设计可以说是对自己很好的锻炼。本程序在查询部分并不完善，查询方法还有待优化，查询方式过于单一，数据较少还可以，数据多了就反应太慢。题目二【便利店选址】问题描述某小区决定在小区内部建一家便利店，现小区内部共有八栋楼，它们的地理坐标分别为：（10，20） （30，34） （19，25） （38，49.1） （9，38.1） （2，34） （5，8） （29，48）。同时，其中的住户人数分别为：30, 4

19、5, 28, 8, 36, 16, 78, 56。为了方便更多的住户购物，要求实现总体最优，请问便利店应该建立在哪里？解题思路 本题目通过建立数学模型后可以转换为二元函数求最值问题，其中f(x,y)表示为距离*权重的累加，只要找到点使得f(x)最小则该点时最优解！算法描述 本题采用PSO粒子群算法找到最优解 PSO算法描述如下： a). 初始化一群微粒（群体规模为m），包括随机的位置和速度；b). 评价每个微粒的适应度；c). 对每个微粒，将它的适应值和它经历过的最好位置pbest的作比较，如果较好，则将其作为当前的最好位置pbest；d). 对每个微粒，将它的适应值和全局所经历最好位置gbe

20、st的作比较，如果较好，则重新设置gbest的索引号；e). 根据方程(1)变化微粒的速度和位置；f). 如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数Gmax），回到b)。程序设计#include #include #include using namespace std;#define size 30typedef struct double x; double y;point;point loc_house8=10,20,30,34,19,25,38,49.1,9,38.1,2,34,5,8,29,48;double weight8=30,45,28,8,36,16,78,

21、56;/以下是pso所需变量的定义int iteration=100;/迭代次数/int size=100; /种群数量double w;double w_max=1.7,w_min=-1.7;double best_in_history=100000;/全局历史最优值double max_v=0.3; /最大速度限制double best_fitness=100000; /最优适应值double pop_matrixsize8;double c1=2;double c2=2;double x_max=100;double y_max=100;double x_min=0;double y_min=0;double gbest_x;/全局最优值Xdouble gbest_y;/全局最优值yvoid init();void cal_fitness();void update_pos();void update_v();void find_best_fit();double dist(point p1,point p2);int main() /第一步进行初始化 init(); time_t t; srand(unsigned(time(&t); /进入迭代循环 for(int i=0;iiteration;i+) w=w_max-(w_max-w_min)*(i