c語言逆鄰接表的存儲結構定義

① c語言對於順序表的存儲結構定義如何理解,為什麼把順序表定義成結構體類型。

你理解數組嗎？順序表說白了就是一個數組

MAXSIZE是數組最大寬度
size是數組下標，初始值為0或-1，范圍是：小於MAXSIZE
數組a是用來存儲元素

② c語言圖的遍歷，鄰接表存儲，深度，廣度優先遍歷

（1） 圖的建立，按採用鄰接表作為存儲結構。
（2） 從指定頂點出發進行深度優先搜索遍歷。
（3） 從指定頂點出發進行廣度優先搜索遍歷。

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"

#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定義隊列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}

void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("隊列滿!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("隊列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;

}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("請輸入頂點數和弧數：");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("請依次輸入頂點名：\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("請輸入相鄰的兩個定點和權值：");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}

void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}

}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);

}
}

void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}

}
}

void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("請輸入深度優先遍歷開始點的名：");
scanf("%s",name);
printf("深度優先遍歷：");
DFSTravel(ga,name);
printf("\n");
printf("請輸入廣度優先遍歷開始點的名：");
scanf("%s",name);
printf("廣度優先遍歷：");
BFSTravel(ga,name);
printf("\n");

}

③ 請教編程大神數據結構題目：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;
}

④ c語言，關於鄰接表的建立

AdjList 是自定義類型，是char類型，
第二行 typedef將char類型自定義為 VertexType，即VertexType代表了char型，
VertexType a 就相當於 char a；

同理

倒數第五行 typedef將VertexNode自定義為 AdjList[MaxVertexNum]類型，也就是說現在AdjList就代表了一個 「結構體數組」 類型
AdjList adjlist 相當於 VertexNode adjlist[MaxVertexNum]

這里主要是typedef關鍵字的使用 希望能幫到你