数据结构与算法讲义

海量的课程、、资料，就来“高端课网”，：外泄数据结构内容详解 一、代码书写规范及C&C++语言基础（一）数据类型基本数据类型int、long字符型：charfloat、double结构型例如：typedef struct{int a;char b;float c;}TypeA;海量的课程、、资料，就来“高端课网”，：外泄数据结构内容详解 一、代码书写规范及C&C++语言基础（一）数据类型基本数据类型int、long字符型：charfloat、double结构型例如：typedef struct{int a;char b;float c;}TypeA;制作的数据类型。intcharint *a;char *b;float *c;TypeA*d;一下定义int型变量的语句：int a;下定义char型变量的语句：char b;float型变量的语句：float c;//对比一下定义TypeA型变量的语句：TypeAd;4.结点的构造①链表结点的构造。typedef struct Node{1中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄int data;struct Node *next;//指向Node型变量的指针}②二叉树结点的定义typedef struct BTNode{int data;struct BTNode *lchild;struct BTNode }BTNode;（二）函数一个和一个出口，所谓的，把函数的参数用它的程序。笔记区域：二、算法效率度量（一）时间复杂度复杂度是指执行这个算法所需要的内存空间。间，而是其中基本操作的总次数。海量的课程、、资料，就来“高端课网”，：外泄int data;struct Node *next;//指向Node型变量的指针}②二叉树结点的定义typedef struct BTNode{int data;struct BTNode *lchild;struct BTNode }BTNode;（二）函数一个和一个出口，所谓的，把函数的参数用它的程序。笔记区域：二、算法效率度量（一）时间复杂度复杂度是指执行这个算法所需要的内存空间。间，而是其中基本操作的总次数。作。常用的比较关系为：循环内的语句所描述的操作作为基本操1.计算方法①确定算法中的基本操作以及问题的规模。T(n)=O(f(n)中增长最快的项/此项的系数)。作为算法时间复杂度的度量。2.例题2中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄1（）voidfun（intn）{inti=1,j=100;while（i<n）{++j;i+=2;}}B.O(n2)A.O(n/2)D.O(2)C.O(n)】C。海量的课程、、资料，就来“高端课网”，：外泄1（）voidfun（intn）{inti=1,j=100;while（i<n）{++j;i+=2;}}B.O(n2)A.O(n/2)D.O(2)C.O(n)】C。i+=2i<nn有关，【【nn。因此时间复杂度T(n)=O(n)。2（）voidfun(intn){inti,j,x=0;for(i=1;i<n;++i)for(j=i+1;j<=n;++j)++x;}B.O(n2)A.O(n)D.O(n2/2)C.O(1)】B。【【n2/2T(n)=On2)。（二）空间复杂度算法的空间复杂度指算法在运行时所需空间的度量，记做S(n)=O(f(n))，主要考虑在算法运行过程中临时占用的空间的大小。笔记区域：3中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄三、基本概念（一）基本概述数据数据元素数据元素是数据的基本（如书名、作者名等）为一个数据项。3.数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，大写字母就是一个数据对象，‘AB4.数据结构（1）定义‘Z’}（2）分类①数据的逻辑结构②数据的结构（3）数据的运算在数据的逻辑结构上定义的操作算法，如检索、 、删除等。（二）数据的逻辑结构1.定义指数据元2.分类间的逻辑关系，与在计算机中数据的位置无关。海量的课程、、资料，就来“高端课网”，：外泄三、基本概念（一）基本概述数据数据元素数据元素是数据的基本（如书名、作者名等）为一个数据项。3.数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，大写字母就是一个数据对象，‘AB4.数据结构（1）定义‘Z’}（2）分类①数据的逻辑结构②数据的结构（3）数据的运算在数据的逻辑结构上定义的操作算法，如检索、 、删除等。（二）数据的逻辑结构1.定义指数据元2.分类间的逻辑关系，与在计算机中数据的位置无关。间存在一对一的关系。间存在一对多的关系。3.举例间存在多对多的关系。4中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄（三）数据的1.定义结构指数据元素及其关系在计算机2.分类（1）顺序器内的表示，依赖于计算机语言。逻辑上相邻的结点（2）在物理位置上相邻的单元里。索引结点的同时建立附加的索引表。散列地址。笔记区域：（一）自然语言自然语言通常是指一种自然的随（二）流程图线表示操作的先后次序。优点：形象、直观、容易理解。5中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄（三）数据的1.定义结构指数据元素及其关系在计算机2.分类（1）顺序器内的表示，依赖于计算机语言。逻辑上相邻的结点（2）在物理位置上相邻的单元里。索引结点的同时建立附加的索引表。散列地址。笔记区域：（一）自然语言自然语言通常是指一种自然的随（二）流程图线表示操作的先后次序。优点：形象、直观、容易理解。5中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄（三）伪代码定义特点优点：简洁、易懂、容易修改。缺点：不直观、错误不容易排除。3.举例IF九点以前THENdo私人事务;ELSE9海量的课程、、资料，就来“高端课网”，：外泄（三）伪代码定义特点优点：简洁、易懂、容易修改。缺点：不直观、错误不容易排除。3.举例IF九点以前THENdo私人事务;ELSE918点THEN;ELSE;ENDIF笔记区域：6中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、基本概念（一）定义线性表是最基本、最简单、也是最常用的一种数据结构。线性表是具有n(n≥0)个类型相同的数据元素组成的有限序列。线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。（二）特点除后个元 外均有唯的后件；4.除第一个元（前件。（三）表示方式海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、基本概念（一）定义线性表是最基本、最简单、也是最常用的一种数据结构。线性表是具有n(n≥0)个类型相同的数据元素组成的有限序列。线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。（二）特点除后个元 外均有唯的后件；4.除第一个元（前件。（三）表示方式线性表的顺序表示用一组地址连续的（1）线性链表单元依次线性表的数据元素。用一组任意的（2）循环链表单元线性表的数据元素（可连续、可不连续。（3）双向链表有两个指针域，其一指向直接后继，另一指向直接前趋。笔记区域：线性表的顺序是用一组地址连续的单元依次辑结构上相邻的数据元素在相邻的物理单元中。nko1io：o（）=oc（1+（1）k。线性表的类型定义：#defineMaxSize<顺序表的容量>typedef struct{7中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、 、资料，就来“高端课网”，：外泄ElemType int length;int listsize;/*线性表占用的数组空间*/}SeqList;//顺序表类型的定义笔记区域：三、单链表（一）形式与定义（二）说明data数据域：存放数据next指针域：存放位置（三）单链表的类型定义typedef structLnode{ElemType data;StructLnode }lnode,*LinkList;L=NULL（对于>nex海量的课程、 、资料，就来“高端课网”，：外泄ElemType int length;int listsize;/*线性表占用的数组空间*/}SeqList;//顺序表类型的定义笔记区域：三、单链表（一）形式与定义（二）说明data数据域：存放数据next指针域：存放位置（三）单链表的类型定义typedef structLnode{ElemType data;StructLnode }lnode,*LinkList;L=NULL（对于>nex=U0。若不是空表，则可以通过头指针的数据信息。（四）单链表的操作1.查找e的元素，并返回其下标。代码如下：intLocateElem(SqlistL,inte){inti;if(e==L.data[i])表中结点，找到要的所有结点returni;//若找到，则返回下标00位置上不存放元素return0;}2.个位置上p0，代表 失败；如果p的输入正确，则将顺序表第p个元素及以后元素右移一个位置，腾出一个空位置插1，操作1。8中公教育资料报名专线：400-6300-999同号）：64462131需要可（datanext海量的课程、、资料，就来“高端课网”，：外泄操作代码如下：intinsert(Sqlist&L,intp,inte){inti;if(p<1||p>L.length+1||L.length==maxSize-1) //位置错误或者表长已经达到顺序表的return0;L.data[p]=e;++(L.length);return1;//最大值，此时不，返回零//从后往前逐个将元素往后移动一个位置//e放在位置p上1//1}3.删除海量的课程、、资料，就来“高端课网”，：外泄操作代码如下：intinsert(Sqlist&L,intp,inte){inti;if(p<1||p>L.length+1||L.length==maxSize-1) //位置错误或者表长已经达到顺序表的return0;L.data[p]=e;++(L.length);return1;//最大值，此时不，返回零//从后往前逐个将元素往后移动一个位置//e放在位置p上1//1}3.删除的元素，e。代码如下：10，并将删除元素的值赋intlistDelete(Sqlist&L,intp,int&e){inti;//需要改变的变量用型if(p<1||p>L.length+1||L.length==maxSize-1) 0，代表删除不return0;e=L.data[p];efor(i=p;i<L.length;++i)L.data[i]=L.data[i+1];开始将其后面的元素逐个前移一个位置--(L.length);return1;//1//删除1}笔记区域：四、循环链表NULL了单链形式的循环链表，并称为循环单链表。9中公教育资料报名专线：400-6300-999同号）：64462131需要可（海量的课程、、资料，就来“高端课网”，：外泄笔记区域：五、双向链表（一）结构（二）说明data：数据域next：后继指针域（三）双链表的结构定义typedefstructDulNode{ElemType data;StructDulNode *prior,*next;}DulNode,*DuLinklist;（四）特点海量的课程、、资料，就来“高端课网”，：外泄笔记区域：五、双向链表（一）结构（二）说明data：数据域next：后继指针域（三）双链表的结构定义typedefstructDulNode{ElemType data;StructDulNode *prior,*next;}DulNode,*DuLinklist;（四）特点p指向双链表中某一结点，则有下式成立：p->prior->next=p=p->next->prior10（中公教育资料报名专线：400-6300-999同号）：64462131需要可priordatanext海量的课程、、资料，就来“高端课网”，：外泄（五）双链表的算法操作1.结点的算法假设在双链表中p所指的结点之后s->next=p->next;s->prior=p;p->next=s;s，其操作语句如下：s->next->prior=s指针变化过程//假如p指向最后一个结点，则本行可去掉。2.删除结点的算法设要删除双链表中p结点的后继结点，其操作语句如下：q=p->next;>next=q->next;>next->prior=p;free(q);11（海量的课程、、资料，就来“高端课网”，：外泄（五）双链表的算法操作1.结点的算法假设在双链表中p所指的结点之后s->next=p->next;s->prior=p;p->next=s;s，其操作语句如下：s->next->prior=s指针变化过程//假如p指向最后一个结点，则本行可去掉。2.删除结点的算法设要删除双链表中p结点的后继结点，其操作语句如下：q=p->next;>next=q->next;>next->prior=p;free(q);11（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄笔记区域：六、广义表（一）定义（listslist的区别。广义n（n>=0）个数据元素a1，a2，…，an海量的课程、、资料，就来“高端课网”，：外泄笔记区域：六、广义表（一）定义（listslist的区别。广义n（n>=0）个数据元素a1，a2，…，an的有序序列，一般记做：Ls=（a1，a2，…，an）nai（1<=i<=n）Ls的成员，它可以是单个元素，LsLsLs的（a2，…，an）Ls的表尾。显然，广义表的定义是递归的。A=（）B=（e）C（b，D=（A，B，C）E=（a，E）=（）（二）广义表的性质广义表是一种多层次的数据结构广义表可以是递归的表广义表可以为其他表所共享（三）广义表的1.头尾表示法结构若广义表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种方法。由于广义表中的数据元素既可能是列表也可能是原子，相应的在头尾表示法中结点的结构形式有两种：一种是表结点，用以表示列表；另一种是原子结点，用以表示原子。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在原子结点中应该包括所表示原子的元素值。为了区分这两类结点，10，则表示该结点为原子。2.孩子兄弟表示法0，则表示该结点为无孩子结点。（四）广义表基本操作的实现12（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄1.广义表的取头、取尾CLNode* if(head==NULL)returnhead;}GLNode*&GetTail(){p=NULL;if(tag==1)p=tp;海量的课程、、资料，就来“高端课网”，：外泄1.广义表的取头、取尾CLNode* if(head==NULL)returnhead;}GLNode*&GetTail(){p=NULL;if(tag==1)p=tp;returnp;}2.建立广义表的结构voidCreateGlist(CString S){GLNode *p,*q;if(S.strEmpty()) else{if(!(head=newGLNode())) return;if(S.Length()==1){head->tag=0;head->data=S.First();}else{head->tag=1;p=head;Cstring sub,hsub;sub=S.SubString(2,S.Length()-2);//脱去外层括号do{ sever(sub,hsub);subhsubq=p;if(!sub.StrEmpty()){if(!(p=newGLNode()))return;p->tag=1;q->ptr.tp=p;}13（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、 、资料，就来“高端课网”，：外泄}while(!sub.strEmpty());q->ptr.tp=NULL;}}}广义表的深度int Depth(){if(!head)return 1;if(head->tag==0)return 0;1//0for(max=0,p=head;p;p=p->tp){dep=Depth(p->hp);海量的课程、 、资料，就来“高端课网”，：外泄}while(!sub.strEmpty());q->ptr.tp=NULL;}}}广义表的深度int Depth(){if(!head)return 1;if(head->tag==0)return 0;1//0for(max=0,p=head;p;p=p->tp){dep=Depth(p->hp);if(dep>max) }returnmax+1; 1}笔记区域：14（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、基本概念（一）定义1.栈是一种只能在一端进行或删除操作的线性表。其中进行或删除操作的一端称为栈顶，和删除操作一般称为入栈和出栈。通常用在表达式中括号是否匹配。2.队列队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。Rea；on向队列添加元素称为入队，从队列中删除元素称为出队。（二）特点栈O（O例析：栈具有LIFO海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、基本概念（一）定义1.栈是一种只能在一端进行或删除操作的线性表。其中进行或删除操作的一端称为栈顶，和删除操作一般称为入栈和出栈。通常用在表达式中括号是否匹配。2.队列队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。Rea；on向队列添加元素称为入队，从队列中删除元素称为出队。（二）特点栈O（O例析：栈具有LIFO1、2、3，则输出序列应该有多少种呢？1开头：123、1322开头：213、2313开头：321队列O（三）结构1.栈有两种主要的结构：顺序栈和链式栈。2.队列的结构有顺序队和链队两种。笔记区域：二、栈的抽象数据类型定义（一）数据元素15（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄（二）关系（三）基本操作niSac（S。DeoSac（SS海量的课程、、资料，就来“高端课网”，：外泄（二）关系（三）基本操作niSac（S。DeoSac（SSeaSac（S：栈SSackEpt（SS为空栈，则返回UASE。Sackeng（SGeopS,：用ESPus（S,e：E为新的栈顶元素。PoS,SE笔记区域：（一）栈在计算机中的两种 形式顺序栈顺序 的栈。链栈以链式的栈。（二）顺序栈的基本算法操作1.顺序栈的定义typedef{intintstructdata[maxSize]; //存放栈中元素，maxSize是已定义的常量top;//栈顶指针//顺序栈类型定义}SqStack;2.初始化栈的算法初始化一个栈，只需将栈顶指针置为-1即可，代码如下：void initStack(Sqstack &st){st.top=-1;}3.栈空的算法为空的时候返回1，否则返回0，其对应算法如下：int IsEmpty(SqStack st){16（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄if(st.top==-1)return1;elsereturn0;}4.进栈算法int Push(SqStack &st,int{if(st.top==maxSize-1)return 0;x)//进栈的时候必须,栈满不能进栈++(st.top);st.data[st.top]=x;return 1;//先移动指针，再进栈}5.出栈算法海量的课程、、资料，就来“高端课网”，：外泄if(st.top==-1)return1;elsereturn0;}4.进栈算法int Push(SqStack &st,int{if(st.top==maxSize-1)return 0;x)//进栈的时候必须,栈满不能进栈++(st.top);st.data[st.top]=x;return 1;//先移动指针，再进栈}5.出栈算法int Pop(SqStack &st,int &x){if(st.top==-1) 如果栈空，不能出栈return 0;x=st.data[st.top];return1;//先取出元素，再移动指针}笔记区域：（一）队列的两种1.循环队列结构单元依次存放从队列头到队列尾的元 外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。下图为循环队列的三种状态：17（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄Q.front=Q.rearfrontrear不能判定队列是空还是满。2.循环队列空状态和满状态的判别设一个标志区别队列是空还是满。count用来时队列为满。count==0count=Maxqsize队满条件为：(sq.rear+1)modmaxsize==sq.frontsq.rear==sq.front3.链队列frontrear指向链表的表尾。一般海量的课程、、资料，就来“高端课网”，：外泄Q.front=Q.rearfrontrear不能判定队列是空还是满。2.循环队列空状态和满状态的判别设一个标志区别队列是空还是满。count用来时队列为满。count==0count=Maxqsize队满条件为：(sq.rear+1)modmaxsize==sq.frontsq.rear==sq.front3.链队列frontrear指向链表的表尾。一般frontrear都需要修改。（二）顺序队列的基本算法操作1.定义typedef{intintintstruct QNodedata[maxSize];front;rear;队首指针//队尾指针//顺序队类型定义}Sueue;初始化int InitQueue(SQ.front=Q.rear=0;}队空ueue &Q){int QueueEmpty(Sueue qu)18（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄{if(qu.front==qu.rear)return1;//若队首和队尾两指针重合，即为空队elsereturn0;}4.元素进队int enQueue(S{ueue &qu,int x)if((qu.rear+1)%maxSize==qu.front)return 0;//队满的条件，队满则不能入队qu.rear=(qu.front+1)%maxSize;//若队未满，则先移动指针qu.data[qu.rear]=x;return 1;//再存入元素}5.元素出队int deQueue(S{ueue &qu,int &x)if(qu.rear==qu.front)return 0;x=qu.data[qu.front];//若队空，则不能出队//若队不空，先取出元素qu.front=(qu.front+1)%maxSize;return 1;//海量的课程、、资料，就来“高端课网”，：外泄{if(qu.front==qu.rear)return1;//若队首和队尾两指针重合，即为空队elsereturn0;}4.元素进队int enQueue(S{ueue &qu,int x)if((qu.rear+1)%maxSize==qu.front)return 0;//队满的条件，队满则不能入队qu.rear=(qu.front+1)%maxSize;//若队未满，则先移动指针qu.data[qu.rear]=x;return 1;//再存入元素}5.元素出队int deQueue(S{ueue &qu,int &x)if(qu.rear==qu.front)return 0;x=qu.data[qu.front];//若队空，则不能出队//若队不空，先取出元素qu.front=(qu.front+1)%maxSize;return 1;//再移动指针}笔记区域：19（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、树的基本概念（一）树的定义n个结点的有限集合，在任一棵非空树中：有且仅有一个称为根的结点。其余结点可分为m个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树，因此树是递归结构。（二）表示方法1.树形表示法2.嵌套集合表示法3.凹入表示法海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、树的基本概念（一）树的定义n个结点的有限集合，在任一棵非空树中：有且仅有一个称为根的结点。其余结点可分为m个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树，因此树是递归结构。（二）表示方法1.树形表示法2.嵌套集合表示法3.凹入表示法个根下的各子树的根对应的条形长度是一样。20（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄4.广义表形式表示法（A）第一层（（CD第二层（（（，，C海量的课程、、资料，就来“高端课网”，：外泄4.广义表形式表示法（A）第一层（（CD第二层（（（，，CG，H，，）（（（（，，，（，H（，，（三）树的基本术语结点的度数：结点的非空子树个数。树的度：树中各节点中度的最大值。0的结点。0的结点。孩子：结点的子树的根。双亲：结点的直接前驱。兄弟：同一个双亲的孩子之间互为兄弟。21（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄1；结点高度是从最底层的叶1。（四）树的结构双亲孩子结构结构笔记区域：二、二叉树（一）二叉树的定义3。有根二叉树还要满足根结点的度不大二叉树是2个子结点。（二）二叉树的主要性质①二叉树的第i2i-1个结点。k2k-1个结点。（补充概念：k2k-1个结点。完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对1n③叶子结点n0海量的课程、、资料，就来“高端课网”，：外泄1；结点高度是从最底层的叶1。（四）树的结构双亲孩子结构结构笔记区域：二、二叉树（一）二叉树的定义3。有根二叉树还要满足根结点的度不大二叉树是2个子结点。（二）二叉树的主要性质①二叉树的第i2i-1个结点。k2k-1个结点。（补充概念：k2k-1个结点。完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对1n③叶子结点n02n2n0n2+1。④ng2+。n⑤n个结点的完全二叉树，结点按层次编号。a.in/2i1时为根（无双亲。b.i2i2i>n，则无左孩子。2i12i1>n则无右孩子。（三）二叉树的结构1.顺序顺序结构结构即用一个数组来一般二叉树则会浪费大量的 一棵二叉树的顺序。例：22（中公教育资料报名专线：400-6300-999同号）：64462131需要可结点ABCDE数组下标012345海量的课程、 、资料，就来“高端课网”，：外泄2.链式结构域，分别用于左孩子结点和右孩子结点的位置。对应的结点类型的定义如下：typedef struct BTNode{chardata;datachar型，如果题目中需要其他类型//则只需要修改此处*lchild;*rchild;structstruct}BTNode;BTNodeBTNode（四）二叉树的遍历算法D海量的课程、 、资料，就来“高端课网”，：外泄2.链式结构域，分别用于左孩子结点和右孩子结点的位置。对应的结点类型的定义如下：typedef struct BTNode{chardata;datachar型，如果题目中需要其他类型//则只需要修改此处*lchild;*rchild;structstruct}BTNode;BTNodeBTNode（四）二叉树的遍历算法DR、DLR--先（根）序遍历；LDR--中（根）序遍历；LRD--后（根）序遍历。1.先序遍历（1）根结点上图的先序遍历为ABDEGCF。对应的算法描述如下：void preorder(BTNode *p){if(p!=NULL){23（中公教育资料报名专线：400-6300-999同号）：64462131需要可lchilddatarchild海量的课程、、资料，就来“高端课网”，：外泄visit(p);preorder(p->lchild);preorder(p->rchild);//先序遍历左子数先序遍历右子树}}2.中序遍历（1）中序遍历左子树。（2）根结点。（3）中序遍历右子树。中序遍历为DBGEACF。对应的算法描述如下：海量的课程、、资料，就来“高端课网”，：外泄visit(p);preorder(p->lchild);preorder(p->rchild);//先序遍历左子数先序遍历右子树}}2.中序遍历（1）中序遍历左子树。（2）根结点。（3）中序遍历右子树。中序遍历为DBGEACF。对应的算法描述如下：void inorder(BTNode {if(p!=NULL){visit(p);inorder(p->rchild);}}3.后序遍历后序遍历左子树。后序遍历右子树。（3）根结点。后序遍历为DGEBFCA。对应的算法描述如下：void postorder(BTNode *p){if(p!=NULL){preorder(p->lchild);preorder(p->rchild);24（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄visit(p);}}笔记区域：三、树和森林（一）孩子兄弟结构孩子兄弟结构又称为二叉树表示法，以二叉链表作为树的结构。（二）森林与二叉树的转换1.将树转换成二叉树1所示。2所示。3所示。2.将森林转换成二叉树25（中公教育资料报名专线：400-6300-999同号）：64462131需要可指向下一个兄弟结点指向第一个孩子结点lchilddatarchild海量的课程、、资料，就来“高端课网”，：外泄visit(p);}}笔记区域：三、树和森林（一）孩子兄弟结构孩子兄弟结构又称为二叉树表示法，以二叉链表作为树的结构。（二）森林与二叉树的转换1.将树转换成二叉树1所示。2所示。3所示。2.将森林转换成二叉树25（中公教育资料报名专线：400-6300-999同号）：64462131需要可指向下一个兄弟结点指向第一个孩子结点lchilddatarchild海量的课程、、资料，就来“高端课网”，：外泄3棵树的森林转换为二叉树。棵二叉树作为第二棵二叉树的右子树。（三）树和森林的遍历1.先根遍历先根结点A；A的第一棵子树，B的第一个孩子E；B的第二个孩子F；A的第二棵子树，C的第一个孩子G；A的第三棵子树，D的第一个孩子H；I；D的第三个孩子J。海量的课程、、资料，就来“高端课网”，：外泄3棵树的森林转换为二叉树。棵二叉树作为第二棵二叉树的右子树。（三）树和森林的遍历1.先根遍历先根结点A；A的第一棵子树，B的第一个孩子E；B的第二个孩子F；A的第二棵子树，C的第一个孩子G；A的第三棵子树，D的第一个孩子H；I；D的第三个孩子J。子树时先根节点B；子树时先根节点C；子树时先根节点D；A，B，E，F，C，G，D，H，I，J。2.后根遍历先根节点A的第一棵子树，B的第二个孩子F；B；子树时先B的第一个孩子E；26（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”， ：外泄A的第二棵子树，C；A的第三棵子树，I；D的第三个孩子J；D；根节点A。子树时先根C的第一个孩子G；子树时先根D的第一个孩子H海量的课程、、资料，就来“高端课网”， ：外泄A的第二棵子树，C；A的第三棵子树，I；D的第三个孩子J；D；根节点A。子树时先根C的第一个孩子G；子树时先根D的第一个孩子H；最后。笔记区域：（一）二叉排序树与平衡二叉树（后面查找章节详解）的二叉树：左、右子树也分别为二叉排序树；没有键值相等的结点。AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝1，并且左右两个子树都是一棵平衡二叉树。（二）赫夫曼树和赫夫曼编码1.基本概念路径路径是指从树中一个结点到另一个结点之间的分支序列。路径长度树的路径长度结点的权带权路径长度为树中所有叶子结点的带权路径长度之和，记为：n为叶子结点的个数，wii个叶子结点的权值，lii个叶子结点的路径长度。27（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄WPL（a）=7×2＋5×2＋2×2＋4×2＝36WPL海量的课程、、资料，就来“高端课网”，：外泄WPL（a）=7×2＋5×2＋2×2＋4×2＝36WPL（b）=4×2＋7×3＋5×3＋2×1＝46WPL（c）=7×1＋5×2＋2×3＋4×3＝35最优二叉树最小的二叉树叫做最优二叉树。赫夫曼树的构造值，用图中各结点构造一棵赫夫曼树。构造步骤如下：第一步a、b、c、d4棵二叉树。第二步cd，将它们作为左、右子树，构造一棵新的二叉树。新的二叉树的根结cdcd1所示。28（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄第三步5+6=1156的两棵树，同时将新构造的二叉2所示。海量的课程、、资料，就来“高端课网”，：外泄第三步5+6=1156的两棵树，同时将新构造的二叉2所示。第四步711的两个根，将它们作为左、右子树，构造一棵新的73所示。第五步此时，集合中只剩下一棵二叉树，这棵二叉树就是赫夫曼树，至此赫夫曼树的构造结束。计算其bd4是最小的。4.赫夫曼编码1组成的字符串A、B、C、D4个字符组成的一些文字，那么可以用编码00、01、10、11A、B、C、DADA001100。在传送过程中，我们总是希望编码的长度越短越好，一个可行的办法是为每一个字符设置长度不同的编码，对于那些出现频率高的字符，设置编码的长度短一些，这样就可以有效的减少编码的长度。例最低，那么可B、C、D0、00、01、1ADA010，但是这样会有二义性问题，前缀编码的概念。1000010则是前缀编码。字符组成的文字时，编码总长度最小。AB、29（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄）0.4、0.3、0.2、0.1为例，求赫夫曼编码的过程如下：1所示。01海量的课程、、资料，就来“高端课网”，：外泄）0.4、0.3、0.2、0.1为例，求赫夫曼编码的过程如下：1所示。012所示。2A，B10，C110，D111。笔记区域：30（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、图的基本概念图VE（边的集合）组成的一种数据结构，可以用二元组定义为G=（V，E）。V是顶点的非空有穷集合，E是可空的边的有穷集合。有向图海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、图的基本概念图VE（边的集合）组成的一种数据结构，可以用二元组定义为G=（V，E）。V是顶点的非空有穷集合，E是可空的边的有穷集合。有向图V2>和V2，V1>称为弧；对于弧V1，V2>，顶点V1称为弧尾，V2称为弧头。是连通的，则称此有向图为强连通图，否则称为非强连通图。3.无向图图中所有边的顶点对无序。图B,无向图中（V1，V2）和（V2，V1）代表相同的边。的，则称此无向图为连通图，否则称为非连通图。}V4>，<V4，V1>}。无向完全图边的无向图。有向完全图6.稀疏图31（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄（e<n*lbn）或弧的图。稠密图边很多的图。弧在有向图中，通常将边称为弧，含箭头的一端称为弧尾。顶点的度、入度和出度在无向图中，与顶点vvv的边的条数称为v的入度，由顶点v发出的边的条数称为顶点v的出度。二、图的结构海量的课程、、资料，就来“高端课网”，：外泄（e<n*lbn）或弧的图。稠密图边很多的图。弧在有向图中，通常将边称为弧，含箭头的一端称为弧尾。顶点的度、入度和出度在无向图中，与顶点vvv的边的条数称为v的入度，由顶点v发出的边的条数称为顶点v的出度。二、图的结构若（，G或<，>EGi行第j0图的邻接矩阵定义为：。（一）无向图矩阵的特点矩阵是对称的ii1i的度1的个数的一半为图中边的数目4.很容易顶点ij之间是否有边相连（ij1）（二）有向图矩阵的特点矩阵不一定是对称的i1i的出度i0i的入度1的个数为图中弧的数目5.很容易顶点ij是否有弧相连（三）邻接表kiki相邻的顶点放在一个链表中。邻接表中32（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄息。邻接表的表头结点包括两部分内容：1.（da2.指向表结点的指针（*firstarc）（四）邻接表的表结点包括三部分内容邻接点编号（adjvex）（*nextarc）3.数据域，如权值（weight）（五）无向图邻接表的特点ii的度所有链表中结点数目的一半为图中边数3.占用的单元数目为n+2e（六）有向图连接表的特点海量的课程、、资料，就来“高端课网”，：外泄息。邻接表的表头结点包括两部分内容：1.（da2.指向表结点的指针（*firstarc）（四）邻接表的表结点包括三部分内容邻接点编号（adjvex）（*nextarc）3.数据域，如权值（weight）（五）无向图邻接表的特点ii的度所有链表中结点数目的一半为图中边数3.占用的单元数目为n+2e（六）有向图连接表的特点i的出度所有链表中结点数目为图中弧数3.占用的单元数目为n+e笔记区域：从图的某一顶点出发，图中其余顶点，且使每个顶点仅被一次，这一过程称为图的遍历。（一）深度优先搜索深度优先搜索（DFS）类似于树的先序遍历。假定给定图G的初态是所有顶点均未被中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：过，在G1.首先顶点i，并将其visited[i]=1标记置为33（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄ijj未被过，visited[j]=1j开始重复此过程，若j已过，则j的标记置为i有边相连其它顶点顶点并重复刚才过程，直到所有顶点都3.i有边相连的顶点都被被 。过，则退回到前一个1出发的深度优先搜索遍历序列举三种为：以邻接表为结构的图的深度优先搜索遍历算法如下：int visit[maxSize];/*v是起点编号，visit是一个全局数组，作为顶点的顶点都未标记，以免重复*/void DFS(AGraph{ArcNode *p;visit[v]=1;Visit(v);*G,int v)//置已标记//Visit函数代表了一类顶点v的操作while(p!=NULL){if(visit[p->adjvex]==0)v海量的课程、、资料，就来“高端课网”，：外泄ijj未被过，visited[j]=1j开始重复此过程，若j已过，则j的标记置为i有边相连其它顶点顶点并重复刚才过程，直到所有顶点都3.i有边相连的顶点都被被 。过，则退回到前一个1出发的深度优先搜索遍历序列举三种为：以邻接表为结构的图的深度优先搜索遍历算法如下：int visit[maxSize];/*v是起点编号，visit是一个全局数组，作为顶点的顶点都未标记，以免重复*/void DFS(AGraph{ArcNode *p;visit[v]=1;Visit(v);*G,int v)//置已标记//Visit函数代表了一类顶点v的操作while(p!=NULL){if(visit[p->adjvex]==0)v的第一条边//若顶点未//（1），则递归它DFS(G,p->adjvex);p=p->nextarc;v的下一条边的终点}}笔记区域：（二）广度优先搜索G的初态是所有顶点均未作为初始点，则广度优先的基本思想是：Gi1.首先顶点i，并将其标志置为已被2.接着依次与顶点iW1，W2，…，Wt3.然后再按顺序W1，W2，…，Wt有边相连又未曾过的顶点，依此类推，直到图中所34（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄有顶点都被完为止1出发的深度优先搜索遍历序列举三种为：以邻接表为结构的广度优先搜索遍历算法如下：void BFS(AGraph*G,int v,int visit[maxSize])0{ArcNode *p;intque[maxSize],front=0,rear=0;int j;//这是队列定义的简单写法Visit(v);visit[v]=1//任意v的函数rear=(rear+1)%maxSize;que[rear]=v;//v进队while(front!=rear){//队空的时候说明遍历完成front=(front+1)%maxSize;j=que[front];p=G->adjlist[j].firstarc;//顶点出队//pj的第一条边海量的课程、、资料，就来“高端课网”，：外泄有顶点都被完为止1出发的深度优先搜索遍历序列举三种为：以邻接表为结构的广度优先搜索遍历算法如下：void BFS(AGraph*G,int v,int visit[maxSize])0{ArcNode *p;intque[maxSize],front=0,rear=0;int j;//这是队列定义的简单写法Visit(v);visit[v]=1//任意v的函数rear=(rear+1)%maxSize;que[rear]=v;//v进队while(front!=rear){//队空的时候说明遍历完成front=(front+1)%maxSize;j=que[front];p=G->adjlist[j].firstarc;//顶点出队//pj的第一条边while(p!=NULL){p的所有邻接点中未被的入队if(visit[p->adjvex]==0){Visit(p->adjvex);visit[p->adjvex]=1;//当前邻接顶点未被，则进队rear=(rear+1)%maxSize;que[rear]=p->adjvex;//该顶点进队}p=p->nextarc;j的下一条边}}}35（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄笔记区域：（代价）生成树（一）普里姆算法普里姆算法思想（权值最小）的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵3个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。普里姆算法执行过程①从树中某一个顶点v0开始，构造生成树的算法执行过程如下：②将v0到其他顶点的所有边当作候选边。③重复以下步骤n-1n-1个顶点被并入到生成树中。海量的课程、、资料，就来“高端课网”，：外泄笔记区域：（代价）生成树（一）普里姆算法普里姆算法思想（权值最小）的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵3个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。普里姆算法执行过程①从树中某一个顶点v0开始，构造生成树的算法执行过程如下：②将v0到其他顶点的所有边当作候选边。③重复以下步骤n-1n-1个顶点被并入到生成树中。v并入生成树中；vi]（v，vilowcostvi]。例如，成过程如下：5、121。15、3、2、622。25、3、232。23、453。3的边，此时所有顶点都已并入生成树中，生成树求解过程完毕。36（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄3.普里姆算法时间复杂度分析普里姆算法中有两重forOn2)ne无关，（二）克鲁斯卡尔算法1.克鲁斯卡尔算法思想从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树n-1海量的课程、、资料，就来“高端课网”，：外泄3.普里姆算法时间复杂度分析普里姆算法中有两重forOn2)ne无关，（二）克鲁斯卡尔算法1.克鲁斯卡尔算法思想从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树n-1条边为止。2.克鲁斯卡尔算法时间复杂度分析O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。（选讲）（一）迪杰斯特拉算法1.迪杰斯特拉算法思想STST存放图中剩余顶点。S中只包含源点v0T中选取到顶点v0路径长度最短的顶点vu并入到集合SS每并入一个新的顶点vu，都要修改顶点v0T中顶点的最短路径长度值。不断重复此过程直到集合T的顶点全部并入到S中为止。2.迪杰斯特拉算法执行过程引进三个辅助数组dist[]、path[]、set[]。distvi]表示当前已找到的从v0到每个终点vi的最短路径的长度。它的初态为：若从v0到vi有边，]distvi]为∞。path[vi]中保存从v0到vi最短路径上viv01v2，v0到vipathviv0path[vi]=-1。set[]为标记数组，setvi]=0表示viT中，即没有被并入最短路径；setvi]=1表示viS中，即初态为：setv0]=10。vu。37（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄②循环扫面图中顶点，对每个顶点进行以下检测：假设当前顶点为vj，检测vjSsetvj]=1setvj]=1，则什么海量的课程、、资料，就来“高端课网”，：外泄②循环扫面图中顶点，对每个顶点进行以下检测：假设当前顶点为vj，检测vjSsetvj]=1setvj]=1，则什么w为边vuvj>的权值。这个比较就是要看v0经过旧的最短路径到达vj和v0经过含有vu的新的最短路径到达vj哪个更短一点，如果vu加入路径中，且作为路径上vj之前的那个顶点；否则什么都不做。n1次（n，即可得到v03.迪杰斯特拉算法时间复杂度分析On2)。笔记区域：（二）弗洛伊德算法1.弗洛伊德算法思路从图的带权邻接矩阵A=[a(i,j)]n×nn次更新，即由矩阵D(0)=A，按一个公式，D(1)D(1)D(2)；……D(n-1)构造出矩D(n)D(n)ijijD(n)为图的距离矩阵，path来2.弗洛伊德算法过程两点间的最短路径。穷大。uvwuwv比已知的路径更短。如果是更新它。把图用邻接矩阵Gi到VjG,dG,D用来所D,表示从i到VjD,。把各个顶点图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]D[i,j]=kGD中则包含了最短通路径的信息。V5V1DD(5,1)=3V5V1V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。3.弗洛伊德算法时间复杂度分析38（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄n3，因此时间复杂度为O(n3)。（选讲））AOV动之间的先后关系的有向图。（二）拓扑排序算法在一个有向图中找到一个拓扑排序序列过程：（入度为零）的顶点输出；海量的课程、、资料，就来“高端课网”，：外泄n3，因此时间复杂度为O(n3)。（选讲））AOV动之间的先后关系的有向图。（二）拓扑排序算法在一个有向图中找到一个拓扑排序序列过程：（入度为零）的顶点输出；③重复上述两步，直到剩余的网中不存在没有前驱的顶点为止。（选讲）活动在边上的网（ActivityOnEdgenetwork，AOE）AOV的相同点：都是有向无环图。值，边代表活动持续时间；顶点表示，是图中新活动开始或者旧活动结束的标志。AOV网的顶点表示活动，边无权值，边代表活动之间的先后关系。AOE0的顶点，称为源点，表示整个工程的开始；也0的顶点，称为汇点，表示整个工程的结束。39（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、基本概念（一）查找表或）的集合。由于集合中的数据元间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。（二）对查找表经常进行的操作1.某个“特定的”数据元素是否在查找表中2.检索某个“特定的”数据元素的各种属性3.在查找表中一个数据元素4.从查找表中删去某个数据元素（三）查找表的分类静态查找表只能进行“查找”操作的查找。动态查找表元素操作的查找表。（四）关键字，则称此关键字为主关键字（对不同的，其主关键字均不同。反之，称用以识别若干的关键字（五）查找（六）平均查找长度或数据元素的过程。二、常考查找法（一）顺序查找法1.基本思路k相等，则查找2.代码实现k的，则查找失败。海量的课程、、资料，就来“高端课网”，：外泄内容详解 一、基本概念（一）查找表或）的集合。由于集合中的数据元间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。（二）对查找表经常进行的操作1.某个“特定的”数据元素是否在查找表中2.检索某个“特定的”数据元素的各种属性3.在查找表中一个数据元素4.从查找表中删去某个数据元素（三）查找表的分类静态查找表只能进行“查找”操作的查找。动态查找表元素操作的查找表。（四）关键字，则称此关键字为主关键字（对不同的，其主关键字均不同。反之，称用以识别若干的关键字（五）查找（六）平均查找长度或数据元素的过程。二、常考查找法（一）顺序查找法1.基本思路k相等，则查找2.代码实现k的，则查找失败。n1开始k的算法。若查找 ，则返回元素在数组中的位置；若查找不 ，则返回0。int Search(int a[],int n,int k)40（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄{int i;for(i=1;i<=n;++i)if(a[i]==k)return i;return 0;}笔记区域：（二）折半查找法1.要求必须采用顺序结构。2.基本思路k先与中间结点的关键字比较，；若不相等，再根据k与该中间结点关键字的比较3.代码实现int Bsearch(int R[],int{int mid;while(low<=high){mid=(low+high)/2;if(R[mid]==k)return mid;海量的课程、、资料，就来“高端课网”，：外泄{int i;for(i=1;i<=n;++i)if(a[i]==k)return i;return 0;}笔记区域：（二）折半查找法1.要求必须采用顺序结构。2.基本思路k先与中间结点的关键字比较，；若不相等，再根据k与该中间结点关键字的比较3.代码实现int Bsearch(int R[],int{int mid;while(low<=high){mid=(low+high)/2;if(R[mid]==k)return mid;else high=mid-1;low,int high,int k)//1的时候进行循环//取当前表的中间位置//找到后返回元素的位置//说明需要在R[low,…,mid-1]中查找else中查找low=mid+1;}return 0;}4.题目类型//查找不041（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄笔记区域：（三）分块查找线性表顺序而且按照关键码排序。i，i+1块中的所有节点的关键码值。此外，还要建立一个索辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。顺序查找，即可找到对应的节点。（一）二叉排序树1.二叉排序树的定义它的左、右子树也都分别是二叉排序树2.二叉排序树的基本算法（1）查找关键字海量的课程、、资料，就来“高端课网”，：外泄笔记区域：（三）分块查找线性表顺序而且按照关键码排序。i，i+1块中的所有节点的关键码值。此外，还要建立一个索辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。顺序查找，即可找到对应的节点。（一）二叉排序树1.二叉排序树的定义它的左、右子树也都分别是二叉排序树2.二叉排序树的基本算法（1）查找关键字若二叉排序树为空，则查找不。否则①若给定值等于根结点的关键字，则查找。②若给定值小于根结点的关键字，则继续在左子树上进行查找。③若给定值大于根结点的关键字，则继续在右子树上进行查找。代码如下。BTNode* BSTSearch(BTNode* bt,int key){//key代表关键字42（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄if(bt==NULL)return NULL;else{//查找不，返回NULLreturn bt;else if(key<bt->key)//查找，返回关键字所在结点指针//小于根结点中的关键字，到左子树中查找returnBSTSearch(bt->lchild,key);//大于根结点中的关键字，到右子树中查找BSTSearch(bt->rchild,key);elsereturn}}（2）关键字一个关键字首先要找到的关键字，其查找不的位置即为该关键字的 位置。代码如下。BTNode* BSTInsert(BTNode *&bt,int key){if(bt==NULL){//当前指针为空，创建新结点进行bt=(BTNode*)malloc(sizeof(BTNode));bt->lchild=bt->rchild=NULL;//创建新结点bt->key=key;return 1;//将待插关键字存入新结点内，1}else{//如果结点不为空，则查找位置，return 0;else if(key<bt->key)//关键字已存在于树中，0海量的课程、、资料，就来“高端课网”，：外泄if(bt==NULL)return NULL;else{//查找不，返回NULLreturn bt;else if(key<bt->key)//查找，返回关键字所在结点指针//小于根结点中的关键字，到左子树中查找returnBSTSearch(bt->lchild,key);//大于根结点中的关键字，到右子树中查找BSTSearch(bt->rchild,key);elsereturn}}（2）关键字一个关键字首先要找到的关键字，其查找不的位置即为该关键字的 位置。代码如下。BTNode* BSTInsert(BTNode *&bt,int key){if(bt==NULL){//当前指针为空，创建新结点进行bt=(BTNode*)malloc(sizeof(BTNode));bt->lchild=bt->rchild=NULL;//创建新结点bt->key=key;return 1;//将待插关键字存入新结点内，1}else{//如果结点不为空，则查找位置，return 0;else if(key<bt->key)//关键字已存在于树中，0return BSTInsert(bt->lchild,key);elsereturn BSTInsert(bt->rchild,key);}}（3）删除关键字假设被删结点是pf，下面分三种情况讨论：43（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄pf的指针即可；p只有左子树或者只有右子树，此时只需将p删掉，然后将pp与其f相连的指针上即可，；p结点既有左子树又有右子树。先沿着p的左子树根结点的右指针一直往右走，直到来到其右子r（p的右子树根节点的左指针一直往左走，直到来到其左子树的最r。（二）平衡二叉树1.平衡二叉树的概念海量的课程、、资料，就来“高端课网”，：外泄pf的指针即可；p只有左子树或者只有右子树，此时只需将p删掉，然后将pp与其f相连的指针上即可，；p结点既有左子树又有右子树。先沿着p的左子树根结点的右指针一直往右走，直到来到其右子r（p的右子树根节点的左指针一直往左走，直到来到其左子树的最r。（二）平衡二叉树1.平衡二叉树的概念AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高1树中的所有结点的平衡因子的取值只能是-1、0、1三个值。2.平衡二叉树的建立建立平衡二叉树的过程和建立二叉排序树的过程基本一样，都是将关键字逐个空树中的过程。平衡调整。3.平衡调整假定向平衡二叉树中新结点后失去调整为平衡子树后，无需调整原有其他所有不平衡子树，整个二叉树就会成为一棵平衡二叉树。失去平衡的最小子树是以距离 且平衡因子绝对值大于1的结点作为根的子树。平衡调整有4种情况：LL型、RR型、LR型、RL型。树。①建立二叉树，16，此时树空，可直接；② 3，316小，从根结点向左走找到位置后，没有发生不平衡现象；44（中公教育资料报名专线：400-6300-999同号）：64462131需要可海量的课程、、资料，就来“高端课网”，：外泄③7，16分别为其左、右子结点，这样仍能保持根大于左小于右的特性，这里进行的是7作为根结点，3和LR调整；④ LL调整；7RR调整；16RL调整；海量的课程、、资料，就来“高端课网”，：外泄③7，16分别为其左、右子结点，这样仍能保持根大于左小于右的特性，这里进行的是7作为根结点，3和LR调整；④ LL调整；7RR调整；16RL调整；LR调整。⑤⑥⑦⑧4.删除结点16。四、散列表（一）散列表（Hash）的概念kf(k)的位置上。由此，不需比较便可直接取得所查。称这个f为散列函数，按这个思想建立的表为散列表。Hash表的特点是能根据给定的关键字来计算出关键字在表中的地址。（二）散列表的建立方法以及1.Hash表的建立方法解决方法根据给定的关键字依照函数Hkeykey存在这个地址上。例：关键字序列{7,4,1,14,100,30,5,9,20,134}Hash函数为H(key)=keyMod1313报名专线：400-6300-999同号）：64462131表。并求出在等概率的情况下查找和不45（中公教育资料需要可海量的课程、、资料，就来“高端课网”，：外泄求解过程根据表中各个关键字的地址，将关键字填入Hash表中，下面的表即为所得表。4301343个关键字是不 出现的因此要做一些处理来解决，的线性探查解决方法。包含解决的建表过程由此得到Hash表：46（中公教育资料报名专线：400-6300-999同号）：64462131需要可关键字Hash函数计算地址是否冲突解决地址77Mod13=7否无744Mod13=4否无411Mod13=1否无11414Mod13=1是从 1后移一位，得新地址2，不2100100Mod13=9否无93030Mod13=4是从 4后移一位，得新地址5，不555Mod13=5是从 5后移一位，得新地址6，不699Mod13=9是从 移一位，得新地址10，不102020Mod13=7是从 7后移一位，得新地址8，不8134134Mod13=4是从 4后移一位，得新地址海量的课程、、资料，就来“高端课网”，：外泄求解过程根据表中各个关键字的地址，将关键字填入Hash表中，下面的表即为所得表。4301343个关键字是不 出现的因此要做一些处理来解决，的线性探查解决方法。包含解决的建表过程由此得到Hash表：46（中公教育资料报名专线：400-6300-999同号）：64462131需要可关键字Hash函数计算地址是否冲突解决地址77Mod13=7否无744Mod13=4否无411Mod13=1否无11414Mod13=1是从 1后移一位，得新地址2，不2100100Mod13=9否无93030Mod13=4是从 4后移一位，得新地址5，不555Mod13=5是从 5后移一位，得新地址6，不699Mod13=9是从 移一位，得新地址10，不102020Mod13=7是从 7后移一位，得新地址8，不8134134Mod13=4是从 4后移一位，得新地址5，仍 ，继续后移直时不11地址0123456789101112关键字114430关键字函数计算地址地址77Mod13744Mod13411Mod1311414Mod131100100Mod1393030Mod13455Mod13599Mod1392020Mod137134134Mod134海量的课程、、资料，就来“高端课网”，：外泄ASL1，关键是求出对于查找每个关键字所对应的比较次数，通过上面的分析可以知道，如果没有，则只需要比较一次；如果发生，则根据其关键字比较次数解决方法来计算出比较次数。ASL2，关键是求出查找不情况下的比较次数。这里的比较次数是于表中每个可以通是查查找不的平均查找长度。地址比较次数据表可知：2.常用Hash函数的构造方法对数字关键字可有下列构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。（1）直接定址法①构造47（中公教育资料报名专线：400-6300-999同号）：64462131需要可开始到空位置为止所要发生比较操作的地址比较次数00111,2,3322,3233144,5,6,7,8,9,10,11,12955,6,7,8,9,10,11,12866,7,8,9,10,11,12777,8,9,10,11,12688,9,10,11,12599,10,11,1241010,11,1231111,12212121关键字11443057201009134