常见的数据结构总结（8种）

struct SerList//动态顺序表
{
	SQDateType *a;
	int size;
	int capacity;
};
typedef struct SerList SL;

void SeqListPushBack(SL* ps, SQDateType x);
void SeqListPushFront(SL* ps, SQDateType x);
void SeqListPopBack(SL* ps);
void SeqListPopFront(SL* ps);
void SeqListInsert(SL* ps, int pos, SQDateType x);
void SeqListErase(SL* ps, int pos);
int SeqListFind(SL* ps, SQDateType x);
void SeqListModify(SL* ps, int pos, SQDateType x);

顺序表的问题：

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

因此，有了链表！

2. 链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2.1 单链表（SingleList）

单链表的接口：

typedef int SLDateType;
typedef struct SListNode
{
	SLDateType data;
	struct SListNode* next;//注意：这里不能嵌套结构体，只能是地址

}SLTNode;

void SListPrint(SLTNode* phead);
void SListPushBack(SLTNode** pphead, SLDateType x); 
void SListPushFront(SLTNode** pphead, SLDateType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);

SLTNode* SListFind(SLTNode* phead, SLDateType x);

void SListInsert(SLTNode** pphead, SLTNode* pos, SLDateType x);
void SListErase(SLTNode** pphead, SLTNode* pos);

int SListLen(SLTNode* phead);//求链表的长度

2.2 带头双向循环链表（List）

双向循环链表的接口：

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

void ListInit(ListNode** pphead);
void ListDestroy(ListNode* phead);
void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);

void ListPrint(ListNode* phead);
ListNode* ListFind(ListNode* phead, LTDataType x);

void ListInsert(ListNode* phead, ListNode* pos, LTDataType x);
void ListErase(ListNode* phead, ListNode* pos);

2.3 顺序表和链表的对比

顺序表：

优点：空间连续、支持随机访问
缺点：1.中间或前面部分的插入删除时间复杂度O(N) 2.增容的代价比较大。

链表：

优点：1.任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。
缺点：以节点为单位存储，不支持随机访问

3. 栈（Stack）

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除叫做出栈，出数据在栈顶。

栈的接口（用数组来实现的，也可以用链表）：

//栈可以用顺序表（数组）来实现
typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;//top用来操作栈顶的数据，top相当于size
	int capacity;
}Stack;

void StackInit(Stack* pst);
void StackDestroy(Stack* pst);

void StackPush(Stack* pst, STDateType x);
void StackPop(Stack* pst);

STDateType StackTop(Stack* pst);
bool StackEmpty(Stack* pst);
int StackSize(Stack* pst);

4. 队列（Queue）

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列的接口：

typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列可以用链表来实现
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* q);// 初始化队列
void QueueDestroy(Queue* q);// 销毁队列
void QueuePush(Queue* q, QDataType data);// 队尾入队列
void QueuePop(Queue* q);// 队头出队列

QDataType QueueFront(Queue* q);// 获取队列头部元素
QDataType QueueBack(Queue* q);// 获取队列队尾元素
int QueueSize(Queue* q);// 获取队列中有效元素个数
bool QueueEmpty(Queue* q);// 检测队列是否为空

5. 树（Tree）

5.1 树的特点

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；

5.2 二叉树：满二叉树和完全二叉树

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。
二叉树是树的特殊一种，具有如下特点：

每个结点最多有两颗子树，结点的度最大为2。
左子树和右子树是有顺序的，次序不能颠倒。
即使某结点只有一个子树，也要区分左右子树。

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

5.2.1 顺序结构（数组来存储，heap里面讲）

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

5.2.2 链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

链式结构接口如下：（包括三种遍历方式：前序遍历、中序遍历、后序遍历，以及层序遍历）

typedef char BTDataType;
typedef struct BinaryTreeNode
{
     BTDataType _data;
     struct BinaryTreeNode* _left;
     struct BinaryTreeNode* _right; 
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

6. 堆（Heap）其实是完全二叉树

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下：

堆的接口实现：（向下调整算法、向上调整算法）

typedef int HPDataType;
//用数组来实现堆（堆就是完全二叉树）
typedef struct Heap
{
 HPDataType* _a;
 int _size;
 int _capacity; 
}Heap;

void AdjustDown(int* a, int n, int parent);
void AdjustUp(int* a, int child);

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
// 对数组进行堆排序
void HeapSort(int* a, int n);