📄 校园导游图.cpp
字号:
template<class T>
stacklist<T>::stacklist(const stacklist<T> & v)
:data(v.data){}
template<class T>
void stacklist<T>::deleteallvalues()
{
data.deleteallvalues();
}
template<class T>
T stacklist<T>::pop()
{
//弹出并返回表首元素
assert(!isempty());
T result=data.firstelement();
//从表中移出元素
data.removefirst();
return result;
}
template<class T>
T stacklist<T>::top()const
{
assert(!isempty());
return (data.firstelement());
}
template<class T>
int stacklist<T>::isempty()const
{
return (data.isempty());
}
template<class T>
void stacklist<T>::push(T val)
{
data.add(val);
}
//***********************************************************************listiterator
template<class T>class listiterator:public iterator<T>
{
public:
listiterator(list<T>& );
virtual int init(); //初始化游标
virtual int operator!();
virtual T operator()();
virtual int operator++(); //只有该操作能改变游标指向
virtual void operator=(T);
void removecurrent(); //删除当前结点
void addbefore(T); //在当前结点前插入
void addafter(T); //在当前结点后插入
protected:
link<T> * currentlink; //遍历中的游标（指针）
link<T> * previouslink; //遍历中的前驱游标（指针）
list<T>& thelist; //引用一个表
};
//-----------------------------------------------------------------------
template<class T>listiterator<T>::listiterator(list<T>& alist):thelist(alist)
{
init();
}
//------------------------------------------------------------------------
template<class T>int listiterator<T>::init()
{
previouslink=0;
currentlink=thelist.ptrtofirstlink;
return currentlink!=0;
}
//--------------------------------------------------------
template<class T>int listiterator<T>::operator!()
{
if(currentlink!=0)
return 1;
if(previouslink!=0)
return previouslink->ptrtonextlink!=0;
return thelist.ptrtofirstlink!=0;
}
//------------------------------------------------------------------
template<class T>T listiterator<T>::operator()(){
if (currentlink!=NULL) return currentlink->value;
else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
return previouslink->ptrtonextlink->value;
else if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
return thelist.ptrtofirstlink->value;
assert(previouslink!=NULL&&previouslink->ptrtonextlink
!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
//return 1;
}
//----------------------------------------------------------------------------
template<class T>int listiterator<T>::operator++()
{
if(currentlink==0)
{
if(previouslink==0)
currentlink=thelist.ptrtofirstlink;
else
currentlink=previouslink->ptrtonextlink;
}
else
{
previouslink=currentlink;
currentlink=currentlink->ptrtonextlink;
}
return currentlink!=0;
}
//---------------------------------------------------------------
template<class T> void listiterator<T>::operator=(T val){
if (currentlink!=NULL)
{
currentlink->value=val; return;
}
else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
previouslink->ptrtonextlink->value=val;return;
if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
thelist.ptrtofirstlink->value=val; return ;
assert(previouslink!=NULL&&previouslink->ptrtonextlink
!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}
//-------------------------------------------------------//删除当前结点
template<class T>void listiterator<T>::removecurrent()
{
link<T> *p;
if (currentlink!=NULL) {
if (previouslink==NULL)
thelist.ptrtofirstlink=currentlink->ptrtonextlink;
else previouslink->ptrtonextlink=currentlink->ptrtonextlink;
delete currentlink; currentlink=0;
return;
}
else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL){
p=previouslink->ptrtonextlink;
previouslink->ptrtonextlink=p->ptrtonextlink;
delete p; return ;
}
else
if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL){
p=thelist.ptrtofirstlink;
thelist.ptrtofirstlink=p->ptrtonextlink;
delete p;
return ;
}
assert(previousLink!=NULL&&previousLink->ptrToNextLink!=NULL
||previousLink==NULL&&theList.ptrToFirstLink!=NULL);
}
//-----------------------------------------------------------
template<class T>void listiterator<T>::addbefore(T val)
{
if(previouslink)
previouslink=previouslink->insert(val);
else
{
thelist.list<T>::add(val);
previouslink=thelist.ptrtofirstlink;
}
}
//-----------------------------------------------------------------
template<class T>
void listiterator<T>::addafter(T val){
//当前结点非空，在当前结点后插入
if (currentlink!=NULL)
currentlink->insert(val);
else if (previouslink!=NULL)
//当前结点空，但前驱非空
if (previouslink->ptrtonextlink!=NULL)
//前的后继非空，在前驱的后继结点后插入
previouslink->ptrtonextlink->insert(val);
else previouslink->insert(val);
else if (thelist.ptrtofirstlink)//表非空，在第一个结点后插入
thelist.ptrtofirstlink-> insert(val);
else thelist.add(val);
//表空，作为第一个结点插入
}
//*********************************************************排序表
template<class T>class orderedlist:public list<T>
{public:
void add(T value);
};
template<class T>void orderedlist<T>::add(T value)
{
if(ptrtofirstlink==0||value<firstelement())
{this->list<T>::add(value);
return;
}
listiterator<T>itr(*this);
for(itr.init();!itr;++itr)
if(value<itr())
{itr.addbefore(value);
return;
}
itr.addbefore(value);
}
//******************************************************************************* typedef
typedef struct {
int VerCode;
string VerName;
string InsInfo;
double x,y;
}VerType;
//******************************************************************************vertex
template<class T>class vertex
{
public:
vertex();
vertex(T init);
void addarc(vertex<T>&);
T value;
list<vertex<T>&> arcs;
// setlist<vertex<T>&>arcs;
};
template<class T>vertex<T>::vertex()
{
arcs.deleteallvalues();
}
template<class T>vertex<T>::vertex(T init):value(init){}
//******************************************************************warshall
void warshall(double g[9][9])
{
int i,j,m;
for(m=0;m<9;m++)
for(i=0;i<9;i++)
for(j=0;j<9;j++)
g[i][j]=g[i][j]||g[i][m]&&g[m][j];
}
//****************************************************************floyd
void floyd(double g[9][9])
{
int i,j,m;
double newlen;
for(m=0;m<9;m++)
for(i=0;i<9;i++)
for(j=0;j<9;j++){
newlen=g[i][m]+g[m][j];
if(newlen<g[i][j])
g[i][j]=newlen;
}
}
//****************************************************************floyd1
void floyd1(double g[9][9],unsigned p[9][9])
{
int i,j,m;
double newlen;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
p[i][j]=g[i][j]<20?i:-1;
for(m=0;m<9;m++)
for(i=0;i<9;i++)
for(j=0;j<9;j++){
newlen=g[i][m]+g[m][j];
if(newlen<g[i][j]){
g[i][j]=newlen;
p[i][j]=p[m][j];
}
}
}
//*****************************************************************main()
void main(){
char fn[10];
unsigned n,i,j;
cout<<"请输入文件名(默认为g2.dat)：";
cin>>fn;
ifstream fin(fn); //文件读入
if(!fin)
cout<<"File open Error!"<<endl;
fin>>n;
//--------------------------------------------------------
//用二位数组实现原来路径矩阵：
double g[9][9]={
{0, 5, 5, 1000, 1000, 7.8, 1000, 1000, 8.1},
{5, 0, 7.1, 1000 , 1000 , 6, 1000, 1000, 1000},
{5, 7.1, 0, 7.1, 2.2, 5.1, 1000, 000, 4.5},
{1000, 1000, 7.1, 0, 1000, 4, 8, 1000 , 1000},
{1000, 1000, 2.2, 1000, 0, 6.1, 3.6, 1000, 3},
{7.8, 6, 5.1, 4, 6.1, 0, 1000, 1000, 1000},
{10, 1000, 1000, 8, 3.6, 1000, 0, 2.2, 3.2},
{1000, 1000, 1000, 1000, 1000, 1000, 2.2, 0, 2.2},
{8.1, 1000, 4.5, 1000 , 3, 1000, 3.2, 2.2, 0}
};
unsigned p[9][9]={
{0, 0 , 0 , -1 , -1 , 0 , -1, -1 , 0},
{1, 1, 1, -1, -1, 1, -1 , -1, -1},
{2 , 2 , 2 , 2, 2 , 2, -1 , -1 , 2},
{-1 , -1, 3 , 3, -1 , 3, 3 , -1, -1},
{-1 , -1, 4 , -1 , 4 , 4 , 4 , -1, 4},
{ 5 , 5, 5 , 5, 5 , 5, -1 , -1, -1},
{ 6 , -1, -1, 6 , 6 , -1 , 6 , 6, 6},
{-1 , -1 , -1 , -1 , -1, -1 , 7 , 7 , 7},
{8 , -1 , 8 , -1 , 8 , -1 , 8 , 8 , 8}
};
//--------------------------------------------------------
VerType name[1000];
for(i=0;i<n;i++){
fin>>name[i].VerCode;
fin>>name[i].VerName;
fin>>name[i].x;
fin>>name[i].y;
fin>>name[i].InsInfo;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++)
fin>>p[i][j];
}
//---------------------------------------------------------
cout<<"原来的相邻矩阵g:"<<endl;
for(i=0;i<9;i++){
for(j=0;j<9;j++)
cout<<g[i][j]<<" ";cout<<endl;
}
cout<<"原来的路径矩阵p:"<<endl;
for(i=0;i<9;i++){
for(j=0;j<9;j++)
cout<<p[i][j]<<" ";cout<<endl;
}
floyd1(g,p);
cout<<"连通的相邻矩阵g:"<<endl;
for(i=0;i<9;i++){
for(j=0;j<9;j++)
cout<<g[i][j]<<" ";cout<<endl;
}
cout<<"连通的路径矩阵p:"<<endl;
for(i=0;i<9;i++){
for(j=0;j<9;j++)
cout<<p[i][j]<<" ";cout<<endl;
}
//-------------------------------------------------------------------------------
cout<<"*校园导游查询系统*"<<endl;
cout<<"地址编号: 0 --------- 校门(文化路入口)"<<endl;
cout<<"地址编号: 1 --------- 行政楼(行政报告大楼)"<<endl;
cout<<"地址编号: 2 --------- 学博楼(第一教学大楼)"<<endl;
cout<<"地址编号: 3 --------- 学渊楼(第二教学大楼)"<<endl;
cout<<"地址编号: 4 --------- 学思楼(现代教育技术中心)"<<endl;
cout<<"地址编号: 5 --------- 图书馆(图书馆及计算中心、网络中心)"<<endl;
cout<<"地址编号: 6 --------- 美食城(财院食堂)"<<endl;
cout<<"地址编号: 7 --------- 学生宿舍(学生宿舍1-4号楼)"<<endl;
cout<<"地址编号: 8 --------- 运动场(风雨球场)"<<endl;
//-------------------------------------------------------------------------------
unsigned start,end;
char yo;
cout<<"请输入起点与终点地址编号: "<<endl;
do{
cout<<"请输入起点地点编号:"; cin>>start;
cout<<"请输入终点地点编号:"; cin>>end;
if(start==end){
cout<<"地点编号: "<<name[start].VerCode<<endl;
cout<<"地点名称: "<<name[start].VerName<<endl;
cout<<"说明: "<<name[start].InsInfo<<endl;
}
else{
unsigned a[9];
cout<<endl<<"路线:"<<endl<<name[start].VerName<<"->";
for(i=1;i<9;i++)
{
a[0]=p[start][end];
a[i]=p[start][a[i-1]];
}
for(int i=8;i>=0;i--)
{
if(a[i]!=start)
cout<<name[a[i]].VerName<<"->";
}
cout<<name[end].VerName;
}
cout<<endl<<"从"<<name[start].VerName<<"到"<<name[end].VerName<<"的最短路径是: "
<<g[start][end]<<endl;
//-------------------------------------------------------------------------------
cout<<endl<<"是否继续查询?(y/n):";cin>>yo;
}while(yo=='y');
cout<<endl;
cout<<"谢谢您的使用!欢迎下次再来我校，再为你服务!拜拜!"<<endl;
}
/* else{//不同则查询最短路径
//.................
//输出从起点到终点经过的所有景点
cout<<"路线:"<<name[start].VerName<<"->"<<name[p[start][end]].VerName
<<"->"<<name[end].VerName;
cout<<"从"<<name[start].VerName<<"到"<<name[end].VerName<<"的最短路径是: "<<g[start][end]<<endl;
}
else{
cout<<"路线:"<<name[start].VerName<<"->";
unsigned t=p[start][end],t1=end;
end=p[start][end];
if(end!=start)
// cout<<name[p[start][end]].VerName<<"->";
cout<<name[p[start][end]].VerName<<"->"<<name[t].VerName<<"->"<<name[t1].VerName;
cout<<"从"<<name[start].VerName<<"到"<<name[end].VerName<<"的最短路径是: "<<g[start][end]<<endl;
}*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -