十字链表又来:

1.为了方便得到一个图的 入度 或者 出度
2.为了解决邻接表(可以方便得出 图的出度) 和 逆邻接表(可以方便得到 图的 入度)所存在的瑕疵,

具体代码

代码入口函数:void binaryTreeMain(void)
开发环境: C++ 环境

#define MAXLEN 20


// 这个是用来存储边(弧)
typedef struct arcnode{
    int tailVex,headVex; //弧尾 和 弧头顶点的下表
    struct arcnode *tlink,*hlink; //指向 弧尾 和 同弧头的下一个弧节点的指针
    int weight;  // 弧的权值信息
}ArcNode;  // 定义弧节点的类型

// 这个是用来存储顶点的
typedef struct vexnode{
    
    char vertex; // 顶点标志
    ArcNode *firstIn, *firstOut; //指向第一个弧头节点 和 弧尾节点的指针
}VexNode;  //定义顶点结构类型

// 这个是用来存储图的
typedef struct {
    
    VexNode list[MAXLEN];  // 顶点数组
    int vexNum,arcNum; //顶点数 和 弧数
    
}OLGraph;  // 定义十字链表



void createOrthList(OLGraph &G){
    ArcNode *p;
    
    int i,j;
    char arcTail,arcHead; // 弧头 和 弧尾
    
    printf("请输入有向网的顶点数 和 弧数:\n");
    scanf("%d,%d",&G.vexNum,&G.arcNum);
    getchar();
    
    printf("请依次输入%d个顶点(用enter分割):\n",G.vexNum);
    
    for (int i = 0; i < G.vexNum; i++) {
        scanf("%c",&G.list[i].vertex);
        getchar();
        G.list[i].firstIn = NULL;
        G.list[i].firstOut = NULL;
    }
    

    
    printf("顶点数组创建成功");
    
    for (int i = 0; i < G.arcNum; i++) {
        
        p = new ArcNode; // 这里是开辟一个弧节点
        
        printf("请依次输入第%d条弧的弧尾,弧头标志和弧的权值(用逗号分割):\n",i+1);
        scanf("%c,%c,%d",&arcTail,&arcHead,&p->weight);
        getchar();
        
        for (int j = 0; j < G.vexNum; j++) {  // 这个for 循环的意义,找到弧头 和 弧尾的 位置.
            
            if (G.list[j].vertex == arcTail) {
                p->tailVex = j;
            }
            
            if (G.list[j].vertex == arcHead) {
                p->headVex = j;
            }
        }
        
        p->tlink = G.list[p->tailVex].firstOut;
        G.list[p->tailVex].firstOut = p;
        p->hlink = G.list[p->headVex].firstIn;
        G.list[p->headVex].firstIn = p;
        
    }
    
    printf("十字链表创建成功");
}