#include <stdio.h> #include <string.h> #include <alloc.h>

struct Route { char from[16]; char to[16]; int flag; }; typedef struct Route ROUTE;

char **stack_temp; int top=-1; int F=0;

void showroute(char **str1); void push(char **str1,char* str2); void pop(char **str1); int find(ROUTE ** rou,char * str,int v); int main() { int N,V; /*前一个为city个数,后一个为航线个数*/ int i,j; char city[2][16];/*用于储存最西及最东的city */ /*char **stack_temp;*//* **stack_end; */ ROUTE ** route; ROUTE * Rptr;

while(scanf("%d%d",&N,&V)!=EOF) { stack_temp=(char **)malloc((N+1)*sizeof(char *)); /* stack_end=(char **)malloc((N+1)*sizeof(char *)); */ route=(ROUTE **)malloc(V*sizeof(ROUTE *));

for(i=0;i<=N;i++) { stack_temp[i]=(char *)malloc(16*sizeof(char )); /* stack_end[i]=(char *)malloc(16*sizeof(char )); */ } /*建立两个大小为char型 (N+1)*15的空间*/ scanf("%s",city[0]); for(i=1;i<N;i++) { scanf("%s",city[1]); } /*读入最西及最东的城市*/

for(j=0;j<V;j++) { route[j]=(ROUTE *)malloc(sizeof( ROUTE )); scanf("%s%s",route[j]->from,route[j]->to); route[j]->flag=1; } /*建一个航班库*/ /* strcpy(stack_temp[top],city[0]); */ push(stack_temp,city[0]);

while(1) { if(!strcmp(stack_temp[top],city[0])&&F)break; if(!strcmp(stack_temp[top],city[1]))F=1; if(!find(route,stack_temp[top],V))break;

} /*注意为了让你看清程序，该程式没有回溯 */

if(!strcmp(stack_temp[top],city[0])&&top) { printf("%d\n",N); printf("%d\n",top); showroute(stack_temp); } else { printf("%d\n",N); printf("NO SOLUTION\n"); }

for(i=0;i<N;i++)free(stack_temp[i]); free(stack_temp); for(j=0;j<V;j++)free(route[j]); free(route); top=-1; F=0; } } void push(char **str1,char* str2) { ++top; strcpy(str1[top],str2); } void pop(char **str1) { str1[top][0]='\0'; --top; } int find(ROUTE ** rou,char * str,int v) { int i; if(!F) { for(i=0;i<v;i++)

{

if(!(strcmp(str,rou[i]->from))&&rou[i]->flag==1) { rou[i]->flag=-1; push(stack_temp,rou[i]->to); return 1; } } } else { for(i=0;i<v;i++)

{

if(!(strcmp(str,rou[i]->to))&&rou[i]->flag==1) { rou[i]->flag=-1; push(stack_temp,rou[i]->from); return 1; } } }

return 0; } void showroute(char **str1) { int i=0;

while(i<top)printf("%s\n",str1[i++]); printf("%s\n",str1[i]);

}

你的问题不用回溯啊？要回溯自己改吧^_^

还有，top还控制在N之内，回溯你可以利用flag来做。不过你给的例子是不需要的^_^

测试方法:

1.编译后得,如:test.exe

2.将测试例子存为 in.dat

3. dos下,执行: test < in.dat

#include<string> #include<iostream> #include<fstream> #include<vector> using namespace std;

void travel(int m1d[],int visited[],int i,int n,vector<int> &store) { store.push_back(i); //当前访问的城市压入向量 visited[i]=1; //访问过的赋1

int **matrix=new int*[n]; for(int k=0; k<n; k++) matrix[k]=new int[n]; for(k=0; k<n; k++) { for(int l=0; l<n; l++) { matrix[k][l]=m1d[k*n+l]; //一维转二维 //cout<<matrix[k][l]<<" "; } //cout<<endl; }

//判断当前城市是否有与其连通的城市 int pass=0; for(int s=0; s<n; s++) if(matrix[i][s]!=0&&!visited[s]) pass=1;

if(pass==0) store.pop_back(); //若已经没有去路，不要用此航线

//判断整条航线能否回到入口城市 static int end=0; if(i==0) end=1;

//关键循环，递归算法精华所在 for(int j=0; j<n; j++) if(matrix[i][j]!=0&&!visited[j]) { for(k=0; k<n; k++) for(int l=0; l<n; l++) m1d[k*n+l]=matrix[k][l]; //二维转一维

//关键是这里，加一个判断，怎么加，晕~~~

travel(m1d,visited,j,n,store); } //清除临时申请的内存 for(k=0; k<n; k++) delete[] matrix[k]; delete[] matrix;

//若最后不能回到入口城市，退出 if(end==0) { cout<<"No Solution"<<endl; exit(0); } }

void main() { int N,V;

fstream file1; file1.open("E:\\travel.txt"); file1>>N>>V; //读取城市数和航线数 V*=2; //每条航线有两个城市(起点，终点)

string *city=new string[N]; string *route=new string[V];

for(int i=0;i<N;i++) file1>>city[i]; //读取城市名

int start=-1; for(int j=0;j<V;j++) { file1>>route[j]; //读取航线，双数是起点，单数是终点 if(j%2==0&&start!=0) //判断入口起点航班是否存在 start=city[0].compare(route[j]); }

file1.close();

if(start!=0) //若入口起点航班不存在就退出 { cout<<N<<endl; cout<<"NO SOLUTION"<<endl; exit(0); } //用int类型二维数组储存航班路线 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

for(i=0; i<N; i++) for(j=0;j<N;j++) connect[i][j]=0;

//读取当前航线的起点和终点的城市名，连通的数组元素就赋1 for(int k=0; k<V; k+=2) { for(i=0; i<N; i++) if(!(route[k].compare(city[i]))) break; for(j=0; j<N; j++) if(!(route[k+1].compare(city[j]))) break;

connect[i][j]=connect[j][i]=1; }

int *c1d=new int[N*N];

//把图输出一次，输出的同时把值传给一维数组 for(i=0; i<N; i++) { for(j=0; j<N; j++) { //cout<<connect[i][j]<<" "; c1d[i*N+j]=connect[i][j]; //二维数组转一维数组 } //cout<<endl; }

//定义一个变量作访问标记 int *visited=new int[N]; for(i=0; i<N; i++) visited[i]=0;

vector<int> store; //定义向量储存结果路径

travel(c1d,visited,0,N,store); //传递一维数组c1d

//按题目要求输出到屏幕 cout<<N<<endl; vector<int>::iterator pointer; for(pointer=store.begin(); pointer!=store.end(); pointer++) cout<<city[*pointer]<<endl;

//清除刚才申请的所有动态数组用到的内存 delete[] visited; for(i=0; i<N; i++) delete[] connect[i]; delete[] connect; delete[] route; delete[] city; }

[此贴子已经被作者于2004-11-24 00:50:46编辑过]