c语言邻接表的输出函数 c语言邻接表的深度优先遍历
C语言中,输出函数有哪些?
C语言输入输出函数有很多,标准I/O函数中包含了如下几个常用的函数:
创新互联建站专业为企业提供桐城网站建设、桐城做网站、桐城网站设计、桐城网站制作等企业网站建设、网页设计与制作、桐城企业网站模板建站服务,10年桐城做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
scanf,printf,getc,putc,getchar,putchar,gets,puts,fgets,fputs,fgetc,fputc,fscanf,fprintf等.
int
scanf(const
char
*format,
arg_list)
scanf主要从标准输入流中获取参数值,format为指定的参数格式及参数类型,如scanf("%s,%d",str,icount);
它要求在标准输入流中输入类似"son
of
bitch,1000"这样的字符串,同时程序会将"son
of
bitch"给str,1000给icount.
scanf函数的返回值为int值,即成功赋值的个数,在上例中如果函数调用成功,则会返回2,所以我们在写程序时,可以通过
语句if(scanf("%s,%d",str,icount)
!=
2){...}来判断用户输入是否正确.
int
printf(const
char
*format,
arg_list)
printf主要是将格式化字符串输出到标准输出流中,在stdio.h头文件中定义了标准的输入和输出,分别是stdin,stdout.
arg_list可以是变量名,也可以是表达式,但最终都会以值的形式填充进format中.
int
getc(FILE
*fp)
getc主要是从文件中读出一个字符.常用的判断文件是否读取结束的语句为:(ch
=
getc(fp))
!=
EOF.EOF为文件结束标志,
定义在stdio.h中,就像EXIT_SUCCESS,EXIT_FAILURE定义在stdlib.h中一样,文件也可以被理解为一种流,所以当fp为stdin
时,getc(stdin)就等同于getchar()了.
int
putc(int
ch,FILE
*fp)
putc主要是把字符ch写到文件fp中去.如果fp为stdout,则putc就等同于putchar()了.
int
getchar(void)
getchar主要是从标准输入流读取一个字符.默认的标准输入流即stdio.h中定义的stdin.但是从输入流中读取字符时又
涉及到缓冲的问题,所以并不是在屏幕中敲上一个字符程序就会运行,一般是通过在屏幕上敲上回车键,然后将回车前的字符
串放在缓冲区中,getchar就是在缓冲区中一个一个的读字符.当然也可以在while循环中指定终止字符,如下面的语句:
while
((c
=
getchar())
!=
'#')这是以#来结束的.
int
putchar(int
ch)
putchar(ch)主要是把字符ch写到标准流stdout中去.
char
*
gets(char
*str)
gets主要是从标准输入流读取字符串并回显,读到换行符时退出,并会将换行符省去.
int
puts(char
*str)
puts主要是把字符串str写到标准流stdout中去,并会在输出到最后时添加一个换行符.
char
*fgets(char
*str,
int
num,
FILE
*fp)
str是存放读入的字符数组指针,num是最大允许的读入字符数,fp是文件指针.fgets的功能是读一行字符,该行的字符数
不大于num-1.因为fgets函数会在末尾加上一个空字符以构成一个字符串.另外fgets在读取到换行符后不会将其省略.
int
fputs(char
*str,
file
*fp)
fputs将str写入fp.fputs与puts的不同之处是fputs在打印时并不添加换行符.
int
fgetc(FILE
*fp)
fgetc从fp的当前位置读取一个字符.
int
fputc(int
ch,
file
*fp)
fputc是将ch写入fp当前指定位置.
int
fscanf(FILE
*fp,
char
*format,...)
fscanf按照指定格式从文件中出读出数据,并赋值到参数列表中.
int
fprintf(FILE
*fp,
char
*format,...)
fprintf将格式化数据写入流式文件中.
就高手帮帮忙,写一个以邻接表形式构建图并输出的的函数,感激不尽呐!(C语言版的,最好是结构体形式)
没人理你……
我找不到简单的版本的……
只找到一个还算简单的……
#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;iG-vexnum;i++)
S[i]=0;
}
void FindD(ALGraph *G,char arch,int *a)// 找到顶点的下标
{
int m;
for(m=0;mG-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;mG-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;iG-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;kG-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;iG-vexnum;i++)
{
fflush(stdin);
fscanf(fp, "%c", a);
G-adjlist[i].data = a;
G-adjlist[i].firstedge = NULL;
}
for(k=0;kG-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;iG-vexnum;i++)
{
fprintf(fp, "%c", G-adjlist[i].data);
}
for(i=0;iG-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;iG-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;jG-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 == i2j ==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;iG-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文件所以不能直接读取。
在C语言中编程实现建立无向图的邻接表,输出某个点的邻接点~!
用矩阵表示无向图的,设有M个节点,则建立一个MXM矩阵,对每个顶点添加它的邻接点,即每行中对于有标记的列为该行顶点的邻接点。
用邻接表表示的图的输出(PrintGraph)的算法(C语言)
单链表类中的输出流函数重载,输出链表
图类中再次重载输出流函数。
一次顶点表的循环,输出。
结果:start,dest,weight,。。。
分享标题:c语言邻接表的输出函数 c语言邻接表的深度优先遍历
网页链接:http://pwwzsj.com/article/dophdeo.html