线性表的两种存储结构
 
1.顺序结构
 
（1）结点中只有自身的信息域，没有关联信息域。因此，顺序存储结构的存储密度大度、存储空间利用率高。
 （2）通过计算地址直接访问任何数据元素，即可以随机访问。 （3）插入和删除操作会引起大量元素的移动。
 
2.链式结构
 
（1）结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密度小、存储空间利用率低。
 （2）在逻辑上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。
 （3）插入和删除操作方便灵活，不必移动结点只需修改结点中的指针域即可。
 
使用场合的选择
 
1、基于存储空间
 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。链表不用事先估计存储规模，但链表的存储密度较低。顺序存储结构的存储密度是1，而链式存储结构的存储密度小于1。
 2、基于运算
 在顺序表中按序号访问的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)。
 3、基于环境
 顺序表容易实现，在任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲顺序表简单些。
 
总之，两种存储结构各有优势，选择哪一种结构依据实际问题而定。一般来讲，较稳定的线性表选择顺序存储，而频繁的做插入、删除操作的动态性较强的线性表选择链式存储更为合适。

图由结点的有穷结合V和边的集合E组成。为了与树形结构进行区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对。若两个顶点之间存在一条边，则表示这两个顶点具有相邻的关系。
 
图通常有两种存储方式，即邻接矩阵和邻接表。
 
下面介绍一下邻接矩阵。设G=(V,E)是具有n个结点的图，顶点序号依次为0，1，2，3、、、n-1。G的邻接矩阵是具有如下定义的方阵A：
 
A[i][j]=1表示顶点i与顶点j邻接，即i与j之间有一条边或者弧。
 
A[i][j]=0表示顶点i与顶点j不邻接
 
邻接矩阵是图的顺序存储结构。
 
邻接矩阵的结构型定义如下：
 
struct VerType{
	
	int no;//顶点的编号 
	char info;//顶点的其他信息 
	
};
struct MGraph{
	
	int n,e;//结点数目与边数
	int edges[maxn][maxn];//邻接矩阵的定义 
	int VerType[maxn]; //存放结点的信息
	
};
 
关于邻接表的形式： 
 
struct ArcNode{
	int adjvex;//这条边所指向的结点信息
	struct ArcNode *nextarc;//该顶点指向下一条边的指针
	int info;//这条边的相关信息如权值 
}; 
struct VNode {
	char data;//顶点信息 
	ArcNode *firstarc;//指向第一条边的指针 
};
struct Agraph{
	
	VNode adjlist[maxn];//邻接表 
	int n,e;//顶点数目和边数 
};

 
 

常用的逻辑线性结构和逻辑非线性结构：
 堆栈、队列、线性表、数组、链表、普通的树、二叉树、哈夫曼树。
 下面分别介绍这些数据结构的初始化。
 //具体源代码看github：https://github.com/xiami-maker/aboutInitialization/tree/master
 
堆栈
 
堆栈又称为“栈”，是一种线性结构；其最大的特点是：记忆性、先进后出控制堆栈存取数据需要一个“栈顶指针”，通常堆栈还涉及”栈底指针“。
 int top; //栈顶指针，下标
 int bottom; //栈底指针，下标
 top和bottom的初始值都是0，这表示栈为“空”。
 入栈的过程，即，push的过程：stack[top++] = data;这就是data入stack栈的过程。
 数据出栈的过程，即，pop的过程：data = stack[–top];
 堆栈相对于一般的存储结构，最大的不同点是：其中的数据，不能“遍历”！只能直接访问栈顶元素的值，不能访问栈顶元素下面的元素的值！也就是说，堆栈不支持“随机访问（就是通过下标进行访问！）”。
 堆栈的实现：
 由于堆栈有空间、栈顶指针等众多要素，因此，先设计其“控制头”；
 
typedef struct MEC_STACK {
	void **data;
	int capacity;
	int top;
	}MEC_STACK;
 
画图来表示为：
 
 具体源代码看最上方的github；
 
队列
 
线性逻辑结构，一对一；
 基本点：一个入口（队尾）和一个出口（队首）
 特点：先进先出
 画图表示如下
 队列不仅仅是直线的，也可以是环形的。
 如下图所示：
 那么，环形队列的表示用刚才的结构体就无法表示了。这时，我们就要增加结构体里的内容。
 
typedef struct QUEUE {
	USER_TYPE *queue;
	int capacity;
	int head;
	int tail;
	boolean lastAction;
}QUEUE;
#define IN		1
#define OUT		0
 
其中head表示队首，tail表示队尾，lastAction表示上一次操作。
 队列满时，heda == tail;队列空时，head == tail;
 单独从head == tail,无法判断队列的空与满！但是，可以根据上一次队列的操作（入队列或出队列）来综合判断。
 队列中有效元素个数的计算公式：
 (tail - head + capacity ) % capacity;
 
具体源代码看最上方的github；
 
链表
 
链表是一个物理非线性结构。是由一个一个的节点链接而成，每个节点对应一块内存空间，两个节点之间并不是像数组一样连续。
 节点的定义如下：
 
typedef struct NODE {
	void data;
	struct NODE *next;
}NODE;
 
链表形成的链式结构如下图：
 
 具体源代码看最上方的github；
 
树、二叉树与哈夫曼树
 
树的性质：
 1.一棵树最多有一个节点，该节点无前驱节点，即，无父节点，称为：根节点；空树：没有任何节点的树。
 2.树中的任意一个节点，有且仅有一个前驱节点，可以有n（n >= 0）个后继节点。
 3.若一个节点没有后继节点（子节点），则，这个节点称为“叶子节点”。
 树的基本术语：
 根节点：如上，不再赘述。
 节点的度(degree)：一个节点的子节点个数，称为这个节点的度。
 树的度：一棵树中，度最大的节点的度，称为该树的度。
 树的深度（高度）：树的节点的层次数。
 叶子节点：度为0的节点。
 
树的遍历：
 
 二叉树：
 
 满二叉树：
 
 完全二叉树：
 
 
 具体源代码看最上方的github；
 
哈夫曼树：
 由于哈夫曼树涉及到一个非常具有实际意义的问题：哈夫曼压缩与解压缩技术，所以单独写了一篇博文，这里提供博文链接：https://blog.csdn.net/weixin_44836233/article/details/102837718
 
数组
 
int arr[10];
 
数组是一个线性结构，其特点：
 1.数组通常由capaci的限制；
 2.数组中的元素，类型都是一样的；即，数组元素长度相同。
 在学习数组时，需要解决的问题是：地址映射。
 
double ar[10] = {.....};
 
ar[3] 在c编译器的工作下,将转换成：ar + sizeof(double) * 3;这个结果直接在c程序执行时体现，在c语言源代码角度根本看不到这个“地址映射“过程！！！
 现在要求编写一个通用二维数组。
 
typedef struct MATRIX {
	USER_TYPE *data;
	int maxRow;
	int maxCol;
}MATRIX;
 
在这个MATRIX所提供的算子（函数）中，最重要的基础函数是：行、列值与一维数组下标的相互转换。
 
 
线性表
 
线性表是一个逻辑线性结构，即，一对一结构。
 在讨论线性表的实现（存储结构），可以用物理线性结构（数组）实现，也可以用物理非线性结构（链表）实现。
 假设用数组实现：
 一个简单而目光短浅的做法是：直接用数组就好了（代码如下）！！！
 
typedef struct POINT {
	int row;
	int col;
}POINT;

POINT *pointLinear = NULL;
int pointCount = 0;
int capacity = 30;

pointLinear = (POINT *) calloc(sizeof(POINT),capacity);
 
对于线性表的思考：线性表处理需要必须的“存储空间”（就是线性表的主体部分）之外，还需要对线性表进行诸多方面的运算：插入、删除、查找、清空等等，或者说：控制！
 “控制头是基于数据（信息）的”，因此，为了更好地控制线性表，也为了能为“用户”（使用我们所编写的线性表工具，完成自己的APP的那些程序员，就是我们的用户！）提供一个我完善的编程工具，需要先定义一个“控制头”！
 控制头部分至少有如下三种内容：
 1。存储用户数据的线性表空间；
 2.线性表的容量；
 3.用户数据的数量；
 最后一个难题，用户的数据类型！！
 因为工具需要具有普适性。工具不能因为用户的数据类型不一致，而不能使用！！！以前曾经用过USER_TYPE的方式解决用户类型的问题，但是，这是需要用户事先定义USER_TYPE类型，且，这个类型只能是一种；这些约束都使得USER_TYPE方式应该慎重使用。
 这里将使用void **的方案解决用户数据类型普适化的问题！
 假设用户数据类型是：POINT,用数组直接表达的方案，应该如下：POINT data[N]；事实上，上述数组的每一个元素的类型是POINT；
 如果用动态存储分配的方案实现：
 POINT *data;
 data = (POINT *) calloc(sizeof(POINT),capacity);
 事实上，上述动态申请的每一个元素类型是POINT；
 
对于下面的定义，该如何理解？
 POINT *data[N];
 data是一个（拥有N个POINT *类型的元素）数组；所以，data是一个指针数组（由指针组成的数组）！
 如果用动态存储分配方案，则写成：
 POINT **data;
 data = (POINT **) calloc(sizeof(POINT *),capacity);
 这里最关键的问题是：sizeof(POINT *)的结果是4B，而且，无论是否是POINT，任意类型的指针类型，长度都为4B；那么就定义为：
 void **data;
 data = (void **) calloc(sizeof(void *),capacity);
 当然的，在data[i]中，必须存储而且也只能存储用户数据类型的变量的首地址(指针)! data[i]的类型是void *，是一个指针类型；
 综上所述，MEC_LINEAR类型的定义是：
 
typedef struct MEC_LINEAR {
	void **data;	//真正的线性表空间
	int capacity;	//线性表容量
	int count;	//有效的用户数据个数
}MEC_LINEAR;
 
线性表的结构图如图所示：
 

图的两种存储结构各有什么有缺点
 
邻接矩阵
 优点:容易确定两个顶点之前是否存在边,容易确定顶点的度
 缺点:占用空间大(当顶点多边少的时候)
 空间复杂度:n平方
 邻接表:
 优点:无向图邻接表容易求得顶点的度 ,节省空间
 有向图邻接表容易得到顶点的出度,节省空间
 缺点:不容易得到某个顶点的入度
 空间复杂度O(边数+顶点数)