数据结构知识点-个人笔记.docx

《数据结构知识点-个人笔记.docx》由会员分享，可在线阅读，更多相关《数据结构知识点-个人笔记.docx（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构与算法复习第1部分：1. 概念：数据结构，存储结构，逻辑结构注：磁盘文件管理系统是树状结构。1.1基本概念 （1）数据：指所有能够输入到计算机中并被计算机程序处理的符号的总称（图像声音都可以通过编码归于数据的范围），范围大 （2）数据项：数据的不可分割的最小单元 （3）数据元素：是数据的基本单位，有若干数据项组成，通常作为一个整体考虑 （4）数据对象：性质相同的数据元素的集合，是数据的一个子集。例子：数据项数据元素数据对象数据 表A 科目分数是否及格数学99是语文89是 表B姓名性别身高小花女100小草男120 其中，A表为成绩表，B表为学生信息表，这两张表就是数据；单独的一张表就称为

2、数据对象，即A和B表都是一个数据对象；每张表中的每一行就称为数据元素；姓名，性别，身高，科目，分数就称为数据项1.2数据结构 定义：相互之间存在一种或多种特定关系的数据元素的集合，这种关系包括三方面的内容，即数据逻辑结构，数据存储结构，数据的操作。 2. 数据元素是组成数据的基本单位3. 算法，算法分析，算法特性，时间复杂度3.1算法：描述求解问题方法操作步骤的集合。（不是所有的程序都是算法，要满足五个特性）3.2时间复杂度3.2.1定义：在算法分析中，一般用算法中的语句的执行次数来度量算法的时间效率，时间效率也就是时间复杂度。3.2.2计算方法：对于问题规模为n的某个函数f(n)，算法时间复

3、杂度记为T(n)，存在一个正常数c，使cf(n)T(n)恒成立，则T(n)=Of(n)，称Of(n)为时间复杂度。 时间复杂度的大O表示法：保留最高次数项，令最高次数项的系数为1。例如O(8)-O(1)，O(2n3+2n2)-O(n3)，O(n*log2 n)第2部分1. 线性表的概念，特点，存储结构1.11线性表的概念：线性表是最简单，最常见，最基本的一种线性结构（数据的逻辑结构的一种），元素之间为线性关系，即除了第一个和最后一个元素之外，所有的元素都有前驱和后继元素，同一个线性表中的数据类型相同。 当数据元素为0时，可以是空表，但是没有空图的说法。1.1.2线性表的特点：插入删除算法的时间

4、复杂度为O(n)，不适合多次插入或删除1.2.1线性表的存储方式： （1）顺序存储（又称顺序表）物理地址相连a0A1A2A3A4A5A6A7A8A9 （2）链式存储（又称链式表）数据域指针域 1.2.2链式表的特点：可动态分配空间，插入删除算法的时间复杂度为O(1) 单链表在特定节点插入和删除元素之前需要遍历链表，所以算法的时间复杂度为O(n)，对于单链表的求表长，取元素，插入删除，释放掉几个操作的平均时间复杂度都是O(n)，但是链表只需比较元素不用移动元素，所以时间效率上优于顺序表2. 顺序存储时插入、删除（移动元素的个数）（1）定义顺序表的数据类型：typedef structInt li

5、stmaxsize;Int size （2）初始化 void listinitial(sequence *L)L-size=0; （3）插入元素：在i位置前插入一个新的元素，原顺序表中i位置之后的元素都要移动，并修改L-size+1； Int insert(sequence *L, int i, int x)int j;if(L-size)=mavsizeprintf(“线性表已满”)else if (iL-size) printf(“参数不合法”)else for(j=L-size;ji;i+) /j指向顺序表最后一个元素size-1的后面L-listj=listj-1; /先逐个移动元素L

6、-listi=x; /再插入新的元素L-size+; /使得线性表的总长度+1插入算法的时间效率：平均移动元素的次数看做n/2（即移动一半元素），时间复杂度为O(n) （4）删除元素:删除i位置上的元素，将i后面的元素依次往前移，再令L-size-1 ,int insert(sequence *L, int i , int x)int j;if(L-size) =0printf(“线性表为空，无法删除”)else if (iL-size) printf(“参数不合法”)else *x=L-listi;for(j=i+1;jsize-1;i+) / j指向要删除的元素的后一位L-listj-1=

7、listj; /再将i后面的元素逐个前移L-size-;删除算法的时间效率：任意删除一个元素平均需要移动的次数看做n/2（即移动一半元素）时间复杂度为O(n) （5）取元素 *x=L-listi;3. 链式存储的插入，删除的语句如何写，如何判空。（1）定义链式表：typedef struct Node int data; /这样定义就是定义了一个数组 相当于int data struct Node *next; Lnode,*LinkList; /Lnode等价于struct node定义了一个新的数据类型/Lnode *L等价于 LinkList L定义一个指向节点的指针变量 （2）插入元素

8、 Lnode *q=(Lnode *)malloc (sizeof(Lnode) ; /分配一个新的节点空间 q-data=ele; /是该结点的数据域赋值为ele q-next=temp-next; /把插入的节点的指针域指向下一个节点的data域 temp-next=q; /然后让要插入的节点的前一个节点的指针域指向该插入节点的数据域，两者的顺序不能乱，否则的话就丢失了插入节点的后一个节点的指针，找不到他了 （3）删除元素 Lnode * del=temp-next; /单独设置一个指针指向被删除结点以防丢失temp-next=temp-next-next; /删除del的方法就是更改de

9、l-1的指针域,让他指向del+1的数据域，一步成功free(del); /释放删除的节点del的空间 （4）单链表判空 1、不带头结点的单链表first为空的判定条件：first =NULL； 2、带头结点的单链表first为空的判定条件：first -= NULL；4. 顺序存储与链式存储的优缺点。顺序表的存储优点是：方法简单，容易实现；不用为表示节点间的逻辑关系而额外增加储存开销；具有按元素序号随机访问的特点顺序表的存储缺点是：对于n较大的顺序表，插入和删除元素需要移动的次数较大，效率低；需要预先分配足够大的空间，可能会导致大量闲置空间或者出现数据溢出；链式表的优缺点与顺序表相反。在选择

10、存储方式时，若n较大，多进行插入删除操作，建议用链式存储，若按序号访问元素时，建议按顺序表存储（时间效率为O(1)）例题：第3部分1. 字符串的基本操作，什么叫模式匹配、1.1串的定义：字符串（也就是串）是0个或多个字符序列组成的有限序列。l 串就是数据元素为单个字符的特殊线性表。l “qhjkdcbjsb”（隐含结束符0）就是一个字符串，引号起界定作用，“”表示空串，串长为0l “ ”空格串不是空串，串长为空格数1.2串的存储类型：顺序存储：定长顺序存储结构、堆分配存储结构（动态分配连续内存）链式存储1.3串的模式匹配：就是指定一个主串S和子串T，求T在S中第一次出现的位置。 （1）朴素模式

11、匹配（BP算法） 核心思想：主串S和子串T，S1和T1比较，S2与T2比较，直到Sn与Tn都是相等的为止，若Si与Ti不相等，则子串向右移动一个（一个字符）继续比较 时间复杂度：主串S长度为n，子串T长度为m，最多进行m(m-n+1)次，最坏的时间复杂度为O(mn) 效率不高 （2）KMP算法 核心思想：尽量利用已经得到的“部分匹配”的结果信息，不要让i回溯，加快子串右滑的速度，问题由子串决定而不是主串决定的 next数组：是一个智能数组，指导子串下一步改用几号元素去匹配，next数组的next1和next2永远为0和1，其余nextn看n位的前后缀的相同数目 实例：（1）现有子串i=“ABA

12、BAAABA”,求其next数组i9ababaaabaj0123456789next011234223Next数组中对应i数组的值前缀后缀Next的值Nextj1000Nextj2AA1Nextj3AB1Nextj4AA2Nextj5ABAB3Nextj6ABAABA4Nextj7AA2Nextj8AA2Nextj9ABAB3（2）实例，不详细解释主串是S=“bbsbbcdfbb”子串是“bbsbbs”,求next数组T6bbsbbsJ0123456next012123主串是S=“sssssvsd”,子串是T=“ssssb”求next数组S5ssssBl012345Next01234Next数

13、组中对应i数组的值前缀后缀Next的值Nextj1000Nextj2ss1Nextj3ss2Nextj4ssss3Nextj5ssssss4KMP算法的时间复杂度：O(m+n)第4部分1. 栈的基本概念与特点栈和队列也是线性表，只是操作受限制的线性表，他们线性表的区别在于线性表可以在在任意位置插入或删除元素，而栈只能在栈顶操作，队列只能在队尾操作。1.1栈的特点：后进先出（LIFO）可看做装电池，只能对栈顶进行操作1.2存储方式：顺序存储和链式存储 有n个元素的栈的顺序存储 栈的链式存储2. 栈的两种存储结构的基本操作，如何入栈，出栈，判空？操作栈存储方式类型顺序栈链式栈定义数据类型Typed

14、ef struct Int stackmaxsize; Int top;sequencestack;Typedef struct snode Int data; Int snode *next;singlelinkednode;初始化S-top=0;取栈顶*d=S.stackS.top-1;Singlelinkednode *p=head-next;*d=p-data;入栈S-stackS-top=x;S-top+;移动top指针Singlelinkednode *p；p-data=x;p-next=head-next；/先执行head-next=p; /后执行出栈S-top-;直接移动top

15、指针，不用删除原栈顶head-next=head-next-next;free(p);/需要释放出栈的元素判空if(S-top=0) printf(“stack is empty”);If(head-next=null) Printf(“stack is empty”);例题：3. 栈的应用举例（进制转换，递归，迷宫，表达式求值等）栈的应用内容进制转换算法原理：辗转相除法 算法公式：N=(N div 2) * 2 +N mod 2 递归迷宫表达式求值例1：A+(B-C/D)*E （也称为中缀表达式）前缀表达式为：+A*-B/CDE 即运算符在数值前面后缀表达式为：ABCD/-E*+ 运算符在数

16、值后面例2：(a+b)+c*(d+e)+f*(g+h)前缀表达式为：*+ab*+cdeg+gh后缀表达式为：ab+cde+*+f+gh+*例题：4. 队列的基本概念与特点4.1队列的特点：先进先出（FIFO）可看做排队买冰淇淋，只能对队头和队尾进行操作4.2存储方式：顺序存储和链式存储（注意front和rear的位置）队列的顺序存储 队列的链式存储4.3假溢出问题 队列中因为多次出队入队而导致的存储空间不足的问题解决办法：循环队列 front+1=front+1%maxsize;5. 队列的两种存储结构的基本操作，队空，队满，环形队列，假溢出？队列的操作循环队列链式队列定义数据类型Typede

17、f structInt queuemaxsize;Int rear,front,count;seqrencequeue;定义节点类型Typedef struct qnodeInt data；Struct qnode *next;linkedqueuenode;定义队列的结构体Typedef structLinkedqueuenode *front;Linkedqueuenode *front;Lqueue;判空与判满方法一：使用count记录元素个数队列已满count0&rear=front;或count=maxsize;队列已空count=0;方法二：加设标志位出队时置入队时置队列已满：ta

18、g=1 & rear=front队列已空：tag=0 & rear=front方法三：用掉一个存储单元（默认）队列已满：front=(rear+1)%MaxQueueSize队列已空：rear=frontIf(Q.front=null) Printf(“”queue is empty);链式队列不会满入队(在队尾入队)Seqrencequeue Q;Q-queueQ-rear=x;Q-rear=(Q-rear+1)% maxsize;P=(linkedqueuenode *)malloc(sizeof(linkedqueuenode)Q-rear=p;p-next=null;出队（在队头出队）

19、*d=Q-queueQ-front；Q-front=Q-front+1%maxsize;P=Q-front;Q-front=Q-front-next;Free(p;)取队头元素*d=Q-queueQ-front;*d=Q.front-data;例题：6. 队列的应用举例（CPU对资源的管理，图的广度周游等，树的层次周游）7. 写算法：从把一个队列中的元素存储到栈。将一个栈中的元素放于队列中的算法（写算法要求会写程序，核心语句一定要会）（可以直接调用push pop操作）1. 把队列中的元素存到栈中（1） 新建队列与栈并赋值Q=createEmptyQueue_seq();/队列S= creat

20、eEmptyStack_seq();/栈（2）取队头： n=frontQueue_seq(Q);（3）将队头入栈顶：push_seq( S, n );（4）出队： popQueue_seq(Q);2. 把栈中的元素存到队列中（1）取出栈顶： n=top_seq( S);（2）将栈顶入队尾：pushQueue_seq(Q,n);（3）出栈: popStack_seq(S);第5部分1. 二叉树的概念，性质1-61.1树：即树形结构，是数据逻辑结构的一种。 （1）特点：每个结点最多一个前驱结点，多个后继结点 （2）度的概念：结点的度就是结点的孩子数，树的度就是所有结点的度的最大值。 （3）深度的概

21、念：根的层次为0，依次往下数。 （4）实例：磁盘文件的目录结构。 （5）有序树与无序树：即对子树是否加以区别。1.2.1二叉树：结点有限，区分左右子树的有序树。二叉树不是树的特殊情况，树与二叉树的区别在于二叉树是有序的。1.2.2二叉树的分类1.2.3二叉树的性质1.2.4二叉树的存储方式 （1）顺序存储：采用一组连续的存储单元存放二叉树的节点，没有节点的地方需要补上。（2） 链式存储：用一条链表储存二叉树，一个节点有数据域和两个左右孩子的指 针组成，若没有左/右孩子用表示lchilddatarchild1.3线索二叉树1、定义：增加节点标志域，利用这些指针把节点的前驱和后继的节点的信息连接起

22、来，建立线索二叉树，主要是为了保留在各种遍历时得到的节点前驱和后继节点信息（即保留在各种遍历时产生的线性关系）。Lefttaglchilddatarchildrighttag2、实例：中序周游的结果是：CDBAEGHTF,有边相连就无需用虚线相连，无边相连则用虚线连起来2. 二叉树的周游，中，先后，画树先序周游中序周游后序周游顺序根左右左根右左右根实例*+ab-cdA+b*c-dAb+cd-*递归运算void postOrder(BNode p) if (p = NULL) return;visit(p);postOrder(leftChild_btree(p);postOrder(right

23、Child_btree(p);void postOrder(BNode p) if (p = NULL) return;postOrder(leftChild_btree(p);visit(p);postOrder(rightChild_btree(p);void postOrder(BNode p) if (p = NULL) return;postOrder(leftChild_btree(p);postOrder(rightChild_btree(p);visit(p);3. 二叉树的存储结构，写出链式存储结构4. 写算法：二叉树的中序，先序，后序的递归算法，求叶子结点算法求叶子节点的算

24、法代码：Void contleaf(BiTree T,int *count)If(T)If(!T-lchild)&(!T-rlichild) *Count)+; /计算根节点 Countleaf(T-)lchild ,count); /递归调用求左子树的节点 Countleaf(T-)rchild ,count); /递归调用求右子树的节点5. 哈夫曼算法及哈夫曼编码，WPL的计算5.1哈夫曼树相关概念 （1）路径长度：从A-B所经过的分支序列称路径，经过的分支个数称为路径长度 （2）带权路径长度：若二叉树中的叶节点都带有权值，从根节点到叶节点的路径长度与相应的叶节点权值乘积之和称为该树的带权

25、路径长度（WPL）WPL=wi*pi在1,n求和（3）哈夫曼树：一组带权的叶节点可以构造多个二叉树，其中WPL最小的树称为哈夫曼树或最优二叉树。（4）假设哈夫曼树叶子节点的个数为m，则哈夫曼树的分支节点为m-1，总共节点个数为2m-1 5.2哈夫曼树的构造：原则是将权值大的结点靠近根。根节点的值等于所有叶子节点的权值之和 例子：用7，10，1,3,4,6,17构造一棵哈夫曼树 5.3哈夫曼树编码：在哈夫曼树中把每个节点引向左孩子上的边标为0，引向右孩子的边标为1，再从上至下写出节点的编码6. 二叉树与树的转换6.1树的表示方法6.1.1父指针表示法6.1.2孩子链表表示法6.1.3孩子兄弟表示

26、法增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针，即左分支存放孩子节点，有分支存放兄弟节点6.2树与二叉树的转换6.2.1树转为二叉树1、树中同一结点的兄弟相连；2、保留结点的最左孩子连线，删除其它孩子连线；3、调整位置；1. 2. 3. 6.2.2二叉树转为树 即把所有右孩子节点变为兄弟节点1. 2.6.2.3森林转为树 森林中各树先各自转为二叉树;依次连到前一个二叉树的右子树上6.2.4树转为森林 沿着右孩子链搜索，把所有右孩子连线去掉；把得到的每棵二叉树转换为树第6部分 1. 图的概念、图的存储结构，由图写矩阵或由矩阵画图，矩阵的特点，时空复杂度。1.1图的概念：由顶点集合

27、及顶点间的关系集合组成的一种数据结构。图是一种非线性结构，图形结构是数据的逻辑结构的一种，节点使一对多的关系，不具有明显的分层关系。图的基本术语解释及注意事项无向图若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图有向图若 n 个顶点的有向图有 n(n-1) 条边, 称为有向完全图无向完全图在无向图中任意两个顶点之间都有连线有向完全图在有向图中任意两个顶点之间都有连线度顶点的度=出度+入度出度顶点指出去的边入度指向顶点的边权值权值可以表示从前一个工程到后一个工程所需的时间或者代价路径长度路径（path）上边或者弧的数目简单路径若一条路径上顶点不重复出现就称为简单路径简单回路除第

28、一个和最后一个顶点相同外，其余点不重复的回路称简单回路回路第一个顶点和最后一个顶点相同的回路或环连通图无向图中任意两顶点之间有是连通的，没有孤立点称为连通图连通分量无向图的最大连通子图称为连通分量强连通图有向图中任意两顶点之间是连通的称为连通图强连通分量有向图的最大连通子图称为连通分量极小连通子图是指在包含所有顶点并且保证连通的前提下包含原图中最少的边。生成树包含图的全部顶点的一个极小连通子图1.2邻接矩阵顺序存储 （1）邻接矩阵：用两个数组表示图，一个是存储图中顶点信息的一维数组，一个是存储边信息的二维数组。无向图： 有向图： （2）邻接矩阵的特点：a、无向图的邻接矩阵是一个对称矩阵。存放时

29、只需要存放上三角矩阵的元素即可 b、查找图中任一顶点的度方便，易于判定任意两个顶点之间是否有边相连。对于无向图而言，顶点vi的度就是邻接矩阵中第i行或第i列中非o或非的元素个数。对于有向图而言，顶点vi的入度是邻接矩阵中第i列中非0或非的元素个数，顶点vi的出度是邻接矩阵中第i行中非0或非的元素个数。 c、查找图中任一条边或弧的权值方便。 1.2邻接表顺序存储和链式存储的结合 （1）用一个一维顶点数组存储顶点信息，每个顶点元素有data域和指针域，指针域存放该顶点的邻接表的第一个节点的地址。（3）空间复杂度：a、当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)

30、,其中n为顶点数b、当以邻接表作图的存储结构时，找邻接点所需时间为O(e),其中e为无向图中边的数或有向图中弧的数c、当以邻接表作为存储结构时，深度优先遍历图的时间复杂度为O(n + e).2. 图的周游/遍历（注意其存储结构）遍历：从图的某个顶点出发，按照一定的顺序访问图中的每个顶点，且每个顶点有且仅有一个被访问。2.1深度优先遍历：类似与树的先序遍历，遍历的结果不唯一。通常采用栈实现解释：从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接顶点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被遍历过。若此时图中尚有未被访问的顶点，则另选图中一个未被访问的顶点作为起始点，重复

31、上述过程，直到图中所有顶点都被访问到为止。2.2广度优先遍历：类似于树的层次遍历，采用队列实现 解释：在访问了起始点v之后，依次访问 v的邻接点；然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；直到所有顶点都被访问过为止。 2.3两种遍历算法的区别对于上图的遍历中，深度优先遍历得到的结果是：v0,v1,v3,v7,v4,v2,v5,v6 广度优先遍历得到的结果是: v0,v1,v2,v3,v4,v5,v6,v73. 最小生成树算法：PRIM与KRUSKAL算法最小生成树：连通图的生成树中权值总和最小的生成树，称为最小代价生成树(MST)特点：必须包含所有(n)个顶点；最小生成树有且

32、仅有n-1条边；不存在回路。构造方法：prim算法和kruskal算法。（1） prim算法：假设图 G=(V,E) 中已落在生成树上的顶点集为U，则尚未落在生成树上的顶点集为 V-U，从 (V-U) 顶点集中选取顶点w加U集合，顶点 w 需满足下列条件：它和生成树上的顶点之间的边上的权值是在联接这两类顶点的所有边中权值最小。（2） kruskal算法：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止4. 最短路径算法：Dijkstra算法最短路径的概念：即弧的权值之和取最小值的那条路径算法思想：按各

33、条最短路径长度递增的次序，产生最短路径的算法。5. 拓扑排序、关键路径AOE5.1 AOV网：当有一些活动必须在其他活动完成之后才能开始，用顶点表示活动，弧表示活动间的优先关系，这样的有向图称为AOV网5.2 AOE网：用顶点表示事件，弧表示活动，弧上的权值表示活动所需时间构造的有向无环图称为AOE网。5.3拓扑排序算法的步骤：a、在有向图中选择一个入度为0的顶点，输出该顶点 b、从图中删除所有以它为尾的弧 c、重复执行a,b，直到找不到入度为0的顶点，拓扑排序完成。 注：若最终图中仍有顶点存在，不存在入度为0的点，则证明有环 若拓扑排序成功则证明无环路。5.4关键路径：AOE网中存在唯一的、

34、入度为零的顶点，叫做源点，存在唯一的、出度为零的顶点，叫做汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫关键路径。第7部分1. 字典的相关概念,ASL（1） 什么是字典：字典是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。（2） 关键字是数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。（3） 检索：根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素。 1.基于线性表的检索：顺序检索、二分检索2.根据关键码值直接访问：散列检索，基于数组下标的直接检索3.树索引方法：二叉搜索树、字符树、B树（4）平均查找长度ASL查找过程中对关键字需要

35、执行的平均比较次数 其中：n是数据元素的个数Pi是查找第i个数据元素概率（通常取等概率,即Pi=1/n）Ci是找到第i个记录时所经历的比较次数。（5）查找方法1.静态查找1.1顺序表的查找 思想：从顺序表的一端开始扫描，将给定的元素与每个数值比较 成功查找长度ASL: ASL=(n+1)/2，若失败则ASL=n+1 优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL 太大，时间效率太低。 存储：顺序表查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（单链表）1.2二分查找(折半查找) （1）基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素

36、相比，若key小，则缩小至前半部内查找；若key大，则缩小至后半部内查找。在每个区域内再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 （2）对线性表的要求：要求线性表按关键字排序，排序本身是一种费时的运算，所以二分法的时间复杂度最好也是O(nlog 2 n)，增加了算法的时间复杂度 （3）算法ASL=log2 n （4）二分查找只适用于顺序存储结构的有序表，链表无法实现二分查找。 （5）二分查找的比较次数(Ci)需要借用判定树来计算判定树的画法：按照比较的次数生成判定树,比较1次的是根结点,比较2次的在第二层,比较3次的在第三层,.一次类推,也可以说是每次的mid即形成判定树的

37、结点,左子树上的结点是有序表前半部分的所有结点,右子树是后半部分的结点.判定树求平均成功平均查找长度和不成功平均查找长度的方法：例题：2二分查找对线性表的要求，会写二分检索算法。代码如下：int BinarySearch(SequenceList R，ElemType x) int low=0，high=R.size-1，mid； while(lowx.key) /若keymid则在mid右边的元素进行递归查找 low=mid+1； /注意此时在设定low时不用加上mid return -1 /*当lowhigh时表示查找区间为空，查找失败*/2.动态查找二叉排序树二叉搜索树（1）特征a、若左

38、子树非空，则左子树的所有元素均小于根元素 b若右子树非空，则右子树的所有元素均大于根元素 c. 左右子树本身又各是一颗二叉排序树（2）二叉排序树可以通过树的中序周游获得关键字的有序序列（3）二叉排序树的生成：每读入一个元素，建立一个新的结点，若二叉排序树为空，则新插入的结点成为二叉排序树的根；若二叉排序树为非空，则将新结点的值与根结点的值相比较，如果小于根结点的值，则插入到左子树中，若大于根结点的值，则插入到右子树中；若与根结点值相等，则停止插入。 （输入序列 15 13 17 12 14 18）（4）二叉排序树的的查找（5）二叉排序树的插入:（6）二叉排序树的删除： 1、要删除无孩子结点，直

39、接删除该结点2、要删除只有左孩子或右孩子结点，删除该结点，且使被删除结点的双亲结点指向被删除结点的左孩子结点或右孩子结点3、要删除有左右孩子的结点，首先寻找数据元素的关键字值大于要删除结点数据元素关键字的最小值，即寻找要删除结点右子树的最左结点；然后把右子树的最左结点的数据元素值拷贝到要删除的结点上；最后删除右子树的最左结点。（7）平均查找长度：ni 是每层结点个数； Ci 是结点所在层次数；m 为树深。最坏情况：插入的n个元素从一开始就有序（单支树）ASL= (n+1)/2 最好情况：与折半查找中的判定树相同（即形态比较均衡）树的深度为log 2n +1 ASL=log 2(n+1) 1（8

40、）二叉树排序树的算法性能比较：a) 二叉排序树的平均查找长度与二叉树的形态有关。N个节点不同序可能有n！中不同二叉树，其中有的二叉树形态相同。b) 最坏情况下退化为深度为n的单支树，ASL=(n+1)/2c) 最好情况下，二叉排序树的心态比较均匀，类似于完全二叉树，ASL=log2 n，所以需要使用平衡二叉树（见下）。d) 二叉排序树的插入，删除和查找算法的时间复杂度为O(log2 n)3. 散列法中负载因子的概念,设计散列函数需要考虑的因素，拉链法3.1散列表的定义 散列表的目的：使用关键码直接找到记录存储地址 散列表（哈希表）：以关键码k为自变量，通过一定的函数关系h(k)计算 出对应数值的函数值，把这个值作为k的存储地址，检索时用同样的方法得到存储地址，然后得到相应的结点。3.2冲突（碰撞）及负载因子 冲突：是指两个不相等的关键码k1,k2，用散列函数h(k)得到的结果h(k1)=h(k2),这种现象称为冲突。 发生碰撞的两个或多个关键码称为同义词。 负载因子：3.3设计散列函数需要考虑的因素：