当前位置：首页 » 编程语言 » 邻接表c语言

邻接表c语言

发布时间: 2021-03-16 12:25:16

① 请教编程大神数据结构题目：c语言使用邻接链表存储结构实现用户输入的无向图的连通性判断

#include<stdio.h>
#include<stdlib.h>
#defineMAX_VERTEX_NUM100
typedefstructArcNode{
intadjvex;//该边的另一个顶点的位置
structArcNode*nextarc;//指向下一条边
}ArcNode;
typedefstructVNode{
intdata;//顶点的值
ArcNode*firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;//顶点数组
intvexnum,arcnum;
}ALGraph;
intLocateVex(ALGraphG,intv){//定位函数
for(inti=0;i<G.vexnum;i++){
if(v==G.vertices[i].data)returni;
}
}
voidCreateUDG(ALGraph&G){
ArcNode*p,*q;
inti,j,k,v1,v2;
printf("分别输入顶点个数和边的数目：
");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("分别输入各个顶点值：
");
for(i=0;i<G.vexnum;i++){
scanf("%d",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;//初始化
}
printf("分别输入各条边的两个顶点：
");
for(k=0;k<G.arcnum;k++){
scanf("%d%d",&v1,&v2);
i=LocateVex(G,v1);j=LocateVex(G,v2);//定位
p=(ArcNode*)malloc(sizeof(ArcNode));//申请一个结点
p->adjvex=j;p->nextarc=NULL;//赋值
p->nextarc=G.vertices[i].firstarc;//连接结点
G.vertices[i].firstarc=p;//连接结点
q=(ArcNode*)malloc(sizeof(ArcNode));
q->adjvex=i;q->nextarc=NULL;
q->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=q;
}
}
voidPrintUDG(ALGraphG){//输出邻接表
inti,j;
for(i=0;i<G.vexnum;i++){
printf("%d:",i);
ArcNode*p;
p=G.vertices[i].firstarc;
while(p!=NULL){
printf("->%d",p->adjvex);
p=p->nextarc;
}
printf("
");
}
}
intmain(){
ALGraphG;
CreateUDG(G);
PrintUDG(G);
return0;
}

② 用邻接表表示的图的输出(PrintGraph)的算法(C语言)

DFS算法源程序
/* dfs算法 */
#include<alloc.h>
#include<stdio.h>
#include<malloc.h>
#include<conio.h>

/* 函数结果状态代码 */
#define True 1
#define False 0
#define Ok 1
#define Error 0
#define Infeasible -1
#define Overflow -2
#define Null 0
#define STACK_INIT_SIZE 100
#define Stackincrement 10

#define INFINITY 10000 /* 最大值10000 */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
#define Status int
typedef char TElemType; /* 抽象元素类型为char类型 */

typedef struct ArcNode{
int adjvex; /* 该弧所指向的顶点的位置 */
int weight; /* 边的权值 */
struct ArcNode *nextarc; /* 指向下一条弧的指针 */
}ArcNode;

typedef struct VNode{
char data; /* 顶点向量 */
ArcNode *firstarc; /* 指向第一条依附该顶点的弧的指针 */
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
}ALGraph;

struct STU{
char data;
};
typedef struct STU SElemType;

struct STACK
{
SElemType *base;
SElemType *top;
int stacksize;
};

typedef struct STACK SqStack;
int visited[MAX_VERTEX_NUM]; /* visited[MAX_VERTEX_NUM]为全局变量，记录相应顶点是否被访问过，访问过则为1，否则为0 */

Status InitStack(SqStack *S)
/* 构造一个空栈 */
{
S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemTy pe));
if(!S->base)
exit(Overflow); /* 存储分配失败 */
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return Ok;
} /* InitStack() */

Status StackEmpty(SqStack *S)
/* 判断栈S是否为空 */
{
if(S->top==S->base) return True;
else
return False;
} /* StackEmpty() */

Status GetTop(SqStack *S,SElemType **e)
/* 若栈不空，则用e返回S的栈顶元素，并返回Ok，否则返回Error */
{
if(S->top==S->base)
return Error;
else
{
*e=S->top-1;
return Ok;
} /* else */
} /* GetTop() */

Status Push(SqStack *S,char e)
/* 插入元素e为新的栈顶元素 */
{
if(S->top-S->base>=S->stacksize) /* 栈满，追加存储空间 */
{
S->base=(SElemType*)realloc(S->base,(S->stacksize+S tackincrement)*sizeof(SElemType));
if(!S->base)exit(Overflow);
S->top=S->base+S->stacksize;
S->stacksize+=Stackincrement;
} /* if */
S->top->data=e;
++S->top;
} /* Push() */

Status Pop(SqStack *S,SElemType **e)
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回Ok；否则返回Error */
{
if(S->top==S->base)
return Error;
else
{
(*e)->data=(S->top-1)->data;
--S->top;
} /* else */
return Ok;
} /* Pop() */

void CreateGraph(ALGraph *G)
/* 生成G的存储结构-邻接表 */
{
int w,i,j,k;
char sv,tv;
ArcNode *pi,*pj;

printf("Please input the number of the vertex and arc:\n");
printf("vertex:"); /* 输入顶点数 */
scanf("%d",&G->vexnum);
printf("arc:"); /* 输入弧数 */
scanf("%d",&G->arcnum);
printf("Please input the vertex:");
getchar();

for(i=0;i<G->vexnum;i++) /* 构造顶点数组 */
{
scanf("%c",&G->vertices.data); /* 输入顶点 */
G->vertices.firstarc=Null; /* 初始化链表头指针为空 */
}

getchar();
for(k=0;k<G->arcnum;k++) /* 输入各边并构造邻接表 */
{
pi=(ArcNode*)malloc(sizeof(ArcNode));
if(!pi)
exit(Overflow); /* 分配存储失败 */
printf("Please input two points of one arc and it's weight:");
scanf("%c%c%d",&sv,&tv,&w); /* 输入一条弧的始点和终点及其权值 */

getchar();
pi->weight=w;
i=LocateVex(G,sv); /* 确定sv和tv在G中位置，即顶点在G->vertices中的序号 */
j=LocateVex(G,tv);
pi->adjvex=j; /* 对弧结点赋邻接点位置 */
pi->nextarc=G->vertices.firstarc;
G->vertices.firstarc=pi; /* 插入链表G->vertices */

pj=(ArcNode*)malloc(sizeof(ArcNode));
if(!pj)
exit(Overflow); /* 分配存储失败 */
pj->adjvex=i; /* 对弧结点赋邻接点位置 */
pj->weight=w;
pj->nextarc=G->vertices[j].firstarc;
G->vertices[j].firstarc=pj; /* 插入链表G->vertices[j] */
} /* for */
} /* CreateGraph() */

Status STraverse_Nonrecursive(ALGraph *G,int(*Visit)(TElemType))
/* 非递归遍历图G,图G采用邻接表存储方式 */
{
int record=1,i,j,k; /* record记录已经打印的顶点数目 */
SElemType *e;
SqStack *s;

s=(SqStack*)malloc(sizeof(SqStack));
if(!s)
exit(Overflow); /* 存储分配失败 */
InitStack(s);
Push(s,G->vertices[0].data); /* 将第一个顶点入栈 */
Visit(G->vertices[0].data); /* 访问第一个顶点 */
for(i=1;i<G->vexnum;i++)
visited=0; /* 对visited初始化为0 */
visited[0]=1; /* 第一个顶点已访问过 */

while(record<G->vexnum) /* 循环执行直到record=G->vexnum */
{
if(!StackEmpty(s))
{
while(GetTop(s,&e)&&e)
{
j=FirstAdjVex(G,*e);
while(j==-1&&!StackEmpty(s)&&GetTop(s,&e )&&e)
{
j=FirstAdjVex(G,*e);
Pop(s,&e);
}
if(j!=-1&&!visited[j])
{
Visit(G->vertices[j].data);
visited[j]=1;
record++;
Push(s,G->vertices[j].data); /* 向左走到尽头 */
if(record==G->vexnum) /* 如果所有顶点都已被访问过，则退出 */
return 1;
} /* if */
} /* while */
if(!StackEmpty(s))
{
Pop(s,&e);
GetTop(s,&e);
k=FirstAdjVex(G,*e); /* 向右走一步 */
if(k!=-1&&!visited[k])
{
Visit(G->vertices[k].data);
visited[k]=1;
Push(s,G->vertices[k].data);
record++;
if(record==G->vexnum) /* 如果所有顶点都已被访问过，则退出 */
return 1;
} /* if */
}
} /* if */
} /* while */
} /* STraverse_Nonrecursive() */

Status FirstAdjVex(ALGraph *G,char v)
/* 图G存在，v是G中的某个顶点,返回v的第一个未被访问的邻接顶点的序号，若顶点再G中没有邻接顶点，则返回-1 */
{
ArcNode *p;
int i;
for(i=0;i<G->vexnum;i++) /* 寻找v所在的邻接表中的序号 */
{
if(v==G->vertices.data)
break;
} /* for */
p=G->vertices.firstarc; /* p指向v的第一个邻接点 */
while(p)
{
if(visited[p->adjvex]) /* 如果此邻接点已被访问则p指向v的下一个邻接点 */
p=p->nextarc;
else
return p->adjvex;
} /* while */
return -1;
} /* FirstAdjVex() */

Status LocateVex(ALGraph *G,char vex)
/* 确定vex在G中的位置 */
{
int i;
for(i=0;i<G->vexnum;i++) /* 确定v1在G中位置 */
if(vex==G->vertices.data)
return i;
} /* LocateVex() */

int PrintGraph(TElemType e)
/* 输出图中的每一个结点 */
{
printf("%c ",e);
return Ok;
}

main()
{
ALGraph *G;
int i;

G=(ALGraph*)malloc(sizeof(ALGraph));
CreateGraph(G);
STraverse_Nonrecursive(G,PrintGraph);
}

③ 在C语言中编程实现建立无向图的邻接表,输出某个点的邻接点~!

用矩阵表示无向图的，设有M个节点，则建立一个MXM矩阵，对每个顶点添加它的邻接点，即每行中对于有标记的列为该行顶点的邻接点。

④ 数据结构-图的邻接表表示（C语言）

//grap_theory.cpp:定义控制台应用程序的入口点。

//#include"stdafx.h"//VS2010头文件

#include<stdio.h>

#defineNTOTAL(26*4)//最大路径数目

#defineMAX_DISTANCE10000.0

structpiont{

intline_adjacency_list;

intnum_piont;

inttest_num[2];

charfrom[NTOTAL];

charto[NTOTAL];

charall_piont[NTOTAL];

intall_piont_num[NTOTAL];

floatdistance[NTOTAL];

floatdistance_all[NTOTAL][NTOTAL];

};//结构体定义

voidread(piont*test){

inti;

chartemp[100];

scanf("%d",&test->line_adjacency_list);//读取行数

gets(temp);//读取回车字符

for(i=0;i<test->line_adjacency_list;i++){//读取列表

scanf("%c%c%f",&test->from[i],&test->to[i],&test->distance[i]);

gets(temp);//读取回车字符

}

scanf("%c%c",&test->from[i],&test->to[i]);//读取短短路径名称

}

voidcal_num_piont(piont*test){

inti,j;

intfrom_num,to_num;

test->num_piont=0;

for(i=0;i<NTOTAL;i++){

test->all_piont_num[i]=0;//点的度数清零

test->distance_all[i][i]=0.0;

for(j=i+1;j<NTOTAL;j++){

test->distance_all[i][j]=MAX_DISTANCE;

test->distance_all[j][i]=MAX_DISTANCE;

}

for(i=0;i<test->line_adjacency_list;i++){

//判断from

for(j=0;j<test->num_piont;j++){

if(test->from[i]==test->all_piont[j]){

from_num=j;

test->all_piont_num[j]++;

break;

}

if(j==test->num_piont){

test->all_piont[j]=test->from[i];

from_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

//判断end

for(j=0;j<test->num_piont;j++){

if(test->to[i]==test->all_piont[j]){

to_num=j;

test->all_piont_num[j]++;

break;

}

if(j==test->num_piont){

test->all_piont[j]=test->to[i];

to_num=j;

test->all_piont_num[j]++;

test->num_piont++;

}

test->distance_all[from_num][to_num]=test->distance[i];

test->distance_all[to_num][from_num]=test->distance[i];

}

//判断所求点的位置

for(i=0;i<test->num_piont;i++){

if(test->from[test->line_adjacency_list]==test->all_piont[i])

test->test_num[0]=i;

if(test->to[test->line_adjacency_list]==test->all_piont[i])

test->test_num[1]=i;

}

floatmin_distance(piont*test){

inti,j,k,n;

floatmin_dis;

floatdis_i_k_add_k_j;

n=test->num_piont;

//Floyd-Warshall算法

for(k=0;k<n;k++){

for(i=0;i<n;i++){

for(j=0;j<n;j++){

dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);

if(test->distance_all[i][j]>dis_i_k_add_k_j)

test->distance_all[i][j]=dis_i_k_add_k_j;

}

min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];

returnmin_dis;

}

voidtest_printf(piont*test,floatmin_dis){

inti;

printf("%d ",test->num_piont);

for(i=0;i<test->num_piont;i++){

printf("%d ",test->all_piont_num[i]);

}

printf("%-8.0f ",min_dis);

}

voidmain()

{

floatmin_dis;

pionttest1;//结构体声明

read(&test1);

cal_num_piont(&test1);

min_dis=min_distance(&test1);

test_printf(&test1,min_dis);

}

⑤ C语言关于图的邻接表建立

#include "iostream.h"

const int Max_vertex=5;
const int Max_Edge=8;
int visited[Max_vertex+1]; //访问标志数组

struct ArcNode
{
int adjvex;
ArcNode *nextarc; //指向下一条弧
};

struct Vnode
{
int v; //顶点信息
ArcNode *next;
}a[Max_vertex+1];

/* 无向图的建立 */
void creategraph()
{
int i,j,k;
ArcNode *s;
//初始化
for(i=1;i<=Max_vertex;i++)
{
a[i].v=i;
a[i].next=NULL;
}

/*以头插法建立 */

for(k=1;k<=Max_Edge;k++)
{
cout<<"请输入第"<<k<<"条边:";
cin>>i>>j;
if(i>9||i<0||j<0||j>9)
{
cout<<"输入错误!!\n"<<endl;
break;
}
else{
cout<<endl;
s=new ArcNode;
s->adjvex=j;
s->nextarc=a[i].next;
a[i].next=s;
s=new ArcNode;
s->adjvex=i;
s->nextarc=a[j].next;
a[j].next=s;
}
}
}

void display()
{
ArcNode *p;
cout<<"你建立的图为:"<<endl;
for(int i=1;i<=Max_vertex;i++)
{
p=a[i].next;
cout<<a[i].v<<"->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"->";
p=p->nextarc;
}
cout<<p->adjvex<<endl;
}
}

void main()
{
cout<<"/******\t本算法以关插法建立无向图的邻接表为例!\t******/"<<endl;
char yn='y';int k;
creategraph();
display();

}

⑥ c语言，关于邻接表的建立

AdjList 是自定义类型，是char类型，
第二行 typedef将char类型自定义为 VertexType，即VertexType代表了char型，
VertexType a 就相当于 char a；

同理

倒数第五行 typedef将VertexNode自定义为 AdjList[MaxVertexNum]类型，也就是说现在AdjList就代表了一个 “结构体数组” 类型
AdjList adjlist 相当于 VertexNode adjlist[MaxVertexNum]

这里主要是typedef关键字的使用希望能帮到你

⑦ c语言图的邻接表建立，建立应该怎么写，说一下具体的思路就行，不要给代码

在读入顶点信息的时候，将每个点的第一条置为空。如node[x].first_edge = NULL
读入每条边的时候，边的信息应该包括这条边所连接的两个点，即为ilink和jlink。然后执行
edge = malloc...
edge->next_edge = node[ilink].first_edge;
node[ilink].first_edge = edge;
即，将ilink的第一条边指向刚刚输入的这条边，而该边的下一条边置为原本ilink的第一条边。
重复这一过程，直至读完所有边的信息。

⑧ 求个有向图的邻接表（C语言）

#include <stdio.h>
#include<stdlib.h>
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
int *info; // 该弧相关信息的指针
}ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧
}VNode, AdjList[50];
typedef struct {
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
}ALGraph;

int locateALG(ALGraph g,int v){
for(int i=0;i<g.vexnum;i++){
if(g.vertices[i].data==v)
return i;
}
return -1;
}

int CreateADG(ALGraph &g){
int i,j,k,l;
ArcNode *p;
int v1,v2;
int c;
printf("请输入有向图的顶点数:");
scanf("%d",&g.vexnum);
while(g.vexnum>50){

printf("\n请输入有向图的顶点数：");
scanf("%d",&g.vexnum);
}
i=g.vexnum*(g.vexnum-1);
printf("请输入有向图的边数:");
scanf("%d",&g.arcnum);
while(g.arcnum>i){

printf("\n请输入有向图的边数：");
scanf("%d",&g.arcnum);
}
getchar();
printf("请依次输入有向图的各个顶点:");
for(i=0;i<g.vexnum;i++){//输入顶点信息

scanf("%d",&c);
l=locateALG(g,c);
if(l>=0){
printf("输入的顶点重复，请重新输入\n");
i--;
continue;
}
g.vertices[i].data=c;
g.vertices[i].firstarc=NULL;
}
for(k=0;k<g.arcnum;k++){//输入边的信息

printf("请输入第%d条弧的起点与终点(用逗号分隔)：",k+1);
scanf("%d,%d",&v1,&v2);
i=locateALG(g,v1);
j=locateALG(g,v2);
if(i<0||j<0||i==j||(g.vexnum<0)){

k--;
continue;
}
p=(ArcNode*)malloc(sizeof(ArcNode));//建立结点
if(!p) return -1;

p->adjvex=j;
p->nextarc=g.vertices[i].firstarc;//顶点i的链表
g.vertices[i].firstarc=p;//添加到最左边

}
printf("有向图的邻接表创建成功\n");
return 1;
}

void printGra(ALGraph G){
ArcNode *p;
int i;
printf("图中有%d个顶点，%d条弧：\n",G.vexnum,G.arcnum);
for(i=0;i<G.vexnum;i++){
p=G.vertices[i].firstarc;
printf("%d\t",G.vertices[i].data);
while(p){
printf("<%d,%d>",G.vertices[i].data,G.vertices[p->adjvex].data);
p=p->nextarc;
}
printf("\n");
}
}
int main(void)
{
ALGraph g;
CreateADG(g);
printGra(g);
return 0;
}

阅读全文

邻接表c语言

与邻接表c语言相关的阅读推荐