神秘国度的爱情故事 算法与数据结构课程设计

神秘国度的爱情故事 算法与数据结构课程设计

#include
#define MAXNODE 64
#define NULL 0
using namespace std;
/*邻接表存储结构*/
typedef struct arc
   {int adjvex;           //邻接点在顶点中的下标
    struct arc *next;
}ArcNode;

typedef struct VexNode
{                            
int leftright;
 ArcNode *firstarc;//指向第一邻接点的指针
}VerNode;

typedef VerNode AdjList[MAXNODE];
/*创建图*/
int visited[MAXNODE];
                                                      
int vsum;
void creatgraph（AdjList GL）
{int ijk;char y;
 ArcNode *p;
 cout<<“请输入村子数:“;
 cin>>vsum;
   for（i=1;i<=vsum;i++）
   {                                                
      GL[i].firstarc=NULL;
      }
 cout<<“请输入村之间的所有路    一条路的两个端点之间用，分隔\n需满足任意两村之间有且仅有一条路:“< for（k=0;k     {
      cin>>i>>y>>j;
      if（i&&j）
	  {
	   p=new ArcNode; 
	   p->adjvex=j;p->next=GL[i].firstarc;GL[i].firstarc=p;
	   p=new ArcNode;
	   p->adjvex=i;p->next=GL[j].firstarc; GL[j].firstarc=p;
	  }
      }
 }

/*深度优先遍历*/
int i=0;
void dfs（AdjList Gint v）
 {ArcNode *q; 
if（!visited[v]）  {i++; G[v].left=i;cout<    visited[v]=1;
    q=G[v].firstarc;
    while（q!=NULL）
     {if（!visited[q->adjvex]） dfs（Gq->adjvex）;
		q=q->next;
		if（q==NULL）{i++; G[v].right=i;cout<  }
}
void DfsAdjlist（AdjList GLint v）
{int i;
 for（i=1;i<=vsum;i++） visited[i]=0;
 if（!visited[v]） dfs（GLv）;
 }
/*判断c是否为a和b的最近祖先*/
void  Near（AdjList Gint aint bint c）
{int lr;ArcNode *q; int i=0;int m=0;
int H[32];
  q=G[c].firstarc;                           
  if（G[a].left>G[b].left）{l=G[b].left;r=G[a].right;}
	else{l=G[a].left;r=G[b].right;}
	while （q!=NULL）{
	if（G[c].leftadjvex].left）{//必需不是c的祖先
			m++;H[m]=G[q->adjvex].left;    //cout<		m++;H[m]=G[q->adjvex].right;       //cout<	}
		q=q->next;
}
 	//cout<	int low=1;int high=m;//二分查找
	int mid;
	while（low+1		mid=（low+high）/2;
		if（l>=H[mid]）  low=mid;
		else high=mid-1;
	}
	switch（low%2）
	{case 0:cout<<“皇天不负有心人“<	case 1:if（r<=H[low+1]） cout<<“白等“<		else cout<<“皇天不负有心人“<default:cout<<“错误“<	   }
}

/*判断c是否在b到c上 函数*/
void Decide（AdjList Gint a int bint c）{
    int k=0;
	if（G[c].leftG[b].right） k++;
	if（G[c].leftG[a].right） k++;
    switch（k）{
	case 0:cout<<“白等“<	case 1:cout<<“皇天不负有心人“<	case 2:Near（Gabc）;break;                      //c为a和b祖先
	default:cout<<“Error“<	}
}
void  main（）
 {AdjList GL;int m=0;
  int a[20]b[20]c[20];int z;char t;
  cout<<“                **************神秘国度的爱情故事***************       “<  creatgraph（GL）;
  DfsAdjlist（GL1）;
  cout<  cout<<“请输入测试组数:“;
  cin>>z;
  while（z>0）{
	z--;m++;
    cout<<“请分别输入第“<    cin>>a[m]>>b[m]>>c[

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     548926  2011-01-04 13:01  神秘国度的爱情故事\Debug\love.exe

     文件     788700  2011-01-04 13:01  神秘国度的爱情故事\Debug\love.ilk

     文件     259005  2011-01-04 13:11  神秘国度的爱情故事\Debug\love.obj

    I.A....   2001184  2011-01-02 10:09  神秘国度的爱情故事\Debug\love.pch

     文件    1115136  2011-01-04 13:00  神秘国度的爱情故事\Debug\love.pdb

     文件     123904  2011-01-04 13:11  神秘国度的爱情故事\Debug\vc60.idb

     文件     110592  2011-01-04 13:00  神秘国度的爱情故事\Debug\vc60.pdb

     文件       3378  2011-01-04 13:00  神秘国度的爱情故事\love.cpp

     文件       3717  2010-12-30 15:02  神秘国度的爱情故事\love.dsp

     文件        533  2010-12-30 16:51  神秘国度的爱情故事\love.dsw

     文件      50176  2011-01-05 15:57  神秘国度的爱情故事\love.ncb

     文件      48640  2011-01-05 15:57  神秘国度的爱情故事\love.opt

     文件        688  2011-01-04 13:11  神秘国度的爱情故事\love.plg

     文件         56  2011-01-04 15:03  神秘国度的爱情故事\readme.txt

     目录          0  2011-01-04 13:00  神秘国度的爱情故事\Debug

     目录          0  2011-01-05 15:57  神秘国度的爱情故事

----------- ---------  ---------- -----  ----

              5054635                    16