當前位置：首頁 » 編程語言 » 鄰接表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語言相關的閱讀推薦