Question

就高手帮帮忙,写一个以邻接表形式构建图并输出的的函数,感激不尽呐!(C语言版的,最好是结构体形式)

只写有向图的就可以了

Answer 1

没人理你……

我找不到简单的版本的……

只找到一个还算简单的……

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <ctype.h>
#define MaxVerNum 50
#define OK 1
#define NULL 0
typedef int Status;
int visited[MaxVerNum];


typedef struct Arcnode{     
	int adjvex;
	struct Arcnode *next;
	int info;
}ArcNode;

typedef struct vnode{
	char data;
	ArcNode *firstedge;
}VNode;

typedef VNode AdjList[MaxVerNum];

typedef struct {
	AdjList adjlist;
	int vexnum,arcnum;
} ALGraph; 


Status Visit(char e)//输出一个字母
{
	printf("%2c",e);
	return OK;
}

void Get(char *e)//输入一个字母
{
	scanf("%c",e);
	while(!('A' <= *e && *e<= 'Z')||('a' <= *e && *e <= 'z'))
			scanf("%c",e);
}
void TGet(int *e)//输入一个数字
{
	
	scanf("%d",e);
	while(scanf("%d", e) <= 0)
	{  
		getchar();
	}
}


void InIt(ALGraph *G,int S[])//数组初始化
{
	for(int i=0;i<G->vexnum;i++)
		S[i]=0;
}


void FindD(ALGraph *G,char arch,int *a)// 找到顶点的下标
{
	int m;

	for(m=0;m<G->vexnum;m++)
	{
		if(arch == G->adjlist[m].data)
			*a = m;
	}
}

void Find(ALGraph *G,char arch,char arce,int *a,int *b)// 找到弧头和弧尾的下标
{
	FindD(G,arch,a);
	FindD(G,arce,b);
}

Status IsBe(ALGraph *G,char arch)// 判断顶点是否已存在
{
	for(int m=0;m<G->vexnum;m++)
	{
		if(arch == G->adjlist[m].data)
		{
			return OK;
		}
	}
	return 0;
}//IsBe


Status AIsBe(ALGraph *G,int i,int j) //判断弧是否存在

{

	ArcNode *s;

	s = G->adjlist[i].firstedge;
	while(s)
	{
		if(s->adjvex == j)
		{
			return OK;
		}
		s = s->next;
	}
	return 0;
}//AIsBe


Status GetIn(ALGraph *G,char arch,char arce) //得到弧的权值

{

	int i,j;
	ArcNode *s;

	Find(G,arch,arce,&i,&j);
	s = G->adjlist[i].firstedge;
	while(s)
	{
		if(s->adjvex == j)
		{
			return (s->info);
		}
		s = s->next;
	}
	return 0;
}//AIsBe


          
void CreatALGraph(ALGraph *G)//           建立图的邻接表 
{
	int i,j,k,m;
	char a,arch,arce;
	ArcNode *s;

	printf("请输入顶点数:");
	scanf("%d",&G->vexnum);   
	printf("请输入弧的条数:");
	scanf("%d",&G->arcnum); 

	printf("下面请输入图中的%d个顶点:\n",G->vexnum);
	for(i=0;i<G->vexnum;i++)
	{
		fflush(stdin);
		printf("输入第%d个顶点:",i+1);
		Get(&a);
		if(!IsBe(G,a))
		{
		G->adjlist[i].data = a;
		G->adjlist[i].firstedge = NULL;
		}
		else
		{
			printf("顶点%c已存在，请重新",a);
			i--;
		}
	}

	printf("下面请输入图中的%d条弧：\n",G->arcnum);
	for(k=0;k<G->arcnum;k++)
	{
		fflush(stdin);
		printf("输入第%d条弧:",k+1);
		Get(&arch);Get(&arce);TGet(&m);
		Find(G,arch,arce,&i,&j);
		if(!AIsBe(G,i,j))
		{
			fflush(stdin);
			s=(ArcNode *)malloc(sizeof(ArcNode));
			s->adjvex = j;
			s->info = m;
			s->next=G->adjlist[i].firstedge;
			G->adjlist[i].firstedge = s;
		}
		else
		{
			printf("弧%c,%c已存在，请重新",arch,arce);
			k--;
		}
	}
	printf("图的邻接表储存结构创建成功!\n");
}//CreatALGraph



void ACreateALGraph(FILE *fp,ALGraph *G)//           从文件读取图的邻接表 
{	
	int i,j,k,m;
	char a,arch,arce;
	ArcNode *s;


	fscanf(fp, "%d", &G->vexnum);
	fscanf(fp, "%d", &G->arcnum);
	for(i=0;i<G->vexnum;i++)
	{
		fflush(stdin);
		fscanf(fp, "%c", &a);
		G->adjlist[i].data = a;
		G->adjlist[i].firstedge = NULL;
	}
	for(k=0;k<G->arcnum;k++)
	{
		fscanf(fp, "%c", &arch);
		fscanf(fp, "%c", &arce);
		fscanf(fp, "%d", &m);
		Find(G,arch,arce,&i,&j);
		s=(ArcNode *)malloc(sizeof(ArcNode));
		s->adjvex = j;
		s->info = m;
		s->next=G->adjlist[i].firstedge;
		G->adjlist[i].firstedge = s;
	}
}//ACreateALGraph

void save(ALGraph *G)//保存文件
{
	FILE *fp;
	int i,j,k;
	ArcNode *p;

	// 打开文件
	if((fp=fopen("AL.dat", "wb"))==NULL)
	{
		printf("数据文件打开失败，保存不成功，程序异常退出！\n");
		exit(-1);
	}
	fprintf(fp, "%d", G->vexnum);
	fprintf(fp, " ");
	fprintf(fp, "%d", G->arcnum);

	for(i=0;i<G->vexnum;i++)    
	{
		fprintf(fp, "%c", G->adjlist[i].data);
	}
	for(i=0;i<G->vexnum;i++)    
	{
		p = G->adjlist[i].firstedge;
		while(p != NULL)
		{
			j = p->adjvex;
			k = p->info;
			fprintf(fp, "%c", G->adjlist[i].data);
			fprintf(fp, "%c", G->adjlist[j].data);
			fprintf(fp, "%d", k);
			p = p->next ;
		}

	}

	// 关闭文件
	fclose(fp);

	printf("图中的数据已经成功写入文件!\n");
}//save



void Traverse(ALGraph *G)   //输出邻接表
{
	int i,j,k;ArcNode *p;


	for(i=0;i<G->vexnum;i++)    
	{
		printf("%2d|",i);
		Visit(G->adjlist[i].data);     
		p = G->adjlist[i].firstedge;
		while(p != NULL)
		{
			j = p->adjvex;
			k = p->info; 
			printf(" ★-->%2d %2d",j,k);
			p = p->next ;
		}
		printf(" △\n");

	}
}//Traverse


void DFSM(ALGraph *G,int i)//深度优先遍历
{
    ArcNode *p;

    Visit(G->adjlist[i].data);
    visited[i]=1;                
    p=G->adjlist[i].firstedge;         
    while(p)
	{
     if(! visited[p->adjvex])
		 DFSM(G,p->adjvex);
	 p = p->next;
    }
}//DFSM

void DFSTraverse(ALGraph *G)
{
	InIt(G,visited);
	for(int j=0;j<G->vexnum;j++)
		if(!visited[0])
			DFSM(G,0); 
}//DFSTraverse

        
void BFSTraverse(ALGraph *G)         //广度优先遍历
{
	int k=0;
    int i,f=0,r=0;
    ArcNode *p;
	int cq[MaxVerNum];
    

	InIt(G,visited);
    for(i=0;i<=G->vexnum;i++)
    cq[i]=-1;
	Visit(G->adjlist[k].data);
	visited[k]=1;
	cq[f]=k;
	while(cq[r]!=-1)
	{
		i=cq[r];
		r=r+1;
		p=G->adjlist[i].firstedge;
		while(p)
		{
			if(!visited[p->adjvex]) 
			{
				Visit(G->adjlist[p->adjvex].data);
				visited[p->adjvex]=1;
				f=f+1; cq[f]=p->adjvex;
			}
			p=p->next;
		}
	}                               
}      // BFSTraverse

Status InArc(ALGraph *G,int i,int j,int k)   //插入一条弧
{
	ArcNode *s;

	s=(ArcNode *)malloc(sizeof(ArcNode));
	s->adjvex = j;
	s->info = k;
	s->next=G->adjlist[i].firstedge;
	G->adjlist[i].firstedge = s;
	return OK;
}//InArc



Status InAr(ALGraph *G)   //插入一条弧

{
	int i,j,k;
	char arch,arce;


	printf("输入要增加的弧<弧尾，弧头，权值>:\n");
	fflush(stdin);
	Get(&arch);Get(&arce);TGet(&k);
	Find(G,arch,arce,&i,&j);
	if(!AIsBe(G,i,j))
	{
		InArc(G,i,j,k);
		printf("弧%c,%c,%d添加成功!\n",arch,arce,k);
		return OK;
	}
	else
	{
		k = GetIn(G,arch,arce);
		printf("已存在弧%c,%c,%d，请重新",arch,arce,k);
		InAr(G);
		return OK;
	}
}//InAr




Status DeArc(ALGraph *G,int i,int j) //删除一条弧
{
	ArcNode *s,*ss;
	
	
	ss = G->adjlist[i].firstedge;
	if(ss->adjvex == j)
	{
		G->adjlist[i].firstedge = ss->next ;
		free(ss);
		return OK;
	}
	else
	{
		while(ss->next)
		{
			if(ss->next->adjvex != j)
			{
				ss = ss->next ;
			}
			else
			{
				s = ss->next ;
				ss->next = s->next ;
				free(s);
				return OK;
			}
		}
	}
	return OK;
}//DeArc

Status DelArc(ALGraph *G)
{
	int i,j,h;
	char arch,arce;
	fflush(stdin);
	printf("输入要删除的弧<弧尾，弧头>:\n");
	Get(&arch);Get(&arce);h = GetIn(G,arch,arce);
	Find(G,arch,arce,&i,&j);
	if(AIsBe(G,i,j))
	{
		DeArc(G,i,j);
		printf("弧%c,%c,%d已被删除\n",arch,arce,h);
		return OK;
	}
	else
	{
		printf("弧%c,%c不存在，请重新",arch,arce);
		DelArc(G);
		return 0;
	}
	
			
}//DelArc


Status ModifyArc(ALGraph *G)   //修改一条弧
{
	int i,j,k,i2,j2,k2,m = 1;
	char arch,arce,arch2,arce2;
	ArcNode *s;


	printf("输入要修改的弧<弧尾，弧头>:\n");
	fflush(stdin);
	Get(&arch);Get(&arce);k=GetIn(G,arch,arce);
	Find(G,arch,arce,&i,&j);
	
	if(AIsBe(G,i,j))
	{
		while(m)
		{
		printf("输入修改后的弧<弧尾，弧头，权值>:\n");
		fflush(stdin);
		Get(&arch2);Get(&arce2);TGet(&k2);
		Find(G,arch2,arce2,&i2,&j2);
		if(!AIsBe(G,i2,j2)||(i == i2&&j ==j2))
		{
			if(i != i2)
			{
			DeArc(G,i,j);
			InArc(G,i2,j2,k2);
			}
			else
			{
				s = G->adjlist[i].firstedge;
				while(s->adjvex != j)
				{
					s = s->next ;
				}
				s->adjvex = j2;
				s->info = k2;
			}
			printf("已将弧%c,%c,%d修改为%c,%c,%d!\n",arch,arce,k,arch2,arce2,k2);
			m = 0;
		}
		else
		{
			k2 = GetIn(G,arch,arce);
			printf("已存在弧%c,%c,%d，请重新",arch2,arce2,k2);
		}
		}
		return OK;
	}
	else
	{
		printf("弧%c,%c不存在，请重新",arch,arce);
		ModifyArc(G);
		return OK;
	}
}//ModifyArc



Status InTop(ALGraph *G) //增加一个顶点
{
	int i;char a;


	printf("输入要添加的顶点:\n");
	fflush(stdin);
	Get(&a);
	if(!IsBe(G,a))
	{
		i = G->vexnum++;
		G->adjlist[i].data = a;
		G->adjlist[i].firstedge = NULL;
		printf("已成功将顶点%c加入图中!",a);
		return OK;
	}
	else
	{
		printf("顶点%c已存在，请重新",a);
		InTop(G);
		return OK;
	}
}//InTop


Status DeTop(ALGraph *G) //删除一个顶点
{
	int i,m;char a;
	ArcNode *s;



	printf("输入要删除的顶点:\n");
	fflush(stdin);
	Get(&a);
	
	if(IsBe(G,a))
	{
		FindD(G,a,&m);
		for(i = 0;i < G->vexnum ;i++)
		{
			if(AIsBe(G,i,m))
				DeArc(G,i,m);
		}
		for(i = m;i < (G->vexnum)-1 ;i++)
		{
			G->adjlist[i].data = G->adjlist[i+1].data;
			G->adjlist[i].firstedge = G->adjlist[i+1].firstedge ;
		}
		G->vexnum--;

		for(i = 0;i < G->vexnum ;i++)
		{
			s = G->adjlist[i].firstedge;
			if(s != NULL)
				while( s->next!= NULL)
				{
					if(s->adjvex >= m)
						(s->adjvex)--;
					s = s->next ;
				}
		}
		printf("成功将顶点%c删除!",a);
		return OK;
	}
	else
	{
		printf("顶点%c不存在，请重新",a);
		DeTop(G);
		return OK;
	}
}//DeTop



Status ModifyTop(ALGraph *G)
{
	int m;
	char a,b;

	printf("输入要修改的顶点：");
	fflush(stdin);
	Get(&a);
	if(IsBe(G,a))
	{
		FindD(G,a,&m);
		printf("请输入修改后的顶点：");
		Get(&b);
		while(IsBe(G,b))
		{
			printf("不能修改为已有顶点!请重新输入:");
			Get(&b);
		}
		G->adjlist[m].data = b;
		printf("已将顶点%c修改为%c",a,b);
		return OK;
	}
	else
	{
		printf("顶点%c不存在，请重新",a);
		ModifyTop(G);
	}
	return OK;
}//ModifyTop
Status Destroy(ALGraph *G)
{
	for(int i=0;i<G->vexnum;i++)
	{	
		G->adjlist[i].data =0;
		G->adjlist[i].firstedge =NULL;
	}
	G->arcnum = 0;
	G->vexnum = 0;

	return OK;
}//Destroy


void menu()                               
{
	printf("\n");
	printf("\t***********0233唐明邻接表****************\n");
	printf("\t*        1  创建图的邻接表储存结构      *\n");
	printf("\t*        2  读取图的邻接表储存结构      *\n");
	printf("\t*        3  储存图的邻接表储存结构      *\n");
	printf("\t*        4  输出邻接表数据              *\n");
	printf("\t*        5  深度优先遍历图（DFS）       *\n");
	printf("\t*        6  广度优先遍历图（BFS）       *\n");
	printf("\t*        7  弧的修改                    *\n");
	printf("\t*        8  顶点的修改                  *\n");
	printf("\t*        9  销毁整个图                  *\n");
	printf("\t*        10 清          屏              *\n");
	printf("\t*        0  退  出  程  序              *\n");
	printf("\t*****************************************\n");
	printf("\t请选择菜单项：");
}



int main()
{
    ALGraph *G;	
	G=(ALGraph *)malloc(sizeof(ALGraph));
	FILE *fp;
	int choice,choice2,choice3;
	int is = 0;

	while(1)
	{
start:
		menu();
		fflush(stdin);
		scanf("%d", &choice);
		
		switch(choice)
		{
		case 1:
			if(!is)
			{
				CreatALGraph(G);
				is = 1;
			}
			else
			{
				printf("请先将图销毁，再创建新图");
			}
			break;
		case 2:
			if(!is)
			{
				fp = fopen("AL.dat", "r");
				if(fp==NULL)
				{
					fp = fopen("AL.dat", "w+");
					printf("尚未建立AL.dat，图创建失败！\n");
					printf("现已建立AL.dat，请先存入数据！\n");
					break;
				}
				ACreateALGraph(fp,G);
				fclose(fp);
				is = 1;
				printf("图的邻接表储存结构创建成功!\n");
			}
			else
			{
				printf("请先将图销毁，再创建新图");
			}
			break;
		case 3:
			save(G);
			break;
		case 4:
			if(is)
			{
				printf("邻接表中的数据如下：\n");
				printf("下标   顶点    链表结点（弧头下标，弧的权值，指针）\n");
				Traverse(G);
			}
			else
				printf("尚未创建图，请先创建");
			break;
		case 5:
			if(is)
			{
				printf("深度优先遍历如下\n");
				DFSTraverse(G);
			}
			else
				printf("尚未创建图，请先创建");
			break;
		case 6:
			if(is)
			{
				printf("广度优先遍历如下\n");
				BFSTraverse(G);
			}
			else
				printf("尚未创建图，请先创建");
			break;
		case 7:
			if(is){
			printf("(1 增加 2 删除 3 修改)");
			scanf("%d",&choice2);
			switch(choice2)
			{
			case 1:
					InAr(G);
					goto start;break;
			case 2:
					DelArc(G);
					goto start;break;
			case 3:
					ModifyArc(G);
					goto start;break;
			default:	goto start;break;}
			}
			else
					printf("尚未创建图，请先创建");
			break;
		case 8:
			if(is){
			printf("(1 增加 2 删除 3 修改)");
			scanf("%d",&choice3);
			switch(choice3)
			{
			case 1:
					InTop(G);
					goto start;break;
			case 2:
					DeTop(G);
					goto start;break;
			case 3:
					ModifyTop(G);
					goto start;break;
			default:	goto start;break;}
			}
			else
					printf("尚未创建图，请先创建");
			break;		
		case 9:
			if(is)
			{
				Destroy(G);
				is = 0;
				printf("图已销毁!");
			}
			else
				printf("尚未创建图，请先创建");
			break;
		case 10:
			system("cls");
			break;
		case 0:
			exit(0);
			break;	
		default:
			printf("\t您输入的菜单项不存在，请重新选择!\n");
		}
	}
	return OK;
}

这是在我大一的草稿文件中找到的……完美的被我直接放U盘上，交了之后删了。不过你应该够用了，如果嫌功能多了……自己删吧，我记得我交上去的有十几项选项，几十条功能。你第一次运行，要么下我传上去的，要么你先输入图，再储存。因为没有AL.dat文件所以不能直接读取。