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关键字的使用 希望能帮到你