Graph
Created|Updated
|Post Views:
图的存储
邻接矩阵
我们使用邻接矩阵来表示图的边。
邻接表法
这里的表是指链表。
表面一个顶点所邻接的边。
Related Articles
2020-05-12
顺序队列
前言队列也是一种表。它把线性表限制了只能在第一项删除和最后一项添加数据。由此，它的结构– 指向头和尾的指针 每一项的数据 由于队列的删除和插入操作，需要移动数据而且时间复杂度为O(n)，但可以通过引入循环队列来使得时间复杂度变为O(1) 队列也同线性表类似，可以有两种存储结构。顺序存储结构 和 链式存储结构 顺序存储说明同样地，顺序存储结构用到数组来实现。结构中记录头和尾的指针其实是数组的下标(int)（front,rear)注意，rear是指队尾元素的下一个位置，front是队头（第一个元素） 空队列的判断。所以，当rear == front的时候，不是还剩一个元素，而是空队列。（一个元素都没有） 当我们用循环队列的时候，如果，元素把整个数组都占满的时候，那么rear == front着个等式不是也成立吗？那么我们怎么区分满队列和空队列呢？我们应该采取一种方法—永远不要让元素占满整个数组。应该留一个空位。 满队列的判断。因为要留下一个位置不能用，要用Q->rear + 1 == Q->front判断队列为满 队列长度。因为队列是循环结构，所以可能...
2020-05-17
二叉树的存储结构
前言二叉树也有顺序存储结构和链式存储结构。由于二叉树是一种特殊的树，所以也可以通过顺序存储结构来实现。因为是顺序存储结构，所以要用数组来实现。 顺序存储结构 存放数据的区域（数组），而且数组的下标也要体现节点间的逻辑关系。 数组的大小要定义为完全二叉树的大小。当中某些节点有可能是为空的，所以顺序存储结构一般只用于完全二叉树，否则会造成空间的浪费。 链式存储结构既然顺序存储结构的适用性不强，所以将引入二叉链表。它一般被分为两个区域——数据区和指向左右孩子的指针区。然而它还可以在指针区增加一个指针来指向父母。 123456789typedef struct Node *PtrToNode;typedef PtrToNode Tree;typedef int ElementType;typedef struct Node{ ElementType e; PtrToNode lchild, rchild;}Node
2020-05-26
图的存储结构
前言由于图的多方向性，不能用顺序存储结构来实现。如果我用多重链表的话，那么结构中的多个指针就会造成空间资源的浪费（因为图的顶点上的度是不确定的）。因此图的存储结构，不应该使用物理存储去实现。图的实现被提供了5种存储结构。1. 邻接矩阵 2.邻链表 3.十字链表 4. 邻接多重链表 5. 边集数组。 邻接矩阵由顶点数组（一维）和边或弧数组（二维）组成 无向图 例如a[i][j]的0，1值表示，从i–j这个edge是否存在，1存在，0不存在。所以类似于a[i][i]这样的顶点到顶点的值都为0 无向图的边数组是一个对称矩阵，即满足a[i][j] == a[j][i]因为它是无向的，i–j不存在，则j–i也不存在。那么i–j存在，则，j–i也存在啊所以，在无向图中a[i][j]和a[j][i]无区别 Vi的度就是把第i行（或列）的元素加起来 有向图 有向图就不是对称矩阵了。因为它们顶点的指向是有方向的，i–>j不一定j–>i。 出度和入度。有向图中，要研究这两个。只要知道前面的指向问题，就可以知道。Vi的出度是看矩阵中的行a[i]--[]，Vi的入度是看矩阵中的...
2022-01-28
Stack
栈栈也是一种线性表，它也可以由顺序表，和链表来实现。 只不过栈是一种被限制的线性表，它只能对栈顶（线性表的最末端的元素）进行基本操作（增删改查）。 本次，主要讲栈的顺序存储结构。 顺序栈结构 数组data[MaxSize] 当前栈顶top 1234typedef struct { ElemType data[MaxSize]; int top;}SqStack; 操作流程图 实现代码1234567891011121314151617181920212223242526272829303132333435363738394041void Init(SqStack &s) { s.top = -1;}bool IsEmpty(SqStack s) { if (s.top == -1) { return true; } return false;}bool IsFull(SqStack s) { if (s.top >= MaxSize - 1) { return...
2020-05-06
ADT的设计
前言ADT（抽象数据类型），如果我们的程序需要使用类型，C中没有与之匹配的基本类型。那我们可以自己定义抽象数据类型。如果，我们要设计一个数据类型需要： 提供存储数据的方法。（定义一个结构） 描述操控该数据的方法 如何实现？ 对数据类型进行一个属性和操作的描述。 开发一个实现ADT的接口。（在.h头文件） 编写代码实现接口。（.c文件） 例如int类型给我们的属性是：它代表一个整数值。操作是：可以进行+ - * / % Anyway.ADT就是描述一些这个类型是属性和操作。如果要实现它，再通过接口(.h .c)来实现它。
2020-05-12
链队列
前言链队列就是限制了只能在首端和尾端进行插入，删除操作的表。 链队列中需要头节点 实现它需要声明两个结构。QNode存储某一项的数据，和指向下一项的结构指针。ListQueue存储指向头节点和尾节点的结构指针。 12345678910typedef struct QNode{ ElementType data; struct QNode *next;}QNode, *QNodePtr;typedef struct ListQueue{ QNodePtr front, rear;}ListQueue, *ListQueuePtr; 空队列判断条件 front和rear同时指向头节点 操作插入12345678910111213void EnQueue(ListQueuePtr Q, ElementType e){ QNodePtr P = (QNodePtr)malloc(sizeof(QNode)); if(P == NULL) { fprintf(stder...