一道面试题,求教~!

Question

题目:
已知    A B 互通
        C D 互通
        F E 互通
        B D 互通
        C E 互通
        用C++ 写出程序 ,求A-F的路线- -...我的想法是直接求向量.ab+bd=ad,ad+dc=ac,ac+ce=ae.ae+ef=af...但是我感觉这个太简单了 0 0,没含量,面试的应该不会出这样的题...麻烦各位大哥,谁知道的帮我解答一下.谢谢了

Answer 1

#include <iostream>using namespace std;typedef struct nPoint
{
char Name;
nPoint * left;// 点的左
nPoint * right; // 点的右
nPoint  * Next; //输出时下一个.
};
nPoint * goPoint(nPoint *startPoint,nPoint *toPoint)
{
nPoint *temp = startPoint;
nPoint *prior = startPoint;
int direction = 0;// 0 先去左 1 左失败 取右 2 空 
while (true)
{
temp = startPoint;
switch(direction)
{
case 0://首先遍历左
temp->Next = temp -> left;
temp = temp -> left;
while (temp != NULL)
{
if (temp->Name == toPoint->Name)
{
return startPoint;
}
if (temp->right->Name == startPoint->Name || temp->left->Name != prior->Name)
{
prior = temp;
temp->Next = temp->left;
temp = temp->left;
}
else
{
prior = temp;
temp->Next = temp->right;
temp = temp->right;
}
}
direction = 1;
break;
case 1:
temp->Next = temp -> right;
temp = temp -> right;
while (temp != NULL)
{ if (temp->Name == toPoint->Name)
{
return startPoint;
}
if (temp->left->Name == startPoint->Name || temp->right->Name != prior->Name)
{
prior = temp;
temp->Next = temp->right;
temp = temp->right;
}
else
{
prior = temp;
temp->Next = temp->left;
temp = temp->left;
}
}
direction = 2;
break;
case 2:
return NULL;
break;
}
}}
int main()
{
//首先已知 有6个点.
nPoint *A = new nPoint;
nPoint *B = new nPoint;
nPoint *C = new nPoint;
nPoint *D = new nPoint;
nPoint *E = new nPoint;
nPoint *F = new nPoint;
//首先将 已知 对象连接起来
A->left = NULL;
A->right = B;
A->Name = 'A';
A->Next = NULL;
B->left = A;
B->right = D;
B->Name = 'B';
B->Next = NULL;
C->left = E;
C->right = D;
C->Name = 'C';
C->Next = NULL;
D->left = B;
D->right = C;
D->Name = 'D';
D->Next = NULL;
E->left = C;
E->right = F;
E->Name = 'E';
E->Next = NULL;
F->left = E;
F->right = NULL;
F->Name = 'F';
F->Next = NULL; //然后求

nPoint * tempP = goPoint(F,A); //GO 求A到F的路线

while (tempP != NULL)
{
cout << tempP->Name << "→";
tempP = tempP->Next;
}
cout << "结束";

return 0;
}