4.19作业

二叉树

#include "btree.h"
node_p creat_btree()  //创建二叉树
{
	char data='\0';  //定义一个char类型的变量，接收输入的结点的值
	scanf(" %c",&data);  //用户终端输入想创建的二叉树（输入结点值），scanf需要空格吸收垃圾字符
	if(data=='#')  //判断用户输入是否有意义的结点值
	{
		return NULL;  //如果是#不创建二叉树
	}
	node_p new=creat_node(data);
	new->lchild=creat_btree();
	new->rchild=creat_btree();
	return new;  //把第一个输入的根结点返回
}
node_p creat_node(char data)  //创建结点
{
	node_p new=(node_p)malloc(sizeof(node));
	if(new==NULL)
	{
		printf("创建结点失败\n");
		return NULL;
	}
	new->data=data;
	return new;
}
void pri_show(node_p T)  //先序遍历
{
	if(T==NULL)
		return;
	printf("%c",T->data);
	pri_show(T->lchild);
	pri_show(T->rchild);
}
void mid_show(node_p T)  //中序遍历
{
	if(T==NULL)
		return;
	mid_show(T->lchild);
	printf("%c",T->data);
	mid_show(T->rchild);
}
void last_show(node_p T)  //后序遍历
{
	if(T==NULL)
		return;
	last_show(T->lchild);
	last_show(T->rchild);
	printf("%c",T->data);
}

链式队列

#include "link_queue.h"
Tnode_p create_link_queue()  //创建链式队列
{
	Tnode_p T=(Tnode_p)malloc(sizeof(Tnode));
	if(T==NULL)
	{
		printf("空间申请失败\n");
		return NULL;
	}
	T->front=NULL;
	T->rear=NULL;
	return T;
}
node_p create_node(int data)  //创建结点
{
	node_p new=(node_p)malloc(sizeof(node));
	if(new==NULL)
	{
		printf("创建结点失败\n");
		return NULL;
	}
	new->data=data;
	return new;
}
int empty_link_queue(Tnode_p T)  //判空
{
	if(T==NULL)
	{
		printf("入参为空，请检查\n");
		return -1;
	}
	return T->front==NULL && T->rear==NULL;
}
void push_link_queue(Tnode_p T,int data)  //入队
{
	if(T==NULL)
	{
		printf("入参为空，请检查\n");
		return;
	}
	node_p new=create_node(data);
	if(T->front==NULL)
	{
		new->next=T->front;
		T->front=new;
		T->rear=new;
	}
	else
	{
		new->next=T->rear->next;
		T->rear->next=new;
		T->rear=new;
	}
	printf("入队元素为%d\n",new->data);
}
void pop_link_queue(Tnode_p T)  //出队
{
	if(T==NULL)
	{
		printf("入参为空，请检查\n");
		return;
	}
	if(empty_link_queue(T))
	{
		printf("队列为空，无需出队\n");
		return;
	}
	printf("出队的元素为%d\n",T->front->data);
	node_p del=T->front;
	T->front=del->next;
	free(del);
}
void show_link_queue(Tnode_p T)  //输出
{
	if(T==NULL)
	{
		printf("入参为空，请检查\n");
		return;
	}
	if(empty_link_queue(T))
	{
		printf("队列为空，无需输出\n");
		return;
	}
	node_p p=T->front;
	while(p!=NULL)
	{
		printf("%-4d",p->data);
		p=p->next;
	}
	putchar(10);
}