1.数据

数据：可输入计算机并可由计算机处理各种符号的集合

• 信息的载体
• 是客观事物符号化的表现
• 能被计算机识别、存储和加工

包括：

• 数值型的数据：整数、实数等
• 非数值数据：文本、图像、图形、声音等

2.数据元素

是数据的基本单位，通常在计算机程序中作为一个整体来考虑和处理。

也简称为元素，或称为记录、结点或顶点。

一个数据元素可以由几个数据元素组成数据项组成。

3.数据项

数据项：构成数据元素的不可分割最小单位。

数据、数据元素和数据项之间的关系：

数据>数据元素>数据项

4.数据对象

是集合相同性质的数据元素，是数据的子集。

数据元素与数据对象：

• 数据元素：构成数据的基本单位。
  • 与数据的关系：是个体的集合
• 数据对象：收集性质相同的数据元素。
  • 与数据的关系：集合子集

线性表具有相同特性的数据元素有限序列

（a1,a2,…ai-1,ai,ai 1,…,an)

线性表的基本操作：

• 初始化 InitList(&L)，构建空线性表
• 销毁线性表 DestroyList(&L)
• 清除线性表 ClearList(&L),将线性表重置为空表
• 判断线性表是否为空 ListEmpty(L)
• 寻求线性表的长度 ListLength(L),返回线性表元素的数量，即线性表的长度
• 获取线性表元素 GetElem(L,i,&e) 返回线性表第一个元素的值e
• 定位/找到线性表元素 LocateElem(L,e,compare()),compare()作为判断函数，返回第一个与e满足compare()条件元素序列。
• 获得元素前驱 PriorElem(L,cur_e,&pre_e) 若cur_e使用L的数据元素pro_e回到它的前驱
• 获取元素后继 NextElem(L,cur_e,&next_e) 若cur_e使用L的数据元素next_e回到它的后继
• 插入元素 ListInsert(&L,i,e) 在线性表L的第一个位置插入新元素e
• 删除元素 DeleteList(&L,i,e) 删除第一个位置的元素
• 遍历 ListTraverse(&L,visited()) 遍历线性表，每一个元素visited()操作

**顺序存储：**在物理上存储相邻存储单元中存储逻辑上相邻数据元素的存储结构

顺序表的特点：

• 元素的逻辑顺序与物理顺序相同

顺序表的优缺点：

• 优点
  • 存储密度高，每个结点只存储数据元素
  • 任何元素都可以随机存取
• 缺点
  • 插入和删除操作需要移动大量元素
  • 浪费存储空间
  • 属于静态存储形式，数据元素的数量不能自由扩展

注：线性表与数组的区别：线性表长可变（删除），数组长度不能动态定义

1. 静态定义

   typedef int ElemType;  typedef struct{  ElemType data[MaxSize];//  int length;////当前顺序表的长度 }SqList;  /// void InitList(SqList &L) {  for (int i = 0; i < MaxSize; i  )   L.data[i] = 0;  L.length = 0; } 

   注：若采用数组定义，则销毁操作不可用free函数。系统将在静态数组运行后自动回收。

2. 动态定义

   #define InitSize 10 ///默认最大长度 typedef struct {  int *data; ///指示动态分配数组的指针  int MaxSize;////顺序表的最大容量  int length;////当前顺序表的长度 }SqList;  /// void InitList(SqList &L) {  //用malloc函数申请连续存储空间  L.data = (int *)malloc(InitSize * sizeof(int));  L.length = 0;  L.MaxSize = InitSize; }  ////增加动态数组的长度 void IncreaseSize(SqList &L,int len) {  int *p = L.data;  ///这里开放的地址空间是一个新的连续空间，所以要转存以前的数组，释放旧地址空间  L.data = (int *)malloc((L.MaxSize   len) * sizeof(int));  for (int i = 0; i < L.length; i  ) {   L.data[i] = p[i]; ///将数据复制到新区域  }  L.MaxSize = L.MaxSize   len; ///len  free(p);     //释放原来的内存空间 } 

//动态定义 typedef int ElemType;  typedef struct {  ElemType *data;  int length; }SqList;  //初始化 bool InitList(SqList &L) {  L.data = (ElemType *)malloc(sizeof(ElemType )* MaxSize);  L.length = 0;  return true; } 

注：malloc(m)函数，打开m字节长度的地址空间，并返回该空间的第一个地址

sizeof(x)计算变量x的长度

free§函数，释放指针p所指变量的存储空间，即完全删除变量

上述函数需要加载头文件#include <stdlib.h>

//销毁顺序表 void DestroyList(SqList &L) {  if (L.data) {   free(L.data);  }  L.length = 0; } //顺序表的清除 void ClearList(SqList &L) {  L.length = 0; } ////求线性表L的长度 int GetLength(SqList L){     return (L.length); } ////判断线性表L是否空 int IsEmpty(SqList L){     if(L.length==0)         return 1;     else         return 0; } //按位搜索据元素
ElemType SearchList_index(SqList &L, int e) {
	if (e<1 || e>L.length)
		return false;
	return L.data[e - 1];
}
//按值查找
int SearchList_value(SqList &L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e)
			return i + 1;
	}
	return false;
}
//顺序表的插入
/**************************************************************
算法思想：	1.判断插入位置是否合法
		   2.判断顺序表的存储空间是否已满，若已满返回ERROR
		   3.将第n至第i位的元素依次向后移动一个位置，空出第i个位置
		   4.将要插入的新元素e放入第i个位置
		   5.表长加1，插入成功，返回true
***************************************************************/
bool ListInsert(SqList &L, int i, int e) {
	//判断插入的位置是否合法
	if (i<1 || i>L.length + 1)
		return false;
	//判断内存是否足够
	if (L.length == MaxSize)
		return false;
	for (int j = L.length; j >= i; j--)	//将第i个元素及后面的元素后移
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;		//在位置i出放入e
	L.length++;				//长度加1
	return true;
}

//删除指定位置的元素
/**************************************************************
算法思想：	1.判断删除位置是否合法	
		   2.将要删除的元素保留在e中
		   3.将第i+1至第n位的元素依次向前移动一个位置
		   4.表长减1，删除成功，返回true
***************************************************************/
bool DeleteList(SqList &L, int i, int &e) {
	if (i > L.length || i < 1)
		return false;
	e = L.data[i - 1];
	for (int j = i; j < L.length; j++)
		L.data[j - 1] = L.data[j];
	L.length--;
	return true;
}

注：查找、插入、删除算法的平均时间复杂度为O(n)

链表由表头唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L。

链表的特点：

1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点。

typedef int ElemType; 

typedef struct LNode{ 	//定义单链表的结点类型 
	ElemType data;    	//每个节点存放一个数据元素 
	struct LNode *next;	//指针指向下一个结点
}LNode,*LinkList;

/*
//LinkList强调的是链表，LNode *强调的是结点，两者等价 
LNode *L;		//声明指向单链表第一个结点的指针 
LinkList L;		//声明指向单链表第一个结点的指针  (代码可读性更强） 
*/ 

//带头结点的单链表的初始化
/**************************************************
步骤：	1.生成一个新结点作为头结点，用头指针L指向头结点
		2.将头结点的指针域置空
 * ***********************************************/
bool InitLinkList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode)); //分配一个头结点
	if(L==NULL)				//内存不足，分配失败 
		return false;
	L->next=NULL;			//头结点之后暂时还没有结点 
	return true; 
} 

/*************************************不带头结点*****************************/
typedef int ElemType; 

typedef struct LNode{ 	//定义单链表的结点类型 
	ElemType data;    	//每个节点存放一个数据元素 
	struct LNode *next;	//指针指向下一个结点
}LNode,*LinkList;

/*
//LinkList强调的是链表，LNode *强调的是结点，两者等价 
LNode *L;		//声明指向单链表第一个结点的指针 
LinkList L;		//声明指向单链表第一个结点的指针  (代码可读性更强） 
*/ 

//不带头结点的单链表的初始化
bool InitLinkList(LinkList &L){
	L=NULL;		//空表，暂时没有任何结点 
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
	if(L==NULL)
		return true;
	else
		return false;
}

//按位序插入（不带头结点）
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	if(i==1){		//	插入第一个结点的操作与其他结点的操作不同
		LNode *s=(LNode *)malloc(sizeof(LNode));
		s->data=e;
		s->next=L;
		L=s;		//头指针指向新结点
		return true;
	}
	LNode *p;		//指针p指向当前扫描到的结点
	int j=1;		//当前p指向的是第几个结点
	p=L;			//p指向第一个结点（注意：不是头结点）
	while(p!=NULL&&j<i-1){	//循环找到第i-1个结点
		p=p->next;
		j++;
	}	
	if(p==NULL)		//i值不合法
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;	//插入成功
}

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL) //内存分配失败
        return false;
    s->data=e; //用结点s保存数据元素e
    s->next=p->next;
    p->next=s;  //将结点s连接到p之后
    return true;
}

//前插操作：在p结点之前插入结点s
bool InsertPriorNode(LNode *p,LNode *s){
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    p->next=s;
    ElemType temp=p->data;
    p->data=s->data;
    s->data=temp;
    return false;
}

//判断单链表是否为空
/*判断头指针指针域是否为空即可*/
bool Empty(LinkList L){
	if(L->next==NULL)
		return true;
	else
		return false;
}

//单链表的销毁(从头指针开始，依次释放所有结点)
bool DestroyList(LinkList &L){
	if(L==NULL)
		return false;
	LNode *p=L;
	while(L!=NULL){
		L=L->next;
		free(p);
		p=L;
	}
	return true;
}

//清空单链表（依次释放所有结点，并将头结点指针域置空）
bool ClearList(LinkList &L){
	if(L==NULL)
		return false;
	LNode *p=L->next;
	while(p!=NULL){
		L->next=p->next;
		free(p);
		p=L->next;
	}
	//或者，两种思路
	/*
	LNode *p=L->next,*q;
	while(p!=NULL){
		q=p->next;
		free(p);
		p=q;
	}
	*/
	L->next=NULL;
	return true;
}

//求表的长度
int Length(LinkList L){
	int len=0;
	LNode *p=L;
	while(p->next!=NULL){
		p=p->next;
		len++;
	}
	return len;
}

//取值
/************************************************************************************
算法步骤：1.从第一个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next。
		2.j做计数器，累计当前扫描过的结点数，j初值为1
		3.当p指向扫描下一个结点时，计数器j加1
		4.当j==i时，p所指向的结点就是要找的第i个结点
*************************************************************************************/
bool GetElem(LinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    LNode *p=L->next;
    int j=1;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL)//第i个元素不存在
        return false;
    e=p->data;
    return true;
}

//按值查找
/************************************************************************************
算法步骤：1.从第一个结点开始，依次和e值比较
		2.如果找到一个其值与e相等的元素，则返回其在链表中的位置或地址。
		3.如果遍历完之后没有与e值相等的元素，则返回0或者NULL
*************************************************************************************/
//返回地址
LNode * LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}
//返回位序
int LocateElem(LinkList L,ElemType e){
    LNOde *p=L->next;
    int j=1;
    while(p!=NULL&&p->data!=e){
        p=p->next;
        j++;
    }
    if(p!=NULL)
        return j;
    else		//不存在
        return 0;
}
//插入(在第i个位置插入)
/************************************************************************************
算法步骤：1.找到第i-1个结点的位置
		2.生成一个数据域为e的新结点s
		3.插入新结点s
*************************************************************************************/
bool InsertList(LinkList &L,int i,ElemType e){
    if(i<1)
        ruturn false;
    int j=0;
    LNode *p=L;
    while(p!=NULL&&J<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
   	LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return ture;
}
//删除(删除第i个结点)
/************************************************************************************
算法步骤：1.找到第i-1个结点的位置，保存要删除的结点的元素值
		2.第i-1个结点的指针域指向第i个结点的next域
		3.释放第i个结点存储空间
*************************************************************************************/
bool DeleteList(LinkList &L,int i,ElemType &e){
    if(i<1)
		return false;
    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p->next==NULL)
        return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}
//头插法建立单链表
 bool CreateList_H(LinkList &L,int n){
     LNode *s;
     for(int i=0;i<n;i++){
         s=(LNode *)malloc(sizeof(LNode));
         scanf("%d",&s->data);
         s->next=L->next;
         L->next=s;
     }
     return true;
 }

//尾插法建立单链表
bool CreatList_R(LinkList &L,int n){
    LNode *s,*p=L;
    for(int i=0;i<n;i++){
        s=(LNode *)malloc(sizeof(LNode));
        scanf("%d",&s->data);
        p->next=s;
        p=s;
	}
    p->next=NULL;
    return true;
}

查找、删除、头插法、尾插法

优点：

• 是一种动态的数据结构，可以在运行的过程中通过分配和取消分配内存来插入和删除结点
• 插入和删除元素不需要移动元素，只需要更新结点的next指针域
• 大小可以根据需求在运行时增加或减少，内存利用率高

缺点：

• 与数组相比，存储元素需要更多内存，因为单链表的每个结点都包含一个指针域用来保存下一节点的地址。
• 结点遍历困难，访问元素的效率低。

typedef int ElemType;

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

//双链表的初始化(带头结点)
bool InitDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=NULL; //头结点的prior永远指向NULL
    L->next=NULL;
    return true;
}

//插入
bool InsertList(DLinkList &L, int i, ElemType e) {
	if (i < 1)
		return false;
	int j = 0;
	DNode *p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	DNode *s = (DNode *)malloc(sizeof(DNode));
	//这里理解插入的思想，不同的顺序对应的代码不同，一定要理解插入的过程
	s->data = e;
	s->next = p->next;
	if(p->next!=NULL)//判断当前链表是否为空！！！！！！！！
		p->next->prior = s;
	s->prior = p;
	p->next = s;
}
//双链表的插入，在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL) //非法参数
        return false;
    s->next=p->next;
    if(p->next!=NULL)  //如果p结点有后继节点
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}
//删除
bool DelertDNode(DLinkList &L,int i,ElemType &e){
    if(i<1)
        return false;
    int j=0;
    DNode *p=L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL)//不存在第i个结点
        return false;
    e=p->data;
    p->prior->next=p->next;
    if(p->next!=NULL)
        p->next->prior=p->prior;
    free(p);
    return true;
}

在单链表的基础上增加了一个指向前一个结点的指针域，解决了单链表中无法通过指定结点找到其之前结点的问题。

优点：从表中任意位置出发均可以找到其他结点

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)
        return false;
    L->next=L; //头结点的next指向头结点
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L){
    if(L->next==L)
        return true;
    else    
        return false;
}

//判断p结点是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
    if(p->next==L)
        return true;
    else    
        return false;
}

int main()
{
    LinkList L;
    InitList(L);
    //...
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->prior=L; //头结点的prior指向头结点
    L->next=L;  //头结点的next指向头结点
    return true;
}
//判断循环双链表是否为空
bool Empty(DLinkList L){
    if(L->next==L)
        return true;
    else    
        return false;
}

//判断p结点是否为循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p){
    if(p->next==L)
        return true;
    else    
        return false;
}

//插入,在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    s->next=p->next;
    p->next->prior=s;//这里无需判断是否为表尾结点
    s->prior=p;
    p->next=s;
}

//删除p结点的后继节点
bool DeleteNextDNode(DNode *p,DNode *q){
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
}


int main()
{
    DLinkList L;
    InitDLinkList(L);
    //...
    return 0;
}

typedef struct DNode{
    ElemType data;
    int next;
}SLinkList[MaxSize];

①线性表的合并

//这是一个通用的算法，La、Lb具体是顺序表还是链表可根据具体情况确定
/************************************************************
描述：利用La和Lb分别表示两个集合A和B，现要求一个新的集合A=AUB
*************************************************************/

void union(List &La,List &b){
    La_len=ListLength(La);	//求La的长度
    Lb_len=ListLength(Lb);	//求Lb的长度 
    for(i=1;i<Lb_len;i++){	//对Lb中的元素依次遍历
        GetElem(Lb,i,e);	//取值
        if(!LocateElem(La,e))	//在La中按值查找，如果不存在就在La中插入该元素
            Listlnsert(&La,++La_len,e);
    }
}

②有序表的合并

//已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素任按照非递减有序排列
/**********************************************************************************************
算法步骤：1.创建一个空表Lc
		2.依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变为空表为止
		3.继续将La和Lb其中一个表的剩余结点插在Lc表的最后
*********************************************************************************************/
//用顺序表实现过程
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
    pa=La.elem; //指针pa和pb的初始值分别指向两个表的第一个元素
    pb=Lb.elem;
    Lc.length=La.length+Lb.length; //新表长度为两个表的长度之和
    Lc.elem=(ElemType *)malloc(sizeof(ElemType)*Lc.length); //为新表分配数组空间
    pc=Lc.elem; //指针pc指向新表的第一个元素
    pa_last=La.elem+La.length-1; //指针pa_last指向La表的最后一个元素
    pb_last=Lb.elem+Lb.length-1; //指针pb_last指向Lb表的最后一个元素
    while(pa<=pa_last&&pb<=pb_last){ //两个表都非空
        if(*pa<=*pb)    //依次“摘取”两表中值较小的结点
            *pc++=*pa++
        else
            *pc++=*pb++;
    }
    while(pa<=pa_last) //Lb表已到达表位，将La中剩余元素加入Lc
        *pc++=*pa++;
    while(pb<=pb_last) //La表已到达表位，将Lb中剩余元素加入Lc
        *pc++=*pb++;
}

//用链表实现过程
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    pa=La->next;
    pb=Lb->next;
    pc=Lc=La; //用La的头结点作为Lc的头结点
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else{
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    pc->next=pa?pa:pb; //插入剩余段
    free(Lb);  //释放Lb的头结点
}

栈是只允许在一端（表尾）进行插入或删除操作的线性表。（先进后出，或后进先出）

其中，表尾成为栈顶，表头称为栈底。

栈的基本操作：

• 初始化 InitStack(&S)
• 销毁 DestrouStack(&L)
• 进栈 Push(&s,x)
• 出栈 Pop(&s,&x)
• 查(读栈顶元素) GetTop(s,&x)
• 判断是否为空 StackEmpty(S)
• 清空
• 求栈的长度

#define MaxSize 10
typedef int ElemType;

//定义
typedef struct{
    ElemType data[MaxSize];
    int top;    //栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top=-1;       //初始化栈顶指针
}

//判断栈是否为空
bool StackEmpty(SqStack S){
    if(S.top==-1)
        return true;
    return false;
}

//进栈操作
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1) //栈满
        return false;
    S.top=S.top+1;
    S.data[S.top]=x;
    //或者直接写成以下形式
    //S.data[++S.top]=x;
    return true;
}

//出栈操作
bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1) //栈空
        return false;
    x=S.data[S.top]; //保存出栈元素
    S.top=S.top-1;
    //或者直接写成以下形式
    //x=S.data[S.top--];
    return true;
}

//读栈顶元素
bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1) //栈空
        return false;
    x=S.data[S.top];
    return true;
}

//测试代码
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10

typedef struct {
	int *elem;
	int top;
}Stack;

//-初始化 InitStack(&S)
bool InitStack(Stack &S) {
	S.elem = (int *)malloc(MaxSize * sizeof(int));
	S.top = -1;
	return true;
}
//- 销毁 DestrouStack(&L)
bool DestrouStack(Stack &S) {
	if (S.elem == NULL)
		return false;
	free(S.elem);
	return true;
}
//- 进栈 Push(&s, x)
bool Push(Stack &S, int x) {
	if (S.top >= MaxSize-1)//栈满
		return false;
	S.top += 1;
	S.elem[S.top] = x;
	printf("元素%d进栈成功！\n",x);
	return true;
}
//- 出栈 Pop(&s, &x)
bool Pop(Stack &S, int &x) {
	if (S.top == -1)//栈空
		return false;
	x = S.elem[S.top];
	S.top -= 1;
	printf("元素%d出栈成功！\n", x);
	return true;
}
//- 查(读栈顶元素) GetTop(s, &x)
bool GetTop(Stack S, int &x) {
	if (S.elem == NULL || S.top==-1)
		return false;
	x = S.elem[S.top];
	return true;
}
//- 判断是否为空 StackEmpty(S)
bool StackEmpty(Stack S) {
	if (S.top == -1)
		return true;
	else
		return false;
}
//- 清空
bool ClearStack(Stack &S) {
	if (S.elem == NULL || S.top==-1)
		return false;
	S.top = -1;
	return true;
}
//- 求栈的长度
bool GetLength(Stack S) {
	return S.top + 1;
}

bool Print(Stack S) {
	printf("当前栈内的元素为：");
	if (S.elem == NULL || S.top==-1)
		return false;
	int p = S.top;
	while (p > -1) {
		printf("%d ", S.elem[p]);
		p--;
	}
	printf("\n");
	return true;
}
bool Create(Stack &S,int n) {
	printf("请输入入栈元素：");
	if (n > MaxSize)
		return false;
	for (int i = 0; i < n; i++) {
		S.top++;
		scanf("%d", &S.elem[S.top]);
	}
	printf("\n");
	return true;
}
int main()
{
	Stack S;
	InitStack(S);
	Create(S, 6);
	Print(S);
	Push(S, 7);
	Print(S);
	int x;
	Pop(S, x);
	Print(S);
	return 0;
}

共享栈*

#define MaxSize 10
typedef int ElemType;

//定义
typedef struct{
    ElemType data[MaxSize];
    int top1;    //1号栈顶指针
    int top2;    //2号栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top1=-1;       //初始化栈顶指针
    S.top2=MaxSize;
}
//栈满条件：top1+1==top2

/********************************************************************************************************
注意每次入栈或出栈的都是从链表的表头开始的，入栈之后要将链表的表头指针指向新入栈的元素，出栈即将表头元素出栈，要修改头指针为出栈元素的下一个元素
******************************************************************************************************/
typedef int ElemType;

//定义
typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

//初始化
void InitStack(LinkStack &S){
    S=NULL;
}

//判断栈是否为空
bool StackEmpty(LinkStack S){
    if(S==NULL)
        return true;
    else
        return false;
}

//入栈
bool Push(LinkStack &S,ElemType x){
    StackNode *p=(StackNode *)malloc(sizeof(StackNode)); //生成新结点p
    p->data=x;  //将新结点数据域置为x
    p->next=S;  //将新结点插入栈顶
    S=p;        //修改栈顶指针
    return true;
}

//出栈
bool Pop(LinkStack &S,ElemType &x){
    if(S==NULL)
        return false;
    StackNode *p=S;
    x=S->data;
    S=S->next;
    free(p);
    return true;
}

//取栈顶元素
ElemType GetTop(LinkStack S){
    if(S==NULL)
        return false;
    return S->data;
}

递归：若一个对象部分的包含它自己，或用它自己给自己定义，则称这个对象是递归的；

若一个过程直接或间接的调用自己，则称这个过程是递归的过程。

递归问题——用分治法求解

分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。

必备的三个条件：

1. 能够将一个问题转变成一个新的问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
2. 可以通过上述转化而时问题简化
3. 必须有一个明确的递归出口，或递归的边界。

分治法求解递归问题的算法一般形式：

void p([参数]){
    if(递归结束条件)
        直接求解步骤；  //基本项
    else
        p([较小的参数]); //归纳项
}

递归的优缺点：

• 优点：结构清晰，程序易读
• 缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。（入栈出栈在系统内部实现）

递归 -> 非递归：

• 方法1：尾递归、单向递归 -> 循环结构
• 方法2：自用栈模拟系统的运行时栈

队列是只允许在一端（表尾）进行插入（入队），在另一端（表头）进行删除（出队）的线性表。（先进先出）

队列的基本操作：

• 初始化 InitQueue(&Q)
• 销毁 DestroyQueue(&Q)
• 清空 ClearQueue(&Q)
• 入队 EnQueue(&Q,x)
• 出队 DeQueue(&Q,&x)
• 读队头元素 GetHead(Q,&x)
• 判断是否为空 QueueEmpty(Q)
• …

注意：一定要先搞清除头指针和尾指针的指向位置是怎么规定的，不同情况下的代码会不同，要理解其中的思想和原理，其次：不管在什么情况下，首相要搞清楚判断队列为空和队列已满这两个条件，非常重要。

#define MaxSize 10
typedef int ElemType;

//定义
//注意：在本代码中，对尾指针始终指向的是即将要插入元素的位置
typedef struct{
    ElemType *data;
    int front,rear; //队头指针和队尾指针
}SqQueue;

//初始化
bool InitQueue(SqQueue &Q){
    Q.data=(ElemType *)malloc(MaxSize*sizeof(ElemType));
    Q.front=0;
    Q.rear=0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if(Q.front==Q.rear)     //队列为空条件
        return true;
    else
        return false;
}

//判断队列是否为满队列
bool QueueFull(SqQueue Q){
    if(Q.rear+1==Q.front||(Q.rear+1>=MaxSize&&Q.front==0))
        return true;
    else
        return true;
}

顺序循环队列：

#define MaxSize 10
typedef int ElemType;

//定义
//注意：在本代码中，对尾指针始终指向的是即将要插入元素的位置
typedef struct{
    ElemType data[MaxSize];
    int front,rear; //队头指针和队尾指针
}SqQueue;

//初始化
bool InitQueue(SqQueue &Q){
    Q.front=0;
    Q.rear=0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if(Q.front==Q.rear)     //队列为空条件
        return true;
    else
        return false;
}

//入队
/******************************************************************
算法思想：1.在队尾插入元素
         2.尾指针后移一位
******************************************************************/
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front) //判断队满条件
        return false;
    Q.data[Q.rear]=x;           //将x值插入对尾
    Q.rear=(Q.rear+1)%MaxSize;   //队尾指针加1取模
    return true;
}

//出队(删除一个队头元素，用x返回)
/******************************************************************
算法思想：头指针后移
******************************************************************/
bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.front==Q.rear) //判断队列为空的条件
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

//获得队头元素的值，用x返回
bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    return true;
}

不同方案情况下判断队列已满/为空的条件：

/***************方案一******************/
//定义
typedef struct{
    ElemType data[MaxSize];
    int front,rear; //队头指针和队尾指针
}SqQueue;

//初始化
bool InitQueue(SqQueue &Q){
    Q.front=0;
    Q.rear=0;
}
//队列为空的条件：Q.rear==Q.front;
//队列已满的条件：对尾指针的在下一个位置是对头，即(Q.rear+1)%MaxSize==Q.front;(此时会浪费最后一片存储空间)
//队列元素个数：(rear+MaxSize-front)%MaxSize

/***************方案二******************/
//定义
typedef struct{
    ElemType data[MaxSize];
    int front,rear; //队头指针和队尾指针
    int size; //队列当前长度
}SqQueue;

//初始化
bool InitQueue(SqQueue &Q){
    Q.front=0;
    Q.rear=0;
    Q.size=0;
}
/****************************************************************************
在定义时额外定义一个变量用来存储当前队列的长度，可以不浪费最后一块存储空间，此时：
队列为空的条件：Q.size==0;
队列已满的条件：Q.size==MaxSize;
******************************************************************************/

/***************方案三******************/
//定义
typedef struct{
    ElemType data[MaxSize];
    int front,rear; //队头指针和队尾指针
    int tag; //最近进行的是删除/插入
    //每次删除成功时，都令tag=0，每次插入成功时，都令tag=1
    //只有删除操作，才有可能导致队空，只有插入操作，才有可能导致队满
}SqQueue;

//初始化
bool InitQueue(SqQueue &Q){
    Q.front=0;
    Q.rear=0;
    Q.tag=0;
}
/****************************************************************************
在定义时额外定义一个变量用来存表示最近进行的是插入还是删除操作，此时：
队列为空的条件：Q.front==Q.real&&tag==0;因为只有最后进行删除才能使队列为空
队列已满的条件：Q.front==Q.real&&tag==1;因为只有最后进行插入才能使队列为满
******************************************************************************/

注意：链队列中不需要判断队列是否满的情况。

带头结点：

typedef int ElemType;

//定义
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{         //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//初始化（带头结点）
void InitQueue(LinkQueue &Q){
    //初始时front、real都指向头结点
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

//入队（带头结点）
bool EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;  //新结点插入到rear之后
    Q.rear=s;        //修改表尾指针
}

//出队（带头结点）
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear)//空队
        return false;
    LinkNode *p=Q.front->next;
    x=p->data; //返回队头元素
    Q.front->next=p->next;//修改头结点的next指针
    if(Q.rear==p)       //如果是最后一个元素出队，修改rear指针
        Q.rear=Q.front;
    free(p);        //释放结点空间
    return true;    
}

不带头结点：

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

//定义
typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{         //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

//初始化（不带头结点）
void InitQueue(LinkQueue &Q){
    //初始时，front、real都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL)
        return true;
    else
        return false;
}

//入队（不带头结点）
bool EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){  //在空队列中插入第一个元素
        Q.front=s;      //修改队头队尾指针
        Q.rear=s;
    }
    else{
        Q.rear->next=s; //新结点插入到rear结点之后
        Q.rear=s;       //修改rear指针
    }
}

//出队
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==NULL) //空队
        return false;
    LinkNode *p=Q.front; //p指向此次出队的结点
    x=Q.front->data;     //返回队头元素
    Q.front=p->next;     //修改front指针
    if(Q.rear==p){       //此次是最后一个结点出队
        Q.front=NULL;    //front、real都指向NULL
        Q.rear=NULL;
    }
    free(p);
    return true;

}

int main()
{
    LinkQueue Q;
    InitQueue(Q);
    
    return 0;
}

//test.cpp
#include <stdio.h>
#include <stdlib.h>
/***********************************************************************
不带头结点的链式队列
判断队列为空的条件：Q.front==NULL，
本代码中的尾指针始终执行队尾元素
*************************************************************************/
typedef int Elemtype;
typedef struct QueueNode {
	Elemtype data;
	struct QueueNode *next;
}QueueNode;
typedef struct{
	QueueNode *front, *real;
}QueueList;

//-初始化 InitQueue(&Q)
bool InitQueue(QueueList &Q) {
	Q.front = NULL;
	Q.real = NULL;
	printf("链队初始化成功！\n");
	return true;
}
//- 销毁 DestroyQueue(&Q)
bool DestroyQueue(QueueList &Q) {
	if (Q.front == NULL)
		return false;
	QueueNode *p;
	while (Q.front!=NULL) {
		if (Q.front == Q.real) {
			p = Q.front->next;
			free(Q.front);
			Q.real = NULL;
		}
		else {
			p = Q.front->next;
			free(Q.front);
			Q.front = p;
		}
	}
	return true;
}
//- 清空 ClearQueue(&Q)
bool ClearQueue(QueueList &Q) {
	if (Q.front == NULL)
		return false;
	QueueNode *p;
	while (Q.front != NULL) {
		if (Q.front == Q.real) {
			p = Q.front->next;
			free(Q.front);
			Q.real = NULL;
		}
		else {
			p = Q.front->next;
			free(Q.front);
			Q.front = p;
		}
	}
	return true;
}
//- 入队 EnQueue(&Q, x)
bool EnQueue(QueueList &Q, Elemtype x) {
	QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
	p->data = x;
	p->next = NULL;
	if (Q.front == NULL) {
		Q.front = p;
		Q.real = p;
	}
	else {
		Q.real->next = p;
		Q.real = p;
	}
	printf("元素%d入队成功！\n",x);
	return true;
}
//- 出队 DeQueue(&Q, &x)
bool DeQueue(QueueList &Q, Elemtype &x) {
	if (Q.front == NULL)
		return false;
	x = Q.front->data;
	QueueNode *p = Q.front;
	Q.front = Q.front->next;
	if (Q.real == p) {
		Q.real = NULL;
	}
	free(p);
	return true;
}
//- 读队头元素 GetHead(Q, &x)
bool GetHead(QueueList &Q, Elemtype &x) {
	if (Q.front == NULL)
		return false;
	x=Q.front->data;
	return true;
}

//- 判断是否为空 QueueEmpty(Q)
bool QueueEmpty(QueueList &Q) {
	if (Q.real == Q.front&&Q.real == NULL)
		return true;
	else
		return false;
}

int main()
{
	int x;
	QueueList Q;
	InitQueue(Q);
	EnQueue(Q, 3);
	GetHead(Q, x);
	printf("当前队头元素为%d", x);
	EnQueue(Q, 5);
	GetHead(Q, x);
	printf("当前队头元素为%d", x);
	DeQueue(Q,x);
	printf("元素%d出队成功！\n", x);
	GetHead(Q, x);
	printf("当前队头元素为%d", x);
	return 0;
}

双端队列：只允许从两端插入、两段删除的线性表。（可根据需求自由设定输入输出受限）

串：即字符串（string）是由零个或多个字符组成的有限序列。

子串：串中任意个连续的字符组成的子序列

主串：包含子串的串

字符在主串中的位置：字符在串中的序号

子串在主串中的位置：子串的第一个字符在主串中的位置

空格串：由一个或多个空格组成的串

注意：空串和空格串的区别

串是一种特殊的线性表，数据元素之间呈现线性关系。

• 赋值操作 StrAssign(&T,chars)——把串T赋值为chars
• 复制操作 StrCopy(&T,S)——由串S复制得到串T
• 判空操作 StrEmpty(S)——若串S为空，则返回true，否则返回false。
• 求串长 StrLength(S) ——返回串S的元素个数
• 清空操作 ClearString(&S)——将串S清空为空串
• 销毁串 DestroyString(&S)——将串S销毁
• 串连接 Concat(&T,S1,S2) ——用T返回由S1和S2连接而成的新串
• 求子串 SubString(&Sub,S,pos,len) ——用Sub返回串S的第pos个字符起长度为len的子串。
• 定位操作 Index(S,T) ——若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0.
• 比较操作 StrCompare(S,T) 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0.

串的比较：从第一个字符开始往后依次对比，先出现更大字符的串就更大，长串的前缀与短串相同时，长串更大，只有两个串完全相等时，才算相等

#include <stdio.h>
#include <stdlib.h>
#define Maxlen 255 //预定义最大串长为255
typedef struct{
    char ch[Maxlen+]; //每个分量存储一个字符，一般情况下第一个位置不存储数据
    int length;//串的实际长度
}SString;

//比较操作 StrCompare(S,T) 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0.
int StrCompare(SString S,SString T){
    for(int i=1;i<=S.length&&i<=T.length;i++){
        if(S.ch[i]!=T.ch[i])
            return S.ch[i]-T.ch[i];
    }
    //扫描过的所有字符都相同，则长度长的串更大
    return S.length-T.length;
}

//求串长 StrLength(S) ——返回串S的元素个数
int StrLength(SString S){
    return S.length;
}
//求子串 SubString(&Sub,S,pos,len) ——用Sub返回串S的第pos个字符起长度为len的子串。
bool SubString(SString &Sub,SString S,int pos,int len){
    //子串范围越界
    if(pos+len-1>S.length)
        return false;
    for(int i=pos;i<pos+len;i++){
        Sub.ch[i-pos+1]=S.ch[i];
    }
    Sub.length=len;
    return true;
}

//定位操作 Index(S,T)
// ——若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0.
int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T);
    SString sub;//用于暂存子串
    while(i<=n-m+1){
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0)
            ++i;
        else    
            return i;//返回子串在主串中的位置
    }
    return 0;//S中不存在与T相等的子串
}

#define Maxlen 255 //预定义最大串长为255
typedef struct StringNode{
    char ch[4];//每个结点存多个字符
    struct StringNode *next;
}StringNode,*String;

//或者
typedef struct Chunk{
    char ch[Maxlen];
    struct Chunk *next;
}Chunk;
typedef struct{
    Chunk *head,*real;//串的头指针和尾指针
    int curlen;//串的当前长度
}LString;

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置。

朴素模式匹配算法：设主串长度为n，模式串长度为m，将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

int Index_BF(SString S,SString T){
	int i=1,j=1;
	while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[j]){//主串和子串依次匹配下一个字符
            ++i;  
            ++j;
        }
        else{ //主串、子串指针回溯重新开始下一次匹配
            i=i-j+2;
            j=1;
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}

//求子串,从中间某个位置开始匹配
int Index(SString S, SString T,int pos) {
	int i = pos, j = 1;
	while (i <= S.length&&j <= T.length) {
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;
			j = 1;
		}
	}
	if (j>T.length)//如果子串在主串中完全匹配，则j的值一定是大于子串的长度的
		return i-T.length;
	else
		return 0;
}
//事件复杂度：O(n*m)

利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针i不必回溯，可以提速到O(n+m)

最坏时间复杂度：O(m+n)

其中，求next数组时间复杂度O(m)，模式匹配过程最坏时间复杂度O(n)

int Index(SString S, SString T,int pos) {
	int i = pos, j = 1;
	while (i <= S.length&&j <= T.length) {
		if (j==0||S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			j=next[j];   /*i不变，j后退*/
		}
	}
	if (j>T.length)//如果子串在主串中完全匹配，则j的值一定是大于子串的长度的
		return i-T.length;
	else
		return 0;
}

//求next数组
void get_next(SString T,int &next[]){
    int i=1;
    next[1]=0;
    int j=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;
            ++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

//KMP算法完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxSize 255
int next[MaxSize + 1], nextval[MaxSize + 1];

typedef struct {
	char ch[MaxSize + 1];
	int length;
}SString;

void get_next(SString T, int *next) {
	int i = 1;
	next[1] = 0;
	int j = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j];
	}
}
int KMP(SString S, SString T) {
	int i = 1, j = 1;
	while (i<=S.length&&j<=T.length) {
		if (j == 0 || S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			j = next[j];
		}
	}
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

int main()
{
	SString S, T;
	printf("请输入主串:");
	gets_s(S.ch);
	S.length = strlen(S.ch);
	printf("请输入子串:");
	gets_s(T.ch);
	T.length = strlen(T.ch);
	get_next(T, next);
	printf("%d",KMP(S, T));
	
	
	return 0;
}

int Index(SString S, SString T,int pos) {
	int i = pos, j = 1;
	while (i <= S.length&&j <= T.length) {
		if (j==0||S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			j=nextval[j];   /*i不变，j后退*/
		}
	}
	if (j>T.length)//如果子串在主串中完全匹配，则j的值一定是大于子串的长度的
		return i-T.length;
	else
		return 0;
}

//求next数组
void get_next(SString T,int &next[]){
    int i=1;
    next[1]=0;
    int j=0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;
            ++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

//基于next数组，求nextval数组
void get_nextval(){
    nextval[1]=0;
    for(int j=2;j<=T.length;j++){
        if(T.ch[next[j]]==T.ch[j])
            nextval[j]=nextval[next[j]];
        else
            nextval[j]=next[j];
    }
}

树的定义：

树是n(n>=0)个结点的有限集。

​ 若n=0，称为空树；

​ 若n>0，则它满足如下两个条件：

​ ①有且仅有一个特定的称为根的结点；

​ ②其余结点可分为m(m>=0)个互不相交的有限集，其中每一个集合本身又是一棵树，并称为根的子树。

树的基本术语：

根结点：非空树中无前驱结点的结点

结点的度：结点拥有的子树树。

树的度：树内各结点的度的最大值

叶子结点：度为0的结点，也叫终端结点

分支结点：度不为0的结点，也叫非终端结点。根节点以外的分支结点称为内部结点。

结点的子树的根称为该结点的孩子，该结点称为孩子的双亲

结点的祖先：从根到该结点所经过的分支上的所有的结点。

兄弟结点：拥有同一个双亲结点的结点之间称为兄弟结点。

堂兄弟：双亲在同一层的结点。

树的深度：树中结点的最大层次。

有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。

无需树：树中结点的各子树无次序。

森林：是m(m>=0)颗互不相交的树的集合。（把根结点删了就成了森林，一棵树也可以看成是一个特殊的森林）。

线性结构和树结构的比较：

• 线性结构：一对一
• 树结构：一对多

为何要重点研究二叉树：

• 二叉树的结构最简单，规律性最强
• 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

普通树（多叉树）若不转化为二叉树，则运算很难实现。

二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何数都可以与二叉树相互转换 ，这样就解决了树的存储结构及其在运算中存在的复杂性。

二叉树的定义：

二叉树是n(n>=0)个结点的有限集，它或者是空集(n=0),或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。

二叉树的特点：

• 每个结点做多有两个孩子（二叉树中不存在度大于2的结点）。
• 子树有左右之分，其次序不能颠倒。
• 二叉树可以是空集合，根可以有空的左子树或空的右子树。

注：二叉树不是树的特殊情况，他们是两个概念

二叉树结点的子树要区分左子树和右子树，即使只有一颗子树也要进行区分，说明它是左子树还是右子树。

树当结点只有一个孩子时，就无需区分它是左还是右的次序。因此二者是不同的，这是二叉树与树的最主要的差别。

1. 在二叉树的第i层上至多有2^(i-1)个结点（i>=1)。（第i层至少有1个结点）
2. 深度为k的二叉树至多有(2^k )- 1个结点（k>=1)。（深度为k时至少有k个结点）
3. 对任何一颗二叉树T,如果其叶子树为n0,度为2的结点数为n2,则n0=n2 + 1。
4. 具有n个结点的完全二叉树的深度为log2^n向下取整+1
5. 如果对一棵有n个结点的完全二叉树（深度为log2^n向下取整+1）的结点按层序编号（从第1层到 log 2^n向下取整+1层，每层从左到右），则对任意结点i（1<=i<=n），有：
   • 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点 i/2 的向下取整
   • 如果2i>n，则结点i为叶子结点，无左孩子；否则，其右孩子是结点2i
   • 如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1

两种特殊形式的二叉树：

• 满二插树：一棵深度为k且有(2^k) -1个结点的二叉树称为满二叉树。

  • 特点：①每一层上的结点数都是最大结点数（每层都满）

    ​ ②叶子结点全部在最底层

• 完全二叉树：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。

  • 特点：①叶子只可能分布在层次最大的两层上。

    ​ ②对任意结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1

注：①在满二叉树中，从最又一个结点开始，连续去掉任意个结点，即是一颗完全二叉树。一定是连续去掉！！！！！

​ ②满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

为什么要研究这两种特殊形式的二叉树？

• 因为它们在顺序存储方式下可以复原！

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。适合存放满二叉树和完全二叉树

typedef struct Bitree{
    Elemtype data[MaxSize];
    int length;
}BiTree;

①二叉链表

//定义
typedef struct BiNode{
    TelemType data;
    struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;

②三叉链表

//定义
typedef struct TriTNode{
    TelemType data;
    struct TriTNode *lchild,*parent,*rchild;//左右孩子指针,双亲结点指针
}TriTNode,*TriTTree;

常用以下三种遍历方法：

若二叉树为空，则空操作；否则：①访问根节点；②先序遍历左子树；③先序遍历右子树（递归操作）

typedef struct BiNode{
    TelemType data;
    struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;

int PreOrderTraverse(BiTree T){
    if(T!=NULL){
        printf("%c ",T->data);//输出根节点
        PreOrderTraverse(T->Lchild);//递归遍历左子树
        PreOrderTraverse(T->Rchild);//递归遍历右子树
        return 1;
    }
    else
        return 0;
}

若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树（递归操作）

typedef struct BiNode{
    TelemType data;
    struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;

int InOrederTraverse(BiTree T){
    if(T!=NULL){
        InOrderTraverse(T->Lchild);
        printf("%c ",T->data);
        InOrderTraverse(T->Rchild);
        return 1;
    }
    else
        return 0;
}

若二叉树为空，则空操作；否则：①后序遍历左子树；②后序遍历右子树；③访问根节点（递归操作）

int PostOrderTraverse(BiTeen T){
    if(T!=NULL){
        PostOrderTraverse(T->Lchild);
        PostOrderTraverse(T->Rchild);
        printf("%c ",T->data);
    }
}

//二叉树的遍历完整代码 
#include <stdio.h>
#include <stdlib.h>

typedef struct BiNode {
	char data;
	struct BiNode *Lchild, *Rchild;
}BiNode, *BiTree;
//先序建立二叉树
BiNode* CreateBiTree_Pro(BiTree &p) {
	char data;
	scanf("%c", &data);
	if (data != '#') {
		p = (BiNode *)malloc(sizeof(BiNode));
		p->data = data;
		p->Lchild = CreateBiTree_Pro(p->Lchild);
		p->Rchild = CreateBiTree_Pro(p->Rchild);
	}
	else {
		p = NULL;
	}
	return p;

}
//先序遍历(递归)
void PreOrderTraverse(BiT