#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVex 20
typedef struct ArcNode
{//int arcData;//这是权值，我们不需要暂时int headVertex, tailVertex;//(vi,vj)入边->出边struct ArcNode* nextHeadArc, * nextTailArc;//下一个出边地址 下一个入边地址
}ArcNode,*ArcList;
typedef struct VertexNode
{char vertexData;ArcList headList, tailList;//出边地址 入边地址
}VertexNode,*VertexList;
typedef struct
{VertexList vertexList_arr;//VertexList类型数组int numVertexs, numArcs;//顶点数+边数（弧）;
}OLGraph;
//初始化十字链表
void initOLGraph(OLGraph* G)
{G->numArcs = 0;G->numVertexs = 0;G->vertexList_arr = (VertexList*)malloc(MAXVex * sizeof(VertexNode));//给这个数组分配空间 20int i;for (i = 0; i < MAXVex; i++){//出边地址和入边地址的指针全部申请空间//指向头的的弧链表初始化G->vertexList_arr[i].headList = (ArcNode*)malloc(sizeof(ArcNode));G->vertexList_arr[i].headList->nextHeadArc = NULL;G->vertexList_arr[i].headList->nextTailArc = NULL;//指向尾的弧链表初始化G->vertexList_arr[i].tailList = (ArcNode*)malloc(sizeof(ArcNode));G->vertexList_arr[i].tailList->nextHeadArc = NULL;G->vertexList_arr[i].tailList->nextTailArc = NULL;}printf("十字链表初始化成功\n");
}
void CreateOLGraph(OLGraph* G)
{printf("请输入顶点数和边数\n");scanf("%d%d", &G->numVertexs, &G->numArcs);getchar();//吸收scanf残留的换行符int i, j, k;printf("请输入顶点的信息\n");for (i = 0; i < G->numVertexs; i++){scanf("%c", &G->vertexList_arr[i].vertexData);//3}for (k = 0; k < G->numArcs; k++){printf("请输入(vi,vj)的边数,一共有%d条\n", G->numArcs);scanf("%d%d", &i, &j);ArcNode* s;s = (ArcNode*)malloc(sizeof(ArcNode));//(vi,vi)s->headVertex = i;s->tailVertex = j;//由顶点的顺序结构出边地址指向s//i是指向j的出度，那么j就是接收i的入度s->nextHeadArc = G->vertexList_arr[i].headList->nextHeadArc;G->vertexList_arr[i].headList->nextHeadArc = s;s->nextTailArc = G->vertexList_arr[j].tailList->nextTailArc;G->vertexList_arr[j].tailList->nextTailArc = s;}printf("十字链表创建完成\n");
}
void DisplayOLGraph(OLGraph G)
{int i;ArcNode* p;for (i = 0; i < G.numVertexs; i++){printf("顶点:%c\n", G.vertexList_arr[i].vertexData);printf("\t出度: ");p = G.vertexList_arr[i].headList;//p指向出度指针地址while (p->nextHeadArc)//下一个出度不为NULL{p = p->nextHeadArc;//第一次指向第一个出度s 然后一直下一个出度地址printf("(%c,%c) -> ",G.vertexList_arr[p->headVertex].vertexData,G.vertexList_arr[p->tailVertex].vertexData);//p->headVertex -> i(0)即 V1}printf("NULL\n");printf("\t入度: ");p = G.vertexList_arr[i].tailList;//p指向入度的指针地址while (p->nextTailArc)//下一个入度不为NULL{p = p->nextTailArc;//第一次指向第一个入度的s，然后一直下去找printf("(%c,%c) -> ", G.vertexList_arr[p->headVertex].vertexData,G.vertexList_arr[p->tailVertex].vertexData);}printf("NULL\n");}
}
int main()
{OLGraph G;initOLGraph(&G);CreateOLGraph(&G);DisplayOLGraph(G);return 0;
}运行后终端输入内容如下:
十字链表初始化成功
请输入顶点数和边数
4 7
请输入顶点的信息
0123
请输入(vi,vj)的边数,一共有7条
0 1
请输入(vi,vj)的边数,一共有7条
0 2
请输入(vi,vj)的边数,一共有7条
3 0
请输入(vi,vj)的边数,一共有7条
3 1
请输入(vi,vj)的边数,一共有7条
3 2
请输入(vi,vj)的边数,一共有7条
2 0
请输入(vi,vj)的边数,一共有7条
2 3
十字链表创建完成
顶点:0
出度: (0,2) -> (0,1) -> NULL
入度: (2,0) -> (3,0) -> NULL
顶点:1
出度: NULL
入度: (3,1) -> (0,1) -> NULL
顶点:2
出度: (2,3) -> (2,0) -> NULL
入度: (3,2) -> (0,2) -> NULL
顶点:3
出度: (3,2) -> (3,1) -> (3,0) -> NULL
入度: (2,3) -> NULL
