2.27数据结构

1.链队

//link_que.c
#include "link_que.h"//创建链队
Q_p create_que()
{Q_p q = (Q_p)malloc(sizeof(Q));if(q==NULL){printf("空间申请失败\n");return NULL;}node_p L=(node_p)malloc(sizeof(node));if(L==NULL){printf("申请空间失败\n");return NULL;}L->next=NULL;q->front = L;q->rear = L;return q;
}
//创建结点
node_p create_node()
{node_p new=(node_p)malloc(sizeof(node));if(new==NULL){printf("申请空间失败\n");return NULL;}new->data=0;new->next=NULL;return new;
}
//判空
int empty_que(Q_p q)
{if(q==NULL){printf("入参为空\n");return -1;}return q->front==NULL?1:0;
}
//入队
void push_que(Q_p q,datatype e)
{if(q==NULL){printf("入参为空\n");return;}node_p s=create_node();s->data=e;q->rear->next=s;q->rear=s;
}
//出队
void pop_que(Q_p q)
{if(q==NULL){printf("入参为空\n");return;}if(empty_que(q)){printf("队为空\n");return;}if(q->front->next==q->rear){q->rear==q->front;}node_p p=q->front->next;printf("出队元素为:%d\n",p->data);q->front->next=p->next;free(p);p=NULL;	
}
//打印
void show(Q_p q)
{if(q==NULL){printf("入参为空\n");return;}if(empty_que(q)){printf("队为空\n");return;}node_p p=q->front;while(p->next!=NULL){p=p->next;printf("%d\n",p->data);}
}
//销毁
void free_que(Q_p *q)
{if(q==NULL||*q==NULL){printf("入参为空\n");return;}free(*q);*q=NULL;
}

//link_que.h
#ifndef __LINK_QUE_H__
#define __LINK_QUE_H__
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{datatype data;struct node *next;
}node,*node_p;
typedef struct Q
{node_p front;node_p	rear;
}Q,*Q_p;//创建链队
Q_p create_que();
//创建结点
node_p create_node();
//判空
int empty_que(Q_p q);
//入队push_que
void push_que(Q_p q,datatype e);
//出队pop_que
void pop_que(Q_p q);
//打印
void show(Q_p q);
//销毁
void free_que(Q_p *q);#endif

//main.c
#include "link_que.h"int main()
{Q_p q = create_que();push_que(q,90);push_que(q,12);push_que(q,6);show(q);putchar(10);pop_que(q);putchar(10);show(q);putchar(10);push_que(q,1);push_que(q,7);push_que(q,5);push_que(q,4);push_que(q,3);push_que(q,2);show(q);putchar(10);free_que(&q);show(q);return 0;
}

2.二叉树的遍历

//tree.c
#include "tree.h"
//创建结点
tree_p create_node(char data)
{tree_p new = (tree_p)malloc(sizeof(tree));if(new==NULL){printf("空间申请失败\n");return NULL;}new->data=data;return new;	
}
//创建二叉树
tree_p create_tree()
{char data = '\0';scanf("%c",&data);getchar();if(data=='#')return NULL;tree_p T = create_node(data);T->lch=create_tree();T->rch=create_tree();return T;	
}
//先序遍历,根左右
void pri(tree_p T)
{if(T==NULL)return;printf("%c->",T->data);pri(T->lch);pri(T->rch);
}
//中序遍历,左根右
void mid(tree_p T)
{if(T==NULL)return;mid(T->lch);	printf("%c->",T->data);mid(T->rch);
}
//后序遍历,左右根
void last(tree_p T)
{if(T==NULL)return;last(T->lch);last(T->rch);	printf("%c->",T->data);
}

//tree.h
#ifndef __TREE_H__
#define __TREE_H__
#include <stdio.h>
#include <stdlib.h>typedef struct tree_node
{char data;struct tree_node *lch;struct tree_node *rch;
}tree,*tree_p;//创建结点
tree_p create_node(char data);
//创建二叉树
tree_p create_tree();//先序遍历,根左右
void pri(tree_p T);
//中序遍历,左根右
void mid(tree_p T);
//后序遍历,左右根
void last(tree_p T);#endif

//main.c
#include "tree.h"int main()
{tree_p T=create_tree();printf("先序遍历\n");pri(T);putchar(10);printf("中序遍历\n");mid(T);putchar(10);	printf("后序遍历\n");last(T);putchar(10);return 0;
}