【问题求助】图的十字链表
程序代码：#include <stdio.h>
#include <malloc.h>
#include <string.h>// 包含strcmp字符串比较函数,strlen计算字符串函数
#define MAX_NAME 100// 最大顶点数
typedef char VertexType[MAX_NAME];
typedef char InfoType;//该弧的相关信息
#define MAX_INFO 20// 最大附加信息
/* 边表结点 */
typedef struct EdgeNode
{
int tailvex;// 该弧的狐尾
int headvex;// 该弧的狐头
struct EdgeNode *headlink;// 狐头相同的下一条边
struct EdgeNode *taillink;// 狐尾相同的下一条边
InfoType *info;// 该弧的相关信息
}EdgeNode;
/* 顶点结点 */
typedef struct VertexNode
{
VertexType data;// 顶点信息
EdgeNode *firsrin;// 该结点入表边第一个结点
EdgeNode *firsrout;// 该结点出边表第一个结点
}VertexNode, AdjList;
typedef struct
{
AdjList adjlist[MAX_NAME];// 表头向量（数组）
int numVertexes;// 当前顶点个数
int numEdgexes;// 当前边个数
}GraphAdjList;
int LocateVertex (GraphAdjList &G, VertexType u)
{/* 查找u在顶点的位置，查找到则返回位置，否则返回-1 */
int i;
for (i=0; i<G.numVertexes; i++)
if (!strcmp (G.adjlist[i].data, u))// if (strcmp (G.adjlist[i].data, u) == 0)
return i;// 返回位置
return -1;
}
int InsertVerex (GraphAdjList &G)
{// 插入顶点和插入顶点相关的弧
EdgeNode *e;
int i, j, k;
int length;// 存放相关信息的长度
VertexType v1, v2, s;// 存放相关信息
int n;// 相关顶点的弧数
int Info;
printf ("请输入要插进入顶点的值：");
gets (v1);
length = strlen (v1);
if (length)
{
strcpy (G.adjlist[G.numVertexes].data, v1);
G.numVertexes ++;
printf ("请输入新插的顶点相关的弧数(>0)：");
scanf ("%d%*c", &n);
for (k=0; k<n; k++)
{
printf ("请输入另一个顶点 和 另一个顶点的位置(0狐头1狐尾), (以空格隔开)：");
scanf ("%s%*c%d%*c", &v2, &Info);
if (Info)
{// i=狐尾，j=狐头
j = LocateVertex (G, v1);
i = LocateVertex (G, v2);
}
else
{
j = LocateVertex (G, v2);
i = LocateVertex (G, v1);
}
if (0>i || 0>j)
return -1;
e = (EdgeNode *) malloc (sizeof (EdgeNode));
if (NULL == e)
return -1;
e->tailvex = i;
e->headvex = j;
e->headlink = G.adjlist[j].firsrin;
e->taillink = G.adjlist[i].firsrout;
G.adjlist[j].firsrin = G.adjlist[i].firsrout = e;
G.numEdgexes ++;
printf ("请输入该弧是否有相关信息(1是，0否)：");
scanf ("%d%*c", &Info);
if (Info)
{
printf ("请输入相关信息：");
gets (s);
length = strlen (s);
if (length)
{
e->info= (InfoType *) malloc ((length + 1) * sizeof (InfoType));
strcpy (e->info, s);
}
else
printf ("输入字符无效！\n");
}
else
e->info = NULL;
}
}
else
{
printf ("插入失败，输入顶点的值无效！\n");
return -1;
}
return 0;
}
int PutVerex (GraphAdjList &G)
{// 替换
int i;
VertexType v1, v2;// 定义原始顶点和要替换顶点的数组变量
printf ("请输入原始顶点和要替换的顶点(以空格隔开)：");
scanf ("%s%c%s%*c", &v1, &v2);
i = LocateVertex (G, v1);// 查找位置原始顶点在数组中的位置
if (0 > i)
return -1;// 不在范围
strcpy (G.adjlist[i].data, v2);// 完成替换
return 0;
}
void CreateALGraph (GraphAdjList &G)
{// 采用十字链表的存储方式构造有向图
int i, j, k;
InfoType s[MAX_INFO];// 存放相关信息有无
int length;// 存放相关信息的长度
int IncInfo;// 记录相关信息有无
VertexType v1, v2;
EdgeNode *e;
printf ("请输入有向图的顶点数和弧数，相关信息1（有），0（无）(以空格隔开)：");
scanf ("%d%*c%d%*c%d%*c", &G.numVertexes, &G.numEdgexes, &IncInfo);
for (i=0; i<G.numVertexes; i++)
{// 输入顶点信息并且初始化入边表和出边表的指针域；
printf ("请输入第%d个顶点信息：", i+1);
scanf ("%s%*c", &G.adjlist[i].data);
G.adjlist[i].firsrin = NULL;
G.adjlist[i].firsrout = NULL;
}
printf ("*********请输入%d条的弧***********\n", G.numEdgexes);
for (k=0; k<G.numEdgexes; k++)
{
printf ("请输入第%d条的狐尾→狐头(以空格隔开)：", k+1);
scanf ("%s%*c%s%*c", &v1, &v2);// 为了代码的清晰加取地址符号，也可以不要取地址符号；
i = LocateVertex (G, v1);// 狐尾在顶点的位置
j = LocateVertex (G, v2);// 狐头在顶点的位置
e = (EdgeNode *) malloc (sizeof (EdgeNode));
e->tailvex = i;
e->headvex = j;
e->taillink = G.adjlist[i].firsrout;
e->headlink = G.adjlist[j].firsrin;
G.adjlist[i].firsrout = G.adjlist[j].firsrin = e;
if (IncInfo)
{
printf ("请输入该弧的相关信息(<%d字符)：", MAX_INFO);
gets (s);
length = strlen (s);
if (length)
{
e->info = (InfoType *) malloc ((length + 1) * sizeof (InfoType));
strcpy (e->info, s);
}
}
else
e->info = NULL;
}
}
void Display (GraphAdjList &G)
{// 输出有向图
EdgeNode *e;
int i;
printf ("一共有%d个顶点和%d条弧\n", G.numVertexes, G.numEdgexes);
for (i=0; i<G.numVertexes; i++)
{
printf ("************顶点%s*********\n", G.adjlist[i].data);
printf ("\n入度：\n");
e = G.adjlist[i].firsrin;
if (e)
{
while (e)
{
printf ("%s→%s ", G.adjlist[e->tailvex].data, G.adjlist[i].data, e->info);
if (e->info)
printf ("相关信息：%s\n", e->info);
e = e->headlink;
}
printf ("\n");
}
else
printf ("该顶点的入度为空！\n");
printf ("出度：\n");
e = G.adjlist[i].firsrout;
if (e)
{
while (e)
{
printf ("%s→%s ", G.adjlist[i].data, G.adjlist[e->headvex].data);
if (e->info)
{
printf ("相关信息：%s\n", e->info);
}
e = e->taillink;
}
printf ("\n");
}
else
printf ("该顶点的出度为空！\n");
}
return;
}
int main (void)
{
GraphAdjList G;
CreateALGraph (G);//构建有向图，采用十字链表
// Display (G);// 输出十字链表存储结构的有向图
// PutVerex (G);//替换
// Display (G);// 输出十字链表存储结构的有向图
InsertVerex (G);// 插入顶点和新插顶点相关的弧
Display (G);// 输出十字链表存储结构的有向图
return 0;
}
插入函数InsertVerex这个好像有问题，把这个函数去除其他一切都正常，把这个函数加上去再输出就意外停止了，求大牛帮忙改正，小弟感激不尽！还有什么好的写建议给我说说！谢谢
