华为2014上机考试样题(4)

int i;
 for(i=0; i<35; i++) //第一边表初始化，分配内存
 {
  e1[i] = new edgeNode;
 }
 for(i=0; i<33; i++) //第二边表初始化，分配内存
 {
  e2[i] = new edgeNode;
 }
 for(i=0; i<2; i++) //第三、四边表初始化，分配内存
 {
  e3[i] = new edgeNode;
  e4[i] = new edgeNode;
 }

//第一边表数据域，即第一边表顶点号
  //A
 for(i=0; i<18; i++)
 {
  e1[i]->eVerIndex = i+1;
 }
  //修正A
 e1[8]->eVerIndex = 33; //A9-->T1
 e1[12]->eVerIndex = 34; //A13-->T2
 e1[17]->eVerIndex = 0; //A18-->A1
 
  //B
 for(i=18; i<18+15; i++)
 {
  e1[i]->eVerIndex = i+1;
 }
  //修正B
 e1[22]->eVerIndex = 33; //B5-->T1
 e1[27]->eVerIndex = 34; //B10-->T2
 e1[32]->eVerIndex = 31; //B15-->B14

//T1 T2
 e1[33]->eVerIndex = 9; //T1-->A9
 e1[34]->eVerIndex = 13; //T2-->A14

//第二边表数据域，即第二边表顶点号
  //A
 for(i=0; i<18; i++)
 {
  e2[i]->eVerIndex = i-1;
 }
  //修正A
 e2[0]->eVerIndex = 17; //A1-->A18
 e2[9]->eVerIndex = 33; //A10-->T1
 e2[13]->eVerIndex = 34; //A14-->T2

//B
 for(i=18; i<31; i++)
 {
  e2[i]->eVerIndex = i;
 }
  //修正B
 e2[22]->eVerIndex = 33; //B6-->T1
 e2[27]->eVerIndex = 34; //B11-->T2

//T1 T2
 e2[31]->eVerIndex = 8; //T1-->A9
 e2[32]->eVerIndex = 12; //T2-->A13

//第三边表数据域，即第三边表顶点号
  //T1 T2
 e3[0]->eVerIndex = 23; //T1-->B6
 e3[1]->eVerIndex = 28; //T2-->B11

//第四边表数据域，即第四边表顶点号
 e4[0]->eVerIndex = 22; //T1-->B5
 e4[1]->eVerIndex = 27; //T2-->B10

//第一边表指针域
 for(i=0; i<18; i++)
 {
  e1[i]->nextEdge = e2[i];
 }
 e1[18]->nextEdge = NULL;
 for(i=19; i<32; i++)
 {
  e1[i]->nextEdge = e2[i-1];
 }
 e1[32]->nextEdge = NULL;

e1[33]->nextEdge = e2[31];
 e1[34]->nextEdge = e2[32];

//第二边表指针域
 for(i=0; i<33; i++)
 {
  e2[i]->nextEdge = NULL;
 }
 e2[31]->nextEdge = e3[0];
 e2[32]->nextEdge = e3[1];

//第三边表指针域
 e3[0]->nextEdge = e4[0];
 e3[1]->nextEdge = e4[1];

//第四边表指针域
 e4[0]->nextEdge = NULL;
 e4[1]->nextEdge = NULL;

/*************************************************************/

/***完善顶点表数据域和指针域，关联顶点表与第一边表****/

for(i=0; i<VerNum; i++)
 {
  g->adjList[i].verIndex = i; //顶点表数据域
  g->adjList[i].firstEdge = e1[i]; //顶点表指针域
 }

/***********************************************************/

}

/***打印邻接表信息*******/
#ifdef DEBUG //只在DEBUG模式下打印
void printGraph(graphList *g)
{
 int i;
 edgeNode *p;

for(i=0; i<VerNum; i++)
 {
  cout << "顶点号：" << i << " 边号：";
  p = g->adjList[i].firstEdge;

while(p)
  {
   cout << p->eVerIndex << " ";
   p = p->nextEdge;
  }
  cout << endl;
 }
}
#endif

/***************************************************/

/****BFS广度优先搜索邻接表，找出最短路径***********
参考：

******************************************************/

//队列链表结点结构，单向链表
typedef struct qNode
{
 int qVerIndex; //队列数据域，结点存储的顶点号
 struct qNode *nextQNode; //队列指针域，结点指向的下一个队列结点
}qNode; //队列链表结点结构别名为qNode

//队列链表
typedef struct
{
 qNode *front; //队列头，删除
 qNode *rear; //队列尾，添加
}queue; //队列链表别名queue