数据结构

前言

由于数据结构上课的的确确听的还认真，(的确，但凡C语言指针没有忘，上课就跟玩一样)但是呢…代码是一点都没有碰(哪怕是有上机作业呢：)，加之想复习一下关于C/C++的代码以及代码的调试功能，于是开始了我的数据结构赎罪之路。

visual studio常见报错

• 使用了可能未初始化的本地指针变量“xxx

项目属性->配置属性->C/C++->SDL检查，选测是或者否。

线性表

带头结点的单链表

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

//定义类型
typedef struct List
{
	double element;
	List* next;
}List;

//初始化
List* ListInit()
{
	List* head;
	head = (List*)malloc(sizeof(List));
	if (head == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	head->next = NULL;
	head->element = NULL;

	return head;
};

//输入数据
void CreatList(List* head)
{
	int choice = 1;
	List* p, * last;

	last = head;
	while (last->next != NULL)	//找最后一个元素位置；
	{
		last = last->next;
	}

	while (choice == 1)
	{
		p = (List*)malloc(sizeof(List));
		if (p == NULL)
		{
			printf("开辟空间失败\n");
			exit(0);
		}
		printf("元素：");
		scanf_s("%lf", &(p->element));
		p->next = NULL;
		last->next = p;
		last = p;
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//判断空链表		1-非空	0-空
int EmptyList(List* head)
{
	if (head->next != NULL)
	{
		return 1;
	}
	return 0;
}

//输出链表
void OutputList(List* head)
{
	if (EmptyList(head) == 0)
	{
		printf("链表为空\n");
	}
	else
	{
		List* p;
		p = head->next;
		while (p != NULL)
		{
			printf("%lf", p->element);
			if (p->next != NULL)
			{
				printf(" -> ");
			}
			p = p->next;
		}
		printf("\n");
	}
}

//链表长度	空表为0
int LongList(List* head)
{
	int longlist = 0;
	List* p;
	p = head->next;
	while (p != NULL)
	{
		p = p->next;
		longlist++;
	}
	return longlist;
}

//返回值为a的首个节点的位置
int FindElement(List* head, double a)
{
	List* p;
	p = head->next;
	int order = 1;
	while (p != NULL)
	{
		if (p->element == a)
		{
			printf("%lf 存在于第 %d 个节点里\n", p->element, order);
			break;
		}
		else
		{
			p = p->next;
			order++;
		}
	}
	if (order > LongList(head))
	{
		order = -1;
		printf("不存在值为%lf的节点\n", a);
	}
	return order;
}

//删除值为a的首个节点
void DeleteElement(List* head, double a)
{
	List* p, * q;
	p = head;
	int mark = 0;
	while (p->next != NULL)
	{
		if (p->next->element == a)
		{
			q = p->next;
			p->next = q->next;
			free(q);
			mark = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	if (mark == 1)
	{
		printf("%lf 已被删除\n", a);
	}
	else
	{
		printf("无法找到元素 %lf\n", a);
	}
}

//清空链表
void ClearList(List* head)
{
	List* q, * p;
	q = head->next;
	while (q != NULL)
	{
		p = q;
		q = q->next;
		p->next = NULL;
		free(p);
	}
	head->next = NULL;
	printf("链表已被删除\n");
}

//删除第i个节点
void DeleteThElement(List* head, int order)
{
	int l = LongList(head);
	if (order < 1 || l < order)
	{
		printf("不存在序号为%d的节点\n", l);
	}
	else
	{
		List* p, * q;
		p = head;
		int mark = 0;
		while (p->next != NULL)
		{
			if (mark == order - 1)
			{
				q = p->next;
				p->next = q->next;
				free(q);
				printf("第%d个节点已被删除\n", order);
				break;
			}
			else
			{
				p = p->next;
				mark++;
			}
		}
	}
}

//在第i个位置插入数据
void InsertList(List* head, int order, double data)
{
	if (order < 0)
	{
		printf("不存在负序号的元素\n");
	}
	else if (int l = LongList(head) < order)
	{
		printf("不存在序号为 %d 的元素\n", order);
	}
	else
	{
		List* p, * q;
		q = (List*)malloc(sizeof(List));
		if (q == NULL)
		{
			printf("开辟空间失败\n");
			exit(0);
		}
		q->element = data;

		int mark = 0;
		p = head;
		while (mark != order)
		{
			mark++;
			p = p->next;
		}
		q->next = p->next;
		p->next = q;
	}
}

//返回第i个位置的元素值
double FindThElement(List* head, int order)
{
	if (int l = LongList(head) < order || order < 1)
	{
		printf("不存在序号为%d的元素\n", order);
		return -9999;
	}
	else
	{
		List* p;
		int mark = 0;
		p = head;
		while (mark != order)
		{
			p = p->next;
			mark++;
		}
		return p->element;
	}
}

//交换两个元素的位置
void SwapElememt(List* head, int order1, int order2)
{
	int l = LongList(head);
	if (order1 < 1 || order2 < 1)
	{
		printf("不存在非正序号的元素\n");
	}
	else if (order1 > l || order2 > l)
	{
		printf("不存在序号超过 %d 的元素\n", l);
	}
	else
	{
		int min = order2, max = order1, mark = 0;
		double t;
		if (order1 < order2)
		{
			min = order1;
			max = order2;
		}
		List* p, * q;
		q = head;
		while (mark != min)
		{
			mark++;
			q = q->next;
		}
		p = q;
		while (mark != max)
		{
			mark++;
			q = q->next;
		}
		t = p->element;
		p->element = q->element;
		q->element = t;
	}
}

//前者比后者大
int greater(double a, double b)
{
	if (a > b)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

//前者比后者小
int smaller(double a, double b)
{
	if (a > b)
	{
		return -1;
	}
	else
	{
		return 1;
	}
}

//找最大或最小的元素位置
int FindBig_Small(List* head, int (*compare)(double, double))
{
	if (EmptyList(head) == 0)
	{
		printf("空链表无最大元素\n");
		return 0;
	}
	else
	{
		List* p, * q;
		int mark = 1, flag = 1;
		p = head->next;
		double big_small;
		big_small = p->element;
		while (p->next != NULL)
		{
			p = p->next;
			flag++;
			if (compare(p->element, big_small) > 0)
			{
				big_small = p->element;
				mark = flag;
			}
		}
		return mark;
	}
}

//判断链表是否递增或递减	递增\递减 - 1	相反 - 0
int In_DecrementList(List* head, int (*compare)(double, double))
{
	int flag = 1;
	List* p;
	p = head->next;
	while (p != NULL)
	{
		if (p->next != NULL && compare(p->element, p->next->element) > 0)
		{
			flag = 0;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	return flag;
}

//排序	
void SortList(List* head, int (*compare)(double, double))
{
	List* p;
	p = ListInit();
	int order = 0;
	int flag;
	while (EmptyList(head) == 1)
	{
		flag = FindBig_Small(head, compare);
		InsertList(p, order, FindThElement(head, flag));
		order++;
		DeleteThElement(head, flag);
	}
	head->next = p->next;
	p->next = NULL;
	free(p);
}

//链表逆置
void ConverseList(List* head)
{
	List* p, * q;
	p = head->next;
	q = ListInit();
	while (p != NULL)
	{
		head->next = head->next->next;
		p->next = q->next;
		q->next = p;
		p = head->next;
	}
	head->next = q->next;
	free(q);
}

//合并两个链表
List* MergeList(List* La, List* Lb, int (*compare)(double, double))
{
	SortList(La, compare);
	SortList(Lb, compare);
	List* p, * q, * t;
	p = La;
	q = Lb->next;
	while (q != NULL)
	{
		while (compare(q->element, p->next->element) < 0 && p->next != NULL)
		{
			p = p->next;
		}
		t = q;
		q = q->next;
		t->next = p->next;
		p->next = t;
	}
	Lb->next = NULL;
	ClearList(Lb);
	free(Lb);
	return La;
}

//链表功能
void FunctionList(List* head)
{
	int choice = 1;
	double data;
	int order, order1;
	while (choice != 0)
	{
		printf("链表为：\n");
		OutputList(head);

		printf("输入想实现的功能：\n");
		printf("1 - 输出链表的长度\n");
		printf("2 - 返回值为a的首个节点的位置\n");
		printf("3 - 删除值为a的首个节点\n");
		printf("4 - 删除第i个节点\n");
		printf("5 - 在第i个位置插入数据\n");
		printf("6 - 返回第i个位置的元素值\n");
		printf("7 - 交换链表第n个节点与第m个节点的位置\n");
		printf("8 - 寻找链表最大或最小的元素的位置\n");
		printf("9 - 链表从大到小排序\n");
		printf("10 - 链表从小到大排序\n");
		printf("11 - 链表逆置\n");
		printf("12 - 从大到小合并两个链表\n");
		printf("13 - 从小到大合并两个链表\n");
		printf("其他 - 退出\n");

		printf("选择：");
		scanf_s("%d", &choice);

		if (choice == 1)
		{
			printf("链表的长度为：%d\n", LongList(head));
		}
		else if (choice == 2)
		{
			printf("查找的值为：");
			scanf_s("%lf", &data);
			printf("%lf 的位置为 %d\n", data, FindElement(head, data));
		}
		else if (choice == 3)
		{
			printf("删除的值为：");
			scanf_s("%lf", &data);
			DeleteElement(head, data);
		}
		else if (choice == 4)
		{
			printf("删除的位置为：");
			scanf_s("%d", &order);
			DeleteThElement(head, order);
		}
		else if (choice == 5)
		{
			printf("插入的位置为：");
			scanf_s("%d", &order);
			printf("插入的元素为：");
			scanf_s("%lf", &data);
			InsertList(head, order, data);
		}
		else if (choice == 6)
		{
			printf("查找的位置为：");
			scanf_s("%d", &order);
			printf("链表第 %d 个的值为 %lf \n", order, FindThElement(head, order));
		}
		else if (choice == 7)
		{
			printf("交换节点的位置为：");
			scanf_s("%d", &order);
			scanf_s("%d", &order1);
			SwapElememt(head, order, order1);
		}
		else if (choice == 8)
		{
			printf("最大元素的位置为：%d\n", FindBig_Small(head, greater));
			printf("最小元素的位置为：%d\n", FindBig_Small(head, smaller));
		}
		else if (choice == 9)
		{
			SortList(head, greater);
		}
		else if (choice == 10)
		{
			SortList(head, smaller);
		}
		else if (choice == 11)
		{
			ConverseList(head);
			printf("链表已逆置\n");
		}
		else if (choice == 12)
		{
			printf("创建需要合并的链表\n");
			List* L;
			L = ListInit();
			CreatList(L);
			head = MergeList(head, L, greater);
			printf("链表已合并\n");
		}
		else if (choice == 13)
		{
			printf("创建需要合并的链表\n");
			List* L;
			L = ListInit();
			CreatList(L);
			head = MergeList(head, L, smaller);
			printf("链表已合并\n");
		}
		else
		{
			break;
			printf("退出\n");
		}
	}
}

int main()
{
	List* head;
	head = ListInit();
	CreatList(head);
	FunctionList(head);
	free(head);

	return 0;
}

带头节点的双链表

#include <stdio.h>
#include <stdlib.h>
using namespace std;

//定义类型
typedef struct List
{
	double element;
	List* next;
	List* before;
}List;

//初始化
List* ListInit()
{
	List* head;
	head = (List*)malloc(sizeof(List));
	if (head == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	head->next = NULL;
	head->before = NULL;
	head->element = NULL;
	return head;
};

//输入数据
void CreatList(List* head)
{
	int choice = 1;
	List* p, * last;
	last = head;
	while (last->next != NULL)
	{
		last = last->next;
	}

	while (choice == 1)
	{
		p = (List*)malloc(sizeof(List));
		if (p == NULL)
		{
			printf("开辟空间失败\n");
			exit(0);
		}
		printf("元素为：");
		scanf_s("%lf", &(p->element));
		p->before = last;
		p->next = NULL;
		last->next = p;
		last = p;
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//判断空链表		1-非空	0-空
int EmptyList(List* head)
{
	if (head->next != NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//链表长度	无法输出空表的0
int LongList(List* head)
{
	int longlist = 0;
	List* p;
	p = head->next;
	while (p != NULL)
	{
		p = p->next;
		longlist++;
	}
	return longlist;
}

//输出链表
void OutputList(List* head)
{
	if (EmptyList(head) == 0)
	{
		printf("链表为空\n");
	}
	else
	{
		List* p;
		p = head->next;
		printf("从前往后输出：");
		while (p != NULL)
		{
			printf("%lf", p->element);
			if (p->next != NULL)
			{
				printf(" <--> ");
			}
			p = p->next;
		}
	}
}

//从后向前输出链表
void BeOutputList(List* head)
{
	List* p;
	p = head->next;
	while (p->next != NULL)
	{
		p = p->next;
	}
	printf("\n从后往前输出");
	while (p != head)
	{
		printf("%lf", p->element);
		if (p->before != head)
		{
			printf(" <- ");
		}
		p = p->before;
	}
	printf("\n");
}

//清空链表
void ClearList(List* head)
{
	List* q;
	while (head->next != NULL)
	{
		q = head->next;
		head->next = q->next;
		q->next->before = head;
		free(q);
	}
	printf("链表已清空\n");
}

//删除第几个节点
void DeleteThElement(List* head, int order)
{
	if (order < 1 || order > LongList(head))
	{
		printf("不存在序号为%d的节点\n", order);
	}
	else
	{
		List* p, * q;
		p = head;
		int mark = 0;
		while (mark != order)
		{
			p = p->next;
			mark++;
		}
		p->next->before = p->before;
		p->before->next = p->next;
		free(p);
	}
}

//删除符合条件的第一个节点
void DeleteElement(List* head, double a)
{
	List* p, * q;
	p = head;
	int flag = 0;
	while (p->next != NULL)
	{
		if (p->next->element == a)
		{
			q = p->next;
			p->next = q->next;
			q->next->before = p;
			free(q);
			flag = 1;
			printf("%lf被删除\n", a);
			break;
		}
		else
		{
			p = p->next;
		}
	}
	if (flag == 0)
	{
		printf("无法找到%lf", a);
	}
}

//根据位置插入数据
void InsertList(List* head, int order, double data)
{
	if (order < 0 || order > LongList(head))
	{
		printf("不存在序号为%d的元素", order);
	}
	else
	{
		List* p, * q;
		q = (List*)malloc(sizeof(List));
		if (q == NULL)
		{
			printf("开辟空间失败\n");
			exit(0);
		}
		q->element = data;
		q->next = NULL;
		q->before = NULL;

		int mark = 0;
		p = head;
		while (mark != order)
		{
			mark++;
			p = p->next;
		}

		q->next = p->next;
		q->before = p;
		if (p->next != NULL)
		{
			q->next->before = q;
		}
		p->next = q;
	}
}

int main()
{
	List* head;
	head = ListInit();
	CreatList(head);
	OutputList(head);
	BeOutputList(head);
	printf("链表长度%d\n", LongList(head));

	DeleteThElement(head, 2);
	OutputList(head);
	BeOutputList(head);

	DeleteElement(head, 1);
	OutputList(head);
	BeOutputList(head);

	InsertList(head, 1, 4);
	OutputList(head);
	BeOutputList(head);

	system("pause");
	return 0;
}

双向循环列表

#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef struct List
{
	double element;
	struct List* next;
	struct List* before;
}List;

//链表初始化
List* InitList()
{
	List* head;
	head = (List*)malloc(sizeof(struct List));
	if (head == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	head->before = head;
	head->next = head;
	head->element = NULL;
	return head;
}

//创建链表
void CreatList(List* head)
{
	int choice = 1;
	struct List* p, * last;
	while (choice == 1)
	{
		p = (List*)malloc(sizeof(struct List));
		if (p == NULL)
		{
			printf("开辟空间失败\n");
			exit(0);
		}
		printf("元素为：");
		scanf_s("%lf", &(p->element));
		if (head->next == head)		//第一个
		{
			head->next = p;
			head->before = p;
			p->before = head;
			p->next = head;
		}
		else
		{
			last->next = p;
			p->before = last;
			p->next = head;
			head->before = p;
		}
		last = p;
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//判断空链表		1-非空	0-空
int EmptyList(List* head)
{
	if (head->next != head)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//链表长度	无法输出空表的0
int LongList(List* head)
{
	int longlist = 0;
	List* p;
	p = head->next;
	while (p != head)
	{
		p = p->next;
		longlist++;
	}
	return longlist;
}

//输出链表
void OutputList(List* head)
{
	if (EmptyList(head) == 0)
	{
		printf("链表为空\n");
	}
	else
	{
		List* p;
		p = head->next;
		printf("从前往后输出：");
		while (p != head)
		{
			printf("%lf", p->element);
			if (p->next != head)
			{
				printf(" <--> ");
			}
			p = p->next;
		}
	}
}

//从后向前输出链表
void BeOutputList(List* head)
{
	List* p;
	p = head->before;
	printf("\n从后往前输出：");
	while (p != head)
	{
		printf("%lf", p->element);
		if (p->before != head)
		{
			printf(" <- ");
		}
		p = p->before;
	}
	printf("\n");
}

//清空链表
void ClearList(List* head)
{
	List* q;
	while (head->next != head)
	{
		q = head->next;
		head->next = q->next;
		q->next->before = head;
		free(q);
	}
	printf("链表已清空\n");
}

//将两个循环链表首尾相接	第二个表接在第一个表之后，且链接完成后删除第二个表头
List* MergeList(List* La, List* Lb)
{
	La->before->next = Lb->next;
	Lb->next->before = La->before;
	La->before = Lb->before;
	La->before->next = La;
	free(Lb);
	return La;
}

int main()
{
	List* head;
	head = InitList();
	CreatList(head);
	printf("%d\n", LongList(head));
	OutputList(head);
	BeOutputList(head);
	List* head2;
	head2 = InitList();
	CreatList(head2);
	head = MergeList(head, head2);
	OutputList(head);
	BeOutputList(head);

	system("pause");
	return 0;
}

堆栈

#include<stdio.h>
#include<stdlib.h>
#define stack_init_size 5

typedef struct Stack
{
	double* base;	//栈底指针
	double* top;	//栈顶指针，指向待插入元素
	int stacksize;	//当前分配的存储容量
}Stack;

//初始化栈
Stack* InitStack()
{
	Stack* s;
	s = (Stack*)malloc(sizeof(struct Stack));
	s->base = (double*)malloc(stack_init_size * sizeof(double));
	if (s->base == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	s->top = s->base;
	s->stacksize = stack_init_size;
	return s;
}

//空栈	1-非空	0-空
bool EmptyStack(Stack* s)
{
	if (s->base == s->top)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//栈的大小
int StackSize(Stack* s)
{
	/*
	double* p;
	int count = 0;
	p = s->top;
	while (s->base != p)
	{
		p--;
		count++;
	}
	return count;
	*/
	return s->top - s->base;
}

//满栈	1-栈满	0-栈非满
bool FullStack(Stack* s)
{
	if (StackSize(s) == s->stacksize)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//入栈
void Push(Stack* s, double a)
{
	if (FullStack(s) == 1)
	{
		printf("栈满，停止输入\n");
	}
	else
	{
		*s->top = a;
		s->top++;
	}
}

//创建栈
void CreatStack(Stack* s)
{
	double a;
	int choice = 1;
	while (choice == 1)
	{
		printf("输入: ");
		scanf_s("%lf", &a);
		Push(s, a);
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//出栈
double Pop(Stack* s)
{
	if (EmptyStack(s) == 0)
	{
		printf("栈空，返回-9999\n");
		return -9999;
	}
	else
	{
		s->top--;
		return *(s->top);
	}
}

//返回栈顶元素
double TopStack(Stack* s)
{
	if (EmptyStack(s) == 0)
	{
		printf("栈空，返回-9999\n");
		return -9999;
	}
	else
	{
		return *(s->top - 1);
	}
}

//遍历栈
void PrintStack(Stack* s)
{
	if (EmptyStack(s) == 0)
	{
		printf("栈空\n");
	}
	else
	{
		double* p;
		p = s->top;
		printf("===\n");
		while (p != s->base)
		{
			p--;
			printf("%lf ", *p);
		}
		printf("===\n");
	}

}

//清空栈
void ClearStack(Stack* s)
{
	free(s->base);
	free(s);
	printf("栈已被清空\n");
}

int main()
{
	Stack* s;
	s = InitStack();
	CreatStack(s);
	PrintStack(s);
	printf("返回栈顶元素: %lf\n", TopStack(s));
	ClearStack(s);
	PrintStack(s);
    
	system("pause");
	return 0;
}

链栈

#include<stdio.h>
#include<stdlib.h>
#define stack_init_size 5

typedef struct StackNode
{
	double element;
	StackNode* next;
}StackNode;

//初始化栈	创建top指针，指向栈顶
StackNode* InitStack()
{
	StackNode* top;
	top = (StackNode*)malloc(sizeof(StackNode));
	if (top == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	top->next = NULL;
	top->element = NULL;
	return top;
}

//空栈	1-非空	0-空
bool EmptyStack(StackNode* top)
{
	if (top->next == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//栈的大小
int StackSize(StackNode* top)
{
	StackNode* p;
	int count = 0;
	p = top->next;
	while (p != NULL)
	{
		p = p->next;
		count++;
	}
	return count;
}

//入栈	头插法
void Push(StackNode* top, double a)
{
	StackNode* p;
	p = (StackNode*)malloc(sizeof(StackNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->element = a;
	p->next = top->next;
	top->next = p;
}

//创建栈
void CreatStack(StackNode* top)
{
	double a;
	int choice = 1;
	while (choice == 1)
	{
		printf("输入: ");
		scanf_s("%lf", &a);
		Push(top, a);
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//出栈
double Pop(StackNode* top)
{
	if (EmptyStack(top) == 0)
	{
		printf("栈空，返回-9999\n");
		return -9999;
	}
	else
	{
		StackNode* p;
		double a;
		p = top->next;
		a = p->element;
		top->next = p->next;
		free(p);
		return a;
	}
}

//返回栈顶元素
double TopStack(StackNode* top)
{
	if (EmptyStack(top) == 0)
	{
		printf("栈空，返回-9999\n");
		return -9999;
	}
	else
	{
		return top->next->element;
	}
}

//遍历栈
void PrintStack(StackNode* top)
{
	if (EmptyStack(top) == 0)
	{
		printf("栈空\n");
	}
	else
	{
		StackNode* p;
		p = top->next;
		printf("===\n");
		while (p != NULL)
		{
			printf("%lf ", p->element);
			p = p->next;
		}
		printf("===\n");
	}

}

//清空栈
void ClearStack(StackNode* top)
{
	StackNode* p;
	while (top->next != NULL)
	{
		p = top->next;
		top->next = p->next;
		free(p);
	}
	printf("栈已被清空\n");
}

int main()
{
	StackNode* top;
	top = InitStack();
	CreatStack(top);
	PrintStack(top);
	printf("返回栈顶元素: %lf\n", TopStack(top));
	ClearStack(top);
	PrintStack(top);

	system("pause");
	return 0;
}

队列

#include<stdio.h>
#include<stdlib.h>
#define queue_init_size 5

typedef struct Queue
{
	double* front;	//队头
	double* rear;	//队尾
	int queuesize;	//最大队长
}Queue;

//初始化队列
Queue* InitQueue()
{
	Queue* q;
	q = (Queue*)malloc(sizeof(Queue));
	q->front = (double*)malloc(queue_init_size * sizeof(double));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->queuesize = queue_init_size;
	return q;
}

//空队	1-非空	0-空
bool EmptyQueue(Queue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//队的大小
int SizeQueue(Queue* q)
{
	return q->rear - q->front;
}

//满队	1-队满	0-队非满
bool FullQueue(Queue* q)
{
	if (SizeQueue(q) == queue_init_size)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//入队
void EnQueue(Queue* q, double a)
{
	if (FullQueue(q) == 1)
	{
		printf("队满，停止输入\n");
	}
	else
	{
		*(q->rear) = a;
		q->rear++;
	}
}

//创建队
void CreatQueue(Queue* q)
{
	double a;
	int choice = 1;
	while (choice == 1)
	{
		printf("输入: ");
		scanf_s("%lf", &a);
		EnQueue(q, a);
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//出队
double DeQueue(Queue* q)
{
	if (EmptyQueue(q) == 0)
	{
		printf("队空，返回-9999\n");
		return -9999;
	}
	else
	{
		double a;
		a = *(q->front);
		q->front++;
		return a;
	}
}

//返回队头元素
double GetHead(Queue* q)
{
	if (EmptyQueue(q) == 0)
	{
		printf("队空，返回-9999\n");
		return -9999;
	}
	else
	{
		return *(q->front);
	}
}

//遍历队
void PrintQueue(Queue* q)
{
	if (EmptyQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		double* p;
		p = q->front;
		printf("===\n");
		while (p != q->rear)
		{
			printf("%lf ", *p);
			p++;
		}
		printf("\n===\n");
	}
}

//清空队
void ClearQueue(Queue* q)
{
	free(q->front);
	free(q);
	printf("队已被清空\n");
}

int main()
{
	Queue* q;
	q = InitQueue();
	CreatQueue(q);
	PrintQueue(q);
	printf("%lf\n", DeQueue(q));
	printf("%lf\n", DeQueue(q));
	EnQueue(q, -1);
	EnQueue(q, -2);
	printf("返回队头元素: %lf\n", GetHead(q));
	PrintQueue(q);
	ClearQueue(q);

	system("pause");
	return 0;
}

循环队列

#include<stdio.h>
#include<stdlib.h>
#define queue_init_size 5

typedef struct SqQueue
{
	double* base;
	int front;	//队头
	int rear;	//队尾
	int maxsize;	//最大队长
	int squeuesize;	//队长
}SqQueue;

//初始化队列
SqQueue* InitSqQueue()
{
	SqQueue* q;
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->base = (double*)malloc(queue_init_size * sizeof(double));
	if (q->base == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front = 0;
	q->maxsize = queue_init_size;
	q->squeuesize = 0;
	return q;
}

//入队
void EnSqQueue(SqQueue* q, double a)
{
	if (q->squeuesize == q->maxsize)
	{
		printf("队满，停止输入\n");
	}
	else
	{
		q->base[q->rear] = a;
		q->rear = (q->rear + 1) % (q->maxsize);
		(q->squeuesize)++;
	}
}

//创建队
void CreatSqQueue(SqQueue* q)
{
	double a;
	int choice = 1;
	while (choice == 1)
	{
		printf("输入: ");
		scanf_s("%lf", &a);
		EnSqQueue(q, a);
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//出队
double DeSqQueue(SqQueue* q)
{
	if (q->squeuesize == 0)
	{
		printf("队空，返回-9999\n");
		return -9999;
	}
	else
	{
		double a;
		a = q->base[q->front];
		q->front = (q->front + 1) % (q->maxsize);
		(q->squeuesize)--;
		return a;
	}
}

//遍历队
void PrintSqQueue(SqQueue* q)
{
	if (q->squeuesize == 0)
	{
		printf("队空\n");
	}
	else
	{
		int p, count;
		p = q->front;
		count = 0;
		printf("===\n");
		while (count < q->squeuesize)
		{
			printf("%lf ", q->base[p]);
			p = (p + 1) % (q->maxsize);
			count++;
		}
		printf("\n===\n");
	}
}

//清空队
void ClearSqQueue(SqQueue* q)
{
	free(q->base);
	free(q);
	printf("队已被清空\n");
}

int main()
{
	SqQueue* q;
	q = InitSqQueue();
	CreatSqQueue(q);
	PrintSqQueue(q);
	printf("%lf\n", DeSqQueue(q));
	printf("%lf\n", DeSqQueue(q));
	EnSqQueue(q, -1);
	EnSqQueue(q, -2);
	PrintSqQueue(q);
	ClearSqQueue(q);

	system("pause");
	return 0;
}

链队列

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

typedef struct QueueNode {
	double element;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue {
	QueueNode* front;
	QueueNode* rear;
}LinkQueue;

//初始化队列
LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->element = NULL;
	return q;
}

//空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//队的大小
int SizeLinkQueue(LinkQueue* q)
{
	int size = 0;
	QueueNode* p;
	p = q->front->next;
	while (p != q->rear)
	{
		size++;
		p = p->next;
	}
	return size;
}

//入队
void EnLinkQueue(LinkQueue* q, double a)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->element = a;
	p->next = NULL;

	q->rear->next = p;
	q->rear = p;

}

//创建队
void CreatLinkQueue(LinkQueue* q)
{
	double a;
	int choice = 1;
	while (choice == 1)
	{
		printf("输入: ");
		scanf_s("%lf", &a);
		EnLinkQueue(q, a);
		printf("continue?1-0	");
		scanf_s("%d", &choice);
	}
}

//出队
double DeLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空，返回-9999\n");
		return -9999;
	}
	else
	{
		QueueNode* p;
		double a;
		p = q->front->next;
		a = p->element;
		q->front->next = p->next;
		if (q->rear == p)
		{
			q->rear = q->front;
		}
		free(p);
		return a;
	}
}

//遍历队
void PrintLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		QueueNode* p;
		p = q->front->next;
		printf("===\n");
		while (p != NULL)
		{
			printf("%lf ", p->element);
			p = p->next;
		}
		printf("\n===\n");
	}
}

//清空队
void ClearLinkQueue(LinkQueue* q)
{
	QueueNode* p, * t;
	p = q->front->next;
	while (p != q->rear)
	{
		t = p;
		p = p->next;
		free(t);
	}
	free(q->front);
	free(q);
	printf("队已被清空\n");
}


int main()
{
	LinkQueue* q;
	q = InitLinkQueue();
	CreatLinkQueue(q);
	PrintLinkQueue(q);
	printf("%lf\n", DeLinkQueue(q));
	printf("%lf\n", DeLinkQueue(q));
	EnLinkQueue(q, -1);
	EnLinkQueue(q, -2);
	PrintLinkQueue(q);
	ClearLinkQueue(q);

	system("pause");
	return 0;
}

树

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

typedef struct BTreeNode
{
	double element;		//节点元素
	BTreeNode* lchild;	//左孩子
	BTreeNode* rchild;	//右孩子
}BTreeNode;

//先序遍历
void Pre_Order(BTreeNode* t)
{
	if (t != NULL)
	{
		printf("%lf ", t->element);
		Pre_Order(t->lchild);
		Pre_Order(t->rchild);
	}
}

//中序遍历
void In_Order(BTreeNode* t)
{
	if (t != NULL)
	{
		In_Order(t->lchild);
		printf("%lf ", t->element);
		In_Order(t->rchild);
	}
}

//后序遍历
void Post_Order(BTreeNode* t)
{
	if (t != NULL)
	{
		Post_Order(t->lchild);
		Post_Order(t->rchild);
		printf("%lf ", t->element);
	}
}

//创建二叉树
BTreeNode* CreatBTree()
{
	BTreeNode* t;
	int choice;
	printf("continue?1-0	");
	scanf_s("%d", &choice);
	if (choice == 1)
	{
		t = (BTreeNode*)malloc(sizeof(BTreeNode));
		scanf_s("%lf", &(t->element));
		t->lchild = CreatBTree();
		t->rchild = CreatBTree();
		return t;
	}
	else
	{
		return NULL;
	}
}

//销毁二叉树
BTreeNode* DestoryBTree(BTreeNode* t)
{
	if (t != NULL)
	{
		t->lchild = DestoryBTree(t->lchild);
		t->rchild = DestoryBTree(t->rchild);
		free(t);
		return NULL;
	}
}

//删除节点
void DeleteNote(BTreeNode* t, double a)
{
	if (t != NULL)
	{
		if (t->element == a)
		{
			t = DestoryBTree(t);
		}
		else
		{
			DeleteNote(t->lchild, a);
			DeleteNote(t->rchild, a);
		}
	}
}

//求树的高度
int max(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

int HighBTree(BTreeNode* t)
{
	if (t == NULL)
	{
		return 0;
	}
	else
	{
		return (max(HighBTree(t->lchild), HighBTree(t->rchild)) + 1);
	}
}

//统计二叉树叶节点个数
int CountLeaf(BTreeNode* t)
{
	if (t == NULL)
	{
		return 0;
	}
	else if (t->lchild == NULL && t->rchild == NULL)
	{
		return 1;
	}
	else
	{
		return CountLeaf(t->lchild) + CountLeaf(t->rchild);
	}
}

//交换左右子树
void ChangeBTree(BTreeNode* t)
{
	if (t != NULL)
	{
		BTreeNode* p;
		p = t->rchild;
		t->rchild = t->lchild;
		t->lchild = p;
		ChangeBTree(t->lchild);
		ChangeBTree(t->rchild);
	}
}

//链队列结构类型
typedef struct QueueNode
{
	BTreeNode* btreenode;
	QueueNode* next;
}QueueNode;

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

LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->btreenode = NULL;
	return q;
}

//空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//入队
void EnLinkQueue(LinkQueue* q, BTreeNode* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->btreenode = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

//出队
BTreeNode* DeLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		BTreeNode* btreenode;
		QueueNode* queuenode;
		queuenode = q->front->next;
		btreenode = queuenode->btreenode;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return btreenode;
	}
}

//层次遍历二叉树
void ShowBTree(BTreeNode* t)
{
	if (t == NULL)
	{
		printf("树空\n");
	}
	else
	{
		LinkQueue* q;
		BTreeNode* node;
		q = InitLinkQueue();	//创建树节点队列
		EnLinkQueue(q, t);
		while (EmptyLinkQueue(q) == 1)		//队不为空
		{
			node = DeLinkQueue(q);
			printf("%lf ", node->element);
			if (node->lchild != NULL)
			{
				EnLinkQueue(q, node->lchild);
			}
			if (node->rchild != NULL)
			{
				EnLinkQueue(q, node->rchild);
			}
		}
		free(q->front);
		free(q);
	}
}

//层次展示二叉树
void LikeBTree(BTreeNode* t)
{
	if (t == NULL)
	{
		printf("树空\n");
	}
	else
	{
		LinkQueue* q;
		BTreeNode* node;
		int high = 1;
		int sumh;
		int highmax;
		int mark = 0;

		BTreeNode* emptynode;
		emptynode = (BTreeNode*)malloc(sizeof(BTreeNode));
		emptynode->element = NULL;
		emptynode->lchild = NULL;
		emptynode->rchild = NULL;

		highmax = HighBTree(t);
		q = InitLinkQueue();	//创建树节点队列

		EnLinkQueue(q, t);
		while (EmptyLinkQueue(q) == 1 && high <= highmax)		//队不为空
		{
			node = DeLinkQueue(q);
			for (int k = 0; k < highmax - high; k++)			//填补前面空缺
			{
				printf("  ");
			}
			if (node == emptynode)
			{
				printf("   #");
			}
			else
			{
				printf("%4g", node->element);
			}
			mark++;
			sumh = pow(2, high) - 1;
			if (mark >= sumh)		//换层
			{
				high++;
				printf("\n");
			}
			if (node->lchild != NULL)
			{
				EnLinkQueue(q, node->lchild);
			}
			else
			{
				EnLinkQueue(q, emptynode);
			}
			if (node->rchild != NULL)
			{
				EnLinkQueue(q, node->rchild);
			}
			else
			{
				EnLinkQueue(q, emptynode);
			}
		}
		free(emptynode);
		free(q->front);
		free(q);
	}
}

//二叉树功能
void FunctionBTree(struct BTreeNode* t)
{
	int choice = 1;
	double data;
	while (choice != 0)
	{
		printf("二叉树为：\n");
		LikeBTree(t);
		printf("\n功能：\n");
		printf("0 - 退出\n");
		printf("1 - 先序遍历二叉树\n");
		printf("2 - 中序遍历二叉树\n");
		printf("3 - 后序遍历二叉树\n");
		printf("4 - 输出二叉树的高度\n");
		printf("5 - 输出二叉树叶子节点的个数\n");
		printf("6 - 删除二叉树元素\n");
		printf("7 - 交换二叉树中的所有左右子树\n");
		printf("8 - 层次遍历二叉树\n");

		printf("选择：");
		scanf_s("%d", &choice);
		if (choice == 1)
		{
			printf("先序遍历二叉树：\n");
			Pre_Order(t);
			printf("\n===\n");
		}
		else if (choice == 2)
		{
			printf("中序遍历二叉树：\n");
			In_Order(t);
			printf("\n===\n");
		}
		else if (choice == 3)
		{
			printf("后序遍历二叉树：\n");
			Post_Order(t);
			printf("\n===\n");
		}
		else if (choice == 4)
		{
			printf("树的高度为：%d\n", HighBTree(t));
		}
		else if (choice == 5)
		{
			printf("二叉树叶子节点的个数：%d\n", CountLeaf(t));
		}
		else if (choice == 6)
		{
			printf("删除的值为：\n");
			scanf_s("%lf", &data);
			DeleteNote(t, data);
			printf("元素已删除\n");
		}
		else if (choice == 7)
		{
			ChangeBTree(t);
			printf("二叉树的所有左右子树已交换\n");
		}
		else if (choice == 8)
		{
			printf("层次遍历二叉树:\n");
			ShowBTree(t);
			printf("\n===\n");
		}
		else
		{
			printf("重新输入:\n");
		}
	}
}

int main()
{
	BTreeNode* t;
	t = CreatBTree();
	FunctionBTree(t);
	DestoryBTree(t);

	system("pause");
	return 0;
}