数据结构C描述（专插本笔记）
数据结构数据结构、数据类型、抽象数据类型数组结构记录结构用C语言描述数据结构与算法变量和指针1、变量：- 变量名：适用于标识变量的符号- 地址：是变量所占据的存储单元的地址。变量的地址属性也称左值- 大小：指该变量所占据的存储空间的数量- 类型：是指变量所取的值域及对变量所能执行的运算集- 值：是指变量所占据的存储单元中的内容。其意义由变量的类型决定- 生命周期：是指执行程序期间变量存在的时段-
数据元素和数据项
数据元素是数据的基本单位：也成为元素、记录、结点、顶点
数据项是构成数据元素的不可分割的最小单位
数据对象是性质相同的数据的集合，是数据的一个子集。
数据结构
数据元素不是孤立存在的，它们之间存在着某种关系，数据元素相互之间的关系成为结构。
是指相互之间存在一种或多种特定关系的数据元素集合
数据结构包括以下三个方面的内容：
- 1、数据元素之间的逻辑关系，也称为逻辑结构。
- 2、数据元素及其关系在计算机内存中的标识（又称为映像），称为数据的物理结构或数据的存储结构。
- 3、数据的运算和实现，即对数据元素可以施加的操作以及这些操作在响应的存储结构上的实现。
逻辑结构与存储结构的关系：
- 存储结构是逻辑关系的映射与元素本身的映象。
- 逻辑结构是数据结构的抽象，存储结构是数据结构的实现。
- 二者集合起来建立了数据元素之间的结构关系
逻辑结构的种类
一、按结构划分
1、线性结构：有且仅有一个开始和一个终端结点，并且所有结点最多只有一个直接前驱和一个直接后继。
例如：线性表、栈、队列、串
2、非线性结构：一个结点可能有多个直接前驱和直接后继
例如：树、图
二、按元素关系划分
1、集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系。
2、线性结构：结构中的数据元素之间存在着一对一的线性关系。
3、树形结构：结构中的数据元素之间存在着一对多的层次关系。
4、图状结构或网状结构：结构中的元素之间存在着多对多的任意关系。
存储结构
1、顺序存储结构
用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示（C语言用数组来实现顺序存储）
2、链式存储结构
用任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示（C语言中用指针来实现链式存储结构）
3、索引存储结构
在存储结点信息的同时，还建立附加的索引表。
4、散列存储结构
根据结点的关键字直接计算出该结点的存储地址
数据结构、数据类型、抽象数据类型
1、数据类型：程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。
例如：C语言中提供的：
- int，char,float,double等基本数据类型
- 数组、结构、共用体、枚举等构造数据类型
- 指针、空类型（void）
- 也可以用typedef自己定义数据类型
一些最基本数据结构可以用数据类型来实现，如数组、字符串等；
而一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示
数据类型的作用：
1、约束变量或常量的取值范围
2、约束变量或常量的操作
数据类型
定义：数据类型是一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称
数据类型=值的集合+值集合上的一组操作
抽象数据类型
定义：指一个数学模型以及定义在此数学模型上的一组操作。
- 由用户定义，从问题抽象出数据模型（逻辑结构）
- 包括定义在数据模型上的一组抽象运算（相关操作）
- 不考虑计算机内的具体存储结构与运算的具体实现算法
抽象数据类型的形式定义：
抽象数据类型可用（D、S、P）三元组表示，其中：
D是数据对象；S是D上的关系集；P是对D的基本操作集
抽象数据类型的定义格式（类比java中的对象实体+接口方法）：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
数据操作：<数据操作的定义>
}ADT 抽象数据类型名
基本操作定义格式说明：
参数表：赋值参数只为操作提供输入值。（引用参数以&打头，除了可提供输入值外，还将返回操作结果）
初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回响应出错信息。若初始条件为空，则省略。
操作结果：说明操作正常完成之后，数据结构的变化状况和对应的返回结果。
eg：抽象数据类型“复数”的实现
typedef struct{
float realpart;/*实部*/
float imagpart;/*虚部*/
}Complex/*定义复数抽象类型*/
数组结构
记录结构
。
算法
定义：算法就是对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令标识一个或多个操作。
流程图、伪代码、程序代码
算法与程序
算法是解决问题的一种方法或过程，考虑如何将输入转换为输出，一个问题可以有多种算法
程序是用某种程序设计语言对算法的具体实现
算法的特性：一个算法必须具备以下五个重要特性：
- 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
- 确定性：算法中的每一条指令必须有确切的含义，没有歧义性。在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
- 可行性：算法是可执行的。
- 输入：一个算法有零个或多个输入。
- 输出：一个算法有一个或多个输出。
算法设计的要求
- 正确性
- 可读性
- 健壮性
- 高效性
满足以上四个方面的情况下，主要考虑***算法的效率***，通过算法的效率高低来评判不同算法的优劣程度。
算法效率从两个方面考虑：
- 时间效率：指的是算法所耗费的时间；
- 空间效率：指的是算法执行过程中所耗费的存储空间；
算法时间效率的度量：
算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。
度量方式：
- 1、事后统计
将算法实现，测算其时间和空间开销；
缺点：所得实验结果依赖于计算机的软硬件等环境因素
- 2、事前统计
对算法所消耗的资源一种估算方法。
为了方便比较不同算法的时间效率，我们仅比较它们的数量级。
时间复杂度数量级高的效率越差
算法中基本语句重复执行的次数是问题规模n的某个函数F(n), 算法的时间量度记作：T(n)=O(f(n))
基本语句：
- 算法中重复执行次数和算法的执行时间成正比的语句
- 对算法运行时间贡献最大
- 执行次数最多
分析算法时间复杂度的基本方法
忽略所有低次幂和最高次幂系数，体现出增长率的含义
时间复杂度是由嵌套层次最深语句的频率决定的
- 1、找出语句频度最大的那条语句作为基本语句
- 2、计算基本语句的频度得到问题规模n的某个函数f(n)
- 3、取其数量级用符号“O”表示
- 一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。
对于复杂的算法，可以将它分成几个容易估算的部分，然后利用O加法法则和乘法法则，计算算法的复杂度：
- a、加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
- b、乘法规则：T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
算法时间的效率比较：
- 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。
渐进空间复杂度：
空间复杂度：算法所需存储空间的度量，记做：S(n)=O(f(n)),其中n为问题的规模。
算法要占据的空间：
- 算法本身要占据的空间：输入/输出，指令，常数，变量等。
- 算法要使用的辅助空间
线性表
一、线性表的定义和特点
线性表：具有相同特性的数据元素的一个有限序列
由n(n>=0)个数据元素(结点)a1,a2,a3…,an组成的有限序列
- 其中数据元素的个数n定义为表的长度
- 当n=0时成为空表
- 将非空的线性表(n>0)记做:(a1,a2,…an)
- 这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同的情况下可以不同
顺序存储结构存在问题：
存储空间分配不灵活
运算的空间复杂度高
链式存储结构
线性表
抽象数据类型线性表的定义：
ADT List{
数据对象：D={ai | ai属于Elemset，（i=1,2,3,4,....n,n>=0）}
数据关系：R={}
基本操作：
}ADT List
基本操作
- InitList(&L):操作结果：构造一个空的线性表L
- DestroyList(&L):
- 初始条件：线性表L已经存在
- 操作结果：销毁线性表L - ClearList(&L):
- 初始条件：线性表L已经存在
- 操作结果：将线性表L重置为空表 - ListEmpty(L)
- 初始条件：线性表L已经存在
- 操作结果：若线性表L为空表，则返回Ture；否则返回False - ListLength(L)
- 初始条件：线性表L已经存在
- 操作结果：返回线性表L中的元素个数 - GetElem(L,i,&e):
- 初始条件：线性表L已经存在，1<=i<=ListLength(L)
- 操作结果：用e返回线性表L中第i个元素的值 - LocateElem(L,e,compare()):
- 初始条件：线性表L已经存在，compare()是数据元素判定函数
- 操作结果：返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在在返回值为0. - PriorElem(L,cur_e,&pre_e):
- 初始条件：线性表L已经存在
- 操作结果：若cur_e是L的元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e无意义 - ListInsert(&L,i,e):
- 初始条件：线性表L已经存在，1<=i<=ListLength(L)+1
- 操作结果：在L的第i个位置之前插入新的数据元素e,L的长度加1 - ListDelete(&L,i,&e):
- 初始条件：线性表L已经存在，1<=i<=ListLength(L)
- 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1. - ListTraverse(&L,visited()):遍历
- 初始条件：线性表L已经存在
- 操作结果：依次对线性表中每个元素调用visited()
以上的运算是逻辑结构上定义的运算。只要给出这些运算的功能是“做什么”，至于“怎么做”等实现细节，只有待确定了存储结构之后才考虑
线性表的存储结构
- 顺序存储结构
线性表的顺序表示又称为顺序存储结构或顺序映象
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
*** 线性表顺序存储结构必须占用一片连续的存储空间，知道某个元素的存储位置就可以计算其他元素的存储位置。***
*** 顺序表的特定：以物理位置相邻表示逻辑关系，任意元素均可随机存取***
线性表的实现
补充
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
1、C语言的内存动态分配
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);//按ElemType类型将sizeof(ElemType)*MaxSize大小的内存分为n个ElemType空间
- malloc(m)函数，开辟m字节长度的地址空间，并返回这段空间的首地址
- sizeof(x)运算：计算变量x的长度
- free§函数：释放指针p所指变量的存储空间，彻底删除一个变量
- 需要加载头文件<stdlib.h>
2、C++语言的内存动态分配
eg：int *p1 = new int ;或 int *p1 = new int(10)；
函数调用时传送给形参表的实参表必须与形参表三个一致：类型、个数、顺序
参数传递有两种方式：
- 传值（参数为基本数据类型）
- 传地址（参数为指针变量、引用类型、数组）
引用类型作形参的两点说明
- 传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。
- 引用类型作形参，在内存中并没有产生实参副本，它直接对实参操作；而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量比较大时，用引用比用一般变量传递参数的时间和空间效率都好。
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
typedef struct {
ElemType* elem;
int length;
}SqList;
Status InitList_Sq(SqList *L) {//构造一个空的顺序表L
L->elem = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);//为顺序表分配空间
if (!L->elem)exit(OVERFLOW); //存储分配失败
L->length = 0; //空表长度为0
return OK;
};
//销毁线性表L
void DestroyList(SqList *L) {
if (L->elem) free(L->elem);
}
//清空线性表L
void ClearList(SqList* L) {
L->length = 0;
}
//求线性表L的长度
int GetLength(SqList L) {
return(L.length);
}
//判断线性表是否为空
int IsEmpty(SqList L) {
if (L.length==0) {
return 1;
}
else {
return 0;
}
}
- 线性表长度可变（增加或者删除）
- 数组长度不可动态定义：C语言不允许对数组的大小作动态定义
用一个变量表示顺序表的长度属性
顺序表结构类型：
#define LIST_INIT_SIZE 100
typedef struct{
ElemType elem[List_INIT_SIZE];
int length;//表示长度的变量
}SqList;
多项式的顺序存储结构类型定义：
#define MAXSIZE 1000//多项式可能达到的最大长度
typedef struct{//多项式非零项的定义
float p;//系数
int e;//指数
}Polynomial;
typedef struct{
Polynomial *elem; //存储空间的基地址
int length;//多项式中当前项的个数
}SqList;//多项式的顺序存储结构类型为SQList
线性表的基本操作实现
- 顺序表的取值（根据位置i获取相应位置元素的内容）
int GetElem(SqList L,int i,ElemType &e){//C++引用类型传值方法
if(i<1||i>L.length)return ERROR;//判断i值是否合理，若不合理，返回ERROR
e = L.elem[i-1];
return OK;
}
//顺序表的查找
//在线性表L中查找与指定值e相同的数据元素的位置
//从表的一段开始，逐个进行记录的关键字和给定值的比较。找到该值，返回该元素的位置序号，未找到返回0
int LocateElem(SqList L,ElemType e){
//在线性表中查找值为e的数据元素，返回其序号
for(int i=0;i<L.length;i++){
if(L.elem[i]==e){
return i+1;//查找成功，返回下标
}
}
return 0;//查找失败，返回0
}
顺序表的查找算法：平均查找长度ASL，为确定记录在表中的位子，需要给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。
顺序表的插入
Status ListInsert_Sq(SqList *L,int i,ElemType e){//在第i位插入e
if(i<1||i>L->length+1)return ERROR;//判断插入的位置是否合理
if(L->length==MAXSIZE)return ERROR;//判断顺序表是否已经满了
for(int j = L->length-1;j>=i-1;j--){//遍历将下标为i-1及其后面的元素往后移动
L->elem[j+1]=L->elem[j];//时间复杂度n/2
}
L->elem[i-1]=e;//将元素插入空出来的i-1位置
L->length++;//长度加1
return OK;
}
顺序表的删除
Status DeletList(SqList *L,int i){
if(i<1||i>L->length+1)return ERROR;
for(j=i;j<=L-length-1;j++){//遍历，将下标为i-1后面的元素往前移动一位
L->elem[j-1] = L->elem[j];
}
L->length--;
return OK;
}
- 链式存储结构
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
线性表的链式表示又称为非顺序映象或链式映象
链式存储结构各个节点由两个域组成：1、数据域：存储元素数值数据 2、指针域：存储直接后继节点的存储位置
与链式存储有关的术语
- 结点：数据元素的存储映象。由数据域和指针域两部分组成
- 链表：n个结点由指针链组成一个链表。
它是线性表的链式存储映象，称为线性表的链式存储结构
单链表、双链表、循环链表：
单链表：结点只有一个指针域的链表，称为**单链表**或**线性链表**
双链表：结点由两个指针域的链表，称为**双链表**
循环链表：首尾相接的链表称为**循环链表**
在链表中设置头结点有什么好处？
- 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理。
- 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和费控表的处理也就统一了。
头结点的数据域内装的是什么？
- 头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。
链表（链式存储结构）的特点
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时只能通过头指针进入链表，并通过每个结点的指针域一次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。（顺序存取法O(n)）
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L
单链表存储结构的定义：
typedef struct Lnode { //声明节点的类型和指向节点的指针类型
ElemType data; //结点的数据域
struct Lnode *next; //结点的指针域
}Lnode,*LinkList; //LinkList为指向结构体Lnode的指针类型
单链表的初始化（带头结点的单链表）：即构造一个空表
- 生成新的节点作头结点，用头指正L指向头结点
- 将头结点的指正域置空
算法描述：
Status InitList(LinkList &L){
//L = new LNode;//C++语法
L=(LinkList)malloc(sizeof(Lnode));//C语法
//------都是从内存中开辟一块空间-----
L->next = NULL;
return OK;
}
判断单链表是否为空：
空表：链表中无元素，成为空链表（头指针和头节点仍然在）
【算法描述】
int LIstEmpty(LinkList L){
if(L->next){//判断是否为null
return 0;
}else{
return 1;
}
}
单链表的销毁
链表销毁后不存在
思路：从头指针开始，依次释放所有结点
【算法描述】
Status DestroyList_L(LinkList L) {
LinkList P;
while (L) {
P = L;
L = L->next;
free(P);
}
return OK;
}
清空链表：
链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然存在）
思路：依次释放所有结点，并将头结点指正域设置为空
【算法描述】
Status xxx(LinkList L){
Lnode *p,*q;
p = L->next;
while(p){
q = p -> next;
free(p);
p=q;
}
L->next = null;
return OK;
}
求链表的表长
思路：从首元结点开始，依次计数所有结点
【算法描述】
int ListLength_L(LinkList L) {
int i = 0;
LinkList P = L->next;
while (P) {
i++;
P = P->next;
}
return i;
}
取值–取单链表中第i个元素的内容
思路：从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止，因此，链表不是随机存储结构
- 从第1个结点(L->next)顺链扫描，用指针P指向当前扫描到的结点，P初始值P=L->next
- 定义j做计数器，累计当前扫描过的结点数，j初始值为1
- 当P指向扫描到的下一个结点时，计数器j+1
- 当j==i时，P所指的结点就是要找的第i个结点，取出该结点的data域的值
-
Status GetElem(LinkList L,int i) {
LinkList P = L->next;//
int j = 1;
while (P&&j<i) {
P = P->next;
++j;
}
if (!P||j>i) {
return ERROR;
}
return P->data;
}
按值查找—根据指定数据获取该数据所在为位置（或地址）
//返回地址值
Lnode *LocateElem_L(LinkList L,Elemtype e){
//在线性表L中查找值为e的数据元素
//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
LinkList P = L->next;
while(p&&p->data!=e){//如果p为空或者p的data==e都直接返回
p=p->next;
}
return p;
}
//返回位置
int LocateElem_L(LinkList L,ElemType e){
LinkList p = L->next;
int i = 1;
while(p&&p->data!=e){//停止循环有两个情况，1、p为空，2、p的data==e
p=p->next;
i++;
}
if(p){
return i;
}else{
return 0;
}
}
插入—在第i个结点前插入值为e的新结点
【算法步骤】
1、首先找到ai-1的存储位置p
2、生成一个数据域为e的新节点s
3、插入新结点：①新结点的指针域指向结点ai
②结点ai-1的指针域指向新结点
【算法描述】
Status ListInsert(LinkList L,int i,ElemType e){
LinkList p=L;int j = 0;
while(p&&j<i-1){
p = p->next;
j++;
}
if(!p||j>i-1){//i大于表长+1或者小1，插入位置非法
return ERROR;
}
LinkList s=(LikeList)malloc(sizeof(Lnode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
删除–删除第i个结点
【算法步骤】
1、首先找到ai-1的存储位置P（如果有需要，保存要删除的a的值）
2、令P->next指向ai+1
【算法描述】
Status ListDelete_L(LinkList L,int i){
LinkList p = L;
int j = 0;
while(p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱
p = p->next;
j++;
}
if(!(p->next)||j>i-1){//删除的位置不合理
return ERROR;
}
q = p->next;//临时保存被删除结点的地址以备释放
p->next = q->next;//改变结点前驱结点的指针域
e = q->data;//保存删除结点的数据域
free(q);//释放删除结点的空间
return OK
}
单链表的查找、插入、删除算法时间效率分析
1、查找：因为线性表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)
2、插入和删除：因为线性链表不需要移动元素，只需要修改指针，修改的时间复杂度是O(1)。但进行插入或者删除都要先找到前驱结点，所以消耗的时间复杂度为O(n)
建立单链表：头插法–元素插入在链表头部，也叫前插法
1、从一个空表开始，重复读入数据
2、生成新结点，将读入数据存放到新结点的数据域中
3、从最后一个结点开始，依次将各结点插入到链表的前端
【算法描述】
void CreateList_H(int n){
LinkList L = (LinkList)malloc(sizeof(Lnode));
L->next = NULL;//先建立一个带头结点的单链表
for(int i = n;i>0;i--){
LinkList p = (LinkList)malloc(sizeof(Lnode));
scanf(p->data);//输入元素值、C++描述：cin>>p->data；
p->next = L->next;
L->next = p;
}
}
建立单链表：尾插法—元素插入在链表尾部
1、从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
2、初始化时，r同L均指向头结点。每读入一个元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点
【算法描述】
void CreateList_R(int n){
LinkList L = (LinkList)malloc(sizeof(Lnode));
L->next = NULL;
LinkList r = L;
for(int i = 0;i<n;i++){
LinkList p = (LinkList)malloc(sizeof(Lnode));//生成新结点
scanf("%d",p->data);//为新结点赋值
p->next = NULL;
r->next = p;
r=p;
}
}
循环链表
循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）
优点：从表中任一结点出发，均可找到表中其他结点。
注意：
由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件不再像非循环链表那样判断p或p->next是否为空，而是判断他们是否等于头指针
带尾指针循环链表的合并
【算法描述】
LinkList Connect(LinkList Ta,LinkList Tb){
//假设Ta、Tb都是非空的单循环链表
p = Ta->next; //P存表头结点
Ta->next = Tb->next->next;//Tb表头连接Ta表尾
free(Tb->next);//释放Tb表头结点
return Tb;
}
//时间复杂度O(1)
双向链表
双向链表的结构定义如下
单循环链表
双循环链表
- 让头结点的前驱指针指向链表的最后一个结点
- 让最后一个结点的后继指针指向头结点
typedef struct DuLNode{
Elemtype data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
双向链表结构的对称性（设指针P指向某一结点）：
P->prior->next = P = P->next->prior
双向链表的插入
void ListInsert_DuL(DuLinkList L,int i,ElemType e){
//在带头结点的双向循环链表L中第i个位置之前插入元素e
DuLinkList p = GetElem_DuL(L,i)
if(!p){
return ERROR;
}
s = (DuLinkList)malloc(size(DuLNode));
s->data = e;
s->prior = p->prior;
p->prior-next = s;
s->next = p;
p->prior = s;
return OK;
}
双向链表的删除
【算法描述】
void ListDelete_Dul(DuLinkList L,int i){
//删除带头结点的双向循环链表L的第i个元素，并用e返回
DuLinkList p = GetElemP_Dul(L,i);
if(!p){
return ERROR;
}
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
顺序表和链表的比较
- 链式存储结构的优点：
- 结点空间可以动态申请和释放；
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
- 链式存储结构的缺点：
- 储存密度小，每个结点的指正域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占储存空间的比重显得很大。
- 链式存储结构是非随机存取结构，对任意结点的操作都需要从头指针根据指针链找到该结点，这增加了算法的负责度。
存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比：
线性表的应用
线性表的合并
- 问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=A∪B
- La=(7,5,3,11) Lb=(2,6,3)---------->La=(7,5,3,11,2,6)
【算法步骤】
依次取出Lb中的每个元素，执行以下操作：
1、在La中查找该元素
2、如果找不到，则将其插入La的最后
【算法描述】
void union(List La,List Lb){
La_len = ListLength(La);
Lb_len = ListLength(Lb);
for(int i = 1;i<=Lb;i++){
ElemType e = GetElem(Lb,i);
if(!LocateElem(La,e)){
ListInsert(La,++La_len,e);
}
}
}
有序表的合并–用顺序表实现
- 问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减(元素不唯一称为非递减)有序排列。
- La=（1,7,8） Lb=(2,4,6,8,10,11)--------------------------->Lc=(1,2,4,6,7,8,8,10,11)
【算法步骤】
1、创建一个空表Lc
2、依次从La或Lb中获取元素值较小的节点插入到Lc表中的最后，直至其中一个表边空为止
3、继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
【算法描述】
void MergeList_Sq(SqList La,SqList Lb){
elemType* pa = La.elem;//指针pa、pb分别指向两个表的第一个元素
elemType* pb = Lb.elem;
Lc_length = pa+pb;//新表长度为待合并两表的长度之和
SqList Lc = (SqList)malloc(sizeof(SqList));//创建新表
Lc.elem = (ElemType)malloc(sizeof(ElemType)*Lc.Length);//为新表分配一个数组空间
elemType* pc = Lc.elem;//指针pc指向新表的第一个元素
elemType* pa_last = LA.elem+La.length-1;//指向两个表元素的指针
elemType* pb_last = Lb.elem+Lb.length-1
while(pa<=pa_last&&pb<=pb_last){//两个表都未非空情况
if(*pa<=*pb)*pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa<=pa_last){//当b表为空时，是需要操作a表
*pc++ = *pa++;
}
while(pb<=pb_last){//当a表为空时，是需要操作b表
*pc++ = *pb++;
}
}
有序表的合并–用链表实现
【算法描述】
void MergeList_L(LinkList La,LinkList Lb){
LinkList pa = La->next;
LinkList pb = Lb->next;
LinkList pc = La;//用La的头结点作为Lc的头结点
LinkList Lc = pc;
while(pa&&pb){
if(pa->data<=pb->data){//如果pa小于pb
pc->next = pa;
pc = pa;
pa = pa->next;
}else{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa?pa:pb;//如果pa还有元素，则将pa剩下的连接到LC。反之亦然
free(Lb);
}
//时间复杂度O(Length(La)+Length(Lb))
栈和队列
- 栈和队列是两种常用的、重要的数据结构
- 栈和队列是限定插入和删除只能在标的 **端点** 进行的**线性表**
栈的应用
由于栈的操作具有后进先出的固有特性，使得栈成为程序设计中的有用工具。
- 如果问题求解的过程具有“后进先出”的天然特性的话，则求解的算法中必然需要利用栈。
eg：
- 数制转换 - 表达式求值（算符优先级）
- 括号匹配的检验（左括号入栈，右括号匹配栈顶元素） - 八皇后问题
- 行编辑程序 - 函数调用
- 迷宫求解 - 递归函数的实现
栈的定义
栈（stack）是一种特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表。
又称为后进先出的线性表，简称LIFO结构
- 栈是仅在表尾进行插入、删除操作的线性表。
- 表尾称为栈顶TOP；表头称为栈底Base
- 插入元素到栈顶（即表尾）的操作，称为入栈
- 从栈顶（表尾）删除最后一个元素的操作，称为出栈
- 入 = 压入 = PUSH(x)
- 出 = 弹出 = POP(y)
- 逻辑结构：与线性表相同，仍为一对一关系
- 存储结构：用顺序栈和链栈存储，但顺序栈更常见
- 运算规则：只能在栈顶运算，且访问结点时依照后进先出的原则（与一般线性表的区别）
- 实现方法：关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同
案例----------------------------------------------------------------------------------------------------------------------------------------
1、进制转换
十进制整数N向其他进制数d（二、八、十六）的转换是计算机实现计算的基本问题
- 转换法则：N除以d取余
eg：把十进制159转换为八进制数
2、表达式的组成：
- 操作数：常数、变量
- 运算符：算数运算符、关系运算符和逻辑运算符
- 界限符：左右括弧和表达式结束符
任何一个算数表达式都由操作数(常数、变量)、运算符(+、-、*、/)和界限符(括号、表达式结束符"#"、虚设的表达式起始符“#”)组成。后两者统称为算符。
--------------------------------------------------------------------------------栈案例结束--------------------------------------------------------
栈的抽象数据类型定义
ADT Stack{
数据对象：D={ai|ai∈ElemSet,i = 1,2,.....,n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,.....,n}
约定an端为栈顶，a1端为栈底
基本操作：初始化、进栈、出栈、取栈顶元素
}ADT Stack
- 用顺序表实现：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端
- 附设top指针，指示栈顶元素在顺序栈中的位置
- base指正：指示栈底元素在顺序栈中的位置
一般为了操作方便，通常top指示真正的栈顶元素之上的下表地址
- 另外，用stacksize表示栈可使用的最大容量，最多可存放到下标为stacksize-1的元素
- 空栈：base == top
- 栈满：top-base == stack
栈满时的处理方法：
1、报错，返回操作系统
2、分配更大空间，作为栈的存储空间。将原栈的内容移入新栈
使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出（数组大小固定）
**上溢：**栈已经满，又要压入元素
**下溢：**栈已经空，还要弹出元素
顺序栈的表示
define MAXSIZE 100
typedef struct{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈最大可用空间
}SqStack;
顺序栈的初始化
Status InitStack(SqStack *s){
s.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
if(!s.base)exit(OVERFLOW);//存储分配失败
s.top = s.base;//栈顶指针等于栈底指针
s.stacksize = MAXSIZE;
return OK;
}
判断顺序栈是否为空
Status StackEmpty(SqStack S){
if(S->top == S->base){
return TRUE;
}else{
return FALSE;
}
}
求顺序栈的长度
int StackLength(SqStack S){
return S- >top - S->base;
}
清空栈
void ClearStack(SqStack S){
if(S->base){
S->top = S->base;
return OK;
}
}
销毁顺序栈
Status DestroyStack(SqStack S){
if(S->base){
free(S->base);
S->stacksize = 0;
S->base = S->top =0;
}
return OK;
}
**顺序栈的入栈 **
【分析】
1、判断是否栈满，若满则出错（上溢）
2、元素e压入栈顶
3、栈顶指针加1
Status Push(SqStatus S,SElemType e){
if(S->top - S->base == S->stacksize){
return ERROR;
}
*S->top++ = e;
return OK;
}
顺序栈的出栈
[分析]
1、判断是否栈空，若空则出错（下溢）
2、获取栈顶元素e
3、栈顶指针减1
SElemType Pop(SqStack S){
if(S->top == S->base){
return ERROR;
}
S->top--;//因为top指在栈顶+1的位置，所以需要向下移动一位才可以找到栈顶元素
SElemType e = *S->top;
return e;
}
——————————————————顺序栈结束——————————————————————
链栈的表示
-链栈是运算受限的单链表，只能在链表头部进行操作
typedef struct StackNode{//栈的节点类型
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;
- 链表的头指针就是栈顶
- 不需要头结点
- 基本不存在栈满的情况
- 空栈相当于头指针指向空
- 插入和删除仅在栈顶处执行
链栈的初始化
void InitStack(LinkStack S){
//构造一个空栈，栈顶指针置为空
S=NULL;
return OK;
}
判断链栈是否为空
Status StackEmpty(LinkStack S){
if(S==NULL){
return TRUE;
}else{
return FALSE;
}
}
链栈入栈
Status Push(LinkStack S,SElemType e){
LinkStack p = (LinkStack)malloc(sizeof(StackNode));
p->next = S;
p->data = e;
S=p;
return OK;
}
链栈出栈
Status Pop(LinkStack S) {
if (S==NULL) {
return ERROR;
}
int e = S->data;
LinkStack p = S;
S=S->next;
free(p);
return OK;
}
-——————————————链栈结束————————————————
递归
若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；
若一个过程直接或者间接地调用自己，则称这个过程是递归的过程。
以下三种情况常常用到递归方法：
- 递归定义的数学函数
- 具有递归性质的数据结构
- 可递归求解的问题
递归问题——分治法求解
分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
必备三个条件：
1、能将一个问题转变成一个新问题，而新问题与原问题的揭发相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
2、可以通过上述转化而使问题简化
3、必须有一个明确的递归出口，或称为递归的边界
函数调用过程
调用前，系统完成：
1、将实参，返回地址等传递给被调函数
2、为被调函数的局部变量分配存储区
3、将控制转移到被调用函数的入口
调用后，系统完成：
1、保存被调用函数的计算结果
2、释放被调用函数的数据区
3、依照被调用函数保存的返回地址将控制转移到调用函数
将递归调用的过程看成入栈的过程，当最上面的一次调用达到临界条件时，将结果返回上一层调用。并出栈，直到栈顶的调用出栈并返回的结果就是最终计算结果。
递归程序运行期间使用的数据存储区——递归工作栈
“工作记录”——实际参数，局部变量，返回地址
递归的优缺点：
优点：结构清晰，程序易读。
缺点：每次调用要生成工作记录，保存状态信息，入栈；
返回时要出栈，回复状态信息。时间开销大
方法1：尾递归、单向递归-》循环结构
方法2：自用栈模拟系统的运行时栈
----------------------------栈结束-------------------------------------
队列的应用
由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具。
eg：
- 脱机打印输出：按申请的向后顺序依次输出
- 多用户系统中，多个用户排成队，分时地循环使用CPU和主存
- 按用户的优先级排成多个队，每个优先级一个队列
- 实时控制系统中，信号按接收的先后顺序依次处理
- 网络电文传输，按到达的时间先后顺序依次进行
队列
定义：队列(queue)是一种先进先出（FIFO）的线性表，在表的一端插入（表尾），在另一端（表头）删除。(头删除尾删)
逻辑结构：与线性表相同，一对一关系
存储结构：顺序队或链队，以循环顺序队列更常见
运算规则：只能在队首和队尾运算，且访问结点时依照**先进先出（FIFO）**的原则
实现方式：关键是掌握入队和出队操作，具体实现依据顺序队或链队的不同而不同
插入元素成为入队；删除元素成为出队。
队列的存储结构为链队或顺序队（常用循环顺序队）
队列的顺序存储–用一维数组base[MAXQSIZE]
#define MAXQSIZE 100
typedef struct{
QElemType *base;//初始化的动态分配存储空间
int front;//队头下标
int rear;//队尾下标
}SqQueue;
溢出：当rear=MAXQSIZE时，则称该队列溢出
1、真溢出：当队列中所有空间都已经填满
2、假溢出：队列front前面有空余的空间
解决假溢出的方法：
1、将队中元素依次向队头方向移动
缺点：浪费时间，每次移动都需要移动队中所有元素。
2、将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为MAXQSIZE时，若向量的开始端空着，又可从头使用空着的空间，当front为MAXQSIZE时也一样。
解决假上溢的方法——引入“循环队列”
base[0]接在base[MAXQSIZE-1]之后，若rear+1==M，则令rear=0
实现方法：利用模（mod,C语言中：%）运算
插入元素：Q.base[Q.rear]=x;
Q.rear[Q.rear+1]%MAXQSIZE;
删除元素：x = Q.base[s.front];
Q.front = (Q.front+1)%MAXQSIZE;
循环队列：循环使用为队列分配的存储空间
循环队列中，当队空/队满时，头尾两个指针都会相等。即front=rear
判别队空/队满的方法：
1、另外设一个标志以区别对空、队满。（设置标志指向队尾元素，如果指向为空，则为空。如果不为空队，则是满队）
2、另设一个变量，记录元素的个数
3、少用一个元素空间
Status InitQueue(SqQueue Q) {
Q.base = (QElemType*)malloc(MAXSIZE*sizeof(QElemType));//分配数组空间
if (!Q.base) {
exit(OVERFLOW);//分配失败直接退出
}
Q.front = Q.rear = 0;//队列为空
return OK;
}
循环队列——求队列的长度
【分析】（队尾下标-队头下标+队列的总长度）%队列的总长度
入队
Status EnQueue(SqQueue Q,QElemType e) {
if ((Q.rear+1)%MAXSIZE==Q.front) {
return ERROR;
}
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXSIZE;
return OK;
}
出队
QElemType OutQueue(SqQueue Q) {
if (Q.rear == Q.front) {
return ERROR;
}
QElemType e = Q.base[Q.rear];
Q.front= (Q.front+ 1) % MAXSIZE;//如果只是取头元素的值，则可以不需要移动
return e;
}
链队——队列的链式表示和实现
若用户无法估计所用队列的长度，则需要采用链队列
链队列的类型定义
#define MAXQSIZE 100
typedef struct{
QElemType data;
struct Qnode *next;
}QNode,*QuenePtr;
链式队列
typedef struct{
QuenePtr front;//队头指针
QuenePtr rear;//队尾指针
}LikeQueue;
初始化链队
Status InitQueue(LinkQueue Q) {
Q.front = Q.rear = (QuenePtr)malloc(sizeof(QNode));
if (!Q.front) {
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
销毁链队列
【算法思想】：从队头结点开始，依次释放所有结点
Status DeleteQueue(LinkQueue Q) {
QuenePtr P;
while (Q.front->next) {
P = Q.front->next;
free(Q.front);
Q.front = P;
}
return OK;
}
插入新结点
Status InsertQueue(LinkQueue Q,QElemType e) {
QuenePtr node = (QuenePtr)malloc(sizeof(QNode));
if (!node) {
exit(OVERFLOW);
}
node->data = e;
node->next = NULL;
Q.rear = node;
return OK;
}
链队出队
Status OutQueue(LinkQueue Q) {
if (Q.front==Q.rear) {
exit(OVERFLOW);
}
QuenePtr p;
p = Q.front->next;
Q.front->next = p->next;
if (Q.rear==p) {
Q.rear = Q.front;
}
free(p);
return OK;
}
---------------------------------------------------------------------链队结束---------------------------------------------------------------
串、数组和广义表
串
串是0个或多个任意字符组成的有限序列
S = "ABCDEFG..............N"(n>=0)
子串：串中任意个连续字符组成的子序列成为该串的子串
主串：包含子串的串相应地称为主串
字符位置：字符在序列中的序号为该字符串在串中的位置
子串位置：子串第一个字符在主串中的位置
空格串：由一个或多个空格组成的串，与空串不同
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的
所有的空串都是相等的
//顺序串
#define MAXLEN 255
typedef struct {
char ch[MAXLEN+1];//存储串的一维数组
int length;//串的当前长度
}SString;
//链串
#define CHUNKSIZE 80
typedef struct {
char ch[CHUNKSIZE];
struct Chunk* next;
}Chunk;
typedef struct {
Chunk* head, * tail;//串的头指针和尾指针
int curlen;//串的当前长度
}LString;//字符串的快链结构
串的模式匹配算法
算法目的：确定主串中所含子串(模式串)第一次出现的位置(定位)
算法应用：搜索引擎、拼写检查、语言翻译、数据压缩
算法种类：
BF算法(又称古典的、经典的、朴素的、穷举的)：简称为简单匹配算法。采用穷举法的思路
算法的思路是从S的每一个字符开始依次与T的字符进行匹配
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;
}
}
KMP算法(特点：速度快)
-利用已知部分匹配的结果而加快模式串的滑动速度，主串的指针不必回溯，，可提速到O(n+m)
int Index KMP(SString S,SString T,int pos){
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){
return i-T.length;//匹配成功
}else{
return 0;//返回不匹配标志
}
}
数组
按照一定格式排列起来的，具有相同类型的数据元素的集合
结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。
数组特点：结构固定——定义后，维数和维界不再改变。
数组基本操作：除了结构的初始化和销毁外，只有取元素和修改元素值的操作
一般采用顺序存储来表示数组
注意：数组可以是多维的，但存储数据元素的内存单元地址是一维的。因此，在存储数组结构之前，需要解决讲多为关系映射到一维关系的问题。
二维数组可以有两种储存方式：
1、以行序为主序
2、以列序为主序
特殊距阵的压缩存储
矩阵：一个由M*N个元素排成的M行N列的表
矩阵常规储存：将矩阵描述为一个二维数组
矩阵的常规存储特点：
- 可以对其元素进行随机存取
- 矩阵运算非常简单；存储的密度为1
不适宜常规存储的矩阵：值相同的元素很多且呈某种规律分布；零元素多
矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间
1、什么是压缩存储？
若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间
2、什么样的矩阵能够压缩？
一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等
1、对称矩阵
- 特点：在n*n的矩阵a中，满足如下特质：a[i,j]=a[ji](1<=i,j<=n)
- 存储方法：只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。
3、什么是稀疏矩阵
矩阵中非零元素的个数较少（一般小于5%）
三元组顺序表
为更可靠描述，通常再加一个“总体”信息：即总行数，总列数，非零元素总个数
- 三元组顺序表又称有序的双下标法
- 三元组顺序表的优点：非零元素在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算
- 三元组顺序表的缺点：不能随机存取。若按行号存取某一行中的非零元素，则需从头开始进行查找
稀疏矩阵的链式存储结构：十字链表
优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。
在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row,col,value）以外，还要有两个域：
- right:用于链接同一行中的下一个非零元素
- down：用于链接同一列中的下一个非零元素
广义表
广义表（又称列表Lists）是n>=0个元素a[0],a[1],.........a[n-1]的有限序列，其中每一个ai或者是原子，或者是一个广义表
广义表通常记作：LS=（a1,a2,a3......,an),其中：LS为表名，n为标的长度，每一个ai为表的元素。
习惯上，一般用大写字母表示广义表，小写字母表示原子。
表头：若LS非空(n>1),则器第一个元素a1就是表头。记做head(LS)=a1.**表头可以是原子，也可以是子表**
表尾：除表头之外的其他元素组成的表。记做tail(LS)=(a2,.....,an).**表尾不是最后一个元素，而是一个子表**
C=(a,(b,c)):长度为2，由原子a和子表(b,c)构成。表头为a；表尾为((b,c))。
D=(a,b,c):长度为3，每项都是原子。表头为a；表尾为（a,b）。
性质
- 广义表中的数据元素有相对次序；一个直接前驱和一个直接后继
- 广义表的长度定义为最外层所包含元素的个数
- 广义表的深度定义为该广义表展开后所含括号的层数；（原子的深度为0，空表的深度为1）
- 广义表可以为其他广义表共享（被其他广义表包含）；A=(),B=(A)
- 广义表可以是一个递归的表（包含自身）；F=(a,F)
递归表的深度是无穷值，长度是有限值
- 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表。而子表的元素还可以是子表
广义表与线性表的区别
广义表可以看成是线性表的推广，线性表是广义表的特例。
广义表的结构相当灵活，在某种前提下，她可以兼容线性表、数组、树和有向图等各种常用的数据结构
当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。
树和有向图也可以用广义表来表示。
广义表的基本运算
1、求表头GetHead(L):非空广义表的第一个元素，可以是一个原子也可以是一个子表。
2、求表尾GetTail(L):非空广义表除去表头元素以外其他元素构成的表。表尾一定是一个表。
------------------------------------------------------线性结构结束------------------------------------------------------
树型结构
树的定义
树（tree）是n(n>=0)个结点的有限集
若n=0,称为空树；
若n>0，则它满足两个条件：
1、有且仅有一个特定的成为根的节点
2、其余结点可分为m(m>=0)个互不相交的有限集T1、T2、T3.......Tm，其中每一个集合本身又是一棵树，并称为根的子树。
树的基本术语
结点：数据元素以及指向子树的分支
根结点：非空树中无前驱结点的结点（有且仅有一个）
结点的度：结点拥有的子树数
树的度：树内各结点的度的最大值
叶子节点/终端结点：度=0的节点
内部结点：度不等于0的分支结点
根结点以外的分支节点
结点的子树的根成为该结点的孩子，该结点成为孩子的双亲结点
树的深度：树中结点的最大层次
有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）
无序树：树种结点的各子树无次序
森林：是m(m>=0)棵互不相交的树的集合
一棵树可以看成一个特殊的森林
把树的根结点删除，树就变成了森林。给森林的各子节点加上一个共同的双亲结点，森林就变成了树
二叉树
二叉树是n(n>=0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵不相交的树分别称为这个根的左子树和右子树的二叉树组
特点：
1、每个结点最多有两个孩子（二叉树中不存在度大于2的节点）
2、子树有左右之分，其次序不能颠倒
3、二叉树可以是空集合，根可以有空的左子树或者空的右子树
二叉树不是树的特殊情况，它们是两个概念
二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也需要进行区分，说明它是左(右)子树。
树当结点只有一个孩子时，无需区分它是左还是右的次序，因此二者不同。这是二叉树和树的最主要区别
也就是二叉树每个结点位置或者说次序都是固定的，可以是空。但是不可以说它没有位置，而树的节点位置是相对于别的结点来说，没有别的结点时，它就无所谓左右了
二叉树的性质和存储结构
性质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
总边数=总节点数-1
总节点数=度为2的结点数2+度为1的结点数1
两种特殊的二叉树
满二叉树
一棵树深度为k且有2的k次方-1个结点的二叉树成为满二叉树
特点：
1、每一层上的结点数都是最大结点数（每层都满）
2、叶子结点区不在最底层
对满二叉树结点位置进行编号：
编号规则：从根结点开始，自上而下，自左而右
每一个结点位置都有元素
满二叉树在同样深度的二叉树中结点个数最多
满二叉树在同样深度的二叉树中叶子结点个数最多
完全二叉树
深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，称之为完全二叉树。
注：在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。（连续的去掉）
特点：1、叶子只可能分布在层次最大的两层上。
2、对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1
数据的压缩问题
将数据文件转换成由0、1组成的二进制串，称之为编码。
1、等长编码方案 2、不等长编码方案1 3、不等长编码方案2
利用二叉树求解表达式的值
以二叉树表达式的递归定义如下：
1、若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；
2、若表达式为“第一操作数 运算符 第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身又为表达式。
二叉树的顺序存储结构
实现：按满二叉树的节点层次编号，依次存放二叉树中的数据元素。
二叉树的顺序存储缺点：
对坏的情况：深度为k且只有k个结点的单支树需要长度为2的k次方-1的以为数组空间。
特点：结点之间关系蕴含在其存储位置中，适于存满二叉树和完全二叉树
二叉树的链式存储结构
//二叉链表
typedef struct BiTree{
ElemType data;
struct BiTree* Ichild,*Rchild;//左右孩子指针
}BiNode,*BiTree;
//三叉链表
typedef struct TriTNode{
ElemType data;
struct TriTNode *Ichild,*Rchild,*parent;//左右孩子、双亲指针
}TriTNode,*TriTree;
在n个结点的二叉链表中，有n+1个空指正域（空指针数目=2n-（n-1））
【分析】必有2n个链域，除根结点外，每个结点有且仅有一个双亲，所以只会有n-1个结点的链域存放指针，指向非空子女结点。
二叉树的遍历
遍历的定义：顺着某一条搜索路径巡访二叉树中的节点，使得每个结点均被访问一次，而且仅被访问一次。
遍历目的：得到树中所有结点的一个线性排列
遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的技术和核心
前序遍历、中序遍历、后续遍历中的X序指的是根结点的遍历位置，如果是前序则第一个访问根结点（根左右）。中序就是第二个访问根结点（左根右），后序就是左右根
根据遍历序列确定二叉树
1、若二叉树中各结点的值均不相同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的。
2、由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树
3、若只知道前序序列和后序序列，不可以确定二叉树
**后续序列的根节点必定会在最后
中序遍历如果跟节点在第一个位置，则说明该根节点没有左子树**
遍历的实现算法-先序遍历
[思路]
1、若二叉树为空，则空操作；
2、若二叉树不为空，
a、访问根节点（D）
b、前序遍历左子树（L）
c、前序遍历右子树（R）
typedef struct BiTree{
int data;
struct BiTree *R,*L;
}BiTree;
Status PreOrderTraverse(BiTree T){
if(T==NULL){
return OK;//空二叉树
}else{
visit(T);
PreOrderTraverse(T->Ichild);//递归遍历左子树
PreOrderTraverse(T->rchild);//递归遍历右子树
}
}
中序遍历
【思路】
1、若二叉树为空，则空操作
2、若二叉树不为空：
a、中序遍历左子树（L）
b、访问根节点（D）
c、访问遍历右子树（R）
Status InOrderTraverse(BiTree T){
if(T==NULL){
return OK;
}else{
InOrderTraverse(T->Ichild);//递归遍历左子树
visit(T);//访问根节点
InOrderTraverse(T->rchild);//递归遍历右子树
}
}
非递归遍历二叉树
二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如果找到该节点的根以及右子树
基本思想：
1、建立一个栈
2、根结点进栈，遍历左子树
3、根结点出栈，输出根结点，遍历右子树
Status InOrderTraverse(BiTree T){
BiTree p,q;//p指向遍历结点的地址，q指向遍历结束输出的结点
InitStack(S);
p=T;
while(p||!StackEmpty(S)){//二叉树不为空，且栈创建成功
if(p){
Push(S,p);//如果结点不为空，就进栈
p=p->Ichild;
}else{
Pop(S,q);//如果结点为空，则将栈顶的元素，即该结点的父结点出栈，并用q指向它
printf("%c",q->data);
p=q->rchild;//遍历右子树
}
}
return OK;
}
二叉树的层次遍历
对于一棵二叉树，从根节点开始，按从上到下、从左到右的顺序访问每一个结点。每个结点仅仅访问一次
【算法设计思路】
1、将根结点入队
2、队不为空时循环：从队列中出列一个结点*p，访问它；
a、若它有左孩子结点，将左孩子结点进队
b、若它有右孩子结点，将右孩子结点进队
使用队列类型定义如下：
typedef struct{
BTNode data[MaxSize];//存放队中元素
int front,rear;//队头和队尾指针
}SqQueue;//顺序循环队列类型
void LevelOrder(BTNode *b){
BTNode *p;
SqQueue *qu;
InitQueue(qu);//初始化队列
enQueue(qu,b);//根结点指针入队
while(!QueueEmpty(qu)){
deQueue(qu,p);//出队结点p
printf("%c",p->data);
if(p->Ichild!=NULL){
enQueue(qu,p->Ichild);
}
if(p->rchild!=NULL){
enQueue(qu,p->rchild);
}
}
}
二叉树遍历算法的应用——二叉树的建立
按先序遍历序列建立二叉树的二叉链表：
1、从键盘输入二叉树的结点信息，建立二叉树的存储结构；
2、在建立二叉树的过程中，按照二叉树先序方式建立；
Status CreateBiTree(BiTree &T){
scanf(&ch);//接受键盘输入的单个字符
if(ch == "#"){//如果只有一个#号，则创建一个空树
T=NULL;
}else{
if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))){
exit(OVERFLOW);//如果创建树节点失败，则直接退出
}
T->data = ch;//生成根结点
CreateBiTree(T->Ichild);//生成左子树
CreateBiTree(T->rchild);//生成右子树
}
return OK;
}
复制二叉树
【算法思路】
1、如果是空树，递归结束
2、如果不是空树，复制根节点
a、递归复制左子树
b、递归复制右子树
int Copy(BiTree T,BiTree &NewT){
if(T==NULL){
NewT=NULL;
return 0;
}else{
NewT = (BiTree *)malloc(sizeof(BiTree));
NewT->data = T->data;
Cop(T->Ichild,NewT->Ichild);
Cop(T->rchild,NewT->rchild);
}
}
计算二叉树深度
1、如果是空树，则深度为0
2、如果非空树，则：
a、递归计算左子树的深度m，
b、递归计算右子树的深度n
二叉树的深度则为m与n的较大者加1
int Depth(BiTree T){
if(T==NULL){
return 0;
}else{
m=Depth(T->Ichild);
n=Depth(T->rchild);
if(m>n){
return m+1;
}else{
return n+1;
}
}
}
计算二叉树节点总数
节点个数为左子树的结点个数+右子树的结点个数再+1
int NodeCount(BiTree T){
if(T==NULL){
return 0;
}else{
return NodeCount(T->Ichild)+NodeCount(T->rchild)+1;
}
}
计算二叉树叶子结点树
叶子结点数：左子树的叶子结点个数+右子树的叶子结点个数
int LeadCount(BiTree T){
if(T==NULL){
return 0;
}
if(T->Ichild == NULL&&T->rchild == NULL){
return 1;
}else{
return LeadCount(T->Ichild)+LeadCount(T->rchild);
}
}
线索二叉树
利用二叉树链表中的空指针域：
如果某个结点的左孩子为空，则将空的左孩子域改为指向其前驱；
如果某个结点的右孩子为空，则将空的右孩子域改为指向其后继；
这种改变指向的指针称为线索
加了线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化
为区分Ichild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag,并约定ltag\rtag=0时，指向该结点的左\右孩子，ltag\rtag=1时,指向该结点的前后驱、后继.
typedef struct BiThrNode{
int data;
int ltag,rtag;
struct BiThrNode *lchild,*rchild;
}BiThrNode,*BiThrTree;
树的存储结构
双亲表示法：
实现：1、定义结构数组存放树的结点
每一个结点都包括：1、数据域 2、指示本结点的双亲结点在数组中的位置
特点：找双亲容易，找子结点难
typedef struct PTNode{
TElemType data;
int parent;//双亲位置域
}PTNode;
#define MAX_TREE_SIZE 100
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int r,n;//根结点的位置和结点的个数
}PTree;
孩子链表
把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点有n个孩子链表（叶子结点的孩子链表为空表）。而n个头指针又组成一个线性表，用顺序表（含n个元素的结构数组）存储
孩子兄弟表示法（二叉树表示法、二叉链表示法）
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
typedef struct CSNode{
ElemType data;
struct CSNode *fitstchild,*nextsibling;
}CSNode,*CSTree;
树与二叉树的转换
- 将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作
- 由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的对应关系
将树转化成二叉树的步骤：
1、加线：在树的兄弟结点之间加一连线
2、抹线：除了左孩子外，去除根结点与其余孩子的关系
3、旋转：以树的根结点为轴心，将整个树顺时针转45°
**树变二叉树：**兄弟相连留长子
将二叉树转换成树
1、加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子…沿分支找到所有的右孩子，都与p的双亲用线连起来
2、抹线：抹掉原二叉树中双亲与右孩子之间的连线
3、调整：将结点按层次排列，形成树结构
森林与二叉树的转化
森林转换成二叉树（二叉树与多棵树之间的关系）
1、将各棵树分别转换成二叉树
2、将每一棵树的根结点用线相连
3、以第一棵树根结点为二叉树的根，再以根结点为轴心。顺时针旋转，构成二叉树结构
口诀：树变二叉根相连
二叉树转换成森林
1、抹线：将二叉树中根结点与其右孩子连线，及沿右支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
2、还原：将孤立的二叉树还原成树
口诀：去掉全部右孩线，孤立二叉再还原
树与森林的遍历
树的遍历（三种形式）
1、先根（次序）遍历：
若树不为空，则先访问根节点，然后一次先根遍历各棵子树
2、后根（次序）遍历：
若树不为空，则先一次后根遍历各棵子树，然后访问根节点
3、按层次遍历：
若树不空，则自上而下，自左而右访问树中每个结点
**森林的遍历 **
将森林看作由三个部分组成：
1、森林中第一棵树的根结点为根
2、森林中第一棵树的子树森林
3、森林中其他树构成的森林
先序遍历
若森林不为空，则
1、访问森林中第一棵树的根结点
2、先序遍历森林中第一棵树的子树森林
3、先序遍历森林中其余树构成的森林
即：依次从左至右对森林中的每一棵树进行先根遍历
中序遍历
若森林不为空，则：
1、中序遍历森林中第一棵树的子树森林
2、访问森林中第一棵树的根结点
3、中序遍历森林中其余树构成的森林
即：依次从左到右对森林中的每一棵树进行后根遍历
哈夫曼树（最优二叉树）
判断树：用于描述分类过程的二叉树
结点
路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
结点的路径长度：两结点间路径上的分支数
权：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积
树
树的路径长度：从树根到每一个结点的路径长度之和。记作TL
结点数目相同的二叉树中，完全二叉树是路径长度 最短的二叉树
树的带权路径长度：树中所有叶子结点的带权路径长度之和。 （每一个叶子 结点的权值和每一个结点的路径相乘，最后求总 和）
带权路径长度最短是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称
哈夫曼树：最优二叉树（带权路径长度（WPL）最短的二叉树）
特点：1、满二叉树不一定是哈夫曼树
2、哈夫曼树中权越大的叶子离根越近
3、具有相同带权结点的哈夫曼 树不唯一
4、哈夫曼树的结点度数为0或者2，不存在度为1的结点
5、包含n个叶子结点的哈夫曼树中共右2n-1个结点
6、包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点
哈夫曼树的构造算法
贪心算法：构造哈夫曼树时首先选择权值小的叶子结点
哈夫曼树算法口诀：1、构造森林全是根 2、选用两小造新树（取出两个权比较小的结点，并给它们添加一个父节点，该父节点的权为这两个结点的权之和 ）
3、删除两小添新人 4、重复2、3剩下单根
哈夫曼编码的性质：
1、哈夫曼编码是前缀编码
2、哈夫曼编码是最优前缀码
哈夫曼编码的算法实现
void CretHuffmanCode(HuffmanTree Ht,HuffmanCode &HC,int n){
//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
char hc[n+1];
char* HC=&hc;
char* cd[n];//分配临时存放编码的动态数组空间
cd[n-1] = '\0';//结束符
for(int i=1;i<=n;i++){
int start = n-1;int c=i;int f = HT[i].parent;
while(f!=0){//从叶子结点开始向上回溯，直到根结点
--start;//回溯一次start向前指一个位置
if(HF[f].lchild == c){//结点C是f的左孩子，则生成代码0
cd[start]='0';
}else{
cd[start]='1';//结点C是f的右孩子，则生成代码1
}
c=f;f=HT[f].parent;//继续向上回溯
} //求出第i个字符的编码
HC[i]=(char*)macoll(sizeof(n-start));//为第i个字符串编码分配空间
strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中
}
close(cd);//释放空间
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)