队列的链式存储

typedef int datatype;                       //定义链队列中数据元素的数据类型
typedef struct node{
 datatype data;                 //数据域
 struct node *next;         //链接指针域
}linklist;　　　　　　　//链表元素类型定义
typedef struct{
 linklist *front, *rear;                     //链表元素类型定义
}linqueue;                               //链队列类型定义
linkqueue *q;                        //定义指向连队列的指针

1. 先写头文件linkqueue.h

#ifndef _LINKQUEUE_H__
#define _LINKQUEUE_H__
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int data_t;   //定义数据类型为int
​
//定义链式队列的结点类型
typedef struct linkqueuenode{
 data_t data;
 struct linkqueuenode *next;
}linkqueue_node, *linkqueue_pnode;
​
//将front和rear指针封装
typedef struct linkqueue
{
 linkqueue_pnode front, rear;
}link_queue, *link_pqueue;
extern void init_linkqueue(link_pqueue *Q);
extern bool in_linkqueue(data_t data, link_pqueue q);
extern bool is_empty_linkqueue(link_pqueue q);
extern bool out_linkqueue(link_pqueue q, data_t *D);
extern void show_linkqueue(link_pqueue q);

2. 写linkqueue.c

#include "linkqueue.h"
void init_linkqueue(link_pqueue *Q)
{
 *Q = (link_pqueue)malloc(sizeof(link_queue));
 if(NULL == (*Q)){
 perror("malloc");
 exit(-1);
 }
 //申请头结点空间
 (*Q)->front = (linkqueue_pnode)malloc(sizeof(linkqueue_node));
 if(NULL == (*Q)->front){
 perror("malloc");
 exit(-1);
 }
 (*Q)->front->next = NULL;
 (*Q)->rear = (*Q)->front;
}
//入队
bool in_linkqueue(data_t data, link_pqueue q)
{
 linkqueue_pnode new;
 new = (linkqueue_pnode)malloc(sizeof(linkqueue_node));
 if(NULL == new){
 printf("入队失败！\n");
 return false;
 }
 new->data = data;
 new->next = q->rear->next;
 q->rear->next = new;
 q->rear = q->rear->next;
 return true;
}
bool is_empty_linkqueue(link_pqueue q)
{
 if(q->rear == q->front)
 return true;
 else
 return false;
}
bool out_linkqueue(link_pqueue q, data_t *D)
{
 linkqueue_pnode t;
 if(is_empty_linkqueue(q)){
 printf("队列已空!\n");
 return false;
 }
 t = q->front;
 q->front = q->front->next;
 *D = q->front->data;
 free(t);
 return true;
}
void show_linkqueue(link_pqueue q)
{
 linkqueue_pnode p;
 for(p= q->front->next;p!= NULL;p=p->next)
 printf("%d\t", p->data);
 printf("\n");
}

3. 写测试程序test.c

/*
 *用链式队列实现如下功能：用户从键盘输入整数，程序将其入队，用户输入字母，程序将队头元素出队，并在每一次出队和入队之后打印队列元素。
 */
#include "linkqueue.h"
int main(void)
{
 link_pqueue q;
 data_t data, t;
 int ret;
 init_linkqueue(&q);
 while(1){
 printf("请输入一个整数:");
 ret = scanf("%d", &data);
 if(ret == 1){
 if(in_linkqueue(data, q))
 show_linkqueue(q);
 }else{
 if(out_linkqueue(q, &t)){
 printf("out:%d\n", t);
 show_linkqueue(q);
 } 
 while(getchar()!= '\n');
 }
 }
 return 0;
}

4. 写Makefile文件

CC = gcc
CFLAGS = -Wall -g -o0
SRC = linkqueue.c test.c
OBJS = test
$(OBJS):$(SRC)
 $(CC) $(CFLAGS) -o $@ $^
.PHONY:
 clean
clean:
 $(RM) $(OBJS) .*.sw?

结果：

树与二叉树

• 树的基本概念

• 二叉树的概念

• 二叉树的性质

• 二叉树的顺序存储

• 二叉树的链式存储

• 二叉树的遍历

树(Tree)是n(n≥0)个节点的有限集合T，它满足两个条件：

• 有且仅有一个特定的称为根(Root)的节点

• 其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、......、Tm，其中每一个集合又是一棵树，并称为其根的子树(Subtree)。

树的定义是递归定义

• 一个节点的个数称为该结点的度数，一棵树的度数是指该树中最大度数。

• 读书为零的节点称为树叶或终端节点，度数不为零的节点称为分支节点，除根节点外的分支结点称为内部节点。

• 一个节点的子树之根结点称为该节点的子结点，该节点称为它们的父节点，同一节点的各个子节点之间称为兄弟节点。一棵树的根结点没有父节点，叶节点没有子节点。

• 一个节点系列k1、k2、.....、k_j，并满足k_i是k_{i+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1，即路径中的边数。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。}

• 节点的层数等于父节点的层数加一，根节点的层数定义为一。树中节点层数最大值称为该树的高度或深度。

• 若书中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则该树称为有序树。一般的树是有序树。

• m（m≥0）棵互不相交的的树的集合称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

• 树的逻辑结构：树中任何节点都可以有零个或多个直接后继节点（子节点），但至多只有一个直接前趋节点（父节点），根节点没有前趋节点，叶节点没有后继节点。

二叉树的概念

二叉树是n（n≥0）个节点的有限集合，它或者是空集（n=0）,或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通书有序数不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

二叉树的性质

• 二叉树第i(i≥1)层上的节点最多为2^i-1个。

• 深度为k(k≥1)的二叉树最多有2^k-1个节点。

• 在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。

  假设：度为0的节点为n0个，度为1的节点为n1个，度为2的节点为n2个。

  总结点数为各类节点数之和：n = n0 + n1 + n2

  总结点数为所有子节点数加一：n = n1 + 2*n2 + 1

  故得：n0 = n2 + 1 //(在二叉树中，度为0的节点总是比度为2的节点多一)