首页 > 代码库 > 有向图的十字链表存储形式

有向图的十字链表存储形式

2024-07-10 01:56:37   218人阅读

十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表（只考虑入度）结合起来得到的一种链表。在十字链表中，对应于有向图中每一个顶点有一个节点，每一条弧也有一个结点。
顶点之间是数组顺序存储，而弧是链式存储。

弧结点结构：


顶点结点结构：


十字链表形态：


实现：

/***********************************************
有向图的存储形式——十字链表
by Rowandjj
2014/6/27
***********************************************/
#include<IOSTREAM>
using namespace std;

#define MAX_VERTEX_NUM 20//顶点最大长度
#define MAX_INFO 20//弧信息的最大长度

typedef struct _ARCBOX_//弧结点
{
    int tailvex,headvex;//该弧的尾和头顶点的位置
    struct _ARCBOX_ *hlink,*tlink;//分别为弧头相同和弧尾相同的弧的链域
    char *info;
}ArcBox;

typedef struct _VEXNODE_//顶点
{
    char data;//顶点名称
    ArcBox *firstin,*firstout;
}VexNode;

typedef struct _OLGRAPH_//图
{
    VexNode xlist[MAX_VERTEX_NUM];//表头向量(数组)
    int vexnum,arcnum;//顶点数目，弧数目
}OLGraph;

//------------------操作定义---------------------------------
int LocateVex(OLGraph G,char u);//返回顶点u在有向图G中的位置(序号),如不存在则返回-1
bool CreateDG(OLGraph* G);//采用十字链表存储表示,构造有向图G
void Display(OLGraph G);//输出有向图G
void DestroyGraph(OLGraph* G);//销毁有向图G
char GetVex(OLGraph G,int v);//返回v的值
bool PutVex(OLGraph* G,char v,char value);//对v赋新值value
int FirstAdjVex(OLGraph G,char v);//返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
int NextAdjVex(OLGraph G,char v,char w);//返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1   
void InsertVex(OLGraph* G,char v);//在有向图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)   
bool DeleteVex(OLGraph* G,char v);//删除G中顶点v及其相关的弧
bool InsertArc(OLGraph* G,char v,char w);//在G中增添弧<v,w>
bool DeleteArc(OLGraph* G,char v,char w);//在G中删除弧<v,w> 
   
void DFSTravel(OLGraph G,void (*Visit)(char));
void DFS(OLGraph G,int v);
void BFSTravel(OLGraph G,void (*Visit)(char));

void (*VisitFunc)(char);  //全局函数指针 
bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
//-----------------------------------------------------------
void Visit(char p)
{
    cout<<p<<" ";    
}

//辅助队列
typedef struct _QUEUENODE_
{
    int data;
    struct _QUEUENODE_ *next;
}QueueNode;
typedef struct _QUEUE_
{
    QueueNode *pHead;
    QueueNode *pTail;
    int size;
}Queue;
bool InitQueue(Queue *Q);
bool DestroyQueue(Queue *Q);
bool DeQueue(Queue *Q,int* e);
bool EnQueue(Queue *Q, int e);
bool QueueEmpty(Queue Q);
//-----------------------------------------------------------
bool InitQueue(Queue *Q)
{
    Q->pHead = Q->pTail = (QueueNode*)malloc(sizeof(QueueNode));
    if(!Q->pHead)
    {
        return false;
    }
    Q->pHead->next = NULL;
    Q->size = 0;
    return true;
}
bool EnQueue(Queue *Q, int e)
{
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if(!newNode)
    {
        return false;
    }
    newNode->data = http://www.mamicode.com/e;>
测试：


联系
我们