算法与数据结构设计报告

算法与数据结构设计报告

（ 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);//主菜单页面调用函数

MGraphInitGraph(void);//初始化地图

void Menu(void);//主菜单界面

void Browser(MGraph *G);//浏览景点

void ShortestPath_DIJ(MGraph * G);// 迪杰斯特拉算法计算出起点到各个顶点之间的最短路径

void Floyd(MGraph *G);//计算两景点间的总路线长

void Search(MGraph *G);//查找景点并输出景点信息

intLocateVex(MGraph *G,char* v);//

MGraph * CreatUDN(MGraph *G);//初始化图形，接受用户输入 void print(MGraph *G);//输出地图信息

void print_Passwd(void);//登录页面，输入登录信息判断是否为景区用户及用户类型

void loadInfoType(); //加载景点信息，景点信息的类型为 infotype void loadMap(); //加载道路信息

void storeInfoType();//保存景点信息

void storeMap();//保存道路信息

三、 概要设计

开始

访问磁盘中的文件， 获取已存储 的信息

访问成功？

否

是

读取用户名和密码

超级管理 员

权限判断

景点管理员

普通用户

对景点的查询， 路线 对用户进行添加， 删除， 权限修改 查询， 景点介绍等功 能

对景点进行 添加， 删 除， 修改

结束

四、 详细设计

1. 加载用户信息，若用户信息文件不存在则输出错误提示

voidloadUser()

{

ifstream in("user.dat");

if(!in)

{

} cout<<"无法加载用户信息，请检查该用户信息文件是否存在" <<endl; return ; } inti = 0; while(!in.eof()) { in.read((char*)&stu[i++], sizeof(User)); } user_num = i-1; in.close();

2. 存储用户信息，创建.dat文件

voidstoreUser()

{

ofstream out("user.dat");

if(!out)

{

cout<<"存储用户信息出错" <<endl;

return ;

}

out.write((char*)stu, sizeof(User)*user_num);

cout<<"保存成功" <<endl;

}

3. 登录页面，输入用户名跟密码，判断用户名跟密码是否正确，错误则输出提示，正确则进入主菜单

voidprint_Passwd(void)

{

int login = -1; //标记当前登录用户的下标 int flag=0;//密码正确标记 char p[10];//用户名 char s[10];//密码

char num=0;//密码次数 printf("请输入登录名:\n"); scanf("%s",p); for(i=0;i<user_num;i++) { if(strcmp(stu[i].user_Name,p)==0) { login = i; flag=1; break; } } if(flag==1) { printf("请输入密码:\n"); scanf("%s",s); } else { printf("没有此用户:\n"); exit(0); } while(strcmp(stu[i].user_Pass,s)!=0) { num++; } printf("密码错误!\n"); printf("请重新输入密码:\n"); scanf("%s",s); printf("登录成功!\n"); if(stu[login].weight == 0) { cout<<"注：普通用户" <<endl; cmd(); } else

}

} if(stu[login].weight == 1) { cout<<"注：景点管理用户" <<endl; cmd2(); } else { } cout<<"注：超级管理员" <<endl; cmd3();

4. 添加用户，输入用户信息，用户已存在时输出错误提示

voidaddUsers()

{

char name[10];

charpwd[10];

int weight;

intpos = -1;

cout<<"请输入需要添加的用户名，密码，以及权限(以空格分开)" <<endl; //权限0 是普通，1 是景点，其他都是超级

cout<<"用户名和密码不要超过 9 位" <<endl;

cin>>name >>pwd>>weight;

for(inti=0; i<user_num; ++i)

{

if(strcmp(stu[i].user_Name, name) == 0)

{

pos = i;

break;

}

}

if(pos == -1)

{

strcpy(stu[user_num].user_Name, name);

strcpy(stu[user_num].user_Pass, pwd);

stu[user_num].weight = weight;

++user_num;

cout<<"用户 " <<name <<" 创建成功" <<endl;

} else { cout<<"用户名 " <<name <<" 已经被占用" <<endl; }

5. 修改用户登录密码，将密码存储到结构体成员中代替原来的变量值

voidupdateUser()

{

intpos = -1;

char name[10];

charpwd[10];

cout<<"请输入需要修改密码的用户名" <<endl;

cin>>name;

for(inti=0; i<user_num; ++i)

{

if(strcmp(stu[i].user_Name, name) == 0)

{

pos = i;

break;

}

}

if(pos == -1)

{

cout<<"不存在该用户" <<endl;

}

else

{

cout<<"请输入新密码" <<endl;

cin>>pwd;

strcpy(stu[pos].user_Pass, pwd);

cout<<"密码修改成功" <<endl;

}

}

6. 删除用户，删除用户后，用户数量减少

voiddeleteUser()

{

intpos = -1;

char name[10];

cout<<"请输入需要删除的用户名" <<endl;

} for(inti=0; i<user_num; ++i) { if(strcmp(stu[i].user_Name, name) == 0) { pos = i; break; } } if(pos == -1) { cout<<"不存在该用户" <<endl; } else { if(pos == user_num-1) { --user_num; } else { strcpy(stu[pos].user_Name, stu[user_num-1].user_Name); strcpy(stu[pos].user_Pass, stu[user_num-1].user_Pass); stu[pos].weight = stu[user_num-1].weight; --user_num; } cout<<"用户 " <<name <<" 已删除" <<endl; }

7. 添加景点，输入景点信息

voidaddPoint()

{

intpos = -1;

char name[30];

char intro[100];

cout<<"请输入要加入的景点的名称，以及简介(各占一行)" <<endl;

cin>>name >>intro;

for(inti=0; i<b.points; ++i)

{

if(strcmp(b.vexs[i].name, name) == 0)

{

pos = i;

} } } if(pos != -1) { cout<<"景点名 " <<name <<" 已经被占用" <<endl; } else { b.vexs[b.points].num = b.points; strcpy(b.vexs[b.points].name, name); strcpy(b.vexs[b.points++].introduction, intro); cout<<"景点 " <<name << " 已经创建" <<endl; }

8. 修改景点名称以及描述

voidupdatePoint()

{

intpos = -1;

char name[30];

char intro[100];

cout<<"请输入需要更新的景点的名称" <<endl;

cin>>name;

for(inti=0; i<b.points; ++i)

{

if(strcmp(b.vexs[i].name, name) == 0)

{

pos = i;

break;

}

}

if(pos == -1)

{

cout<<"不存在该景点" <<endl;

}

else

{

cout<<"请输入该景点的新描述" <<endl;

cin>>intro;

strcpy(b.vexs[pos].introduction, intro);

cout<<"景点信息更新成功" <<endl;

}

}

9. 删除景点，若输入错误则输出错误信息

voiddeletePoint()

{

intpos = -1;

char name[10];

cout<<"请输入需要删除的景点的名称" <<endl;

cin>>name;

for(inti=0; i<b.points; ++i)

{

if(strcmp(b.vexs[i].name, name) == 0)

{

pos = i;

break;

}

}

if(pos == -1)

{

cout<<"不存在该景点" <<endl;

}

else

{

if(pos == b.points-1)

{

--b.points;

}

else

{

strcpy(b.vexs[pos].name, b.vexs[b.points-1].name);

strcpy(b.vexs[pos].introduction, b.vexs[b.points-1].introduction); --b.points;

}

cout<<"景点 " <<name <<" 已删除" <<endl;

}

}

10.添加道路信息，包括起点，终点以及距离

voidaddRoad()

{

int start, end, dis;

start = end = dis = -1;

cout<<"请输入起点(景点编号)，终点(景点编号)，以及它们之间的距离(用空格隔开)" <<endl;

cin>>start >>end >>dis;

if(start>=b.points || start<0 || end>=b.points || end<0)

{

cout<<"起点或终点输入有误，请检查" <<endl;

return ;

}

if(start == end)

{

cout<<"起点与终点相同，不能设置距离" <<endl;

return;

}

if(dis < 0)

{

cout<<"输入有误，距离值小于 0 ";

return;

}

b.arcs[start][end].adj = dis;

b.arcs[end][start].adj = dis;

cout<<"道路增加成功" <<endl;

}

10. 修改道路信息

voidupdateRoad()

{

int start, end, dis;

start = end = dis = -1;

cout<<"请输入起点(景点编号)，终点(景点编号)，以及它们之间的距离(用空格隔开)" <<endl;

cin>>start >>end >>dis;

if(start>=b.points || start<0 || end>=b.points || end<0)

{

cout<<"起点或终点输入有误，请检查" <<endl;

return ;

}

if(start == end)

{

cout<<"起点与终点相同，不能设置距离" <<endl;

return;

}

if(dis < 0)

} { cout<<"输入有误，距离值小于 0 "; return; } b.arcs[start][end].adj = dis; b.arcs[end][start].adj = dis; cout<<"道路更新成功" <<endl;

11. 删除道路信息

voiddeleteRoad()

{

int start, end;

start = end = -1;

cout<<"请输入起点的景点编号及终点的景点编号" <<endl;

cin>>start >>end;

if(start>=b.points || start<0 || end>=b.points || end<0)

{

cout<<"起点或终点输入有误，请检查" <<endl;

return ;

}

if(start == end)

{

cout<<"起点与终点相同，不能设置距离" <<endl;

return;

}

b.arcs[start][end].adj = -1;

b.arcs[end][start].adj = -1;

cout<<"道路删除成功" <<endl;

}

12. 利用杰克斯特拉算法算出起点到终点的最短距离

voidShortestPath_DIJ(MGraph * G)

{

intv,w,i,min,t=0,x,flag=1,v0;

int final[20], D[20], p[20][20];

while(flag)

{

printf("请输入起始景点编号:");

scanf("%d",&v0);

if(v0<0||v0>G->points)

{

printf("景点编号不存在!请重新输入景点编号:");

scanf("%d",&v0);

}

if(v0>=0&&v0<G->points)

flag=0;

}

for(v=0;v<G->points;v++)

{

final[v]=0;

D[v]=G->arcs[v0][v].adj;

for(w=0;w<G->points;w++)

p[v][w]=0;

if(D[v]<INFINITY)

{

p[v][v0]=1;p[v][v]=1;

}

}

D[v0]=0;final[v0]=1;

for(i=1;i<G->points;i++)

{

min=INFINITY;

for(w=0;w<G->points;w++)

if(!final[w])

if(D[w]<min){v=w;min=D[w];}

final[v]=1;

for(w=0;w<G->points;w++)

if(!final[w]&&(min+G->arcs[v][w].adj<D[w]))

{

D[w]=min+G->arcs[v][w].adj;

for(x=0;x<G->points;x++)

p[w][x]=p[v][x];

p[w][w]=1;

}

}

for(v=0;v<G->points;v++)

{

if(v0!=v) printf("%s",G->vexs[v0].name);

for(w=0;w<G->points;w++)

{

if(p[v][w]&&w!=v0) printf("-->%s",G->vexs[w].name);

t++;

}

if(t>G->points-1&&v0!=v)printf(" 总路线长%dm\n\n",D[v]);

}

}

13. 查找景点，查找正确则输出景点信息，错误则输出提示

void Search(MGraph *G)

{

intk,flag=1;

while(flag)

{

printf("请输入要查询的景点编号:");

scanf("%d",&k);

if(k<0||k>G->vexnum)

{

printf("该景点编号不存在!请重新输入景点编号:");

scanf("%d",&k);

}

if(k>=0&&k<G->vexnum)

flag=0;

}

printf("\n");

printf("编号景点名称

\n");

printf("%-4d %-16s

\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);

printf("\n");

}

14.初始化图形，接受用户输入

MGraph * CreatUDN(MGraph *G)

{

inti,j,k,w;

char v1[20],v2[20];

printf("请输入图的顶点数,弧数:");

scanf("%d%d",&G->vexnum,&G->arcnum);

printf("请输入景点的编号、名称、简介:\n");

for(i=0;i<G->vexnum;i++)

{

printf("景点编号:"); 简介%-56s

scanf("%d",&G->vexs->num);

printf("景点名称:");

scanf("%s",G->vexs[i].name);

printf("景点简介:");

scanf("%s",G->vexs->introduction);

}

for(i=0;i<G->vexnum;i++)

for(j=0;j<G->vexnum;j++)

G->arcs[i][j].adj=INFINITY;

printf("请输入路径长度:\n");

for(k=0;k<G->arcnum;k++)

{

printf("第%d条边:\n",k+1);

printf("景点对(x,y):");

scanf("%s",v1);

scanf("%s",v2);

printf("路径长度:");

scanf("%d",&w);

i=LocateVex(G,v1);

j=LocateVex(G,v2);

if(i>=0&&j>=0)

{

G->arcs[i][j].adj=w;

G->arcs[j][i]=G->arcs[i][j];

}

}

return G;

}

五、 测试数据及其结果分析

六、 调试过程中的问题

１. 在设计登录用户时不知道如何才能跟已存入用户信息进行比较，老是出现错误。

２.

２.在求最短路径时不知道用什么算法，开始运用比较大小的算法算时出现很多错误。

３. 文件操作方法使用错误，导致文件访问老是出现错误，输出错误提示。

七、 总结

刚一开始看到这个实验时感觉整个人都要懵了，不知道从何开始。于是疯狂地浏览网上资料，在论坛上求助。终于，有了一点头绪，于是开始自己慢慢地敲。第一次敲那么长的代码，感觉整个人都头昏眼花了，不过在这个过程中，既培养了我的耐心，也大大地提高了我的编程能力以及对Ｃ＋＋中各种方法操作的理解与运用，比如文件操作，各种字符串的方法使用。觉得这个过程中比较有价值的还有学会了迪杰斯特拉算法这一比较经典的算法。不管怎样，在这个实验过程中我的收获很大，不管在编程这方面还是耐性这方面，都有了许多的提高。

本文来源：https://www.bwwdw.com/article/8fvq.html