算法与数据结构设计报告.doc

算法与数据结构设计报告（ 2015 / 2016 学年 第 一 学期）题 目： 景点导游程序 专 业 信息安全 学 生 姓 名 邓佳成 班 级 学 号 B13040701 指 导 教 师 骆 健 指 导 单 位 计算机学院计算机科学与技术系 日 期 一、 课程内容和要求内容：用无向图表示学校的景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点的介绍、游览路径等问题。要求：（1）需设置普通用户、超级管理员、景点管理用户等不同权限的用户。景点管理用户增加、删除、更新有关景点和道路的信息的权限、超级管理员对所有用户有增加、删除和修改权限。（2） 查询各景点的相关信息；（3） 查询图中任意两个景点间的最短路径。（4） 查询图中任意两个景点间的所有路径。（5）所有信息需存放在文本文件中。二、 需求分析void cmd3();/菜单页面调用函数void menu3();/显示菜单页面void addUsers();/添加用户void showUsers();/显示用户信息void updateUser();/修改用户登录密码void deleteUser();/删除该用户void loadUser();/加载用户信息void storeUser();/存储用户信息void cmd2();/菜单页面调用函数void menu2();/菜单页面void showPoints();/显示景点信息void addPoint();添加景点void updatePoint();/修改景点信息void deletePoint();/删除景点void showRoad();/显示路线void addRoad();/添加路线void updateRoad();/修改路线void deleteRoad();/删除路线void cmd(void);/主菜单页面调用函数MGraph InitGraph(void);/初始化地图void Menu(void);/主菜单界面void Browser(MGraph *G);/浏览景点void ShortestPath_DIJ(MGraph * G);/ 迪杰斯特拉算法计算出起点到各个顶点之间的最短路径void Floyd(MGraph *G);/计算两景点间的总路线长void Search(MGraph *G);/查找景点并输出景点信息int LocateVex(MGraph *G,char* v);/ MGraph * CreatUDN(MGraph *G);/初始化图形，接受用户输入void print(MGraph *G);/输出地图信息void print_Passwd(void);/登录页面，输入登录信息判断是否为景区用户及用户类型void loadInfoType(); /加载景点信息，景点信息的类型为 infotypevoid loadMap(); /加载道路信息void storeInfoType();/保存景点信息void storeMap();/保存道路信息三、 概要设计普通用户对景点的查询， 路线查询， 景点介绍等功能读取用户名和密码是权限判断超级管理员景点管理员开始访问磁盘中的文件， 获取已存储的信息访问成功？否结束对用户进行添加， 删除， 权限修改对景点进行添加， 删除， 修改四、 详细设计1. 加载用户信息，若用户信息文件不存在则输出错误提示void loadUser()ifstream in(user.dat);if(!in)cout 无法加载用户信息，请检查该用户信息文件是否存在 endl;return ;int i = 0;while(!in.eof()in.read(char*)&stui+, sizeof(User);user_num = i-1;in.close();2. 存储用户信息，创建.dat文件void storeUser()ofstream out(user.dat);if(!out)cout 存储用户信息出错 endl;return ;out.write(char*)stu, sizeof(User)*user_num);cout 保存成功 endl;3. 登录页面，输入用户名跟密码，判断用户名跟密码是否正确，错误则输出提示，正确则进入主菜单void print_Passwd(void)int login = -1; /标记当前登录用户的下标int flag=0;/密码正确标记char p10;/用户名char s10;/密码char num=0;/密码次数printf(请输入登录名:n); scanf(%s,p);for(i=0;iuser_num;i+)if(strcmp(stui.user_Name,p)=0)login = i;flag=1;break;if(flag=1)printf(请输入密码:n);scanf(%s,s);elseprintf(没有此用户:n);exit(0);while(strcmp(stui.user_Pass,s)!=0)num+;printf(密码错误!n);printf(请重新输入密码:n);scanf(%s,s);printf(登录成功!n);if(stulogin.weight = 0)cout 注：普通用户 endl;cmd();elseif(stulogin.weight = 1)cout 注：景点管理用户 endl;cmd2();elsecout 注：超级管理员 endl;cmd3(); 4. 添加用户，输入用户信息，用户已存在时输出错误提示void addUsers()char name10;char pwd10;int weight;int pos = -1;cout 请输入需要添加的用户名，密码，以及权限(以空格分开) endl; /权限0 是普通，1 是景点，其他都是超级cout 用户名和密码不要超过 9 位 name pwd weight;for(int i=0; iuser_num; +i)if(strcmp(stui.user_Name, name) = 0)pos = i;break;if(pos = -1)strcpy(stuuser_num.user_Name, name);strcpy(stuuser_num.user_Pass, pwd);stuuser_num.weight = weight;+user_num;cout 用户 name 创建成功 endl;elsecout 用户名 name 已经被占用 endl;5. 修改用户登录密码，将密码存储到结构体成员中代替原来的变量值void updateUser()int pos = -1;char name10;char pwd10;cout 请输入需要修改密码的用户名 name;for(int i=0; iuser_num; +i)if(strcmp(stui.user_Name, name) = 0)pos = i;break;if(pos = -1)cout 不存在该用户 endl;elsecout 请输入新密码 pwd;strcpy(stupos.user_Pass, pwd);cout 密码修改成功 endl;6. 删除用户，删除用户后，用户数量减少void deleteUser()int pos = -1;char name10;cout 请输入需要删除的用户名 name;for(int i=0; iuser_num; +i)if(strcmp(stui.user_Name, name) = 0)pos = i;break;if(pos = -1)cout 不存在该用户 endl;elseif(pos = user_num-1)-user_num;elsestrcpy(stupos.user_Name, stuuser_num-1.user_Name);strcpy(stupos.user_Pass, stuuser_num-1.user_Pass);stupos.weight = stuuser_num-1.weight;-user_num;cout 用户 name 已删除 endl;7. 添加景点，输入景点信息void addPoint()int pos = -1;char name30;char intro100;cout 请输入要加入的景点的名称，以及简介(各占一行) name intro;for(int i=0; ib.points; +i)if(strcmp(, name) = 0)pos = i;break;if(pos != -1)cout 景点名 name 已经被占用 endl;elseb.vexsb.points.num = b.points;strcpy(, name);strcpy(b.vexsb.points+.introduction, intro);cout 景点 name 已经创建 endl;8. 修改景点名称以及描述void updatePoint()int pos = -1;char name30;char intro100;cout 请输入需要更新的景点的名称 name;for(int i=0; ib.points; +i)if(strcmp(, name) = 0)pos = i;break;if(pos = -1)cout 不存在该景点 endl;elsecout 请输入该景点的新描述 intro;strcpy(roduction, intro);cout 景点信息更新成功 endl;9. 删除景点，若输入错误则输出错误信息void deletePoint()int pos = -1;char name10;cout 请输入需要删除的景点的名称 name;for(int i=0; ib.points; +i)if(strcmp(, name) = 0)pos = i;break;if(pos = -1)cout 不存在该景点 endl;elseif(pos = b.points-1)-b.points;elsestrcpy(, );strcpy(roduction, roduction);-b.points;cout 景点 name 已删除 endl;10. 添加道路信息，包括起点，终点以及距离void addRoad()int start, end, dis;start = end = dis = -1;cout 请输入起点(景点编号)，终点(景点编号)，以及它们之间的距离(用空格隔开) start end dis;if(start=b.points | start=b.points | end0)cout 起点或终点输入有误，请检查 endl;return ;if(start = end)cout 起点与终点相同，不能设置距离 endl;return;if(dis 0)cout 输入有误，距离值小于 0 ;return;b.arcsstartend.adj = dis;b.arcsendstart.adj = dis;cout 道路增加成功 endl;10. 修改道路信息void updateRoad()int start, end, dis;start = end = dis = -1;cout 请输入起点(景点编号)，终点(景点编号)，以及它们之间的距离(用空格隔开) start end dis;if(start=b.points | start=b.points | end0)cout 起点或终点输入有误，请检查 endl;return ;if(start = end)cout 起点与终点相同，不能设置距离 endl;return;if(dis 0)cout 输入有误，距离值小于 0 ;return;b.arcsstartend.adj = dis;b.arcsendstart.adj = dis;cout 道路更新成功 endl;11. 删除道路信息 void deleteRoad()int start, end;start = end = -1;cout 请输入起点的景点编号及终点的景点编号 start end;if(start=b.points | start=b.points | end0)cout 起点或终点输入有误，请检查 endl;return ;if(start = end)cout 起点与终点相同，不能设置距离 endl;return;b.arcsstartend.adj = -1;b.arcsendstart.adj = -1;cout 道路删除成功 endl;12. 利用杰克斯特拉算法算出起点到终点的最短距离void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020; while(flag) printf(请输入起始景点编号:); scanf(%d,&v0); if(v0G-points) printf(景点编号不存在!请重新输入景点编号:); scanf(%d,&v0); if(v0=0&v0points) flag=0; for(v=0;vpoints;v+) finalv=0; Dv=G-arcsv0v.adj; for(w=0;wpoints;w+) pvw=0; if(DvINFINITY) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ipoints;i+) min=INFINITY; for(w=0;wpoints;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wpoints;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xpoints;x+) pwx=pvx; pww=1; for(v=0;vpoints;v+) if(v0!=v) printf(%s,G-); for(w=0;wpoints;w+) if(pvw&w!=v0) printf(-%s,G-); t+; if(tG-points-1&v0!=v)printf( 总路线长%dmnn,Dv); 13. 查找景点，查找正确则输出景点信息，错误则输出提示void Search(MGraph *G) int k,flag=1; while(flag) printf(请输入要查询的景点编号:); scanf(%d,&k); if(kG-vexnum) printf(该景点编号不存在!请重新输入景点编号:); scanf(%d,&k); if(k=0&kvexnum) flag=0; printf(n); printf(编号 景点名称 简介 n); printf(%-4d %-16s %-56s n,G-vexsk.num,G-,G-roduction); printf(n);14. 初始化图形，接受用户输入MGraph * CreatUDN(MGraph *G) int i,j,k,w; char v120,v220; printf(请输入图的顶点数,弧数:); scanf(%d%d,&G-vexnum,&G-arcnum); printf(请输入景点的编号、名称、简介:n); for(i=0;ivexnum;i+) printf(景点编号:); scanf(%d,&G-vexs-num); printf(景点