二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(19)

typedef struct ArcNode { // 弧结点

int adjvex; // 邻接点

struct ArcNode *nextarc; // 下一个邻接点

} ArcNode;

typedef struct VexNode { // 顶点结点

VertexType data; // 顶点信息

ArcNode *firstarc; // 第一个邻接点

} VexNode;

const int MAX_VERTEX = 最大顶点个数;

typedef struct Graph { // 图

VexNode vexs[MAX_VERTEX]; // 顶点向量

int vexnum, arcnum; // 顶点和弧的个数

} Graph;

边(弧)多则需要存储空间多。

14

逆邻接表

15简言之，“数组(弧头顶点)+链表(逆邻结点)+个数”。

类型定义类似邻接表。

十字链表

16简言之，“数组(顶点)+弧结点(含头和尾)+个数”。边可以看作两条弧。

typedef struct ArcNode { // 弧结点

int vtail, vhead; // 弧尾和弧头顶点编号

struct ArcNode *nexttail, *nexthead; // 指向同弧尾和同弧头的弧结点 } ArcNode;

14

15

16 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

typedef struct VexNode { // 顶点结点

VertexType data; // 顶点信息

ArcNode *firstin, *firstout; // 指向第一条入弧和第一条出弧 } VexNode;

const int MAX_VERTEX = 最大顶点个数;

typedef struct Graph { // 图

VexNode vexs[MAX_VERTEX]; // 顶点向量

int vexnum, arcnum; // 顶点和弧的个数

} Graph;

弧结点中包含两个指针分别指向同一弧头的下一个弧和同一个弧尾的下一个弧。顶点结点则指向第一个同弧头和弧尾的弧。十字链表相当于邻接表和逆邻接表的结合。

技巧：把弧结点按行排整齐，然后画链表。同弧尾的弧组成链表，同弧头的弧组成链表。 邻接多重表

17简言之，“数组(顶点)+边结点”。

typedef struct EdgeNode { // 边结点

int vexi, vexj;

struct EdgeNode *nexti, *nextj;

} EdgeNode;

typedef struct VexNode { // 顶点结点

VertexType

EdgeNode *firstedge;

} VexNode;

const int MAX_VERTEX = 最大顶点个数;

typedef struct Graph { // 图

VexNode vexs[MAX_VERTEX];

int vexnum, edgenum;

} Graph;

只适合存储无向图，不能存储有向图。

17// 边的两个顶点 // 两个顶点所依附的下一条边 data; // 顶点信息 // 指向第一条边 // 顶点向量 // 顶点和边的个数 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

技巧：把边结点按列排整齐，然后画链表。相同顶点组成链表，这里没有起点和终点的区别。 图的遍历

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-19.html