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

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

一、顺序表

1. 顺序表的特点：顺序表（也称作线性表）是一种线性数据结构，其特点主要包括： （1）元素连续存储：顺序表的元素在内存中连续存储，每个元素都占有一个固定的位置，并且可以通过索引直接访问。 （2）随机访问：由于元素连续存储，顺序表支持随机访问，即可以在常数时间内访问任意位置的元素。 （）存储密度高：顺序表不需要额外的指针或引用信息来存储元素之间的关系，因此存储密度较高，内存利用率较好。 （4）物理顺序与逻辑顺序一致：顺序表中元素的物理存储顺序与其逻辑顺序一致，即元素在内存中的排列顺序与它们在顺序表中的顺序相同。
2. 顺序表的优点 （1）访问速度快：由于支持随机访问，顺序表可以在常数时间内访问任意位置的元素，这使得顺序表在需要频繁访问元素的场景中表现出。 （2）易于实现：顺序表可以使用简单的数组来实现，因此其实现相对简单，易于理解和操作。 （）空间利用率高：顺序表不需要额外的指针或引用信息，因此其空间利用率较高，可以节省内存资源。
3. 顺序表的缺点 （1）插入和删除操作慢：在顺序表中插入或删除元素时，需要移动其他元素的位置以保持元素的连续性。这导致插入和删除操作的时间复杂度较高，通常为O(n)，其中n是元素的数量。 （2）静态顺序表的灵活性不高，动态顺序表则需要动态申请空间，会有一定消耗
4. 顺序表的应用场景 （1）需要频繁访问元素的场景：由于顺序表支持随机访问，因此在需要频繁访问元素的场景中表现出。例如，在实现查算法时，顺序表可以高效地定位目标元素。 （2）元素数量相对固定的场景：顺序表适用于元素数量相对固定的场景。如果元素数量频繁变化，则可能需要频繁地进行扩容或缩容操作，这会影响性能。 （）需要存储连续数据的场景：顺序表适用于需要存储连续数据的场景。例如，在图像处理、音频处理等领域中，通常需要处理连续的数据块，此时顺序表是一个合适的选择。 （4）实现简单的数据结构：顺序表可以作为实现其他简单数据结构的基础。例如，可以使用顺序表来实现栈、队列等数据结构，这些数据结构在算法和数据结构中具有广泛的应用。
5. 顺序表源码：

代码语言：javascript代码运行次数：0运行复制

#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 = ULL;
	ps->size = ps->capacity = 0;
}

//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = ULL;
	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 == ULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		tmp = ULL;
	}
}

//打印
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--;
}

二、单链表

1. 单链表的特点：单链表是一种线性数据结构，其特点主要体现在以下几个方面： （1）节点分散存储：单链表的节点在内存中不是连续存储的，每个节点包含数据域和指针域（或称为链域），指针域存储着下一个节点的地址。 （2）链式存储结构：通过指针将各个节点连接起来，形成一条链式的存储结构。这种结构使得单链表在插入和删除节点时不需要移动其他节点的位置。 （）头指针唯一：单链表通常有一个头指针（或称为头节点），它指向链表的第一个节点（如果链表不为空）。头指针是链表的唯一入口。 （4）节点访问需从头开始：由于节点在内存中不是连续存储的，因此不能通过索引直接访问任意位置的节点。需要从头指针开始，依次遍历链表，直到到目标节点。
2. 单链表的优点 （1）插入和删除操作灵活：在单链表中插入或删除节点时，只需要修改相邻节点的指针域，而不需要移动其他节点的位置。这使得单链表在插入和删除操作方面具有较高的灵活性。 （2）动态调整大小：单链表不需要预先分配固定大小的存储空间，可以根据需要动态地增加或减少节点，从而适应不同规模的数据集合。 （）节省空间：对于稀疏的数据集合，单链表可以节省空间。因为不需要像数组那样为未使用的元素分配存储空间。
3. 单链表的缺点 （1）访问速度慢：由于节点在内存中不是连续存储的，因此不能通过索引直接访问任意位置的节点。需要从头指针开始依次遍历链表，直到到目标节点。这使得单链表在访问速度方面相对较慢。 （2）需要额外的存储空间：每个节点都需要一个指针域来存储下一个节点的地址，这增加了额外的存储空间开销。 （）容易出现内存泄漏：在使用单链表时，需要小心管理节点的内存分配和释放。如果忘记释放已删除的节点所占用的内存，可能会导致内存泄漏问题。
4. 单链表的应用场景 （1）需要频繁插入和删除操作的场景：由于单链表在插入和删除操作方面具有较高的灵活性，因此适用于需要频繁插入和删除操作的场景。例如，在实现动态数据结构（如动态数组、栈、队列等）时，可以考虑使用单链表。 （2）元素数量不确定的场景：单链表可以根据需要动态地增加或减少节点，从而适应不同规模的数据集合。因此，适用于元素数量不确定的场景。 （）需要节省空间的场景：对于稀疏的数据集合，单链表可以节省空间。因为不需要为未使用的元素分配存储空间。例如，在实现稀疏矩阵时，可以考虑使用单链表来存储非零元素及其位置信息。 （4）实现复杂数据结构：单链表可以作为实现其他复杂数据结构的基础。例如，可以使用单链表来实现图、树等数据结构中的节点和边
5. 源码：

代码语言：javascript代码运行次数：0运行复制

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

typedef int SLTDateType;

typedef struct SListode
{
	SLTDateType data;
	struct SListode* next;
}SLTode;

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

//申请新节点
SLTode* SLTBuyode(SLTDateType x)
{
	SLTode* newnode = (SLTode*)malloc(sizeof(SLTode));
	newnode->data = x;
	newnode->next = ULL;
	return newnode;
}

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

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

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

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

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

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


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

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

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

三、双链表

1. 双链表的特点：双链表是一种链式数据结构，其特点主要包括： （1）节点结构复杂：双链表的每个节点包含三个部分：一个数据域（存储节点的数据）、一个前驱指针（指向列表中的前一个节点）和一个后继指针（指向列表中的下一个节点）。 （2）双向遍历：由于每个节点都有前驱和后继指针，因此双链表可以从头节点遍历到尾节点，也可以从尾节点遍历到头节点，提供了更高的灵活性。 （）插入和删除操作灵活：在双链表中插入或删除一个节点只需要修改相邻节点的前后指针，而不需要遍历整个链表来查前驱或后继节点。
2. 双链表的优点 （1）灵活性高：双链表可以在任意位置插入或删除节点，而无需重新排列整个链表，这提供了很高的灵活性。 （2）双向遍历：双向遍历的特性使得双链表在某些算法和操作中更加高效，如反转链表、合并链表等。 （）空间利用率相对较好：虽然双链表每个节点需要额外的存储空间来保存前驱指针，但相对于其他复杂数据结构（如哈希表、红黑树等），其空间利用率仍然相对较好。
3. 双链表的缺点 （1）占用内存较多：由于每个节点都需要存储前驱和后继两个指针，因此双链表相对于单向链表会占用更多的内存空间。 （2）操作稍微复杂：在插入或删除节点时，需要同时更新前后两个指针，这使得双链表的操作逻辑相对于单向链表稍微复杂一些。
4. 双链表的应用场景 （1）需要双向遍历的场景：当需要频繁地从链表的两端进行遍历或操作时，双链表是一个很好的选择。例如，在实现双向队列（Deque）时，双链表可以高效地支持从两端进行插入和删除操作。 （2）需要频繁插入和删除的场景：由于双链表在插入和删除操作方面具有较高的灵活性，因此适用于需要频繁插入和删除元素的场景。例如，在实现动态数据结构（如动态数组、栈、队列等）的扩展版本时，可以考虑使用双链表来优化性能。 （）需要反转链表或合并链表的场景：双链表的结构使得反转链表或合并链表等操作变得更加简单和高效。这些操作在算法和数据结构领域中非常常见，因此双链表在这些场景中具有广泛的应用。 （4）内存管理：在数据库系统中，双链表可以用于实现内存池，以提高内存分配和释放的效率。通过将内存池中的空闲内存块组织成双向链表，可以快速到可用的内存块，并减少内存碎片。 （5）日志记录和缓存实现：双链表还可以用于实现日志记录机制和缓存中的数据结构。在日志记录中，每个日志条目可以作为链表中的一个节点，以便快速地添加和删除日志条目。在缓存实现中，每个缓存项可以作为链表中的一个节点，以支持高效的插入、删除和查操作。
5. 源码：

代码语言：javascript代码运行次数：0运行复制

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

typedef int LTDateType;

typedef struct Listode
{
	LTDateType data;
	struct Listode* prev;
	struct Listode* next;
}LTode;

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

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

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

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

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

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

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

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

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

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

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

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

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

四、栈(先进后出)

1. 栈的特点：栈（Stack）是一种特殊的线性数据结构，其特点主要体现在以下几个方面： （1）后进先出（LIFO）：栈的基本操作包括入栈（Push）和出栈（Pop），元素只能在一端（栈顶）进行插入和删除。新加入的元素总是被放在栈的顶部，而离开栈的元素总是栈顶的那个元素，即最后加入的元素最先被移除，这就是后进先出的原则。 （2）限制访问：栈中的元素除了通过入栈和出栈操作进行访问外，通常不允许直接访问栈中的其他元素。这种限制使得栈的操作相对简单和明确。 （）动态大小：栈的大小通常是动态的，可以根据需要增长和缩小。这意味着栈可以容纳的元素数量不是固定的，而是可以根据程序的运行情况进行调整。
2. 栈的优点 （1）操作简便：栈的操作非常简单，只有入栈和出栈两种基本操作，这使得栈的实现和使用都相对容易。 （2）保护数据：由于栈的后进先出特性，它可以自然地保护数据，防止被意外修改或删除。这对于需要维护数据完整性的场景非常有用。 （）节省空间：栈通常只需要维护一个指针（栈顶指针）来跟踪栈顶元素的位置，因此相对于其他数据结构，栈的空间开销较小。
3. 栈的缺点 （1）访问受限：栈只能访问栈顶元素，不能直接访问栈中的其他元素。这种限制在某些情况下可能会降低栈的灵活性。 （2）可能出现栈溢出：如果栈的大小是有限的，并且不断有新的元素入栈而没有相应的出栈操作，那么栈可能会因为空间不足而溢出。这可能导致程序崩溃或异常。
4. 栈的应用场景 （1）函数调用和递归：在编程中，函数调用栈用于存储函数调用过程中的局部变量、返回地址等信息。当函数被调用时，其相关信息被压入栈中；当函数返回时，这些信息被弹出栈。递归算法也利用栈来保存每一层递归调用的状态。 （2）括号匹配和表达式求值：在编译原理中，栈常用于检查括号是否匹配以及计算表达式的值。例如，在解析数学表达式时，可以使用栈来存储操作数和操作符，并根据操作符的优先级进行计算。 （）路径导航和撤销操作：在图形界面或文本编辑器中，栈可以用于实现撤销操作（Undo）。当用户进行一系列操作时，每个操作都被压入栈中；当用户点击撤销按钮时，最近的操作被弹出栈并撤销。此外，栈还可以用于路径导航，如浏览器的历史记录功能。 （4）深度优先搜索（DFS）：在算法和数据结构中，栈常用于实现深度优先搜索算法。通过维护一个栈来记录待访问的节点或状态，可以确保算法按照深度优先的顺序进行搜索。
5. 源码：

代码语言：javascript代码运行次数：0运行复制

#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 = ULL;
	ps->capacity = ps->top = 0;
}

//销毁栈
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = ULL;
	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 == ULL)
		{
			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;
}

五、队列

1. 队列的特点：队列是一种特殊的线性数据结构，其特点主要包括： （1）先进先出（FIFO）原则：队列中的元素按照它们被加入的顺序被移除，即先进入队列的元素先被移除，后进入的元素后被移除。这是队列最显著的特点。 （2）限制访问：队列只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。这种限制使得队列在数据处理上表现出特定的顺序性。 （）动态大小：队列的大小可以动态变化，根据需要增加或减少元素。这意味着队列可以适应不同规模的数据集合。
2. 队列的优点 （1）保持数据处理的顺序：队列能够确保数据按照加入的顺序被处理，这对于需要按顺序执行任务的场景非常有用。 （2）避免数据丢失：由于队列中的元素在被处理之前不会被移除，因此可以避免数据丢失的问题。 （）支持并发操作：在多线程或并发编程中，队列可以用来安全地传递数据或任务，支持多个生产者-消费者模型。
3. 队列的缺点 （1）可能导致阻塞：在队列满的情况下，如果再有元素需要入队，可能会导致阻塞或等待，直到队列中有空间为止。同样，在队列空的情况下，如果再有元素需要出队，也会导致阻塞。 （2）内存开销：虽然队列的大小可以动态变化，但动态调整大小（如扩容或缩容）可能会带来额外的内存开销。
4. 队列的应用场景 （1）任务调度：在计算机系统中，队列常用于任务调度。操作系统将等待执行的任务放入队列中，然后按照先进先出的原则依次处理这些任务。 （2）数据缓冲：在数据传输或处理过程中，队列可以作为缓冲区来存储临时数据。例如，在网络通信中，接收到的数据可以先放入队列中，然后由处理器按照顺序进行处理。 （）并发控制：在多线程或并发编程中，队列可以用来安全地传递数据或任务。生产者线程将数据或任务放入队列中，消费者线程从队列中取出数据或任务进行处理。这种机制可以避免多个线程同时访问共享资源而导致的竞争条件。 （4）广度优先搜索（BFS）：在图的遍历算法中，队列常用于实现广度优先搜索。从起始节点开始，将其所有邻居节点加入队列中，然后依次处理队列中的节点，并将其邻居节点加入队列中，直到队列为空为止。 （5）事件驱动编程：在事件驱动编程中，队列可以用来存储事件或消息。当事件发生时，将其放入队列中，然后由事件处理器按照顺序处理这些事件。
5. 源码：

代码语言：javascript代码运行次数：0运行复制

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

typedef int QDataType;

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

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

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

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

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

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	Queueode* newnode = QueueBuyode(x);
	if (pq->phead == ULL)
	{
		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));
	Queueode* 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;
}

六、二叉树链式结构—堆

1. 堆的特点：堆是一种特殊的树形数据结构，通常表现为一个完全二叉树，并具有以下特点： （1）完全二叉树结构：堆在逻辑上是一颗完全二叉树，这意味着除了最后一层外，每一层都是满的，且最后一层的节点都靠左对齐。 （2）节点值特性：    在大顶堆（最大堆）中，父节点的值总是大于或等于其子节点的值。    在小顶堆（最小堆）中，父节点的值总是小于或等于其子节点的值。 （）高效的插入和删除操作：堆的插入和删除操作的时间复杂度都是O(log n)，其中n是堆中元素的数量。这使得堆在处理大量数据时具有很高的效率。 （4）堆化操作：堆化操作是堆维护其特性的关键步骤。当插入或删除元素后，堆会进行相应的调整以保持其特性。包括“向上调整”（在插入元素时）和“向下调整”（在删除堆顶元素时）。
2. 堆的优点 （1）存取速度快：堆的存取速度仅次于存在CPU中的数据，且数据可以共享，这使得堆在处理大量数据时具有很高的效率。 （2）灵活性强：堆的大小可以动态调整，以适应不同规模的数据集合。同时，堆中的元素可以按需进行插入和删除操作，而无需重新排列整个数据结构。 （）优先级队列的实现：堆是优先级队列的一种高效实现方式。在优先级队列中，每个元素都有一个优先级，优先级最高的元素总是最先被处理。堆的特性使得优先级队列的插入和删除操作都能够在O(log n)的时间复杂度内完成。
3. 堆的缺点 （1）空间开销：虽然堆的大小可以动态调整，但动态调整大小（如扩容或缩容）可能会带来额外的内存开销。此外，堆中的每个节点都需要额外的存储空间来保存指向其子节点的指针（在完全二叉树的数组表示法中，这通常通过索引计算来实现，但本质上仍然需要额外的空间来管理这些索引）。 （2）可操作性差：堆的存放大小和生命周期是固定的，这在一定程度上限制了其可操作性。一旦堆被创建并初始化，其大小和形状就基本确定了，除非进行显式的扩容或缩容操作。
4. 堆的应用场景 （1）优先级队列：堆是优先级队列的一种高效实现方式。在优先级队列中，元素按照优先级进行排序，优先级最高的元素总是最先被处理。这广泛应用于操作系统中的任务调度、网络通信中的数据包处理等领域。 （2）求Top K值问题：堆可以用于解决求Top K值问题，即在一组数据中出前K个最大或最小的元素。这可以通过维护一个大小为K的小顶堆或大顶堆来实现。 （）合并有序文件：在大数据处理中，堆可以用于合并多个有序文件。通过将每个文件的第一行数据放入堆中，并依次取出堆顶元素（即当前最小的元素），然后将其所在文件的下一行数据放入堆中，直到所有文件都被处理完为止。这样可以高效地合并多个有序文件成一个有序的大文件。 （4）内存管理：在操作系统中，堆是内存管理的一个重要组成部分。它用于动态地分配和释放内存块，以支持程序的运行。虽然这里的“堆”与数据结构中的堆有所不同（它指的是操作系统虚拟进程地址空间中的一块区域），但两者都体现了动态调整和高效管理的思想。 （5）堆排序：是一种基于堆数据结构思想的比较排序算法，非常高效，具有原地排序、时间复杂度为O(nlogn)等优点
5. 源码：

代码语言：javascript代码运行次数：0运行复制

#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 = ULL;
	php->size = php->capacity = 0;
}

//堆的销毁
void HPDestroy(HP* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
	php->arr = ULL;
	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 == ULL)
		{
			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;
}

七、二叉树链式结构接口实现

1. 二叉树链式结构的特点：二叉树链式结构，又称二叉链表结构，是二叉树在计算机中的一种常见存储方式。其特点如下： （1）节点结构：每个节点包含三个部分：数据域（存储节点的值）、左孩子指针域（指向该节点的左孩子节点）和右孩子指针域（指向该节点的右孩子节点）。对于没有左孩子或右孩子的节点，相应的指针域为空（即ULL或nullptr）。 （2）层次关系：通过指针域，可以方便地表示节点之间的父子关系和兄弟关系，从而清晰地反映二叉树的层次结构。 （）动态性：链式结构允许二叉树在运行时动态地插入和删除节点，而无需像数组那样预先分配固定大小的空间。 （4）灵活性：链式结构可以灵活地适应不同形状和大小的二叉树，包括完全二叉树、不完全二叉树和退化的链表（即每个节点只有左孩子或右孩子）。 二叉树链式结构的优缺点
2. 优点 （1）节省空间：对于不完全二叉树，链式结构比数组存储更节省空间，因为不需要为不存在的节点预留空间。 （2）插入和删除操作高效：在链式结构中，插入和删除节点只需修改相关节点的指针域，时间复杂度较低。 （）适应性强：链式结构可以灵活地适应各种形状的二叉树，无需担心数组越界或空间浪费的问题。
3. 缺点 （1）指针开销：每个节点都需要额外的指针域来存储左右孩子的地址，这增加了节点的存储开销。 （2）访问速度较慢：与数组相比，链式结构在访问节点时需要通过指针逐级遍历，因此访问速度可能较慢。 （）内存管理复杂：链式结构需要手动管理内存（如分配和释放节点），这增加了程序的复杂性和出错的可能性。
4. 二叉树链式结构的应用场景 （1）表达式树：在编译器设计中，表达式树用于表示和计算数学表达式。每个节点表示一个操作符或操作数，左右孩子节点分别表示该操作符的左操作数和右操作数。 （2）二叉搜索树：二叉搜索树是一种用于高效查、插入和删除元素的树形数据结构。在二叉搜索树中，每个节点的值都大于其左子树中所有节点的值且小于其右子树中所有节点的值。 （）哈夫曼树：哈夫曼树（Huffman Tree）是一种用于数据压缩的树形数据结构。它根据字符出现的频率来构建树，频率高的字符离根节点近，频率低的字符离根节点远。在数据压缩过程中，哈夫曼树用于生成最优前缀码。 （4）AVL树：AVL树是一种自平衡的二叉搜索树，它保证了树的高度始终为O(log n)，从而保证了查、插入和删除操作的时间复杂度始终为O(log n)。AVL树在数据库索引、文件系统和内存管理等场合有广泛应用。 （5）红黑树：红黑树是一种平衡二叉搜索树，它通过颜属性和旋转操作来保持树的平衡性。红黑的树TreeMap在、JavaTreeSet等数据结构中得到了广泛应用。
5. 源码：

代码语言：javascript代码运行次数：0运行复制

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

typedef int BTDataType;

typedef struct BinaryTreeode
{
	BTDataType data;
	struct BinaryTreeode* left;
	struct BinaryTreeode* right;
}BTode;

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

//手动创建一颗链式二叉树
BTode* CreateBinaryTree()
{
	BTode* nodeA = BTBuyode('A');
	BTode* nodeB = BTBuyode('B');
	BTode* nodeC = BTBuyode('C');
	BTode* nodeD = BTBuyode('D');
	BTode* nodeE = BTBuyode('E');
	BTode* nodeF = BTBuyode('F');
	BTode* nodeG = BTBuyode('G');
	BTode* nodeH = BTBuyode('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(BTode* root)
{
	if (root == ULL)
	{
		//走到空节点开始返回
		return;
	}
	//打印根节点
	printf("%c ", root->data);
	//递归左孩子这颗子树
	PreOrder(root->left);
	//递归右孩子这颗子树
	PreOrder(root->right);
}

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

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

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

	return 1 + leftsize + rightsize;
}

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

	return leftsize + rightsize;
}

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

	return leftDepth > rightDepth ? leftDepth : rightDepth;
}

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

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

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

}

//二叉树的层序遍历
void LevelOrder(BTode* root)
{
	if (root == ULL)
	{
		return;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTode* 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(BTode* root)
{
	if (root == ULL)
	{
		return true;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTode* top = QueueFront(&q);
		if (top == ULL)
		{
			break;
		}
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q))
	{
		BTode* top = QueueFront(&q);
		if (top)
		{
			return false;
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return true;
}

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

   今天初阶数据结构的总结分享就到这里啦，有什么不懂的欢迎私信我，后面我们就开始正式学习八大排序算法了，敬请期待吧！    bye~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-20，如有侵权请联系 cloudcommunity@tencent 删除前往查看二叉树数据结构队列链表数据结构与算法