| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
Reworld,下班在家制作游戏,1500万奖金等你拿以码会友 以友辅仁
共有 1640 人关注过本帖
标题:【问题求助】图的十字链表
只看楼主 加入收藏
DebugEason
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2015-2-12
结帖率:0
  已结贴   问题点数:1  回复次数:1   
【问题求助】图的十字链表
程序代码:
#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这个好像有问题,把这个函数去除其他一切都正常,把这个函数加上去再输出就意外停止了,求大牛帮忙改正,小弟感激不尽!还有什么好的写建议给我说说!谢谢
2015-02-12 17:29
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:1 
你写一份测试数据看看,我测试时是正常的。

建议写一个 Destroy函数:
void DestroyALGraph(GraphAdjList &G)    //销毁十字链表并释放空间


[fly]存在即是合理[/fly]
2015-02-13 14:49
快速回复:【问题求助】图的十字链表
数据加载中...
 
   





关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031033 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved