最近一直忙着考研复习，很久都没有更新博客了，今天写一篇数据结构的存储。

?

?

//有向图的十字链表存储表示
//杨鑫
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define MAX_VERTEX_NUM 20 #define OVERFLOW -2 #define OK 1 typedef int Status; typedef char VertexType[MAX_VERTEX_NUM]; typedef char InfoType; //弧（边）的结构体 typedef struct ArcBox { int tailvex,headvex; //该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; //分别为弧头相同和弧尾相同的弧的链域 InfoType *info; //该弧的相关信息的指针 }ArcBox; //顶点的结构体 typedef struct VexNode { VertexType data; ArcBox *firstin, *firstout; //分别指向该顶点的第一条入弧和出弧 }VexNode; //有向图的结构体 typedef struct { VexNode xlist[MAX_VERTEX_NUM]; //表头向量 int vexnum, arcnum; //有向图的当前顶点数和弧数 }OLGraph; int LocateVex(OLGraph &G, VertexType u) { for(int i = 0; i < G.vexnum; ++i) if(strcmp(G.xlist[i].data, u) == 0) return i; return -1; } //构造有向图G; Status CreateDG(OLGraph &G) { int i,j,k; printf(请输入有向图的顶点数以及弧数: ); scanf(%d%d,&G.vexnum, &G.arcnum); printf(请输入%d个顶点的值，之间有空格隔开: ,G.vexnum); for(i=0; i
      
       tailvex = i; p->headvex = j; p->hlink = G.xlist[j].firstin; p->tlink = G.xlist[i].firstout; p->info = NULL; G.xlist[j].firstin = G.xlist[i].firstout = p; //完成在入弧和出弧链头的插入 } getchar(); return OK; } void DisplayArc(OLGraph &G) { ArcBox *p; for(int i=0; i < G.vexnum; ++i) { p=G.xlist[i].firstout; while(p) { printf(<%s,%s> ,G.xlist[p->tailvex].data, G.xlist[p->headvex].data); p = p->tlink; } } printf( ); } //顶点的度：入度+出度 int VexDegree(OLGraph &G, VertexType v) { int k = LocateVex(G,v); if(k<0) exit(OVERFLOW); int id=0,od=0; //入度，出度 ArcBox *pin = G.xlist[k].firstin; ArcBox *pout = G.xlist[k].firstout; while(pin) //求入度 { ++id; pin = pin->hlink; } while(pout) //求出度 { ++od; pout = pout->tlink; } return id+od; //顶点的度 } int main() { int flag = 1; OLGraph G; CreateDG(G); printf(========================================= ); printf(该有向图的弧如下: ); DisplayArc(G); VertexType v; printf( ========================================= ); while(1) { if(flag == 0) break; printf(请输入任意顶点,将输出该顶点度的值:); scanf(%s,v); getchar(); printf(顶点 %s 的度为 :%d ,v,VexDegree(G,v)); printf(结束请输入 0 以回车键结束 ); cin>>flag; } printf(========================================= ); return 0; } 
      
     
    
   
  

?

?

结果：

?

?