数据结构复习笔记

### 数据结构复习笔记 #### 图的数组（邻接矩阵）存储表示及重要的基本操作 **图**是一种非线性数据结构，由顶点集V和边集E组成，表示为G=(V,E)。其中边可以是有向的也可以是无向的。在计算机科学中，图通常用于模拟各种复杂的关系和连接，如社交网络、路径规划等问题。 **邻接矩阵**是一种常见的图存储方法，特别适用于稠密图（即边的数量接近于顶点数量的平方）。对于具有n个顶点的图来说，可以用一个n×n的二维数组来表示这个图。数组中的元素A[i][j]代表了顶点i到顶点j是否存在边以及这条边的权重。 ### 邻接矩阵表示法详解 在邻接矩阵表示法中，我们首先定义了一个`MGraph`结构体来存储整个图的信息： ```c typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 ArcCell AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; ``` 其中： - `VertexType vexs[MAX_VERTEX_NUM]`：用于存储图的所有顶点。 - `ArcCell AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]`：二维数组，用于表示图的邻接矩阵。 - `int vexnum, arcnum`：分别表示图的当前顶点数和弧数。 - `GraphKind kind`：表示图的种类标志，可以通过枚举类型`GraphKind`来指定。 枚举类型`GraphKind`定义如下： ```c typedef enum {DG, DN, UDG, UDN} GraphKind; ``` - `DG`：有向图 - `DN`：有向网 - `UDG`：无向图 - `UDN`：无向网 **ArcCell**结构体定义了邻接矩阵中的单个元素： ```c typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 InfoType *info; // 该弧相关信息的指针(可无) } ArcCell; ``` - `VRType adj`：表示两个顶点之间是否相连以及边的权重。如果是无权图，则用1表示相连，0表示不相连；如果是带权图，则直接存储边的权重。 - `InfoType *info`：指向该弧附加信息的指针，可以为空。 ### 邻接矩阵的基本操作 1. **定位顶点**（`LocateVex`） - **功能**：根据给定的顶点值查找其在图中的位置。 - **输入**：图`G`和顶点值`u`。 - **输出**：返回顶点`u`在图中的索引位置，如果找不到则返回`NULL`。 - **代码实现**： ```c Status LocateVex(MGraph G, VertexType u) { int i; for (i = 0; i < G.vexnum; ++i) if (strcmp(u, G.vexs[i]) == 0) return i; return NULL; } ``` 2. **创建图**（`CreateDG`） - **功能**：使用数组（邻接矩阵）表示法构造一个有向图。 - **输入**：引用类型的图`G`。 - **输出**：无。 - **代码实现**： ```c Status CreateDG(MGraph &G) { // 输入图的信息并构建邻接矩阵 } ``` 这里仅给出了函数的声明，具体的实现逻辑需要根据具体的应用场景来确定。 ### 小结 通过邻接矩阵表示法，我们可以方便地表示和操作图结构。这种方法适用于顶点之间的连接比较密集的情况，并且能够支持多种基本操作，例如定位顶点、添加边等。在实际应用中，选择合适的图存储方式是非常重要的，这将直接影响到算法的效率和性能。