校园导航系统的设计与实现（数据结构课程设计）_智者不惑勇者不惧

http://blog.sina.com.cn/u/2099776892

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

校园导航系统的设计与实现（数据结构课程设计）

(2011-05-26 08:36:09)

标签：

校园导航系统

c

分类：课程设计

浏览题目
题目序号：
标题：
题目描述：	功能：根据学校平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。要求： 1）学校平面图采用数据文件得到，格式自行设计； 2）采用菜单方式操作，实现求最佳路径（最短路径），即根据输入或选择的开始场所和目标场所，得到其详细最短路径； 3）交互方式实现路径的添加、删除、修改操作，并将修改后结果保存到相关文件中。
选题人数：
上传者：
上传时间：

指导老师：
返回

源代码：
#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
using namespace std;
int sizer;
typedef struct
{
int data;
int t;
int fisrt;
}Node;
typedef struct
{
string name;
int a[101];
}Position;

void initdata(Position *P)    //从文件读入学校各地点间的信息
{
ifstream f1("a.in");
int i=1,j;
f1>>sizer;
    for(i=1;i<=sizer;i++)
  f1>>P[i].name;
for(i=1;i<=sizer;i++)
  for(j=1;j<=sizer;j++)
   f1>>P[i].a[j];
}

void savedata(Position *P)//保存信息
{
    string b;
int i,j;
ofstream fout("a.in");
fout<<sizer<<endl;
for(i=1;i<=sizer;i++)
{
  if(i==0) fout<<endl;
  fout<<P[i].name<<' ';
}
fout<<endl;
    for(i=1;i<=sizer;i++)
{
  for(j=1;j<=sizer;j++)
   fout<<P[i].a[j]<<' ';
  fout<<endl;
}
fout.close();
}

//下面建立主菜单界面
int Menu()
{
int command;
cout<<"————————————————————————————————————————";
cout<<"————————————————————————————————————————";
cout<<"||                                                                            ||";
cout<<"||               .............................................                ||";
cout<<"||              ...............................................               ||";
cout<<"||              ..            欢迎使用校园导航系统           ..               ||";
cout<<"||                                                                            ||";
cout<<"||              .. 作者：09级计算机科学与技术专业一班尹智勇 ..               ||";
cout<<"||              ...............................................               ||";
cout<<"||               .............................................                ||";
cout<<"||                                                                            ||";
cout<<"||                    系统说明：您可以实现如下功能:                           ||";
cout<<"||                                                                            ||";
cout<<"||                            0 退出系统                                   ||";
cout<<"||                                                                            ||";
cout<<"||                            1 管理员系统                                ||";
cout<<"||                                                                            ||";
cout<<"||                            2 普通用户系统                             ||";
cout<<"||                                                                            ||";
cout<<"————————————————————————————————————————";
cout<<"————————————————————————————————————————"<<endl;
cout<<"请选择你要进行的操作..."<<endl;
while(cin>>command,command<0||command>2)
{
  cout<<"    输入错误！！！"<<endl;
  cout<<"    请重新输入：";
}
return command;
}

int display_1()//管理员界面
{
    int command;
    cout<<"————————————————————————————————————————";
    cout<<"————————————————————————————————————————";
    cout<<"||                                                                            ||";
    cout<<"||               .............................................                ||";
    cout<<"||              ...............................................               ||";
    cout<<"||              ..            欢迎使用校园导航系统           ..               ||";
    cout<<"||                                                                            ||";
    cout<<"||              .. 作者：09级计算机科学与技术专业一班尹智勇 ..               ||";
    cout<<"||              ...............................................               ||";
    cout<<"||               .............................................                ||";
    cout<<"||                                                                            ||";
    cout<<"||                    管理员系统说明：本系统可实现如下功能:                   ||";
    cout<<"||                           0 返回主菜单                             ||";
   cout<<"||                           1 查看俯瞰图                             ||";
    cout<<"||                           2 录入路径                                 ||";
   cout<<"||                           3 添加路径                                 ||";
   cout<<"||                           4 删除路径                                 ||";
   cout<<"||                           5 修改路径                                 ||";
    cout<<"||                           6 显示路径                                 ||";
   cout<<"||                           7 查询两点间最短路径                     ||";
    cout<<"||                                                                            ||";
   cout<<"————————————————————————————————————————";
   cout<<"————————————————————————————————————————"<<endl;
   cout<<"请选择您要进行的操作..."<<endl;
    while(cin>>command,command<0||command>7)
{
  cout<<"    输入错误！！！"<<endl;
  cout<<"    请重新输入：";
}
return command;
}

int display_2()//普通用户界面
{
int command;
    cout<<"————————————————————————————————————————";
    cout<<"————————————————————————————————————————";
    cout<<"||                                                                            ||";
    cout<<"||               .............................................                ||";
    cout<<"||              ...............................................               ||";
    cout<<"||              ..            欢迎使用校园导航系统           ..               ||";
    cout<<"||                                                                            ||";
    cout<<"||              .. 作者：09级计算机科学与技术专业一班尹智勇 ..               ||";
    cout<<"||              ...............................................               ||";
   cout<<"||               .............................................                ||";
   cout<<"||                                                                            ||";
   cout<<"||                  普通用户系统说明：您可以实现如下功能:                     ||";
    cout<<"||                                                                            ||";
    cout<<"||                            0 返回主菜单                                ||";
    cout<<"||                                                                            ||";
   cout<<"||                            1 查看简易地图                             ||";
    cout<<"||                                                                            ||";
   cout<<"||                            2 两点最短路径                             ||";
   cout<<"||                                                                            ||";
   cout<<"————————————————————————————————————————";
   cout<<"————————————————————————————————————————"<<endl;
   cout<<"请选择您要进行的操作..."<<endl;
while(cin>>command,command<0||command>2)
{
  cout<<"    输入错误！！！"<<endl;
  cout<<"    请重新输入：";
}
return command;
}

void look_up_the_map()        //////浏览平面图
{
char ch;
ifstream input("map.in");
while(input>>ch)
{
  if(ch=='.') cerr<<' ';
  else if(ch=='*') cerr<<endl;
  else cout<<ch;
}
cout<<endl;
input.close();
cout<<" 返回上级菜单请按回车键：";
getchar();getchar();
}

void fill_the_data(Position *P)          /////////重新录入路径
{
int k,i,j;
   cout<<"请输入该次录入的地点数量:"<<endl;
   cin>>k;
   sizer=k;
   for(i=1;i<=k;i++)
{
  cout<<" 请录入第"<<i<<"个地点名：";
  cin>>P[i].name;
  cout<<endl;
}
   cout<<"请以邻接矩阵的形式输入地点两两之间的距离，第i行第j列代表i地点与j地点之间的距离:"<<endl;
for(i=1;i<=k;i++)
  for(j=1;j<=k;j++)
   cin>>P[i].a[j];
savedata(P);
cout<<"         录入成功！！！"<<endl;
cout<<" 返回上级菜单请按回车键：";
getchar();getchar();

}

void add_the_data(Position *P)          ////////添加函数
{
int i;
initdata(P);
if(sizer==0) {cout<<endl;cout<<" 暂时还没有录入信息，请按回车键返回！"<<endl;getchar();getchar();}
else
{
  cout<<"请输入你需要增加的地点名："<<endl;
  cin>>P[sizer+1].name;
  cout<<"请按顺序输入该地点与其他地点之间的距离"<<endl;
  for(i=1;i<=sizer;i++)
  {
   cout<<"请输入该点到"<<P[i].name<<"的距离："<<endl;
   cin>>P[sizer+1].a[i];
   P[i].a[sizer+1]=P[sizer+1].a[i];
  }
  sizer++;
  P[i].a[sizer]=0;
  savedata(P);
  cout<<"         添加成功！！！"<<endl;
}
cout<<" 返回上级菜单请按回车键：";
getchar();getchar();
}

void delete_the_data(Position *P)   ////////////删除函数
{
string name;
int i,j,k;
    initdata(P);
    if(sizer==0) {cout<<endl;cout<<" 暂时还没有录入信息，请按回车键返回！"<<endl;getchar();getchar();}
else
{
  cout<<"请输入你要删除的地点名："<<endl;
  cin>>name;
  for(i=1;i<=sizer;i++)
   if(P[i].name==name) break;
   if(i>sizer) cout<<"     输入错误，该学校地图信息中没有该地点！";
   else
   {
    for(j=i;j<sizer;j++)
       P[j]=P[j+1];
    sizer--;
    for(k=1;k<=sizer;k++)
     for(j=i;j<=sizer;j++)
     {
      P[k].a[j]=P[k].a[j+1];
     }

    savedata(P);
    cout<<"         删除成功！！！"<<endl;
   }
}
cout<<" 返回上级菜单请按回车键：";
getchar();getchar();
}

void change_the_data(Position *P)            //////修改函数
{
    string name;
int i,j,command;
    initdata(P);
    if(sizer==0) {cout<<endl;cout<<" 暂时还没有录入信息，请按回车键返回！"<<endl;getchar();getchar();}
else
{
  cout<<"      1.修改某点到其他各点间距离"<<endl<<endl;
        cout<<"      2.修改地点名"<<endl<<endl;
        while(cin>>command,command<1||command>2)
  {
   cout<<"输入错误！！！"<<endl;
   cout<<"请重新输入：";
  }
  if(command==1)
  {
   cout<<"请输入你要修改路径的地点名：";cin>>name;
   cout<<endl;
   for(i=1;i<=sizer;i++)
    if(P[i].name==name) break;
    if(i>sizer) cout<<"     输入错误，该学校地图信息中没有该地点！";
    else
    {
     cout<<"请重新输入该点到其它点之间的距离：";
     for(j=1;j<=sizer;j++)
     {
      cin>>P[i].a[j];
      P[j].a[i]=P[i].a[j];
     }
     savedata(P);
     cout<<"         修改成功！！！"<<endl;
    }
  }
  else
  {
   cout<<"请输入你要修改的地点名：";cin>>name;
   cout<<endl;
   for(i=1;i<=sizer;i++)
    if(P[i].name==name) break;
    if(i>sizer) cout<<"     输入错误，该学校地图信息中没有该地点！";
    else
    {
     cout<<"请重新输入该地点名：";
     cin>>P[i].name;
     savedata(P);
     cout<<"         修改成功！！！"<<endl;
    }
  }
    }
cout<<" 返回上级菜单请按回车键：";
getchar();getchar();
}

void print_the_data(Position *P)            ///////显示校园各地点信息
{
int i,j;
initdata(P);
    if(sizer==0) {cout<<endl;cout<<" 暂时还没有录入信息，请按回车键返回！"<<endl;getchar();getchar();}
else
{
  cout<<"已录入地点数量："<<sizer<<" 个"<<endl;
     cout<<"所有地点名如下：";
  for(i=1;i<=sizer;i++)
  {
   if(i==0) cout<<endl;
   cout<<P[i].name<<' ';
  }
  cout<<endl;
  for(i=1;i<=sizer;i++)
  {
   for(j=1;j<=sizer;j++)
    cout<<P[i].a[j]<<' ';
   cout<<endl;
  }
}
cout<<" 返回上级菜单请按回车键：";
   getchar();getchar();
}

void f(int n,int i,Position *P,Node *c )        ////递归输出最佳路径
{
if(i==n)
{
  cout<<P[i].name<<" ";
  return ;
}
f(n,c[i].fisrt,P,c);
cout<<P[i].name<<" ";
}

int fun(Node c[])                      //////寻找最小值
{
    int min=9999,i,k=-1;
for(i=1;i<sizer;i++)
  if(c[i].t==1 &&c[i].data<min) {min=c[i].data;k=i;}
  return k;
}

void compute_distance(Position *P)   ///////求最短路径
{
    initdata(P);
    string name1,name2;
int i,j,n,max=9999,k;
Node c[101];
for(i=1;i<=sizer;i++)
{
  c[i].data=max;
  c[i].t=1;
}
cout<<"请输入你要查询的起始位置：";cin>>name1;
cout<<endl;
cout<<"请输入你要查询的终点位置：";cin>>name2;
for(i=1;i<=sizer;i++)
  if(P[i].name==name1) {n=i; c[i].t=0;c[i].fisrt=n;break;}
  if(i>sizer) cout<<"     输入错误，该学校地图信息中没有该地点！";
  else
  {
   for(j=1;j<=sizer;j++)
    if(P[i].a[j]!=0)
    {
     c[j].data=P[i].a[j];
     c[j].fisrt=i;
    }
    int pp=0;
    while(1)
    {
     k=fun(c);
     if(k==-1) break;
     c[k].t=0;
     for(i=1;i<=sizer;i++)
      if(P[k].a[i]!=0 && (P[k].a[i]+c[k].data<c[i].data) )
      {
       c[i].data=P[k].a[i]+c[k].data;
       c[i].fisrt=k;
      }
    }
    for(i=1;i<=sizer;i++)
     if(P[i].name==name2)
     {
      cout<<name1<<"到"<<name2<<"最短路径依次经过的地点为: ";
      f(n,i,P,c);
      cout<<endl;
      cout<<"路径距离为：";
      if(c[i].data==9999)
       cout<<'0'<<endl;
      else cout<<c[i].data<<endl;
      break;
     }
  }
  cout<<" 返回上级菜单请按回车键：";
  getchar();getchar();
}

void main()
{
int command,t1,t2;
string zh,mm;
Position *P=new Position[101];
system("color 2b");
while(1)
{
  command=Menu();
  if(command==1)
  {
   while(1)
   {
    cout<<"请输入账号："<<endl;cin>>zh;
    cout<<"请输入密码："<<endl;cin>>mm;
    if(zh=="0"&&mm=="0") break;
    else cout<<"账号或密码错误，请重新输入..."<<endl;
   }
   system("cls");
   t1=0;
   while(t1==0)
   {
    command=display_1();
    switch(command)
    {
    case 0:t1=1;break;
    case 1:look_up_the_map();system("cls");break;
    case 2:fill_the_data(P);system("cls");break;
    case 3:add_the_data(P);system("cls");break;
    case 4:delete_the_data(P);system("cls");break;
    case 5:change_the_data(P);system("cls");break;
    case 6:print_the_data(P);system("cls");break;
    case 7:compute_distance(P);system("cls");break;
    }
   }

  }
  else if(command==2)
  {
   while(1)
   {
    cout<<"请输入账号："<<endl;cin>>zh;
    cout<<"请输入密码："<<endl;cin>>mm;
    if(zh=="0"&&mm=="0") break;
    else cout<<"账号或密码错误，请重新输入..."<<endl;
   }
            system("cls");
   t2=0;
   while(t2==0)
   {
    command=display_2();
    switch(command)
    {
    case 0:t2=1;break;
    case 1:look_up_the_map();system("cls");break;
    case 2:compute_distance(P);system("cls");break;
    }
   }

  }
  else break;
}
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：[转载]来点雅的

后一篇：钓鱼记

新浪BLOG意见反馈留言板　欢迎批评指正

校园导航系统的设计与实现（数据结构课程设计）

校园导航系统

c

浏览题目