C/C++ 数据结构与算法笔记

实现顺序表

代码语言：javascript复制

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

#define MaxSize 10

int Insert_Elem(int Array[], int *len, int ins, int val)
{
	// 首先来判断,是否是非法插入
	if (*len == MaxSize || ins < 1 || ins > *len   1)
		return -1;

	int x;

	for (x = *len - 1; x >= ins - 1; x--)
		Array[x   1] = Array[x];

	Array[x - 1] = val;      // 插入元素
	*len = *len   1;         // 表长度自增

	return 1;
}

int main(int argc,char * argv[])
{
	int Array[MaxSize] = { 1, 2, 3, 4, 5 };
	int array_len = 5;           // 数组当前长度

	Insert_Elem(Array, &array_len, 2, 10);  // 在第二个位置插入一个10

	system("pause");
	return 0;
}

实现链表结构

什么是静态链表？ 一个案例解决疑问.

代码语言：javascript复制

#include <stdio.h>

struct LinkList
{
	int data;
	char *name;
	struct LinkList *next;
};

int main(int argc,char * argv[])
{
	struct LinkList node1 = { 10, "lyshark",NULL };
	struct LinkList node2 = { 20, "admin",NULL };
	struct LinkList node3 = { 30, "lyshark",NULL };

	node1.next = &node2;
	node2.next = &node3;
	node3.next = NULL;

	struct LinkList *ptr = &node1;
	while (ptr != NULL)
	{
		printf("%d n", ptr->data);
		printf("%s n", ptr->name);
		ptr = ptr->next;
	}

	system("pause");
	return 0;
}

简单的实现静态顺序表：此种简单的顺序表结构并不灵活，因为其无法动态开辟空间。

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 10

//参数1：传递顺序表的首地址
//参数2：len表的长度
//参数3：插入元素的位置
//参数4：待插入的元素值
int InsertElem(int list[], int *len, int x, int y)
{
	if (*len == MaxSize || x < 1 || x > *len   1)
		return 0;
	for (int z = *len - 1; z >= x - 1; z--)
		list[z   1] = list[z];
	list[x - 1] = y;
	*len = *len   1;
	return 1;
}
//参数1：传递顺序表的首地址
//参数2：len表的长度
//参数3：待删除元素的位置
int DeleteElem(int list[], int *len, int x)
{
	int y;
	if (x < 1 || x >len)
		return 0;
	for (y = x; y <= *len - 1; y  )
		list[y - 1] = list[y];
	*len = *len - 1;
	return 1;
}

int main()
{
	int Sqlist[MaxSize] = {1,2,3,4,5};
	int ListLen = 5;

	for (int x = 0; x < ListLen; x  )
		printf_s("%d ", Sqlist[x]);
	printf_s("n得到当前数组长度：%dn", MaxSize - ListLen);

	InsertElem(Sqlist, &ListLen, 3, 100);
	DeleteElem(Sqlist, ListLen, 4);

	for (int x = 0; x < ListLen; x  )
		printf_s("%d ", Sqlist[x]);
	printf_s("n得到当前数组长度：%dn", MaxSize - ListLen);
	getchar();
	return 0;
}

实现动态顺序表,可动态生成数据.

代码语言：javascript复制

#include <stdio.h>
#define MaxSize 10
typedef int ElemType;

typedef struct{
	int *elem;
	int length;
	int size;
}list;

int InitList(list *mem)
{
	mem->elem = (int *)malloc(MaxSize*sizeof(ElemType));
	if (!mem->elem)exit(0);
	mem->length = 0;
	mem->size = MaxSize;
	if (mem->elem != 0)
		return 1;
}

// 参数1：mem类型的指针基地址
// 参数2：i插入元素的位置
// 参数3：item待插入的元素
void InsertElem(list *mem, int i, ElemType item)
{
	ElemType *base, *insertPtr, *p;
	if (i<1 || i>mem->length   1)exit(0);
	if (mem->length >= mem->size)
	{
		// 说明我们的链表满了,需要追加开辟空间
		base = (ElemType*)realloc(mem->elem, (mem->size   10)*sizeof(ElemType));
		mem->size = mem->size   50;
	}
	insertPtr = &(mem->elem[i - 1]); // 取出第二个元素位置地址
	for (p = &(mem->elem[mem->length - 1]); p >= insertPtr; p--)
		*(p   1) = *p;
	*insertPtr = item;
	mem->length  ;
}

// 参数1：mem类型的指针基地址
// 参数2：删除元素的位置
void DeleteElem(list *mem, int i)
{
	ElemType *delItem, *p;
	if (i<1 || i>mem->length)
		exit(0);
	delItem = &(mem->elem[i - 1]);
	p = mem->elem   mem->length - 1;
	for (  delItem; delItem <= p;   delItem)
		*(delItem - 1) = *delItem;
	mem->length--;
}

int main()
{
	list temp;
	InitList(&temp);
	for (int x = 1; x < 15; x  )
		InsertElem(&temp, x, x );             // 插入1-15
	for (int x = 0; x < temp.length; x  )     // 打印1-15 
		printf("%d ", temp.elem[x]);
	// 删除第三个位置的数值
	DeleteElem(&temp, 3);
	// 打印出删除后的结果
	for (int x = 0; x < temp.length; x  )
		printf("n%d ", temp.elem[x]);
	getchar();
	return 0;
}

实现单向链表：

代码语言：javascript复制

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct node{
	ElemType data;
	struct node *next;
}LinkNode, *LinkList;

// 初始化一个链表
LinkList InitLinkList()
{
	LinkList ptr,list = NULL;
	ptr = (LinkList)malloc(sizeof(LinkNode));
	ptr->data = 0;       // 初始化第一个元素始终为0
	ptr->next = NULL;
	if (!list)
		list = ptr;
	return list;
}
// 向链表中指针offset指向节点的后面插入新节点,并赋值为number
void InsertLinkList(LinkList *list, LinkList offset, ElemType number)
{
	LinkList ptr;
	ptr = (LinkList)malloc(sizeof(LinkNode));
	ptr->data = number;
	ptr->next = offset->next;
	offset->next = ptr;
}
// 删除链表中的指定位置中的元素
void DeleteLinkList(LinkList *list, LinkList offset)
{
	LinkList temp;
	if (offset == list){
		*list = offset->next;
		free(offset);
	}
	else
	{
		for (temp = *list; temp->next != offset; temp = temp->next);
			if (temp->next != NULL){
				temp->next = offset->next;
				free(offset);
			}
		}
}
// 销毁链表
void DestroyLinkList(LinkList *list)
{
	LinkList Ptr, temp;
	Ptr = *list;
	while (Ptr)
	{
		temp = Ptr->next;
		free(Ptr);
		Ptr = temp;
	}
	*list = NULL;
}

int main()
{
	LinkList forc, ListPtr;
	ListPtr = InitLinkList(); // 初始化链表

	forc = ListPtr;
	for (int i = 0; i < 10;i  )
	{ // 写入0-10
		InsertLinkList(&ListPtr, forc, i);
		forc = forc->next;
	}

	forc = ListPtr;
	while (forc)
	{ // 循环遍历链表节点
		printf("链表节点中的数据：%d n", forc->data);
		forc = forc->next;
	}

	forc = ListPtr;
	for (int i = 0; i < 4; i  )    // 移动指针 
		forc = forc->next;
	DeleteLinkList(&ListPtr, forc);// 删除第4个位置上的元素

	DestroyLinkList(&ListPtr);  // 销毁链表
	getchar();
	return 0;
}

另一种实现方式（链表）

代码语言：javascript复制

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

// 定义链表节点类型
struct LinkNode
{
	int data;
	struct LinkNode *next;
};

struct LinkNode *init_link()
{  // 创建一个头结点,头结点不需要添加任何数据
	struct LinkNode *header = malloc(sizeof(struct LinkNode));
	header->data = 0;
	header->next = NULL;

	struct LinkNode *p_end = header;    // 创建一个尾指针

	int val = -1;
	while (1)
	{
		scanf("%d", &val);  // 输入插入的数据
		if (val == -1)      // 如果输入-1说明输入结束了
			break;

		// 先创建新节点
		struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
		newnode->data = val;
		newnode->next = NULL;

		// 将节点插入到链表中
		p_end->next = newnode;
		// 更新尾部指针指向
		p_end = newnode;
	}
	return header;
}

// 遍历链表
int foreach_link(struct LinkNode *header)
{
	if (NULL == header || header->next == NULL)
		return 0;

	while (header->next != NULL)
	{
		printf("%d n", header->data);
		header = header->next;
	}
	return 1;
}

// 在header节点中oldval插入数据
void insert_link(struct LinkNode *header,int oldval,int newval)
{
	struct LinkNode *pPrev = header;
	struct LinkNode *Current = pPrev->next;

	if (NULL == header)
		return;


	while (Current != NULL)
	{
		if (Current->data == oldval)
			break;

		pPrev = Current;
		Current = Current->next;
	}
	// 如果值不存在则默认插入到尾部
	//if (Current == NULL)
	//	return;

	// 创建新节点

	struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
	newnode->data = newval;
	newnode->next = NULL;

	// 新节点插入到链表中
	newnode->next = Current;
	pPrev->next = newnode;
}

// 清空链表
void clear_link(struct LinkNode *header)
{
	// 辅助指针
	struct LinkNode *Current = header->next;

	while (Current != NULL)
	{
		// 保存下一个节点地址
		struct LinkNode *pNext = Current->next;
		printf("清空数据: %d n", Current->data);
		free(Current);
		Current = pNext;
	}
	header->next = NULL;
}

// 删除值为val的节点
int remove_link(struct LinkNode *header, int delValue)
{
	if (NULL == header)
		return;

	// 设置两个指针,指向头结点和尾结点
	struct LinkNode *pPrev = header;
	struct LinkNode *Current = pPrev->next;

	while (Current != NULL)
	{
		if (Current->data == delValue)
		{
			// 删除节点的过程
			pPrev->next = Current->next;
			free(Current);
			Current = NULL;
		}
	}

	// 移动两个辅助指针
	pPrev = Current;
	Current = Current->next;
}

// 销毁链表
void destroy_link(struct LinkNode *header)
{
	if (NULL == header)
		return;

	struct LinkNode *Curent = header;
	while (Curent != NULL)
	{
		// 先来保存一下下一个节点地址
		struct LinkNode *pNext = Curent->next;

		free(Curent);

		// 指针向后移动
		Curent = pNext;
	}
}

// 反响排序
void reverse_link(struct LinkNode *header)
{
	if (NULL == header)
		return;

	struct LinkNode *pPrev = NULL;
	struct LinkNode *Current = header->next;
	struct LinkNode * pNext = NULL;

	while (Current != NULL)
	{
		pNext = Current->next;
		Current->next = pPrev;

		pPrev = Current;
		Current = pNext;
	}
	header->next = pPrev;
}


int main(int argc, char* argv[])
{
	struct LinkNode * header = init_link();

	reverse_link(header);
	foreach_link(header);

	clear_link(header);
	system("pause");
	return 0;
}

简单的链表

LinkList.c

代码语言：javascript复制

#include"LinkList.h"


//初始化链表
struct LinkNode *Init_LinkList()
{

	//创建头结点
	struct LinkNode *header = malloc(sizeof(struct LinkNode));
	header->data = - 1;
	header->next = NULL;

	//尾部指针
	struct LinkNode *pRear = header;

	int val = -1;
	while (true)
	{

		printf("输入插入的数据:n");
		scanf("%d",&val);
		if (val == -1)
		{
			break;
		}

		//先创建新节点
		struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
		newnode->data = val;
		newnode->next = NULL;

		//新节点插入到链表中
		pRear->next = newnode;

		//更新尾部指针指向
		pRear = newnode;


	}

	return header;
}

void InsertByValue_LinkList(struct LinkNode *header, int oldval, int newval)
{
	if (NULL == header)
	{
		return;
	}


	//两个辅助指针变量
	struct LinkNode *pPrev = header;
	struct LinkNode *pCurrent = pPrev->next;

	while (pCurrent != NULL)
	{

		if (pCurrent->data == oldval)
		{
			break; 
		}

		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}

#if 0
	//如果pCurrent为NULL  说明链表中不存在值为oldval的结点
	if (pCurrent == NULL)
	{
		return;
	}
#endif


	//先创建新结点
	struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
	newnode->data = newval;
	newnode->next = NULL;

	//新节点插入到链表中
	newnode->next = pCurrent;
	pPrev->next = newnode;



}
//删除值为val的结点
void RemoveByValue_LinkList(struct LinkNode *header, int delValue)
{

	if (NULL == header)
	{
		return;
	}

	//两个辅助指针变量
	struct LinkNode *pPrev = header;
	struct LinkNode *pCurrent = pPrev->next;

	while (pCurrent != NULL)
	{

		if (pCurrent->data == delValue)
		{
			break;
		}

		//移动两个辅助指针
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}

	if (NULL == pCurrent)
	{
		return;
	}

	//重新建立待删除节点的前驱和后继结点关系
	pPrev->next = pCurrent->next;
	//释放删除节点内存
	free(pCurrent);
	pCurrent = NULL;

}
//遍历
void Foreach_LinkList(struct LinkNode *header)
{
	if (NULL == header)
	{
		return;
	}

	//辅助指针变量
	struct LinkNode *pCurrent = header->next;

	while (pCurrent != NULL)
	{
		printf("%d ",pCurrent->data);
		pCurrent = pCurrent->next;
	}

}
//销毁
void Destroy_LinkList(struct LinkNode *header)
{
	if (NULL == header)
	{
		return;
	}

	//辅助指针变量
	struct LinkNode *pCurrent = header;

	while (pCurrent != NULL)
	{
		//先保存下当前结点的下一个节点地址
		struct LinkNode *pNext = pCurrent->next;

		//释放当前结点内存
		printf("%d节点被销毁!n", pCurrent->data);
		free(pCurrent);

		//指针向后移动
		pCurrent = pNext;

	}

}
//清空
void Clear_LinkList(struct LinkNode *header)
{
	if (NULL == header)
	{
		return;
	}


	//辅助指针变量
	struct LinkNode *pCurrent = header->next;

	while (pCurrent != NULL)
	{

		//先保存下当前结点的下一个节点地址
		struct LinkNode *pNext = pCurrent->next;

		//释放当前结点内存
		free(pCurrent);

		//pCurrent指向下一个节点
		pCurrent = pNext;

	}

	header->next = NULL;

}

linklist.h

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS

#pragma once

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

#ifdef __cplusplus
extern "C"{
#endif


	//定义节点数据类型
	struct LinkNode
	{
		int data;
		struct LinkNode *next;
	};

	//初始化链表
	struct LinkNode *Init_LinkList();
	//在值为oldval的位置插入新的数据newval
	void InsertByValue_LinkList(struct LinkNode *header,int oldval,int newval);
	//删除值为val的结点
	void RemoveByValue_LinkList(struct LinkNode *header,int delValue);
	//遍历
	void Foreach_LinkList(struct LinkNode *header);
	//销毁
	void Destroy_LinkList(struct LinkNode *header);
	//清空
	void Clear_LinkList(struct LinkNode *header);

#ifdef __cplusplus
}
#endif

main.c

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"LinkList.h"

void test()
{
	//初始化链表 100 200 666 300 400 500 600
	struct LinkNode *header =  Init_LinkList();
	//打印链表
	Foreach_LinkList(header);
	//插入数据
	InsertByValue_LinkList(header, 200, 666);
	//打印链表
	printf("n-------------------n");
	Foreach_LinkList(header);

	//清空链表
	Clear_LinkList(header);
	//打印链表

	InsertByValue_LinkList(header, 1000, 111);
	InsertByValue_LinkList(header, 1000, 211);
	InsertByValue_LinkList(header, 1000, 311);
	InsertByValue_LinkList(header, 1000, 411);

	printf("n-------------------n");
	Foreach_LinkList(header);


	RemoveByValue_LinkList(header,311);
	printf("n-------------------n");
	Foreach_LinkList(header);

	RemoveByValue_LinkList(header, 211);
	printf("n-------------------n");
	Foreach_LinkList(header);

	//销毁链表
	Destroy_LinkList(header);

}

int main(){

	test();

	system("pause");
	return EXIT_SUCCESS;
}

StaticArray

代码语言：javascript复制

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

#define MaxSize 10
typedef int ElemType;

typedef struct{
	int *data;
	int current_size;
	int max_size;
}Dynamic_Array;

// 初始化动态数组,传递进来一个数组首地址
int Init_Dynamic_Array(Dynamic_Array *Array)
{
	Array->data = (int *)malloc(MaxSize * sizeof(ElemType));
	if (!Array->data)                    // 判断malloc是否分配成功
		return 0;

	Array->current_size = 0;             // 初始化元素个数
	Array->max_size = MaxSize;           // 初始化最大存储个数

	if (Array->data != 0)                // 数组分配成功则返回1
		return 1;
	return 0;
}

// 参数1: Array = > 数组元素指针基地址
// 参数2: ins => 待插入元素的位置
// 参数3: val => 待插入的元素
int Insert_Dynamic_Array(Dynamic_Array *Array, int ins, ElemType val)
{
	ElemType *base, *insertPtr, *p;

	// 判断如果插入元素位置小于开头,或者大于结尾,则直接返回错误
	if (ins < 0 || ins > Array->current_size   1)
		return 0;

	if (Array->current_size >= Array->max_size)
	{
		// 如果循环到这里,说明我们的存储空间满了,需要分配一块更大的空间
		base = (ElemType*)realloc(Array->data, (Array->max_size   10)*sizeof(ElemType));
		Array->max_size = Array->max_size   40;       // 长度递增
	}
	// 取出第二个元素的位置,insertPtr为插入元素的位置
	insertPtr = &(Array->data[ins - 1]);

	// 循环指针,为待插入元素空出一个空间,指针后移操作
	for (p = &(Array->data[Array->current_size - 1]); p >= insertPtr; p--)
		*(p   1) = *p;           // 将ins以后的元素全部后移一个单位
	*insertPtr = val;            // 在第ins个位置上插入元素val
	Array->current_size  ;     // 当前元素数递增
	return 1;
}

// 参数1: Array = > 数组元素指针基地址
// 参数2: ins => 待删除元素的位置
int Delete_Dynamic_Array(Dynamic_Array *Array, int ins)
{
	ElemType *delItem, *p;
	if (ins < 0 || ins>Array->current_size)
		return 0;

	delItem = &(Array->data[ins - 1]);              // delItem指向第ins个元素
	p = Array->data   Array->current_size - 1;      // p指向表尾部

	for (  delItem; delItem <= p;   delItem)        // 从表位向前,ins位置以后的元素依次前移
		*(delItem - 1) = *delItem;

	Array->current_size--;
	return 0;
}

int main(int argc, char * argv[])
{
	Dynamic_Array MyArray;

	// 初始化数组,并保存首地址到MyArray
	Init_Dynamic_Array(&MyArray);

	// 插入测试数据
	for (int x = 0; x <= 20; x  )
		Insert_Dynamic_Array(&MyArray, x, x);

	// 删除元素中的 1,3,5 这几个位置
	Delete_Dynamic_Array(&MyArray, 1);
	Delete_Dynamic_Array(&MyArray, 3);
	Delete_Dynamic_Array(&MyArray, 5);

	// 循环删除后的数据
	for (int x = 0; x < MyArray.current_size - 1; x  )
		printf("%d ", MyArray.data[x]);

	system("pause");
	return 0;
}

DynamicArray

dynamice.h

代码语言：javascript复制

#pragma once

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

#ifdef __cplusplus
extern "C"{
#endif
	struct DynamicArray
	{
		void **addr;   // 存放元素或结构体的首地址
		int curr_size; // 存放当前元素数量
		int max_size;  // 存放当前最大元素数
	};
	struct DynamicArray *Init_DynamicArray(int size);
	void Insert_DynamicArray(struct DynamicArray *ptr, int index, void *data);
	void Foreach_DynamicArray(struct DynamicArray *ptr, void(*_callback)(void *));
	void RemoveByPos_DynamicArray(struct DynamicArray *ptr, int index);
	void RemoveByValue_DynamicArray(struct DynamicArray *ptr, void *data, int(*compare)(void*, void *));
	void Destroy_DynamicArray(struct DynamicArray *ptr);
#ifdef __cplusplus }
#endif

代码语言：javascript复制

#include"DynamicArray.h"

// 初始化动态数组,初始化后直接返回数组的首地址
struct DynamicArray *Init_DynamicArray(int size)
{
	// 如果小于0则说明没有元素,返回NULL
	if (size <= 0)
		return NULL;

	// 分配结构指针,此处分配的是结构体指针,并没有分配空间
	struct DynamicArray *ptr = malloc(sizeof(struct DynamicArray));
	if (ptr != NULL)
	{
		ptr->curr_size = 0;              // 将当前元素索引设置为0
		ptr->max_size = size;            // 默认最大数组元素数为size
		// 实际分配存储空间：大小是max_size 最大元素
		ptr->addr = malloc(sizeof(void *) * ptr->max_size);
		return ptr;
	}
	return NULL;
}

// 将元素插入到指定位置
// 参数1: 传入数组首地址
// 参数2: 传入要插入元素位置
// 参数3: 传入插入的元素或结构
void Insert_DynamicArray(struct DynamicArray *ptr, int index, void *data)
{
	// 判断如果数组不为空,或者是data不为空,则继续执行
	if (ptr != NULL || data != NULL)
	{
		// 如果插入位置小于当前0,或者大于当前元素总个数
		if (index < 0 || index > ptr->curr_size)
		{
			// 就自动把它插入到元素的末尾位置
			index = ptr->curr_size;
		}

		// 紧接着判断当前元素数是否大于最大值,大于则分配空间
		if (ptr->curr_size >= ptr->max_size)
		{
			// 分配一块更大的空间,这里分配原始空间的2倍
			int new_max_size = ptr->max_size * 2;
			void **new_space = malloc(sizeof(void *) * new_max_size);

			// 接着将原来空间中的数据拷贝到新分配的空间
			memcpy(new_space, ptr->addr, sizeof(void *) * ptr->max_size);

			// 释放原来的内存空间,并更新指针的指向为新空间的地址
			free(ptr->addr);
			ptr->addr = new_space;
			ptr->max_size = new_max_size;
		}

		// 开始移动元素,给ins元素腾出空来
		for (int x = ptr->curr_size - 1; x >= index; --x)
		{
			// 从后向前,将前一个元素移动到后一个元素上
			ptr->addr[x   1] = ptr->addr[x];
		}
		// 设置好指针以后,开始赋值
		ptr->addr[index] = data;
		ptr->curr_size  ;
		return 1;
	}
	return 0;
}

// 遍历数组中的元素,这里的回调函数是用于强制类型转换,自定义输出时使用
void Foreach_DynamicArray(struct DynamicArray *ptr, void(*_callback)(void *))
{
	if (ptr != NULL || _callback != NULL)
	{
		for (int x = 0; x < ptr->curr_size; x  )
		{
			// 调用回调函数并将数组指针传递过去
			_callback(ptr->addr[x]);
		}
	}
}

// 根据位置删除指定元素,index = 元素的下标位置
void RemoveByPos_DynamicArray(struct DynamicArray *ptr, int index)
{
	if (ptr == NULL)
		return NULL;

	// 判断当前插入位置index必须大于0且小于curr_size
	if (index > 0 || index < ptr->curr_size - 1)
	{
		for (int i = index; i < ptr->curr_size - 1;   i)
		{
			// 每次循环都将后一个元素覆盖到前一个元素上
			ptr->addr[i] = ptr->addr[i   1];
		}
		ptr->curr_size--;   // 最后当前元素数量应该减去1
	}
}

// 按照元素的指定值进行元素删除,这里需要回调函数指定要删除元素的值是多少
void RemoveByValue_DynamicArray(struct DynamicArray *ptr, void *data, int(*compare)(void*, void *))
{
	if (ptr != NULL && data != NULL && compare != NULL)
	{
		for (int i = 0; i < ptr->curr_size;   i)
		{
			if (compare(ptr->addr[i], data))
			{
				RemoveByPos_DynamicArray(ptr, i);
				break;
			}
		}
	}
}

//销毁数组
void Destroy_DynamicArray(struct DynamicArray *ptr)
{
	if (ptr != NULL)
	{
		if (ptr->addr != NULL)
		{
			free(ptr->addr);
			ptr->addr = NULL;
		}
		free(ptr);
		ptr = NULL;
	}
}

代码语言：javascript复制

#include<stdio.h>
#include"DynamicArray.h"

struct Student
{
	int uid;
	char name[64];
	int age;
};

// 回调函数用于输出元素
void MyPrint(void *data)
{
	// 强制类型转换,转成我们想要的类型
	struct Student *ptr = (struct Student *)data;
	printf("Uid: %d --> Name: %s n", ptr->uid, ptr->name);
}

// 回调函数用于对比元素
int myCompare(void *x, void *y)
{
	struct Student *p1 = (struct Student *)x;
	struct Student *p2 = (struct Student *)y;

	if (strcmp(p1->name, p2->name) == 0)
	{
		return 1;
	}
	return 0;
}

int main()
{
	//创建动态数组
	struct DynamicArray *ptr = Init_DynamicArray(5);

	// 创建元素
	struct Student stu1 = { 1001, "admin1", 22 };
	struct Student stu2 = { 1002, "admin2", 33 };
	struct Student stu3 = { 1003, "admin3", 44 };
	struct Student stu4 = { 1004, "admin4", 55 };

	// 将元素插入到数组
	Insert_DynamicArray(ptr, 0, &stu1);
	Insert_DynamicArray(ptr, 1, &stu2);
	Insert_DynamicArray(ptr, 3, &stu3);
	Insert_DynamicArray(ptr, 4, &stu4);

	RemoveByPos_DynamicArray(ptr, 0);     // 根据下标移除元素

	// 删除元素是 p_delete 的数据
	struct Student p_delete = { 1002, "admin2", 33 };
	RemoveByValue_DynamicArray(ptr, &p_delete, myCompare);

	Foreach_DynamicArray(ptr, MyPrint);   // 遍历元素
	Destroy_DynamicArray(ptr);            // 销毁顺序表

	system("pause");
	return EXIT_SUCCESS;
}

LinkList

linklist.h

代码语言：javascript复制

#pragma once

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

#ifdef __cplusplus
extern "C"{
#endif

	typedef void * LinkList;
	typedef void(*FOREACH)(void *);
	typedef int(*COMPARE)(void *,void *);

	//初始化链表
	LinkList Init_LinkList();
	//插入节点
	void Insert_LinkList(LinkList list,int pos,void *data);
	//遍历链表
	void Foreach_LinkList(LinkList list, FOREACH myforeach);
	//按位置删除
	void RemoveByPos_LinkList(LinkList list,int pos);
	//按值删除
	void RemoveByVal_LinkList(LinkList list, void *data, COMPARE compare);
	//清空链表
	void Clear_LinkList(LinkList list);
	//大小
	int Size_LinkList(LinkList list);
	//销毁链表
	void Destroy_LinkList(LinkList list);


#ifdef __cplusplus
}
#endif

linklist.c

代码语言：javascript复制

#include"LinkList.h"

//链表节点数据类型
struct LinkNode
{
	void *data;
	struct LinkNode *next;
};

//链表数据类型
struct LList
{
	struct LinkNode header;
	int size;
};



//初始化链表
LinkList Init_LinkList()
{
	struct LList *list = malloc(sizeof(struct LList));
	if (NULL == list)
	{
		return NULL;
	}

	list->header.data = NULL;
	list->header.next = NULL;
	list->size = 0;

	return list;
}
//插入节点
void Insert_LinkList(LinkList list, int pos, void *data)
{
	
	if (NULL == list)
	{
		return;
	}

	if (NULL == data)
	{
		return;
	}

	struct LList * mylist = (struct LList *)list;

	if (pos < 0 || pos > mylist->size)
	{
		pos = mylist->size;
	}

	//查找插入位置
	struct LinkNode *pCurrent = &(mylist->header);
	for (int i = 0; i < pos;   i)
	{
		pCurrent = pCurrent->next;
	}

	//创建新节点
	struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
	newnode->data = data;
	newnode->next = NULL;

	//新节点插入到链表中
	newnode->next = pCurrent->next;
	pCurrent->next = newnode;

	mylist->size  ;
}


//遍历链表
void Foreach_LinkList(LinkList list, FOREACH myforeach) /*回调函数*/
{

	if (NULL == list)
	{
		return;
	}

	if (NULL == myforeach)
	{
		return;
	}

	struct LList * mylist = (struct LList *)list;

	struct LinkNode *pCurrent = mylist->header.next;

	while (pCurrent != NULL)
	{
		myforeach(pCurrent->data);
		pCurrent = pCurrent->next;
	}

}


//按位置删除
void RemoveByPos_LinkList(LinkList list, int pos)
{

	if (NULL == list)
	{
		return;
	}

	struct LList *mylist = (struct LList *)list;

	if (pos < 0 || pos > mylist->size - 1)
	{
		return;
	}


	//找位置
	struct LinkNode *pCurrent = &(mylist->header);
	for (int i = 0; i < pos;   i)
	{
		pCurrent = pCurrent->next;
	}


	//先保存待删除结点
	struct LinkNode *pDel = pCurrent->next;
	//重新建立待删除结点的前驱和后继结点关系
	pCurrent->next = pDel->next;
	//释放删除节点内存
	free(pDel);
	pDel = NULL;

	mylist->size--;

}
//按值删除
void RemoveByVal_LinkList(LinkList list, void *data, COMPARE compare)
{

	if (NULL == list)
	{
		return;
	}

	if (NULL == data)
	{
		return;
	}

	if (NULL == compare)
	{
		return;
	}

	struct LList *mylist = (struct LList *)list;

	//辅助指针变量
	struct LinkNode *pPrev = &(mylist->header);
	struct LinkNode *pCurrent = pPrev->next;

	while (pCurrent != NULL)
	{
		if (compare(pCurrent->data, data))
		{
			//找到了
			pPrev->next = pCurrent->next;
			//释放删除节点内存
			free(pCurrent);
			pCurrent = NULL;
			mylist->size--;
			break;
		}

		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}

}
//清空链表
void Clear_LinkList(LinkList list)
{
	if (NULL == list)
	{
		return;
	}

	struct LList *mylist = (struct LList *)list;

	//辅助指针变量
	struct LinkNode *pCurrent = mylist->header.next;

	while (pCurrent != NULL)
	{
		//先缓存下一个节点的地址
		struct LinkNode *pNext = pCurrent->next;
		//释放当前结点内存
		free(pCurrent);

		pCurrent = pNext;

	}

	mylist->header.next = NULL;
	mylist->size = 0;

}
//大小
int Size_LinkList(LinkList list)
{
	if (NULL == list)
	{
		return -1;
	}

	struct LList *mylist = (struct LList *)list;

	return mylist->size;
}
//销毁链表
void Destroy_LinkList(LinkList list)
{

	if (NULL == list)
	{
		return;
	}

	//清空链表
	Clear_LinkList(list);
	free(list);
	list = NULL;
}

main.c

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#include"LinkList.h"

struct Person
{

	char name[64];
	int age;
};

void myPrint(void *data)
{
	struct Person *person = (struct Person *)data;
	printf("Name:%s Age:%dn",person->name,person->age);
}

int myComapre(void *d1,void *d2)
{
	struct Person *p1 = (struct Person *)d1;
	struct Person *p2 = (struct Person *)d2;

#if 0
	if (strcmp(p1->name,p2->name) == 0 && p1->age == p2->age)
	{
		return 1;
	}

	return 0;
#endif

	return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;

}

void test()
{
	//创建链表
	LinkList list = Init_LinkList();

	//创建数据
	struct Person p1 = { "aaa", 10 };
	struct Person p2 = { "bbb", 20 };
	struct Person p3 = { "ccc", 30 };
	struct Person p4 = { "ddd", 40 };
	struct Person p5 = { "eee", 50 };
	struct Person p6 = { "fff", 60 };
	struct Person p7 = { "ggg", 70 };


	//插入数据
	Insert_LinkList(list, 0, &p1);
	Insert_LinkList(list, 0, &p2); //2 3 1
	Insert_LinkList(list, 1, &p3);
	Insert_LinkList(list, 2, &p4); //2 3 4 1
	Insert_LinkList(list, 20, &p5); //2 3 4 1 5
	Insert_LinkList(list, 3, &p6); //2 3 4 6 1 5
	Insert_LinkList(list, 6, &p7); //2 3 4 6 1 5 7

	Foreach_LinkList(list, myPrint);

	printf("----------------------n");
	printf("List Size:%dn", Size_LinkList(list));
	RemoveByPos_LinkList(list, 3);
	printf("----------------------n");
	Foreach_LinkList(list, myPrint);


	struct Person pDelPerson = { "ggg", 70 };
	RemoveByVal_LinkList(list, &pDelPerson, myComapre);
	printf("----------------------n");
	Foreach_LinkList(list, myPrint);

	//清空链表
	Clear_LinkList(list);
	printf("----------------------n");
	printf("List Size:%dn", Size_LinkList(list));

	//销毁链表
	Destroy_LinkList(list);
}

int main(){
	test();
	system("pause");
	return EXIT_SUCCESS;
}

SeqStack

顺序链表就是通过数组的方式实现的链表结构。

SeqStack.h

代码语言：javascript复制

#pragma once

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

#ifdef __cplusplus
extern "C"{
#endif

#define MAX 1024
typedef void * SeqStack;

	struct SStack
	{
		void *data[MAX];   // 存放栈元素
		int size;          // 栈中元素个数
	};
	SeqStack Init_SeqStack();
	void Push_SeqStack(SeqStack stack, void *data);
	void Pop_SeqStack(SeqStack stack);
	void *Top_SeqStack(SeqStack stack);
	int Size_SeqStack(SeqStack stack);
	void Destroy_SeqStack(SeqStack stack);
#ifdef __cplusplus
}
#endif

SeqStack.c

代码语言：javascript复制

#include "SeqStack.h"

// 初始化一个顺序栈
SeqStack Init_SeqStack()
{
	struct SStack *stack = malloc(sizeof(struct SStack));
	// 如果stack指针不为空,则将栈初始化一下
	if (stack != NULL)
	{
		stack->size = 0;
		for (int i = 0; i < MAX;   i)
		{
			stack->data[i] = NULL;
		}
	}
	return stack;
}

// 入栈
void Push_SeqStack(SeqStack stack, void *data)
{
	if (stack == NULL || data == NULL)
	{
		return;
	}

	struct SStack *s = (struct SStack *)stack;
	if (s->size == MAX)
	{
		return;
	}
	s->data[s->size] = data;
	s->size  ;
}

//出栈
void Pop_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return;
	}

	struct SStack *s = (struct SStack *)stack;

	if (s->size == 0)
	{
		return;
	}
	s->data[s->size - 1] = NULL;
	s->size--;
}

//获得栈顶元素
void *Top_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return NULL;
	}

	struct SStack *s = (struct SStack *)stack;
	if (s->size == 0)
	{
		return NULL;
	}
	return s->data[s->size - 1];
}

//获得栈的大小
int Size_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return -1;
	}
	struct SStack *s = (struct SStack *)stack;
	return s->size;
}

//销毁栈
void Destroy_SeqStack(SeqStack stack)
{
	if (NULL != stack)
	{
		free(stack);
	}
	return;
}

main.c

代码语言：javascript复制

#include "SeqStack.h"

struct Student
{
	int uid;
	char name[64];
};


int main(int argc,char *argv[])
{
	// 初始化栈,默认分配空间为1024
	SeqStack stack = Init_SeqStack();

	// 穿件一些测试数据
	struct Student stu1 = { 1001, "admin" };
	struct Student stu2 = { 1002, "guest" };
	struct Student stu3 = { 1003, "lyshark" };

	// 将输入加入到栈中
	Push_SeqStack(stack, &stu1);
	Push_SeqStack(stack, &stu2);
	Push_SeqStack(stack, &stu3);

	// 循环输出栈顶元素
	while (Size_SeqStack(stack) > 0)
	{
		// 获得栈顶元素
		struct Student *ptr = (struct Student *)Top_SeqStack(stack);
		printf("Uid: %d --> Name: %s n", ptr->uid, ptr->name);
		printf("当前栈大小: %d n", Size_SeqStack(stack));
		Pop_SeqStack(stack);
	}

	// 销毁栈
	Destroy_SeqStack(stack);
	stack = NULL;

	system("pause");
	return 0;
}

LinkStack

通过使用链表的方式实现的栈。

LinkStack.h

代码语言：javascript复制

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct StackNode
{
	struct StackNode *next;
};
struct LStack
{
	struct StackNode header;
	int size;
};

typedef void* LinkStack;

#ifdef __cplusplus
extern "C"{
#endif	
	LinkStack Init_LinkStack();
	void Push_LinkStack(LinkStack stack, void *data);
	void Pop_LinkStack(LinkStack stack);
	void* Top_LinkStack(LinkStack stack);
	int Size_LinkStack(LinkStack stack);
	void Destroy_LinkStack(LinkStack stack);
#ifdef __cplusplus
}
#endif

LinkStack.c

代码语言：javascript复制

#include"LinkStack.h"

// 初始化
LinkStack Init_LinkStack()
{
	struct LStack *stack = malloc(sizeof(struct LStack));
	if (NULL == stack)
	{
		return NULL;
	}

	stack->header.next = NULL;
	stack->size = 0;
	return stack;
}

// 入栈
void Push_LinkStack(LinkStack stack, void *data)
{
	if (NULL == stack || NULL == data)
	{
		return;
	}

	// 先将头指针进行强转
	struct LStack *ls = (struct LStack *)stack;
	// 把节点进行强转
	struct StackNode *node = (struct StackNode *)data;

	node->next = ls->header.next;
	ls->header.next = node;
	  (ls->size);
}

// 出栈
void Pop_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return;
	}

	struct LStack *ls = (struct LStack *)stack;

	if (ls->size == 0)
	{
		return;
	}

	//缓存第一个节点
	struct StackNode *pFirst = ls->header.next;
	ls->header.next = pFirst->next;
	ls->size--;
}

// 获得栈顶元素
void* Top_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return NULL;
	}

	struct LStack *ls = (struct LStack *)stack;
	if (ls->size == 0)
	{
		return NULL;
	}

	return ls->header.next;
}

// 获得大小
int Size_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return -1;
	}
	struct LStack *ls = (struct LStack *)stack;
	return ls->size;
}

// 销毁栈
void Destroy_LinkStack(LinkStack stack)
{
	if (NULL != stack)
	{
		free(stack);
		stack = NULL;
	}
	return;
}

main.c

代码语言：javascript复制

#include "LinkStack.h"

struct Student
{
	int uid;
	char name[64];
};

int main(int argc,char *argv[])
{
	// 初始化栈,默认分配空间为1024
	LinkStack stack = Init_LinkStack();

	// 穿件一些测试数据
	struct Student stu1 = { 1001, "admin" };
	struct Student stu2 = { 1002, "guest" };
	struct Student stu3 = { 1003, "lyshark" };

	// 将输入加入到栈中
	Push_LinkStack(stack, &stu1);
	Push_LinkStack(stack, &stu2);
	Push_LinkStack(stack, &stu3);

	// 循环输出栈顶元素
	while (Size_LinkStack(stack) > 0)
	{
		// 获得栈顶元素
		struct Student *ptr = (struct Student *)Top_LinkStack(stack);
		printf("Uid: %d --> Name: %s n", ptr->uid, ptr->name);
		printf("当前栈大小: %d n", Size_LinkStack(stack));
		Pop_LinkStack(stack);
	}

	// 销毁栈
	Destroy_LinkStack(stack);
	stack = NULL;

	system("pause");
	return 0;
}

LinkQueue

LinkQueue.h

代码语言：javascript复制

#pragma once

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

struct BiNode
{
	int data;
	struct BiNode *lchild;
	struct BiNode *rchild;
};

//链表结点的数据类型
struct QueueNode
{
	struct QueueNode *next;
};

//链表数据类型
struct LQueue
{
	struct QueueNode header; //头结点
	struct QueueNode *rear; //尾指针
	int size;
};

typedef void* LinkQueue;

#ifdef __cplusplus
extern "C"{
#endif

	//初始化
	LinkQueue Init_LinkQueue();
	//入队
	void Push_LinkQueue(LinkQueue queue, void *data);
	//出队
	void Pop_LinkQueue(LinkQueue queue);
	//获得队头元素
	void* Front_LinkQueue(LinkQueue queue);
	//获得队尾元素
	void* Back_LinkQueue(LinkQueue queue);
	//大小
	int Size_LinkQueue(LinkQueue queue);
	//销毁队列
	void Destroy_LinkQueue(LinkQueue queue);

#ifdef __cplusplus
}
#endif

LinkQueue.c

代码语言：javascript复制

#include"LinkQueue.h"

//初始化
LinkQueue Init_LinkQueue()
{
	struct LQueue *queue = malloc(sizeof(struct LQueue));
	if (NULL == queue)
	{
		return NULL;
	}

	queue->header.next = NULL;
	queue->size = 0;
	queue->rear = &(queue->header);
	return queue;
}

//入队
void Push_LinkQueue(LinkQueue queue, void *data)
{
	if (NULL == queue || NULL == data)
	{
		return;
	}
	
	struct LQueue *q = (struct LQueue *)queue;
	struct QueueNode *n = (struct QueueNode *)data;

	q->rear->next = n;
	n->next = NULL;
	//更新尾指针
	q->rear = n;
	q->size  ;
}

//出队
void Pop_LinkQueue(LinkQueue queue)
{
	if(NULL == queue)
	{
		return;
	}

	struct LQueue *q = (struct LQueue *)queue;
	
	if (q->size == 0)
	{
		return;
	}

	if (q->size == 1)
	{

		q->header.next = NULL;
		q->rear = &(q->header);
		q->size--;

		return;
	}

	struct QueueNode *pFirstNode = q->header.next;
	q->header.next = pFirstNode->next;
	q->size--;
}

//获得队头元素
void* Front_LinkQueue(LinkQueue queue)
{
	if (NULL == queue)
	{
		return NULL;
	}

	struct LQueue *q = (struct LQueue *)queue;
	return q->header.next;
}

//获得队尾元素
void* Back_LinkQueue(LinkQueue queue)
{
	if (NULL == queue)
	{
		return NULL;
	}

	struct LQueue *q = (struct LQueue *)queue;
	return q->rear;
}

//大小
int Size_LinkQueue(LinkQueue queue)
{
	if (NULL == queue)
	{
		return -1;
	}

	struct LQueue *q = (struct LQueue *)queue;
	return q->size;
}

//销毁队列
void Destroy_LinkQueue(LinkQueue queue)
{
	if (NULL == queue)
	{
		return;
	}
	
	struct LQueue *q = (struct LQueue *)queue;
	q->header.next = NULL;
	q->rear = NULL;
	q->size = 0;
	
	free(queue);
	queue = NULL;
}

main.c

代码语言：javascript复制

#include"LinkQueue.h"

struct Person
{
	struct QueueNode node;
	char name[64];
	int age;
};

int main(){

	//初始化队列
	LinkQueue queue = Init_LinkQueue();

	//创建数据
	struct Person p1 = { NULL, "aaa", 10 };
	struct Person p2 = { NULL, "bbb", 20 };
	struct Person p3 = { NULL, "ccc", 30 };
	struct Person p4 = { NULL, "ddd", 40 };
	struct Person p5 = { NULL, "eee", 50 };
	struct Person p6 = { NULL, "fff", 60 };

	//插入队列
	Push_LinkQueue(queue, &p1);
	Push_LinkQueue(queue, &p2);
	Push_LinkQueue(queue, &p3);
	Push_LinkQueue(queue, &p4);
	Push_LinkQueue(queue, &p5);
	Push_LinkQueue(queue, &p6);

	struct Person *pBack = (struct Person *)Back_LinkQueue(queue);
	printf("队尾元素:%s %dn",pBack->name,pBack->age);

	while(Size_LinkQueue(queue) > 0)
	{
		//获得队头元素
		struct Person *person = (struct Person *)Front_LinkQueue(queue);
		//打印队头元素
		printf("Name:%s Age:%dn", person->name,person->age);
		//弹出队头元素
		Pop_LinkQueue(queue);
	}
	//销毁队列
	Destroy_LinkQueue(queue);

	system("pause");
	return EXIT_SUCCESS;
}

二叉树知识点

二叉树，对每个节点的查看都是，先左后右

DLR - 先序遍历，先访问根，再左，最后右 LDR - 中序遍历 ，先左，再根，再右 LRD - 后序遍历，先左，再右，再根

二叉树递归遍历

代码语言：javascript复制

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

struct BiNode
{
	char ch;
	struct BiNode *lchild;
	struct BiNode *rchild;
};

//二叉树递归遍历
void recursion(struct BiNode *root)
{
	if (NULL == root)
	{
		return;
	}

	//递归遍历左子树
	recursion(root->lchild);
	//递归遍历右子树
	recursion(root->rchild);
	printf("%c ", root->ch);

}

int main()
{
	struct BiNode nodeA = { 'A', NULL, NULL };
	struct BiNode nodeB = { 'B', NULL, NULL };
	struct BiNode nodeC = { 'C', NULL, NULL };
	struct BiNode nodeD = { 'D', NULL, NULL };
	struct BiNode nodeE = { 'E', NULL, NULL };
	struct BiNode nodeF = { 'F', NULL, NULL };
	struct BiNode nodeG = { 'G', NULL, NULL };
	struct BiNode nodeH = { 'H', NULL, NULL };

	nodeA.lchild = &nodeB;
	nodeA.rchild = &nodeF;
	nodeB.rchild = &nodeC;
	nodeC.lchild = &nodeD;
	nodeC.rchild = &nodeE;
	nodeF.rchild = &nodeG;
	nodeG.lchild = &nodeH;
	recursion(&nodeA);
	
	system("pause");
	return EXIT_SUCCESS;
}

求叶子的高度宽度：

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>


struct BiNode
{
	char ch;
	struct BiNode *lchild;
	struct BiNode *rchild;
};

//int num = 0;

void cuculateLeafNum(struct BiNode *root,int *p)
{
	if (NULL == root)
	{
		return;
	}

	if (root->lchild == NULL && root->rchild == NULL)
	{
		(*p)  ;
	}


	cuculateLeafNum(root->lchild, p);
	cuculateLeafNum(root->rchild, p);
}


int getTreeHeight(struct BiNode *root)
{
	if (NULL == root)
	{
		return 0;
	}


	//求树的左子树高度
	int lheight = getTreeHeight(root->lchild);
	//求树的右子树高度
	int rheight = getTreeHeight(root->rchild);

	int height = lheight > rheight ? lheight   1 : rheight   1;

	return height;
}


void showBiTree(struct BiNode *root)
{
	if (NULL == root)
	{
		return;
	}

	printf("%c ",root->ch);
	showBiTree(root->lchild);
	showBiTree(root->rchild);
}


struct BiNode *copyBiTree(struct BiNode *root)
{
	if (NULL == root)
	{
		return NULL;
	}

	//先拷贝左子树
	struct BiNode *lchild = copyBiTree(root->lchild);
	//拷贝右子树
	struct BiNode *rchild = copyBiTree(root->rchild);


	struct BiNode *newnode = malloc(sizeof(struct BiNode));
	newnode->lchild = lchild;
	newnode->rchild = rchild;
	newnode->ch = root->ch;

	return newnode;
}

void freeSpace(struct BiNode *root)
{
	if (NULL == root)
	{
		return;
	}

	//释放左子数内存
	freeSpace(root->lchild);
	//释放右子树
	freeSpace(root->rchild);

	printf("%c 被释放!n", root->ch);
	free(root);
}

int main(){

		struct BiNode nodeA = { 'A', NULL, NULL };
	struct BiNode nodeB = { 'B', NULL, NULL };
	struct BiNode nodeC = { 'C', NULL, NULL };
	struct BiNode nodeD = { 'D', NULL, NULL };
	struct BiNode nodeE = { 'E', NULL, NULL };
	struct BiNode nodeF = { 'F', NULL, NULL };
	struct BiNode nodeG = { 'G', NULL, NULL };
	struct BiNode nodeH = { 'H', NULL, NULL };

	nodeA.lchild = &nodeB;
	nodeA.rchild = &nodeF;
	nodeB.rchild = &nodeC;
	nodeC.lchild = &nodeD;
	nodeC.rchild = &nodeE;
	nodeF.rchild = &nodeG;
	nodeG.lchild = &nodeH;

	//1. 求二叉树的叶子节点数目
	int num = 0;
	cuculateLeafNum(&nodeA, &num);
	printf("叶子节点数目:%dn", num);

	//2. 求二叉树的高度
	int height = getTreeHeight(&nodeA);
	printf("树的高度:%dn",height);

	//3. 拷贝二叉树
	struct BiNode *root = copyBiTree(&nodeA);
	showBiTree(root);
	printf("n");
	showBiTree(&nodeA);

	freeSpace(root);

	system("pause");
	return EXIT_SUCCESS;
}

通过栈实现的二叉树

代码语言：javascript复制

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include"SeqStack.h"

struct BiNode
{
	char ch;
	struct BiNode *lchild;
	struct BiNode *rchild;
};

struct Info
{
	struct BiNode *node;
	bool flag;
};

struct Info* createInfo(struct BiNode *node, bool flag)
{
	struct Info *info = malloc(sizeof(struct Info));
	info->flag = flag;
	info->node = node;

	return info;
}

void nonRecursion(struct BiNode *root)
{

	//初始化栈
	SeqStack stack = Init_SeqStack();
	//先把根节点压入栈中
	Push_SeqStack(stack, createInfo(root, false));

	while (Size_SeqStack(stack) > 0)
	{
		//获得栈顶元素	
		struct Info *info = (struct Info *)Top_SeqStack(stack);
		//弹出栈顶元素
		Pop_SeqStack(stack);


		if (info->flag)
		{
			printf("%c ",info->node->ch);
			free(info);
			continue;
		}

		//将根节压入栈中
		info->flag = true;
		Push_SeqStack(stack, info);

		//将右子树压入栈中
		if (info->node->rchild != NULL)
		{
			Push_SeqStack(stack, createInfo(info->node->rchild, false));
		}

		//将左子树压入栈中
		if (info->node->lchild != NULL)
		{
			Push_SeqStack(stack, createInfo(info->node->lchild, false));
		}
	}

	//销毁栈
	Destroy_SeqStack(stack);
}

int main(){

	struct BiNode nodeA = { 'A', NULL, NULL };
	struct BiNode nodeB = { 'B', NULL, NULL };
	struct BiNode nodeC = { 'C', NULL, NULL };
	struct BiNode nodeD = { 'D', NULL, NULL };
	struct BiNode nodeE = { 'E', NULL, NULL };
	struct BiNode nodeF = { 'F', NULL, NULL };
	struct BiNode nodeG = { 'G', NULL, NULL };
	struct BiNode nodeH = { 'H', NULL, NULL };

	nodeA.lchild = &nodeB;
	nodeA.rchild = &nodeF;
	nodeB.rchild = &nodeC;
	nodeC.lchild = &nodeD;
	nodeC.rchild = &nodeE;
	nodeF.rchild = &nodeG;
	nodeG.lchild = &nodeH;

	nonRecursion(&nodeA);
	system("pause");
	return EXIT_SUCCESS;
}

二叉树 编程算法

0 人点赞