数据结构课程设计 (2).doc

计算机科学与技术学院 课 程 设 计 报 告课程名称 数据结构课程设计专 业： 软 件 工 程 班 级： 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分 中等：7079分 及格：6069分 不及格0分59分 武汉科技大学计算机科学与技术学院制表题目一 通讯录问题描述1） 通过键盘建立通讯录，每条记录至少包括2个数据项：姓名、电话号码；2） 对通讯录进行插入、删除、修改和查找；3） 通过姓名查找，必须实现精确查找和模糊查找，例如输入“张”，则显示第一个姓张的朋友，然后可以选择“下一个”，鼓励思路创新，提供其他多种查找方式，例如拼音查找等；4） 也可以根据电话号码或部分电话号码进行精确查找和模糊查找；5） 自行定义数据结构，可以选择性的将顺序查找、折半查找、索引查找、树型查找、哈希表等灵活运用其中，完成多方式查找功能。解题思路由于题目要求通讯录能增、删、改、查，所以选择用线性链表这一存储结构比较好操作。又由于存放的数据至少包含两个数据，因此节点类型应该为结构体。题目要求实现精确查找和模糊查找，可以利用string类中的strcmp（）函数实现。查找类型为顺序查找。算法描述通讯录管理系统添加修改删除查找模糊查找精确查找添加联系人修改联系人删除联系人程序设计/ data数据类型定义struct ElemTypestring name;string num;/ 线性表的单链表存储结构struct LNodeElemType data;LNode *next;typedef LNode *LinkList; / 另一种定义LinkList的方法void Build(LinkList L, ElemType e) /新建联系人并插入链表 int i;cout请输入姓名：;cout*-*-*-*-*-*endl; cout请输入电话号码：e.num;cout*-*-*-*-*-*endl;i=Locate(L,,e.num);if(i!=0)int j=ListInsert(L,i,e); /调用ListInsert（）函数 printf(新建成功！请选择操作项：n);cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;elsecout请选择操作项：endl;cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*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*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;elsecout对不起，输入的联系人不存在！endl; /输入联系人不存在删除失败printf(请选择操作项：n);cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;int Modify(LinkList L) /修改联系人信息string name;cout请输入要修改的联系人姓名：name;cout*-*-*-*-*-*endl; int i=GetId(L,name); /调用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*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*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请输入更改后的联系人信息：endl;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;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=; b=name;int l=strcmp(a.c_str(),b.c_str();if(lnext;while(lnext)a=;b=name;l=strcmp(a.c_str(),b.c_str();if(lnext;int m=ListInsert(L,s,e);cout修改成功！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-;pos+;p=p-next ;if(r=0)cout查询结果为空endl;elsecoutendl查询结果如下：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;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通讯录信息为空！endl;elsecoutendl以下是通讯录信息：endlnext)cout姓名：t电话号码：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通讯录已启动，请选择操作项：endl;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*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;cout*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*endl;cout通讯录已退出！endl;测试结果程序开始运行，提示用户输入对应序号选择操作项选择操作项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 #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,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*1.0)/iteration;/对于每个粒子，计算适应值，若适应值比pbest_in_history好，则更新cal_fitness();find_best_fit();update_v();update_pos();coutgbest_x gbest_yendl;return 0;void init()int j=0;for(;j8;j+)weightj=weightj/297.0;for(int i=0;isize;i+)pop_matrixi0=rand()%51;/存放当前x的位置pop_matrixi1=rand()%51;/存放当前y的位置pop_matrixi4=pop_matrixi0;/历史最优x位置pop_matrixi5=pop_matrixi1;/历史最优y位置pop_matrixi2=rand()%101/100*0.2-0.1;/存放x速度方向的分量pop_matrixi3=rand()%101/100*0.2-0.1;/存放y速度方向的分量pop_matrixi6=100000;/适应值pbestpop_matrixi7=100000;/个体适应值pgbest_x=pop_matrix00;gbest_y=pop_matrix01;void cal_fitness()int i=0;point p;double temp;for(;isize;i+)/对每个粒子计算适应值temp=0;p.x=pop_matrixi0;p.y=pop_matrixi1;for(int j=0;j8;j+)temp+=dist(p,loc_housej)*weightj;/couttemptemp