期末不知道如何复习数据结构的话，不妨点进来看看。看明白保你过。

 💯 博客内容：复习数据结构

😀 作  者：陈大大陈

🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！

💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘

目录

顺序表

单链表

双向链表

循环双向链表 

栈

队列

循环队列

二叉树

顺序表

这个是动态顺序表，我觉得功能已经十分的齐全了，要是有缺少的功能大家可以私信或者在评论区告诉我，我会修改的。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;//储存的有效数据个数
	int capacity;//容量
}SL;
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);
	if (psl->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;
}
void SLCheckCapacity(SL* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a,sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}
void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl ->capacity = 0;
}

void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//STL命名风格
void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;
}
void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	SLCheckCapacity(psl);
	int end = psl->size-1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;
}
void SLPopBack(SL* psl)
{
	assert(psl);
	if (psl->size <= 0)
	{
		return;
	}
	psl->size--;
}
void SLPopFront(SL* psl)
{
	assert(psl);
	if (psl->size <= 0)
	{
		return;
	}
	for (int i = 0; i < psl->size-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->size--;
}

void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	SLCheckCapacity(psl);;
	for (int i = pos; i < psl->size; i++)
	{
		psl->a[i+1] = psl->a[i];
	}
	psl->a[pos] = x;
	psl->size++;

}
void SLErase(SL* psl, int pos)
{
	assert(psl);
	if (psl->size <= 0)
	{
		return;
	}
	for (int i = pos; i < psl->size-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->size--;

}

// 找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	psl->a[pos] = x;
}
void menu()
{
	printf("***************************************\n");
	printf("1、尾插数据  2、尾删数据\n");
	printf("3、头插数据  4、头删数据\n");
	printf("5、打印数据  6.修改数据\n");
	printf("-1.退出程序\n");
	printf("***************************************\n");
}

int main()
{
	int option = 0;
	SL s;
	SLInit(&s);
	while (option != -1)
	{
		menu();
		printf("请输入你的操作:>");
		scanf("%d", &option);
		if (option == 1)
		{
			/*printf("请输入要尾插的数据，以-1结束:");
			int x = 0;
			scanf("%d", &x);
			while (x != -1)
			{
				SLPushBack(&s, x);
				scanf("%d", &x);
			}*/

			int n = 0;
			printf("请输入要尾插的数据个数，再依次输入要插入的数据:");
			scanf("%d", &n);

			int x = 0;
			while (n > 0)
			{
				scanf("%d", &x);
				SLPushBack(&s, x);
				n--;
			}
		}
		else if (option == 5)
		{
			SLPrint(&s);
		}
		else if (option == 2)
		{
			int n = 0;
			printf("请输入要尾删的数据个数");
			scanf("%d", &n);

			int x = 0;
			while (n > 0)
			{
				SLPopBack(&s);
				n--;
			}
		}
		else if (option == 3)
		{
			int n = 0;
			printf("请输入要头插的数据个数，再依次输入要插入的数据:");
			scanf("%d", &n);

			int x = 0;
			while (n > 0)
			{
				scanf("%d", &x);
				SLPushFront(&s, x);
				n--;
			}
		}
		else if (option == 4)
		{
			int x;
			int n;
			printf("请输入需要头删的个数");
			scanf("%d", &n);
			while (n)
			{
				SLPopFront(&s);
				n--;
			}
		}
		else if (option == 6)
		{
			printf("请输入要修改的数的下标\n");
			int x;
			scanf("%d", &x);
			printf("请输入修改后的数字\n");
			int n;
			scanf("%d", &n);
			SLModify(&s, x, n);
		}
		else if (option == -1)
		{
			break;
		}
		else
		{
			printf("无此选项,请重新输入\n");
		}
	}

	SLDestroy(&s);

	return 0;
}

单链表

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d=>", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
}
SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLPushFront(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = BuyLTNode(x);
	
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* cur = *pphead;

	
	SLTNode* newnode = BuyLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
		newnode = *pphead;
	}
	else
	{
		while (cur->next!= NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

void SLPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
}
void SLPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		// 找到尾结点
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPopFront(&plist);
	SLPushFront(&plist, 1);
	SLPopBack(&plist);
	SLPushBack(&plist, 4);
	SLTPrint(plist);
}

int main()
{
	TestSList2();

	return 0;
}

双向链表

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}LTNode;
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("GUard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = phead;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;

}
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* head = phead->next;
	LTNode* newnode = BuyLTNode(x);
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = head;
	head->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;

}
void LTPopFront(LTNode* phead)
{
	LTNode* head = phead->next;
	LTNode* headnext = head->next;
	phead->next = headnext;
	headnext->prev = phead;
	free(head);
}

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	newnode->next = pos;
	pos->prev = newnode;
	prev->next = newnode;
	newnode->prev = prev;
}
// 删除pos位置的值
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
}
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

void TestList3()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPopFront(plist);
	LTPopBack(plist);
	LTPushBack(plist, 9);
	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	TestList3();

	return 0;
}

像头插，尾删这样的功能，我们可以直接通过复用 LTInsert和LTErase来实现，这样写可以大幅度简化代码，让代码精简。代码如下：

 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct Node
{
	int data;
	struct Node* next;
	struct Node* prev;
}Node;
Node* BuyListNode(int x);
Node* SLInit();
void LTPopFront(Node* phead);
void LTPushFront(Node* phead, int x);
void LTPopBack(Node* phead);
void LTDestroy(Node* phead);
void LTPushBack(Node* phead, int x);
void LTErase(Node* phead);
void LTInsert(Node* pos, int x);
int LTEmpty(Node* phead);
void Print(Node* phead);
Node* BuyListNode(int x)
{
 
	Node* newnode = (Node*)malloc(sizeof(Node));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
Node* SLInit()
{
	Node* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
void LTInsert(Node* pos, int x)
{
	assert(pos);
	Node* newnode = BuyListNode(x);
	Node* prev = pos->prev;
	newnode->next = prev->next;
	newnode->prev = prev;
	prev->next = newnode;
	pos->prev = newnode;
}
void LTPushFront(Node* phead, int x)
{
	assert(phead);
	LTInsert(phead->next, x);
}
void LTPushBack(Node* phead, int x)
{
	assert(phead);
	LTInsert(phead, x);
}
void LTPopFront(Node* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}
void LTErase(Node* pos)
{
	assert(pos);
	Node* prev = pos->prev;
	Node* next = pos->next;
	prev->next = next;
	next->prev = prev;
 
}
void LTPopBack(Node* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}
void LTDestroy(Node* phead)
{
	assert(phead);
	Node* cur = phead->next;
	while (phead != cur)
	{
		Node* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
 
}
int LTEmpty(Node* phead)
{
	assert(phead);
	return phead == phead->next;
}
void Print(Node* phead)
{
	Node* cur = phead->next;
	while (cur != phead)
	{
		Node* next = cur->next;
		printf("%d<==>", cur->data);
		cur = next;
	}
	printf("\n");
}

循环双向链表 

typedef int DLLData;
typedef struct DLLNode
{
	DLLData data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

 
// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
	guard->next = guard->prev = guard;
	return guard;
}
 
// 创建一个新的结点
ListNode* BuyNewnode(LTDataType x)
{
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	new_node->data = x;
	return new_node;
}
 
// 双向链表销毁
void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* tmp = phead->next, *node = phead->next;
	phead->next = NULL;
	while (tmp)
	{
		node = tmp->next;
		free(tmp);
		tmp = node;
	}
}
 
// 双向链表打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* tmp = phead->next;
	printf("phead<=>");
	while (tmp != phead)
	{
		printf("%d<=>", tmp->data);
		tmp = tmp->next;
	}
	printf("phead\n");
}
 
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}
 
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!CheckVoid(phead));
	ListErase(phead->prev);
}
 
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
 
// 双向链表头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(!CheckVoid(phead));
	ListErase(phead->next);
}
 
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* tmp = phead->next;
	while (tmp != phead)
	{
		if (tmp->data == x)
			return tmp;
		tmp = tmp->next;
	}
	return NULL;
}
 
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	ListNode* front = pos->prev;
	ListNode* new_node = BuyNewnode(x);
	front->next = new_node;
	new_node->next = pos;
	pos->prev = new_node;
	new_node->prev = front;
}
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}
 
// 检查链表为空
bool CheckVoid(ListNode* rhs)
{
	assert(rhs);
	return rhs->next == rhs;
}

栈

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//这里要注意，如果设置top为-1，则为指向数据位置，如果设置top=0,则指向数据的下一个位置。
	pst->capacity = 0;
}
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
void STPush(ST* pst, STDataType x)
{
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
void STPop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	pst->top--;
}
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(!STEmpty(pst));
	return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}
void TestStack1()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	printf("%d ", STTop(&st));
	STPop(&st);

	STPush(&st, 3);
	STPush(&st, 4);
	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	STDestroy(&st);
}
int main()
{
	TestStack1();

	return 0;
}

队列

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->ptail = pq->phead = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
	
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//头删
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

int main()
{
	Queue* pq = (Queue*)malloc(sizeof(Queue));;
	QueueInit(pq);
	QueuePush(pq, 1);
	QueuePush(pq, 2);
	QueuePush(pq, 3);
	QueuePush(pq, 4);
	QueuePush(pq, 5);
	printf("%d\n", QueueSize(pq));
	printf("%d\n", QueueFront(pq));
	printf("%d\n", QueueBack(pq));
	return 0;
}

循环队列

# include<stdio.h>
# include<malloc.h>
# define TRUE 1
# define FALSE 0

/*链队列*/
/*链队列的存储结构*/
typedef struct Node {
	int data;						//队列数据域
	struct Node* next;				//队列指针域
}LinkQueueNode;

typedef struct {
	LinkQueueNode* front;//头指针
	LinkQueueNode* rear;//尾指针
}LinkQueue;

/*链队列的初始化*/
int InitQueue(LinkQueue* Q) {
	Q->front = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
	if (Q->front != NULL) {
		Q->rear = Q->front;
		Q->front->next = NULL;
		return TRUE;
	}
	else
		return FALSE;				//溢出
}

/*链队列的创建*/
void CreateQueue(LinkQueue* Q) {
	LinkQueueNode* NewNode;
	int c, flag = 1;
	while (flag) {
		scanf("%d", &c);
		if (c != 0) {
			NewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
			NewNode->data = c;
			Q->rear->next = NewNode;	//新结点插入到队尾
			Q->rear = NewNode;			//修改队尾指针
		}
		else {
			flag = 0;
			NewNode->next = NULL;
		}
	}
}

/*链队列入队*/
int EnterQueue(LinkQueue* Q, int x) {
	/*将数据元素x插入到队列Q中*/
	LinkQueueNode* NewNode;
	NewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
	if (NewNode != NULL) {
		NewNode->data = x;
		NewNode->next = NULL;
		Q->rear->next = NewNode;	//新结点插入到队尾
		Q->rear = NewNode;			//修改队尾指针
		return TRUE;
	}
	return FALSE;
}

/*链队列出队*/
int DeleteQueue(LinkQueue* Q, int* x) {
	/*将队列Q的队头元素出队，并保存到x中*/
	LinkQueueNode* p;
	if (Q->front == Q->rear)		//空队列
		return FALSE;
	p = Q->front->next;				//p指向队头元素
	Q->front->next = p->next;		//队头元素p出队
	if (Q->rear == p)				//若队中只有一个元素p，则p出队后成为空队
		Q->rear = Q->front;
	*x = p->data;
	free(p);
	return TRUE;
}

/*队列输出*/
void Display(LinkQueue* Q) {
	if (Q->front == Q->rear)		//空队列
		printf("空队列！\n");
	else {
		LinkQueueNode* p;
		p = Q->front->next;			//p指向队头元素
		while (p != NULL) {
			printf("%d ", p->data);
			p = p->next;
		}
		printf("\n");
	}
}

int main() {
	int x;
	LinkQueue Q;
	InitQueue(&Q);					//初始化队列

	printf("创建队列(以0结束)：");		//创建
	CreateQueue(&Q);
	printf("创建的队列元素为：");
	Display(&Q);

	EnterQueue(&Q, 5);				//入队
	printf("入队后队中元素为：");
	Display(&Q);

	DeleteQueue(&Q, &x);			//出队
	printf("出队元素为：%d\n", x);
	printf("出队后队中元素为：");
	Display(&Q);
	return 0;
}

二叉树

二叉树的层序遍历需要用到队列的知识，大家看代码可能不理解是什么意思，不过没关系。

只要你画个图，一切就会豁然开朗！

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

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

void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;           
	return newnode;
}
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
int BTNodeSize(BTNode* root)
{
	return root == NULL ? 0 : BTNodeSize(root->left) + BTNodeSize(root->right) + 1;
}
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int LeftHeight = BTreeHeight(root->left);
	int RightHeight = BTreeHeight(root->right);
	return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}
int BTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}
BTNode* BTFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* ret1 = BTFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BTFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}
void BTreeNodeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BTreeNodeDestroy(root->left);
	BTreeNodeDestroy(root->right);
	free(root);
}
// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		// 遇到空就跳出
		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	// 检查后面的节点有没有非空
	// 有非空，不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; ++i)
	{
		// [0, end] 有序，插入tmp依旧有序
		int end = i - 1;
		int tmp = a[i];

		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
}

图的知识太多了，我在这里就不列举了。

大家期末加油。。。祝大家拿满绩。。。文章来源地址https://www.toymoban.com/news/detail-507392.html

到了这里，关于期末不知道如何复习数据结构的话，不妨点进来看看。看明白保你过。的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！