网站加入百度广告联盟,wordpress删除重复文章的三种方法,深圳网站自然优化,制作动漫需要学什么专业第一章 绪论
1.1 数据结构的研究内容
1.2 基本概念和术语
1.2.1 数据、数据元素、数据项和数据对象
1.数据 数据#xff1a;是能够输入计算机且能被计算机处理的各种符号的集合 信息的载体是对客观事物符号化的表示能够被计算机识别、存储和加工 包括#xff1a; 数值型的…第一章 绪论
1.1 数据结构的研究内容
1.2 基本概念和术语
1.2.1 数据、数据元素、数据项和数据对象
1.数据 数据是能够输入计算机且能被计算机处理的各种符号的集合 信息的载体是对客观事物符号化的表示能够被计算机识别、存储和加工 包括 数值型的数据整数、实数等非数值型的数据文字、图像、图形、声音等 2.数据元素 是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理。 也简称为元素或称为记录、结点或顶点。 一个数据元素可以由若干个数据项组成。
3.数据项 数据项构成数据元素的不可分割的最小单位。 数据、数据元素、数据项三者之间的关系
数据数据元素数据项
4.数据对象 是性质相同的数据元素的集合是数据的一个子集。 数据元素与数据对象
数据元素组成数据的基本单位。 与数据的关系是集合的个体 数据对象性质相同的数据元素的集合。 与数据的关系集合的子集
1.3 抽象数据类型的表象与实现
1.4 算法和算法分析
第二章 线性表 线性表是具有相同特性的数据元素的一个有限序列 a1,a2,…ai-1,ai,ai1,…,an) 线性表的基本操作
初始化 InitList(L)构造一个空的线性表线性表的销毁 DestroyList(L)线性表的清除 ClearList(L),即将线性表重置为空表判断线性表是否为空 ListEmpty(L)求线性表的长度 ListLength(L),返回线性表元素个数即线性表的长度获取线性表元素 GetElem(L,i,e) 返回线性表第i个元素的值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的第i个位置插入新元素e删除元素 DeleteList(L,i,e) 删除第i个位置的元素遍历 ListTraverse(L,visited()) 遍历线性表对每个元素进行visited()操作
1.顺序表线性表的顺序存储结构
**顺序存储**把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
顺序表的特点
元素的逻辑顺序与物理顺序相同
顺序表的优缺点
优点 存储密度高每个结点只存储数据元素任意元素均可随机存取 缺点 插入和删除操作需要移动大量的元素浪费存储空间属于静态存储形式数据元素的个数不能自由扩充
注线性表与数组的区别线性表长可变删除数组长度不可动态定义
1.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函数。静态数组运行完之后会被系统自动回收。 动态定义 #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; //顺序表最大长度增加lenfree(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
1.2 顺序表基本操作的实现
//顺序表的销毁
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.length0)return 1;elsereturn 0;
}
//按位查找数据元素
ElemType SearchList_index(SqList L, int e) {if (e1 || eL.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.判断顺序表的存储空间是否已满若已满返回ERROR3.将第n至第i位的元素依次向后移动一个位置空出第i个位置4.将要插入的新元素e放入第i个位置5.表长加1插入成功返回true
***************************************************************/
bool ListInsert(SqList L, int i, int e) {//判断插入的位置是否合法if (i1 || iL.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出放入eL.length; //长度加1return true;
}//删除指定位置的元素
/**************************************************************
算法思想 1.判断删除位置是否合法 2.将要删除的元素保留在e中3.将第i1至第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)
2.链表线性表的链式存储结构 链表由表头唯一确定因此单链表可以用头指针的名字来命名。若头指针名是L则把链表称为表L。 链表的特点
结点在存储器中的位置是任意的即逻辑上相邻的数据元素在物理上不一定相邻。访问时只能通过头指针进入链表并通过每个结点的指针域依次向后顺序扫描其余结点。
2.1 单链表
1.单链表的定义及初始化带头结点
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(LNULL) //内存不足分配失败 return false;L-nextNULL; //头结点之后暂时还没有结点 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){LNULL; //空表暂时没有任何结点 return true;
}//判断单链表是否为空
bool Empty(LinkList L){if(LNULL)return true;elsereturn false;
}//按位序插入不带头结点
bool ListInsert(LinkList L,int i,ElemType e){if(i1)return false;if(i1){ // 插入第一个结点的操作与其他结点的操作不同LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextL;Ls; //头指针指向新结点return true;}LNode *p; //指针p指向当前扫描到的结点int j1; //当前p指向的是第几个结点pL; //p指向第一个结点注意不是头结点while(p!NULLji-1){ //循环找到第i-1个结点pp-next;j;} if(pNULL) //i值不合法return false;LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;return true; //插入成功
}//后插操作在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode));if(sNULL) //内存分配失败return false;s-datae; //用结点s保存数据元素es-nextp-next;p-nexts; //将结点s连接到p之后return true;
}//前插操作在p结点之前插入结点s
bool InsertPriorNode(LNode *p,LNode *s){if(pNULL||sNULL)return false;s-nextp-next;p-nexts;ElemType tempp-data;p-datas-data;s-datatemp;return false;
}2.单链表的基本操作
//判断单链表是否为空
/*判断头指针指针域是否为空即可*/
bool Empty(LinkList L){if(L-nextNULL)return true;elsereturn false;
}//单链表的销毁(从头指针开始依次释放所有结点)
bool DestroyList(LinkList L){if(LNULL)return false;LNode *pL;while(L!NULL){LL-next;free(p);pL;}return true;
}//清空单链表依次释放所有结点并将头结点指针域置空
bool ClearList(LinkList L){if(LNULL)return false;LNode *pL-next;while(p!NULL){L-nextp-next;free(p);pL-next;}//或者两种思路/*LNode *pL-next,*q;while(p!NULL){qp-next;free(p);pq;}*/L-nextNULL;return true;
}//求表的长度
int Length(LinkList L){int len0;LNode *pL;while(p-next!NULL){pp-next;len;}return len;
}//取值
/************************************************************************************
算法步骤1.从第一个结点L-next顺链扫描用指针p指向当前扫描到的结点p初值pL-next。2.j做计数器累计当前扫描过的结点数j初值为13.当p指向扫描下一个结点时计数器j加14.当ji时p所指向的结点就是要找的第i个结点
*************************************************************************************/
bool GetElem(LinkList L,int i,ElemType e){if(i1)return false;LNode *pL-next;int j1;while(p!NULLji){pp-next;j;}if(pNULL)//第i个元素不存在return false;ep-data;return true;
}//按值查找
/************************************************************************************
算法步骤1.从第一个结点开始依次和e值比较2.如果找到一个其值与e相等的元素则返回其在链表中的位置或地址。3.如果遍历完之后没有与e值相等的元素则返回0或者NULL
*************************************************************************************/
//返回地址
LNode * LocateElem(LinkList L,ElemType e){LNode *pL-next;while(p!NULLp-data!e){pp-next;}return p;
}
//返回位序
int LocateElem(LinkList L,ElemType e){LNOde *pL-next;int j1;while(p!NULLp-data!e){pp-next;j;}if(p!NULL)return j;else //不存在return 0;
}
//插入(在第i个位置插入)
/************************************************************************************
算法步骤1.找到第i-1个结点的位置2.生成一个数据域为e的新结点s3.插入新结点s
*************************************************************************************/
bool InsertList(LinkList L,int i,ElemType e){if(i1)ruturn false;int j0;LNode *pL;while(p!NULLJi-1){pp-next;j;}if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;return ture;
}
//删除(删除第i个结点)
/************************************************************************************
算法步骤1.找到第i-1个结点的位置保存要删除的结点的元素值2.第i-1个结点的指针域指向第i个结点的next域3.释放第i个结点存储空间
*************************************************************************************/
bool DeleteList(LinkList L,int i,ElemType e){if(i1)return false;LNode *pL;int j0;while(p!NULLji-1){pp-next;j;}if(p-nextNULL)return false;LNode *qp-next;eq-data;p-nextq-next;free(q);return true;
}
//头插法建立单链表bool CreateList_H(LinkList L,int n){LNode *s;for(int i0;in;i){s(LNode *)malloc(sizeof(LNode));scanf(%d,s-data);s-nextL-next;L-nexts;}return true;}//尾插法建立单链表
bool CreatList_R(LinkList L,int n){LNode *s,*pL;for(int i0;in;i){s(LNode *)malloc(sizeof(LNode));scanf(%d,s-data);p-nexts;ps;}p-nextNULL;return true;
}重点内容
查找、删除、头插法、尾插法
3.单链表的优缺点
优点
是一种动态的数据结构可以在运行的过程中通过分配和取消分配内存来插入和删除结点插入和删除元素不需要移动元素只需要更新结点的next指针域大小可以根据需求在运行时增加或减少内存利用率高
缺点
与数组相比存储元素需要更多内存因为单链表的每个结点都包含一个指针域用来保存下一节点的地址。结点遍历困难访问元素的效率低。
2.2 双向链表带头结点
1.双链表的定义和初始化
typedef int ElemType;typedef struct DNode{ElemType data;struct DNode *prior,*next;
}DNode,*DLinkList;//双链表的初始化(带头结点)
bool InitDLinkList(DLinkList L){L(DNode *)malloc(sizeof(DNode));if(LNULL)return false;L-priorNULL; //头结点的prior永远指向NULLL-nextNULL;return true;
}2.双链表的基本操作
//插入
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(pNULL||sNULL) //非法参数return false;s-nextp-next;if(p-next!NULL) //如果p结点有后继节点p-next-priors;s-priorp;p-nexts;return true;
}
//删除
bool DelertDNode(DLinkList L,int i,ElemType e){if(i1)return false;int j0;DNode *pL;while(p!NULLji){pp-next;j;}if(pNULL)//不存在第i个结点return false;ep-data;p-prior-nextp-next;if(p-next!NULL)p-next-priorp-prior;free(p);return true;
}3.双链表的优缺点
在单链表的基础上增加了一个指向前一个结点的指针域解决了单链表中无法通过指定结点找到其之前结点的问题。
2.3 循环链表
优点从表中任意位置出发均可以找到其他结点
1.循环单链表
#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(LNULL)return false;L-nextL; //头结点的next指向头结点return true;
}//判断循环单链表是否为空
bool Empty(LinkList L){if(L-nextL)return true;else return false;
}//判断p结点是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){if(p-nextL)return true;else return false;
}int main()
{LinkList L;InitList(L);//...return 0;
}2.循环双链表
#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(LNULL)return false;L-priorL; //头结点的prior指向头结点L-nextL; //头结点的next指向头结点return true;
}
//判断循环双链表是否为空
bool Empty(DLinkList L){if(L-nextL)return true;else return false;
}//判断p结点是否为循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p){if(p-nextL)return true;else return false;
}//插入,在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){s-nextp-next;p-next-priors;//这里无需判断是否为表尾结点s-priorp;p-nexts;
}//删除p结点的后继节点
bool DeleteNextDNode(DNode *p,DNode *q){p-nextq-next;q-next-priorp;free(q);return true;
}int main()
{DLinkList L;InitDLinkList(L);//...return 0;
}2.4 静态链表*
typedef struct DNode{ElemType data;int next;
}SLinkList[MaxSize];3.顺序表和链表的比较 4.顺序表的几个常用算法
①线性表的合并
//这是一个通用的算法La、Lb具体是顺序表还是链表可根据具体情况确定
/************************************************************
描述利用La和Lb分别表示两个集合A和B现要求一个新的集合AAUB
*************************************************************/void union(List La,List b){La_lenListLength(La); //求La的长度Lb_lenListLength(Lb); //求Lb的长度 for(i1;iLb_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.创建一个空表Lc2.依次从La或Lb中“摘取”元素值较小的结点插入到Lc表的最后直至其中一个表变为空表为止3.继续将La和Lb其中一个表的剩余结点插在Lc表的最后
*********************************************************************************************/
//用顺序表实现过程
void MergeList_Sq(SqList La,SqList Lb,SqList Lc){paLa.elem; //指针pa和pb的初始值分别指向两个表的第一个元素pbLb.elem;Lc.lengthLa.lengthLb.length; //新表长度为两个表的长度之和Lc.elem(ElemType *)malloc(sizeof(ElemType)*Lc.length); //为新表分配数组空间pcLc.elem; //指针pc指向新表的第一个元素pa_lastLa.elemLa.length-1; //指针pa_last指向La表的最后一个元素pb_lastLb.elemLb.length-1; //指针pb_last指向Lb表的最后一个元素while(papa_lastpbpb_last){ //两个表都非空if(*pa*pb) //依次“摘取”两表中值较小的结点*pc*paelse*pc*pb;}while(papa_last) //Lb表已到达表位将La中剩余元素加入Lc*pc*pa;while(pbpb_last) //La表已到达表位将Lb中剩余元素加入Lc*pc*pb;
}//用链表实现过程
void MergeList_L(LinkList La,LinkList Lb,LinkList Lc){paLa-next;pbLb-next;pcLcLa; //用La的头结点作为Lc的头结点while(papb){if(pa-datapb-data){pc-nextpa;pcpa;papa-next;}else{pc-nextpb;pcpb;pbpb-next;}}pc-nextpa?pa:pb; //插入剩余段free(Lb); //释放Lb的头结点
}第三章 栈和队列
3.1 栈 栈是只允许在一端表尾进行插入或删除操作的线性表。先进后出或后进先出 其中表尾成为栈顶表头称为栈底。 栈的基本操作
初始化 InitStack(S)销毁 DestrouStack(L)进栈 Push(s,x)出栈 Pop(s,x)查(读栈顶元素) GetTop(s,x)判断是否为空 StackEmpty(S)清空求栈的长度
1.顺序栈
#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.topMaxSize-1) //栈满return false;S.topS.top1;S.data[S.top]x;//或者直接写成以下形式//S.data[S.top]x;return true;
}//出栈操作
bool Pop(SqStack S,ElemType x){if(S.top-1) //栈空return false;xS.data[S.top]; //保存出栈元素S.topS.top-1;//或者直接写成以下形式//xS.data[S.top--];return true;
}//读栈顶元素
bool GetTop(SqStack S,ElemType x){if(S.top-1) //栈空return false;xS.data[S.top];return true;
}//测试代码
#include stdio.h
#include stdlib.h
#define MaxSize 10typedef 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;elsereturn 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.top2MaxSize;
}
//栈满条件top11top22.链栈
/********************************************************************************************************
注意每次入栈或出栈的都是从链表的表头开始的入栈之后要将链表的表头指针指向新入栈的元素出栈即将表头元素出栈要修改头指针为出栈元素的下一个元素
******************************************************************************************************/
typedef int ElemType;//定义
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode,*LinkStack;//初始化
void InitStack(LinkStack S){SNULL;
}//判断栈是否为空
bool StackEmpty(LinkStack S){if(SNULL)return true;elsereturn false;
}//入栈
bool Push(LinkStack S,ElemType x){StackNode *p(StackNode *)malloc(sizeof(StackNode)); //生成新结点pp-datax; //将新结点数据域置为xp-nextS; //将新结点插入栈顶Sp; //修改栈顶指针return true;
}//出栈
bool Pop(LinkStack S,ElemType x){if(SNULL)return false;StackNode *pS;xS-data;SS-next;free(p);return true;
}//取栈顶元素
ElemType GetTop(LinkStack S){if(SNULL)return false;return S-data;
}
3.栈与递归 递归若一个对象部分的包含它自己或用它自己给自己定义则称这个对象是递归的 若一个过程直接或间接的调用自己则称这个过程是递归的过程。 递归问题——用分治法求解 分治法对于一个较为复杂的问题能够分解成几个相对简单的且解法相同或类似的子问题来求解。 必备的三个条件 能够将一个问题转变成一个新的问题而新问题与原问题的解法相同或类同不同的仅是处理的对象且这些处理对象是变化有规律的可以通过上述转化而时问题简化必须有一个明确的递归出口或递归的边界。 分治法求解递归问题的算法一般形式
void p([参数]){if(递归结束条件)直接求解步骤 //基本项elsep([较小的参数]); //归纳项
}递归的优缺点
优点结构清晰程序易读缺点每次调用要生成工作记录保存状态信息入栈返回时要出栈恢复状态信息。时间开销大。入栈出栈在系统内部实现
递归 - 非递归
方法1尾递归、单向递归 - 循环结构方法2自用栈模拟系统的运行时栈
3.2 队列 队列是只允许在一端表尾进行插入入队在另一端表头进行删除出队的线性表。先进先出 队列的基本操作
初始化 InitQueue(Q)销毁 DestroyQueue(Q)清空 ClearQueue(Q)入队 EnQueue(Q,x)出队 DeQueue(Q,x)读队头元素 GetHead(Q,x)判断是否为空 QueueEmpty(Q)…
1.顺序队列
注意一定要先搞清除头指针和尾指针的指向位置是怎么规定的不同情况下的代码会不同要理解其中的思想和原理其次不管在什么情况下首相要搞清楚判断队列为空和队列已满这两个条件非常重要。
#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.front0;Q.rear0;
}//判断队列是否为空
bool QueueEmpty(SqQueue Q){if(Q.frontQ.rear) //队列为空条件return true;elsereturn false;
}//判断队列是否为满队列
bool QueueFull(SqQueue Q){if(Q.rear1Q.front||(Q.rear1MaxSizeQ.front0))return true;elsereturn true;
}顺序循环队列
#define MaxSize 10
typedef int ElemType;//定义
//注意在本代码中对尾指针始终指向的是即将要插入元素的位置
typedef struct{ElemType data[MaxSize];int front,rear; //队头指针和队尾指针
}SqQueue;//初始化
bool InitQueue(SqQueue Q){Q.front0;Q.rear0;
}//判断队列是否为空
bool QueueEmpty(SqQueue Q){if(Q.frontQ.rear) //队列为空条件return true;elsereturn false;
}//入队
/******************************************************************
算法思想1.在队尾插入元素2.尾指针后移一位
******************************************************************/
bool EnQueue(SqQueue Q,ElemType x){if((Q.rear1)%MaxSizeQ.front) //判断队满条件return false;Q.data[Q.rear]x; //将x值插入对尾Q.rear(Q.rear1)%MaxSize; //队尾指针加1取模return true;
}//出队(删除一个队头元素用x返回)
/******************************************************************
算法思想头指针后移
******************************************************************/
bool DeQueue(SqQueue Q,ElemType x){if(Q.frontQ.rear) //判断队列为空的条件return false;xQ.data[Q.front];Q.front(Q.front1)%MaxSize;return true;
}//获得队头元素的值用x返回
bool GetHead(SqQueue Q,ElemType x){if(Q.rearQ.front)return false;xQ.data[Q.front];return true;
}
不同方案情况下判断队列已满/为空的条件
/***************方案一******************/
//定义
typedef struct{ElemType data[MaxSize];int front,rear; //队头指针和队尾指针
}SqQueue;//初始化
bool InitQueue(SqQueue Q){Q.front0;Q.rear0;
}
//队列为空的条件Q.rearQ.front;
//队列已满的条件对尾指针的在下一个位置是对头即(Q.rear1)%MaxSizeQ.front;(此时会浪费最后一片存储空间)
//队列元素个数(rearMaxSize-front)%MaxSize/***************方案二******************/
//定义
typedef struct{ElemType data[MaxSize];int front,rear; //队头指针和队尾指针int size; //队列当前长度
}SqQueue;//初始化
bool InitQueue(SqQueue Q){Q.front0;Q.rear0;Q.size0;
}
/****************************************************************************
在定义时额外定义一个变量用来存储当前队列的长度可以不浪费最后一块存储空间此时
队列为空的条件Q.size0;
队列已满的条件Q.sizeMaxSize;
******************************************************************************//***************方案三******************/
//定义
typedef struct{ElemType data[MaxSize];int front,rear; //队头指针和队尾指针int tag; //最近进行的是删除/插入//每次删除成功时都令tag0每次插入成功时都令tag1//只有删除操作才有可能导致队空只有插入操作才有可能导致队满
}SqQueue;//初始化
bool InitQueue(SqQueue Q){Q.front0;Q.rear0;Q.tag0;
}
/****************************************************************************
在定义时额外定义一个变量用来存表示最近进行的是插入还是删除操作此时
队列为空的条件Q.frontQ.realtag0;因为只有最后进行删除才能使队列为空
队列已满的条件Q.frontQ.realtag1;因为只有最后进行插入才能使队列为满
******************************************************************************/2.链队列
注意链队列中不需要判断队列是否满的情况。
带头结点
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.frontQ.rear(LinkNode *)malloc(sizeof(LinkNode));Q.front-nextNULL;
}//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.frontQ.rear)return true;elsereturn false;
}//入队带头结点
bool EnQueue(LinkQueue Q,ElemType x){LinkNode *s(LinkNode *)malloc(sizeof(LinkNode));s-datax;s-nextNULL;Q.rear-nexts; //新结点插入到rear之后Q.rears; //修改表尾指针
}//出队带头结点
bool DeQueue(LinkQueue Q,ElemType x){if(Q.frontQ.rear)//空队return false;LinkNode *pQ.front-next;xp-data; //返回队头元素Q.front-nextp-next;//修改头结点的next指针if(Q.rearp) //如果是最后一个元素出队修改rear指针Q.rearQ.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都指向NULLQ.frontNULL;Q.rearNULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.frontNULL)return true;elsereturn false;
}//入队不带头结点
bool EnQueue(LinkQueue Q,ElemType x){LinkNode *s(LinkNode *)malloc(sizeof(LinkNode));s-datax;s-nextNULL;if(Q.frontNULL){ //在空队列中插入第一个元素Q.fronts; //修改队头队尾指针Q.rears;}else{Q.rear-nexts; //新结点插入到rear结点之后Q.rears; //修改rear指针}
}//出队
bool DeQueue(LinkQueue Q,ElemType x){if(Q.frontNULL) //空队return false;LinkNode *pQ.front; //p指向此次出队的结点xQ.front-data; //返回队头元素Q.frontp-next; //修改front指针if(Q.rearp){ //此次是最后一个结点出队Q.frontNULL; //front、real都指向NULLQ.rearNULL;}free(p);return true;}int main()
{LinkQueue Q;InitQueue(Q);return 0;
}//test.cpp
#include stdio.h
#include stdlib.h
/***********************************************************************
不带头结点的链式队列
判断队列为空的条件Q.frontNULL
本代码中的尾指针始终执行队尾元素
*************************************************************************/
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;xQ.front-data;return true;
}//- 判断是否为空 QueueEmpty(Q)
bool QueueEmpty(QueueList Q) {if (Q.real Q.frontQ.real NULL)return true;elsereturn 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;
}3.3 双端队列* 双端队列只允许从两端插入、两段删除的线性表。可根据需求自由设定输入输出受限 第四章 串 串即字符串string是由零个或多个字符组成的有限序列。 子串串中任意个连续的字符组成的子序列 主串包含子串的串 字符在主串中的位置字符在串中的序号 子串在主串中的位置子串的第一个字符在主串中的位置 空格串由一个或多个空格组成的串 注意空串和空格串的区别
串是一种特殊的线性表数据元素之间呈现线性关系。
4.1 串的基本操作
赋值操作 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) 若ST,则返回值0;若ST,则返回值0;若ST,则返回值0.
串的比较从第一个字符开始往后依次对比先出现更大字符的串就更大长串的前缀与短串相同时长串更大只有两个串完全相等时才算相等
4.2 串的存储结构
1.串的顺序存储
#include stdio.h
#include stdlib.h
#define Maxlen 255 //预定义最大串长为255
typedef struct{char ch[Maxlen]; //每个分量存储一个字符一般情况下第一个位置不存储数据int length;//串的实际长度
}SString;//比较操作 StrCompare(S,T) 若ST,则返回值0;若ST,则返回值0;若ST,则返回值0.
int StrCompare(SString S,SString T){for(int i1;iS.lengthiT.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(poslen-1S.length)return false;for(int ipos;iposlen;i){Sub.ch[i-pos1]S.ch[i];}Sub.lengthlen;return true;
}//定位操作 Index(S,T)
// ——若主串S中存在与串T值相同的子串则返回它在主串S中第一次出现的位置否则函数值为0.
int Index(SString S,SString T){int i1,nStrLength(S),mStrLength(T);SString sub;//用于暂存子串while(in-m1){SubString(sub,S,i,m);if(StrCompare(sub,T)!0)i;else return i;//返回子串在主串中的位置}return 0;//S中不存在与T相等的子串
}
2.串的链式存储块链结构
#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;4.3 字符串的模式匹配 字符串模式匹配在主串中找到与模式串相同的子串并返回其所在的位置。 1.朴素模式匹配算法暴力解法 朴素模式匹配算法设主串长度为n模式串长度为m将主串中所有长度为m的子串依次与模式串对比直到找到一个完全匹配的子串或所有的子串都不匹配为止。 int Index_BF(SString S,SString T){int i1,j1;while(iS.lengthjT.length){if(S.ch[i]T.ch[j]){//主串和子串依次匹配下一个字符i; j;}else{ //主串、子串指针回溯重新开始下一次匹配ii-j2;j1;}}if(jT.length)return i-T.length;elsereturn 0;
}//求子串,从中间某个位置开始匹配
int Index(SString S, SString T,int pos) {int i pos, j 1;while (i S.lengthj T.length) {if (S.ch[i] T.ch[j]) {i;j;}else {i i - j 2;j 1;}}if (jT.length)//如果子串在主串中完全匹配则j的值一定是大于子串的长度的return i-T.length;elsereturn 0;
}
//事件复杂度O(n*m)2.KMP算法 利用已经部分匹配的结果而加快模式串的滑动速度且主串S的指针i不必回溯可以提速到O(nm) 最坏时间复杂度O(mn) 其中求next数组时间复杂度O(m)模式匹配过程最坏时间复杂度O(n) int Index(SString S, SString T,int pos) {int i pos, j 1;while (i S.lengthj T.length) {if (j0||S.ch[i] T.ch[j]) {i;j;}else {jnext[j]; /*i不变j后退*/}}if (jT.length)//如果子串在主串中完全匹配则j的值一定是大于子串的长度的return i-T.length;elsereturn 0;
}//求next数组
void get_next(SString T,int next[]){int i1;next[1]0;int j0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i;j;next[i]j;}elsejnext[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;}elsej next[j];}
}
int KMP(SString S, SString T) {int i 1, j 1;while (iS.lengthjT.length) {if (j 0 || S.ch[i] T.ch[j]) {i;j;}else {j next[j];}}if (j T.length)return i - T.length;elsereturn 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;
}3.KMP算法优化
int Index(SString S, SString T,int pos) {int i pos, j 1;while (i S.lengthj T.length) {if (j0||S.ch[i] T.ch[j]) {i;j;}else {jnextval[j]; /*i不变j后退*/}}if (jT.length)//如果子串在主串中完全匹配则j的值一定是大于子串的长度的return i-T.length;elsereturn 0;
}//求next数组
void get_next(SString T,int next[]){int i1;next[1]0;int j0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i;j;next[i]j;}elsejnext[j];}
}//基于next数组求nextval数组
void get_nextval(){nextval[1]0;for(int j2;jT.length;j){if(T.ch[next[j]]T.ch[j])nextval[j]nextval[next[j]];elsenextval[j]next[j];}
}第五章 数和二叉树
5.1树
树的定义 树是n(n0)个结点的有限集。 若n0称为空树 若n0则它满足如下两个条件 ①有且仅有一个特定的称为根的结点 ②其余结点可分为m(m0)个互不相交的有限集其中每一个集合本身又是一棵树并称为根的子树。 树的基本术语 根结点非空树中无前驱结点的结点 结点的度结点拥有的子树树。 树的度树内各结点的度的最大值 叶子结点度为0的结点也叫终端结点 分支结点度不为0的结点也叫非终端结点。根节点以外的分支结点称为内部结点。 结点的子树的根称为该结点的孩子该结点称为孩子的双亲 结点的祖先从根到该结点所经过的分支上的所有的结点。 兄弟结点拥有同一个双亲结点的结点之间称为兄弟结点。 堂兄弟双亲在同一层的结点。 树的深度树中结点的最大层次。 有序树树中结点的各子树从左至右有次序最左边的为第一个孩子。 无需树树中结点的各子树无次序。 森林是m(m0)颗互不相交的树的集合。把根结点删了就成了森林一棵树也可以看成是一个特殊的森林。 线性结构和树结构的比较
线性结构一对一树结构一对多
5.2 二叉树 为何要重点研究二叉树 二叉树的结构最简单规律性最强可以证明所有树都能转为唯一对应的二叉树不失一般性。 普通树多叉树若不转化为二叉树则运算很难实现。 二叉树在树结构的应用中起着非常重要的作用因为对二叉树的许多操作算法简单而任何数都可以与二叉树相互转换 这样就解决了树的存储结构及其在运算中存在的复杂性。 二叉树的定义 二叉树是n(n0)个结点的有限集它或者是空集(n0),或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树的特点
每个结点做多有两个孩子二叉树中不存在度大于2的结点。子树有左右之分其次序不能颠倒。二叉树可以是空集合根可以有空的左子树或空的右子树。
注二叉树不是树的特殊情况他们是两个概念
二叉树结点的子树要区分左子树和右子树即使只有一颗子树也要进行区分说明它是左子树还是右子树。
树当结点只有一个孩子时就无需区分它是左还是右的次序。因此二者是不同的这是二叉树与树的最主要的差别。
5.3 二叉树的性质和存储结构
1 性质
在二叉树的第i层上至多有2^(i-1)个结点i1)。第i层至少有1个结点深度为k的二叉树至多有(2^k )- 1个结点k1)。深度为k时至少有k个结点对任何一颗二叉树T,如果其叶子树为n0,度为2的结点数为n2,则n0n2 1。具有n个结点的完全二叉树的深度为log2^n向下取整1如果对一棵有n个结点的完全二叉树深度为log2^n向下取整1的结点按层序编号从第1层到 log 2^n向下取整1层每层从左到右则对任意结点i1in有 如果i1则结点i是二叉树的根无双亲如果i1则其双亲是结点 i/2 的向下取整如果2in则结点i为叶子结点无左孩子否则其右孩子是结点2i如果2i1n则结点i无右孩子否则其右孩子是结点2i1
两种特殊形式的二叉树 满二插树一棵深度为k且有(2^k) -1个结点的二叉树称为满二叉树。 特点①每一层上的结点数都是最大结点数每层都满 ②叶子结点全部在最底层 完全二叉树深度为k的具有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时称之为完全二叉树。 特点①叶子只可能分布在层次最大的两层上。 ②对任意结点如果其右子树的最大层次为i则其左子树的最大层次必为i或i1
注①在满二叉树中从最又一个结点开始连续去掉任意个结点即是一颗完全二叉树。一定是连续去掉
②满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树
为什么要研究这两种特殊形式的二叉树
因为它们在顺序存储方式下可以复原
2 存储结构
1二叉树的顺序存储结构
实现按满二叉树的结点层次编号依次存放二叉树中的数据元素。适合存放满二叉树和完全二叉树
typedef struct Bitree{Elemtype data[MaxSize];int length;
}BiTree;2二叉树的链式存储结构
①二叉链表
//定义
typedef struct BiNode{TelemType data;struct BiNode *lchild,*rchild;//左右孩子指针
}BiNode,*BiTree;②三叉链表
//定义
typedef struct TriTNode{TelemType data;struct TriTNode *lchild,*parent,*rchild;//左右孩子指针,双亲结点指针
}TriTNode,*TriTTree;5.4 二叉树的遍历递归算法
常用以下三种遍历方法
1.先根序遍历DLR——(根-左-右)
若二叉树为空则空操作否则①访问根节点②先序遍历左子树③先序遍历右子树递归操作
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;}elsereturn 0;
}2.中根序遍历LDR——(左-根-右)
若二叉树为空则空操作否则①中序遍历左子树②访问根节点③中序遍历右子树递归操作
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;}elsereturn 0;
}3.后根序遍历LRD——(左-右-根)
若二叉树为空则空操作否则①后序遍历左子树②后序遍历右子树③访问根节点递归操作
int PostOrderTraverse(BiTeen T){if(T!NULL){PostOrderTraverse(T-Lchild);PostOrderTraverse(T-Rchild);printf(%c ,T-data);}
}//二叉树的遍历完整代码
#include stdio.h
#include stdlib.htypedef 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(BiTree T) {if (T ! NULL) {printf(%c , T-data);PreOrderTraverse(T-Lchild);PreOrderTraverse(T-Rchild);}
}
//中序遍历
void InOrderTraverse(BiTree T) {if (T ! NULL) {InOrderTraverse(T-Lchild);printf(%c , T-data);InOrderTraverse(T-Rchild);}
}
//后序遍历
void PostOrderTraverse(BiTree T) {if (T ! NULL) {PostOrderTraverse(T-Lchild);PostOrderTraverse(T-Rchild);printf(%c , T-data);}
}
int main()
{BiTree T;printf(请输入二叉树序列空结点用#表示);CreateBiTree_Pro(T);printf(先序遍历);PreOrderTraverse(T);printf(\n中序遍历);InOrderTraverse(T);printf(\n后序遍历);PostOrderTraverse(T);return 0;
}4.根据遍历序列确定二叉树
若二叉树中各结点的值均不相同则二叉树结点的先序序列、中序序列、后序序列都是唯一的由二叉树的先序序列和中序序列、或者中序序列和后序序列可以唯一一颗二叉树但是由先序序列和后序序列是不能唯一确定一棵二叉树
5.5 二叉树的非递归遍历
中序遍历非递归算法
二叉树中序遍历的非递归算法的关键在中序遍历过某结点的整个左子树后如何找到该结点的根以及右子树。
基本思想
建立一个栈根结点进栈遍历左子树根结点出栈输出根结点遍历右子树 5.6 二叉树的层次遍历
算法设计思路使用一个队列
将根结点进队队不空时循环从队列中出列一个结点*p,访问它 若它有左孩子结点将左孩子结点进队若它有右孩子结点将右孩子结点进队 5.7 复制二叉树
算法思想
如果是空树递归结束
否则申请新结点空间复制根结点
递归赋值左子树递归赋值右子树
//复制二叉树
int Copy(BiTree T, BiTree newT) {if (T ! NULL) {newT (BiNode *)malloc(sizeof(BiNode));newT-data T-data;Copy(T-Lchild, newT-Lchild);Copy(T-Rchild, newT-Rchild);}else {newT NULL;return 0;}
}//完整代码
#include stdio.h
#include stdlib.htypedef struct BiNode {char data;struct BiNode *Lchild, *Rchild;
}BiNode, *BiTree;//先序建立二叉树
BiNode * CreateBiTree(BiTree T) {char data;scanf(%c, data);if (data ! #) {T (BiNode *)malloc(sizeof(BiNode));T-data data;T-Lchild CreateBiTree(T-Lchild);T-Rchild CreateBiTree(T-Rchild);}else {T NULL;}return T;
}
//复制二叉树
int Copy(BiTree T, BiTree newT) {if (T ! NULL) {newT (BiNode *)malloc(sizeof(BiNode));newT-data T-data;Copy(T-Lchild, newT-Lchild);Copy(T-Rchild, newT-Rchild);}else {newT NULL;return 0;}
}
//先序遍历递归
void PreOrderTraversal(BiTree T) {if (T ! NULL) {printf(%c , T-data);PreOrderTraversal(T-Lchild);PreOrderTraversal(T-Rchild);}
}
//中序遍历
void InOrderTraversal(BiTree T) {if (T ! NULL) {InOrderTraversal(T-Lchild);printf(%c , T-data);InOrderTraversal(T-Rchild);}
}
//后序遍历
void PostOrderTraversal(BiTree T) {if (T ! NULL) {PostOrderTraversal(T-Lchild);PostOrderTraversal(T-Rchild);printf(%c , T-data);}
}int main()
{BiTree T;CreateBiTree(T);printf(先序遍历);PreOrderTraversal(T);printf(\n中序遍历);InOrderTraversal(T);printf(\n后序遍历);PostOrderTraversal(T);BiTree copy_T;Copy(T, copy_T);printf(\n先序遍历);PreOrderTraversal(copy_T);printf(\n中序遍历);InOrderTraversal(copy_T);printf(\n后序遍历);PostOrderTraversal(copy_T);return 0;
}5.8 计算二叉树的深度
算法思想如果是空树则深度为0
否则递归计算左子树的深度记为m,递归计算右子树的深度记为n,二叉树的深度则为m与n的较大者加1。
int Depth(BiTree T){if(TNULL)return 0;else{mDepth(T-Lchild);nDepth(T-Rchild);if(mn)return (m1);elsereturn (n1);}
}5.9 计算二叉树结点总数
算法思想
如果是空树则结点个数为0否则结点个数为左子树的结点个数右子树的结点个数再1。
int NodeCount(BiTree T){if(TNULL)return 0;elsereturn NodeCount(T-Lchild)NodeCount(T-Rchild)1;
}5.10 计算二叉树叶子结点的个数
算法思想
如果是空树则叶子结点个数为0否则为左子树的叶子结点个数右子树叶子结点个数。
int LeadCount(BiTree T){if(TNULL)return 0;if(T-LchildNULLT-RchildNULL)return 1;elsereturn LeadCount(L-Lchild)LeadCount(L-Rchild);
}5.11 线索二叉树 具有n个结点的二叉链表中一共有2n个指针域因为n个结点中有n-1个孩子即2n个指针域中有n-1个指针域用来指示结点的左右孩子其余n1个指针域为空。 利用二叉链表中的空指针域如果某个结点的左孩子为空则将空的左孩子指针域改为指向前驱结点如果某结点的右孩子为空则将空的右孩子指针域改为指向其后继这种改变指向的指针称为**“线索”加上了线索的二叉树称为线索二叉树**对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。 为区分Lchild和Rchild指针到底是指向孩子的指针还是指向前驱或者后继的指针对二叉链表中**每个结点增设两个标志域ltag和rtag并约定 Itag 0Lchild 指向该结点的左孩子 ltag 1Lchild 指向该结点的前驱 rtag 0Rchild 指向该结点的右孩子 rtag 1Rchild 指向该结点的后继 //线索二叉树的定义
typedef struct BiThrNode{int data;//数据域int ltag,rtag;//两个标志域struct BiThrNode *Lchild,*Rchild;//指针指向两个孩子结点
}BiThrNode,*BiThrTree;1.先序线索二叉树
2.中序线索二叉树
#include stdio.h
#include stdlib.h//线索二叉树的定义
typedef struct BiThrNode{int data;//数据域int ltag,rtag;//两个标志域struct BiThrNode *Lchild,*Rchild;//指针指向两个孩子结点
}BiThrNode,*BiThrTree;//通过中序遍历对二叉树线索化的递归算法
void InBiTreTree(BiThrTree p,BiThrTree pre){if(p!NULL){InBiTreTree(p-Lchild,pre); //递归线索化左子树if(p-LchildNULL){ //左子树为空建立前驱线索p-Lchildpre;p-ltag1;}if(pre!NULLpre-RchildNULL){pre-Rchildp; //建立前驱结点的后继线索pre-rtag1;}prep; //标记当前结点称为刚刚访问过的结点InBiTreTree(p-Rchild,pre); //递归线索化右子树}
}//通过中序遍历建立中序线索二叉树的主过程算法
void CreateInTreTree(BiThrTree T){BiThrTree preNULL;if(T!NULL){ //非空二叉树线索化InBiTreTree(T,pre); //线索化二叉树pre-RchildNULL; //处理遍历的最后一个结点pre-rtag1;}
}3.后序线索二叉树
5.12 树和森林
1.树的存储结构
1双亲表示法
实现定义结构数组存放树的结点每个结点含两个域
数据域存放结点本身信息
双亲域指示本结点的双亲结点在数组中的位置。
特点找双亲容易找孩子难。
//定义节点结构
typedef struct PTNode{TElemType data;int parent;//双亲位置域
}PTNode;
//定义树结构
#define MaxSize 100
typedef struct{PTNode nodes[MaxSize];int r,n;//根结点位置和结点个数
}PTree;2孩子链表
把每个结点的孩子结点排列起来看成是一个线性表用单链表存储。则n个结点有n个孩子链表叶子的孩子链表为空表。而n个头指针又组成一个线性表用顺序表含n个元素的结构数组存储。
特点找孩子容易找双亲难。
//孩子结点结构
typedef struct CTNode{int child;struct CTNode *next;
}*ChildPtr;//定义双亲结点结构
typedef struct{TElemType data;ChildPtr firstchild;//孩子链表头指针
}CTBox;//树结构
typedef struct{CTBox nodes[MaxSize];int n,r;//结点数和根结点的位置
}CTree;3孩子兄弟表示法二叉树表示法二叉链表表示法
实现用二叉链表作树的存储结构链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。
typedef struct CSNode{ElemType data;struct CSNode *firstchild,*nextsibling;//第一个孩子和下一个兄弟指针
}CSNode,*CSTree;2.树与二叉树的转换
第八章 排序
#include iostream
using namespace std;
void Print_res(int A[], int n) {for (int i 0; i n; i)cout A[i] ;cout endl;
}
//插入排序
void InsertSort(int A[], int n) {int i, j, temp;for (i 1; i n; i) {if (A[i] A[i - 1]) {temp A[i];for (j i - 1; j 0 A[j] temp; --j) {A[j 1] A[j];}A[j 1] temp;}}Print_res(A,n);
}//冒泡排序
void BubbleSort(int A[], int n) {for (int i 0; i n; i) {bool flag false;for (int j 1; j n; j) {if (A[j - 1] A[j]) {int temp A[j];A[j] A[j - 1];A[j - 1] temp;flag true;}}if (flag false) {Print_res(A, n);return;}}Print_res(A, n);
}
//希尔排序
void shellSort(int A[],int n){int d,i,j;for(dn/2;d1;dd/2){for(id1;in;i){if(A[i]A[i-d]){A[0]A[i];for(ji-d;j0A[0]A[j];j-d){A[jd]A[j];}A[jd]A[0];}}}
}//快速排序
//用第一个元素将待排序序列划分成左右两部分
int Partition(int A[], int low, int high) {int pivot A[low]; //第一个元素作为枢轴while (low high) { //用low、high搜索枢轴最终的位置while (low highA[high] pivot)--high;A[low] A[high]; //比枢轴小的元素移动到左端while (low highA[low] pivot)low;A[high] A[low]; //比枢轴大的元素移动到右端}A[low] pivot; //枢轴元素存放到最终的位置return low; //返回存放枢轴的最终位置
}
void QuickSort(int A[], int low, int high) {if (low high) { //递归跳出的条件int pivotpos Partition(A, low, high); //划分QuickSort(A, low, pivotpos - 1); //划分左子表QuickSort(A, pivotpos 1, high); //划分右子表}
}//简单选择排序
void swap(int a, int b) {int temp a;a b;b temp;
}
void SelectSort(int A[], int n) {for (int i 0; i n - 1; i) {int min i;for (int j i 1; j n; j)if (A[j] A[min])min j;if (min ! i)swap(A[i], A[min]);}Print_res(A, n);
}int main()
{int a[] { 11,13,12,16,15,9,61 };int len sizeof(a) / sizeof(int);Print_res(a,len);InsertSort(a, len);return 0;
}
