十字链表的建立

雨点打透心脏的1/2处 2022-07-29 06:30 153阅读 0赞

前几天设计图的存储想当然的想到了十字链表。今天发现在这次使用中，其实和邻接表是一样的，就准备换成邻接表就把十字链表记录下来吧

十字链表是一个节点既有指向出度的边，也有指向入度的边。

\#define MAX\_VERTEX\_NUM 60  
  
struct ArcBox            //定义弧节点      
\{                          
    int tailvex;        //该弧尾节点位置  
    int    headvex;        //该弧头结点位置  
    struct ArcBox \*hlink;    //与该弧 弧头相同的弧  
    struct ArcBox \*tlink;    //与该弧弧尾相同的弧  
    int weight;            //该弧的权值  
\};  
struct VexNode            //定义节点  
\{  
    int data;            //数据域  
    ArcBox \*fristin;    //第一条入弧  
    ArcBox \*firstout;    //第一条出弧  
  
\};  
  
struct OLGraph  
\{  
    VexNode xlist\[MAX\_VERTEX\_NUM\];  
    int vexnum;                //节点数  
    int arcnum;                //弧数  
\};

//建立图

int GraphFromFile(char \* fileName, VexNode \*V)            //从文件中读取，并在内存中按十字链表存放  
\{  
    ArcBox \*arcp;  
    int order;  
  
    FILE \*fp = fopen(fileName, "r");  
  
    if (fp == NULL)  
    \{  
        printf("Fail to open file %s.\\n", fileName);  
        return 0;  
    \}  
    while (!feof(fp))  
    \{  
        arcp = (ArcBox \*)malloc(sizeof(struct ArcBox));  
        arcp->hlink = NULL;  
        arcp->tlink = NULL;  
        fscanf(fp, "%d,%d,%d,%d\\n", &order, &(arcp->headvex), &(arcp->tailvex), &(arcp->weight));//按文件存放读取数据  
        arcp->tlink = V\[arcp->headvex\].firstout;                //将弧插入到弧尾相同的链中。  
        V\[arcp->headvex\].firstout = arcp;  
  
        arcp->hlink = V\[arcp->tailvex\].fristin;                    //将弧插入到弧头相同的链中。  
        V\[arcp->tailvex\].fristin = arcp;  
        printf("read a line:%4d %4d %4d %4d\\n", order, arcp->headvex, arcp->tailvex, arcp->weight);  
    \}  
  
  
    fclose(fp);  
      
  
\}