【初阶数据结构与算法】初阶数据结构总结之顺序表、单链表、双链表、栈、队列、二叉树顺序结构堆、二叉树链式结构（附源码）

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

typedef int type;

typedef struct SL
{
	type* arr;
	int size;
	int capacity;
}SL;

#include "SeqList.h"

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//如果空间不够，进行扩容
void SLcheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		type* tmp = (type*)realloc(ps->arr, ps->capacity * sizeof(type));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		tmp = NULL;
	}
}

//打印
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//尾插
void SLPushBack(SL* ps, type x)
{
	assert(ps);
	SLcheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps,type x)
{
	assert(ps);
	SLcheckCapacity(ps);
	memcpy(ps->arr + 1, ps->arr, ps->size * sizeof(type));
	ps->arr[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	memmove(ps->arr, ps->arr + 1, --ps->size * sizeof(type));
}

//指定位置前插入数据
void SLInsert(SL* ps, int pos, type x)
{
	assert(ps);
	assert(pos >=0 && pos <= ps->size);
	memmove(ps->arr + pos + 1, ps->arr + pos, (ps->size - pos) * sizeof(type));
	ps->arr[pos] = x;
	ps->size++;
}

int SLFind(SL* ps, type x)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos <= ps->size);
	memmove(ps->arr + pos, ps->arr + pos + 1, (ps->size - pos - 1) * sizeof(type));
	ps->size--;
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

//链表的打印
void SLTPrint(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

//申请新节点
SLTNode* SLTBuyNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//链表的头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}
	SLTNode* pcur = *pphead;
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	pcur->next = newnode;
}

//链表的头删
void SLTPopFront(SLTNode** pphead)
{
	//这里除了pphead不能为空
	//由于是删除函数，所以头节点不能为空
	//也就是*pphead也不能为空
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = *pphead;
	while (ptail->next)
	{
		//循环结束时，prev就是ptail的前一个节点
		prev = ptail;
		ptail = ptail->next;
	}
	free(ptail);
	ptail = NULL;
	prev->next = NULL;
}

//查找指定节点
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//删除指定节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead && pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
		return;
	}
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}


//在指定节点前插入节点
void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead && pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
		return;
	}
	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}

//在指定节点之后插入节点
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	SLTNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

//链表的销毁
void SLTDestroy(SLTNode** pphead)
{
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* del = pcur;
		pcur = pcur->next;
		free(del);
	}
	*pphead = NULL;
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int LTDateType;

typedef struct ListNode
{
	LTDateType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//初始化1
void LTInit1(LTNode** pphead)
{
	assert(pphead);
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	(*pphead)->next = (*pphead)->prev = *pphead;
}

//初始化2
LTNode* LTInit2()
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->prev = newnode->next = newnode;
	return newnode;
}

//链表的销毁
void LTDestroy(LTNode** pphead)
{
	assert(pphead);
	LTNode* pcur = (*pphead)->next;
	while (pcur->next != *pphead)
	{
		LTNode* del = pcur;
		pcur = pcur->next;
		free(del);
		del = NULL;
	}
	free(*pphead);
	*pphead = NULL;
}

//节点的申请
LTNode* LTBuyNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

//链表的打印
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}
}

//链表的头插
void LTPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

//链表的尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

//链表的查找
LTNode* LTFinde(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//链表的判空
bool LTEmpty(LTNode* phead)
{
	return phead == phead->next;
}

//链表头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	LTNode* new = phead->next->next;
	phead->next = new;
	new->prev = phead;
	free(del);
	del = NULL;
}

//链表尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	LTNode* prev = phead->prev->prev;
	prev->next = phead;
	phead->prev = prev;
	free(del);
	del = NULL;
}

//删除指定节点
void LTErase(LTNode* phead, LTNode* pos)
{
	assert(!LTEmpty(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);  
}

//在指定节点前插入节点
void LTInsert(LTNode* phead, LTNode* pos, LTDateType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	LTNode* prev = pos->prev;
	newnode->prev = prev;
	newnode->next = pos;
	prev->next = newnode;
	pos->prev = newnode;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;//需要动态开辟的数组
	int top;//有效元素个数
	int capacity;//数组总容量
}ST;

//初始化栈
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//销毁栈
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//检查栈是否满了，满了就增容
void STCheckCapacity(ST* ps)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ps->capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity);
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->arr = tmp;
	}
}

//入栈操作
void STPush(ST* ps, STDataType x)
{
	STCheckCapacity(ps);
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//出栈
void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	ps->top--;
}

//取栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	int size;
	QueueNode* phead;
	QueueNode* ptail;
}Queue;

//队列初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//队列销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* del = pcur;
		pcur = pcur->next;
		free(del);
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//申请队列节点
QueueNode* QueueBuyNode(QDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = QueueBuyNode(x);
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
		pq->size++;
		return;
	}
	pq->ptail->next = newnode;
	pq->ptail = newnode;
	pq->size++;
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	QueueNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;
	pq->size--;
}


//取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->phead->data;
}

//取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->ptail->data;
}


//获取队列元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;

//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

//堆的销毁
void HPDestroy(HP* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

//向上调整
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}

	}
}

//入堆
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		php->capacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, php->capacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		php->arr = tmp;
	}
	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	php->size++;
}

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]); 
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//出堆顶元素
void HPPop(HP* php)
{
	assert(!HPEmpty());
	php->size--;
	Swap(&php->arr[0], &php->arr[php->size]);
	AdjustDown(php->arr, 0, php->size);
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty());
	return php->arr[0];
}

//堆的有效数据个数
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

//堆的判空
bool HPEmpty(HP* php)
{
	return php->size == 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//申请节点
BTNode* BTBuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("mallc");
		return NULL;
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

//手动创建一颗链式二叉树
BTNode* CreateBinaryTree()
{
	BTNode* nodeA = BTBuyNode('A');
	BTNode* nodeB = BTBuyNode('B');
	BTNode* nodeC = BTBuyNode('C');
	BTNode* nodeD = BTBuyNode('D');
	BTNode* nodeE = BTBuyNode('E');
	BTNode* nodeF = BTBuyNode('F');
	BTNode* nodeG = BTBuyNode('G');
	BTNode* nodeH = BTBuyNode('H');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeB->right = nodeE;
	nodeC->left = nodeF;
	nodeC->right = nodeG;
	nodeD->left = nodeH;

	return nodeA;
}

//前序遍历:根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		//走到空节点开始返回
		return;
	}
	//打印根节点
	printf("%c ", root->data);
	//递归左孩子这颗子树
	PreOrder(root->left);
	//递归右孩子这颗子树
	PreOrder(root->right);
}

//中序遍历:左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		//走到空节点开始返回
		return;
	}
	//递归左孩子这颗子树
	InOrder(root->left);
	//打印根节点
	printf("%c ", root->data);
	//递归右孩子这颗子树
	InOrder(root->right);
}

//后序遍历:左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//走到空节点开始返回
		return;
	}
	//递归左孩子这颗子树
	PostOrder(root->left);
	//递归右孩子这颗子树
	PostOrder(root->right);
	//打印根节点
	printf("%c ", root->data);
}

//二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftsize = BinaryTreeSize(root->left);
	int rightsize = BinaryTreeSize(root->right);

	return 1 + leftsize + rightsize;
}

//二叉树叶子节点的个数
int BinaryTreeLeaveSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	int leftsize = BinaryTreeLeaveSize(root->left);
	int rightsize = BinaryTreeLeaveSize(root->right);

	return leftsize + rightsize;
}

//二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = 1 + BinaryTreeDepth(root->left);
	int rightDepth = 1 + BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth : rightDepth;
}

//二叉树第k层节点个数
int BinaryTreeKLevelSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int leftKSize = BinaryTreeKLevelSize(root->left, k - 1);
	int rightKSize = BinaryTreeKLevelSize(root->right, k - 1);
	return leftKSize + rightKSize;
}

//二叉树的查找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}

	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;

}

//二叉树的层序遍历
void LevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		printf("%c ", top->data);
		if (top->left)
			QueuePush(&q, top->left);
		if (top->right)
			QueuePush(&q, top->right);
		QueuePop(&q);
	}
	QueueDestroy(&q);
}

//查看二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
	{
		return true;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		if (top)
		{
			return false;
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return true;
}

//二叉树的销毁
void BinaryTreeDestroy(BTNode** proot)
{
	if (*(proot) == NULL)
	{
		return;
	}
	BinaryTreeDestroy(&(*proot)->left);
	BinaryTreeDestroy(&(*proot)->right);
	free(*proot);
	*proot = NULL;
}