数据结构知识点

本文介绍了数据结构的常见知识点，相关算法实践可参考以下文章

第一节 C语言查缺补漏

1.掌握C语言的数据类型(掌握)

         ①这个应该都有基础了,只说下稍微注意下的

         ②在每次for循环,注意结束条件是i<L.length 或 i<n,不带等号

         ③有时排序或者查找时候喜欢把数组第一个元素A[0]当哨兵,也就是暂存元素

2.熟练使用C语言语法(掌握)

         ①默认看此笔记的人都有C语言基础

         ②malloc和free 需要看一下,有时候分配内存时,分配什么类型的,分配几个单元的内存

         ③struct最常用,结构体的定义,联合体和结构体区别

         ④ElemType是自己定义的一个类型比如typedef int ElemType,意思是ElemType等价于int,这样定义无非就是方便阅读

第二节 数据结构基本知识点

1.基本知识(掌握)

①顺序存取:就是存取第N个数据时,必须先访问前(N-1)个数据 (list)

②随机存取:就是存取第N个数据时,不需要访问前(N-1)个数据,直接就可以对第N 个数据操作 (array)

③线性结构:数据元素之间的关系是一一对应的(集合中必存在唯一的第一个和唯一的最后一个元素)

④非线性结构:数据元素之间存在一对多的关系(一个结点元素可能对应多个前驱或后继)

2.数据结构基本概念(掌握)

         ①数据:对客观事物的符号表示,能输入到计算机中并能被计算机处理的符号的总称

         ②数据元素:数据的基本单位,一个数据元素可由若干个不可分割的数据项组成(数据项是最小单位)

         ③数据对象:性质相同的数据元素的集合,是数据的一个子集

         ④数据结构：相互之间存在一种或多种关系特定关系的数据元素集合(有一种错误说法：数据结构是具有结构的数据对象，请注意)

        ⑤根据数据元素之间的不同特性分为:集合、线性结构、树形结构、图状结构或网状结构.(PS:就是上图的非线性结构)

3.逻辑结构和存储结构(掌握)

         ①逻辑结构:指数据的元素之间的逻辑关系,与数据的存储无关,是独立与计算机的

         ②存储结构:数据在计算机中的表示,也称物理结构

         ③顺序表和链表的比较

4.算法分析的基本概念与方法(掌握)

         ①算法的特性

(1)有穷性:算法必须在执行有穷步骤之后结束,每一步都可以在有穷时间内完成

(2)确定性:每条指令必须有切切的含义,相同的输入必定得出相同的输出

(3)可行性:算法中的操作都是可通过已实现的基本运算执行有限次完成

(4)输入输出:输入个数≥0,输出个数≥1(PS:输出个数必须大于1,常考!)

         ②算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求

         ③算法效率分析

                  (1)方法:事后统计方法和事前分析估计方法

                  (2)渐进时间复杂度(时间复杂度):语句的频度指在算法中被重复执行次数

(3)空间复杂度:算法所耗费的存储空间

5.常考知识点题目(掌握)

         ①数据结构：相互之间存在一种或多种关系特定关系的数据元素集合(有一种错误说法：数据结构是具有结构的数据对象，请注意)

         ②线性表的逻辑顺序与物理顺序不一定一致(采用链式不一致)

         ③二维数组是其数据(不是数组！)元素为线性表的线性表

第三节 线性表

1.线性表的基本概念(掌握)

         ①概念:线性表是最常用最简单的一种数据结构,一个线性表是n个数据元素的有限序列

         ②定义

                  (1)唯一的一个”第一个”元素

                  (2)唯一的一个”最后一个”元素

                  (3)除第一个之外,所有的都只有一个前驱

                  (4)除最后一个之外,所有的都只有一个后继

                  (5)PS:上面四句简单的说就是,元素之间只存在一一对应关系,这是和非线性结构的最大区别

         ③在稍复杂的线性表,一个数据元素可由若干数据项组成,数据元素称为记录,线性表称为文件

2.线性表的存储结构(掌握)

         ①顺序存储和链式存储,链式存储一般用单链表双链表(代码都在程序里)

         ②顺序表和链表区别

                  (1)存取方式:顺序表可以随机存储,链表只能顺序存储

                  (2)逻辑结构和物理结构:很简单

                  (3)顺序表支持随机访问,查找速度快。链表查找效率不高,但是插入删除速度效率更高

                  (4)空间分配:顺序表一单分配内存了,使用中不可动态更改,链表则随意

3.顺序和链式下对线性表的各种操作(掌握)

         ①都在程序里

第四节 栈和队列

1.基本知识(掌握)

         ①堆栈和栈:堆栈本质上就是栈,只是换了个名字

2.堆栈和队列的基本概念、特征、存储结构(掌握)

         ①基本概念与特征

                  (1)栈:只能在表尾进行插入删除操作的线性表,后进先出(LIFO),实现方式有顺序栈和链栈

                  (2)队列:只允许在队尾插入、队头出来,先进先出(FIFO)

         ②存储结构和逻辑结构

                  (1)逻辑结构:本质上堆栈都是线性表,区别在于他们是操作受限的线性表

                  (2)存储结构:都可以用顺序和链式存储,顺序可以用来做循环队列

3.顺序和链式下对线性表进行的操作(掌握)

         ①都在程序里

4.补充知识点(掌握)

         ①设栈为S

                  (1)初始化：S.top == -1

                  (2)普通栈判断栈空：S.top == -1

         ②设队列为Q

                  (1)初始化队列：Q.front == Q.rear == 0

                  (2)front永远指向当前最早进队列的元素，rear永远指向当前最新进队列的元素

                  (3)普通队列判断队列空：Q.front == Q.rear == 0

        (PS):(不能用Q.rear == MaxSize当作队满条件)

                  (4)普通队列会出现假溢出现象，即数组虽然有存元素的空位置，但是再入队会上溢出的现象，所以出现了循环队列

                  (5)循环队列(注意判断队满队空的区别)

                          1.初始化：Q.front == Q.rear == 0

                          2.入队：  Q.rear = (Q.rear + 1)%MaxSize

                          3.出队：  Q.front = (Q.front + 1)%MaxSize

                          4.判断队满： (Q.rear + 1)%MaxSize == Q.front

                          5.判断队空： Q.front == Q.rear

                          6.队列中元素： (Q.rear – Q.front +Maxsize )%MaxSize

         ③栈和队列的共同点：都是只允许在端点操作

         ④最适合做链队的链表是只带队尾指针的循环单链表

第五节 串

1.易混淆概念知识点与疑难解释(掌握)

         ①空串与空白串

                  空串:指不包含任何字符的串,长度为0

                  空白串:指一个或多个空格的串(空格也是字符)

         ②串的定长分配弊端:对串的操作时间复杂度基于串长

         ③串是一种特殊的线性表，特殊性体现在数据元素是一个字符

         ④串的两种基本存储方式是顺序存储方式和链式存储方式

         .

2.串的三种存储结构(掌握)

         ①定长顺序存储表示

                  用一组地址连续的存储单元储存串,其中大小需要预定好

                  #define MaxStrlen 255   //一个例子

                  char SString[MaxStrlen]  //C语言中以’\0’结束

         ②堆分配存储表示

                  仍然以一组地址连续的存储单元储存串,但是储存空间是动态获得

                  typdef{

                          char *ch;

                          int length;

}HString;

str = (*char)malloc(sizeof(char)) //为str申请空间

free(str);//释放str的空间

         ③链式分配存储表示(一般做题情况下不用这个方式)

                  每个字符存储的地方可以是离散化的

                  存储量大且操作复杂,一般不用

3.串的基本操作算法(掌握)

        很简单,大概看下就行了 课本70页

4.串的模式匹配算(大纲不要求,最好了解下,以前考过)

         ①简单模式匹配算法

                  暴力破解,方法特别简单

                  从子串第一个和主串第一个位置开始匹配

                  (1)若相等,则继续逐个比较后面的字符,直到匹配完成,则成功

                  (2)若遇到一个不等,则从主串下个字符开始再和子串第一个开始重新比较,重复

                  (3)主串比较完之前如果匹配成功就成功,如果主串结束还没匹配就匹配失败

         ②改进的模式匹配算法KMP(稍微看一下,知道怎么算next数组)

(1)思想:在①基础上,当每次匹配到不等的字符时,不把子串回溯回去,而是利用已经得到的“部分匹配”将子串尽可能向右滑动。

(2)考法:一般就是考求next数组,可以多看看书,KMP有点难不太好理解 王道P265

第六节 数组、广义表、稀疏矩阵

1.数组(掌握)

         ①数组一般不作插入删除操作,所以数组一般用顺序存储结构

         ②Array[m][n];//m行n列

         ③一般会考给你Array[0][0]的地址,求Arrary[x][y]的地址,注意数组类型

2.稀疏矩阵(掌握)

         ①稀疏矩阵一般用顺序表存储(一个Struct结构体)

         ②矩阵的稀疏因子=  其中t是不为的元素

         ③一般认为稀疏因子≤0.05时是稀疏矩阵

         ④稀疏矩阵压缩只存储非零元的下标和值,即三元组 ，还有一种方法是十字链表法(三元组是考点，十字链表法不常用)

3.广义表(掌握) (大写的是广义表,小写的是原子)

         ①广义表中的元素可以具有不同的结构,所以一般采用链式存储结构

         ②广义表A的元素ai,若ai是数据元素称其为A的原子,若不是数据元素称为A的子表

         ③第一个元素a1是A的表头,其余元素组成的表尾A的表尾

         ④举例 C=(a,(b,c,d)) 广义表长度为2,两个元素分别为原子a和子表(b,c,d)

         ⑤E=(a,E),递归表,长度为2,无穷表

         ⑥广义表() 和 广义表(())不同,前者是空表长度为0,后者不是空表长度为1

         ⑦求广义表深度的时间复杂度为O(n)

         ⑧例题(完全理解,考试就考这个,一道填空题或者选择)

                  已知广义表A=((a,b,c),(d,e,f)),则广义表运算head(tail(tail(A))) ;(这道题多方查证做法是这样，记住)

                          tail(A)=((d,e,f))

                          tail(tail(A))=()  ;这说明不管怎么操作tail一定是一个表

                          head(tail(tail(A)))=空表不能操作

第七节 树与二叉树

1.树的概念与基本术语(掌握)

         ①树是n个结点的有限集合(n≥0),n=0时为空树

         ②树只有唯一一个根结点,n大于1时其余集合是它的子树

2.二叉树的概念、存储结构与遍历(掌握)

         ①概念:在树的基础上,每个结点最多有2个子树,称为左、右子树(左右子树不能颠倒顺序,选择题会考此知识点)

         ②存储结构:可以用顺序存储(注意是可以用,不是不能用),但是链式存储最常用

         ③遍历:主要是前中后序递归遍历,前中后序非递归遍历,层序遍历。后序非递归有点复杂,能理解最好,程序里面有详细注释

3.利用二叉树遍历操作解决实际问题(掌握)

         ①王道书上的题和历年的题我都写在程序里了,注释充足

4.森林的概念和遍历(了解)

         ①主要了解森林和二叉树的互相转换方法,王道书上写的比较详细,课后题建议全做

5.哈夫曼树的概念与应用(掌握)

         ①这个相对简单,做几道题基本上就会了

②王道书上写的比较详细,课后题都做了

6.关于一些树的性质(掌握)

①二叉树中 叶子结点数 = 度为2的结点 + 1

②结点N的层次为

③具有N个结点的完全二叉树的高度为 或

④完全二叉树和满二叉树的区别是，完全二叉树最后一层只有左边有连续的叶子结点(可以只有一个左孩子)

7.关于这章的一些重要的知识点(掌握)

①二叉排序树和二分查找类似,平均时间性能差不多,但是二分查找判定树唯一,二叉排序树不唯一,相同的关键字可能生成不同的二叉树。

         ②静态查找表:只做查找操作的查找表。动态查找表:插入或删除

         ③平衡二叉树,左右孩子高度差不超过1,高度差被定义为平衡因子

         ④WPL计算时 路径是边的条数,比结点少一个。(★)

         ⑤如果没有一个编码是另一个编码的前缀,则称为前缀编码

         ⑦哈夫曼树构造出来并不唯一,但是所有的哈夫曼树带权路径长度相等且最优

         ⑧平衡二叉树的构造,所需的最少结点数, 为构造h层所需结点数 = 构造h-1层所需结点数 + 构造h-2层所需结点数其中  0层需要0个结点,1层需要1个结点。

         ⑨度为m的哈夫曼树中只0有度为0和m的结点

         ⑩树和二叉树的转换：左孩子右兄弟，所以转换后的二叉树没有右子树

         ⑪森林和二叉树的转换：先把森林的每个树转换为二叉树，再把后一个树的连到前一个树的左孩子

         ⑫线索二叉树中：TAG等于0表示是指针，等于1表示是线索

第八节 图

1.图的概念(掌握)

         ①无向图

                  (1)连通:v到w 和 w到v都有路径

                  (2)连通图:图中任意2个顶点都是连通的

                  (3)极大连通子图:连通的无向图只有一个极大连通子图,不连通的无向图可以拆分为若干个连通的无向图(可以存在无向图和有向图中)

                  (4)极小连通子图:基本上就是生成树,加一个边就会多一个回路,减一个边就会使图不连通(只能存在无向图中)

                  (5)连通分量:无向图的极大连通子图

         ②有向图

                  (1)强连通图:图中任意2个顶点都有相互的路径

                  (2)强连通分量:极大强连通子图

         ③网:图中每条边上都有一个数字,称为权值,该图称为带权图,也称为网

         ④路径:p到q的路径是顶点序列p.p1.p2……到q ,q=p时称为环

         ⑤简单路径:一个路径中,顶点不重复出现

         ⑥简单回路:一个路径中,只有第一个顶点和最后一个顶点重复

         ⑦有向树:除第一个顶点入度为0,其余顶点入度为1,根到任何顶点有通路

         ⑧简单路径：简单路径是指顶点序列中顶点不重复出现的路径

2.图常用的存储方法(掌握)

         ①邻接矩阵(顺序结构)

                  (1)利弊:不能快速测出有多少边,浪费大量空间

         ②邻接表(顺序+链式结构) 稀疏图用邻接表节省空间

                  (1)利弊:如果是无向图,存储需要O(V+2E),如果是有向图,存储需要O(V+E),在邻接表中查找2个顶点是否相连需要时间复杂度O(n)

         ③十字链表(链式结构)顶点间是顺序存储,只针对有向图

         ④邻接多重表(链式结构)               只针对无向图

         ⑤邻接表可以存储有向图

         ⑥补充考点

                  (1)图的邻接表表示不唯一,图的邻接矩阵表示唯一

                  (2)无向图的邻接矩阵是对称的，矩阵中1的个数刚好是边的2倍

                  (3)有向图的邻接矩阵中，第i行的和是顶点i的出度，第i列的和是顶点i的入度

                  (4)有向图连通是任意两个顶点之间都要有路径，所以具有n个顶点的有向图至少需要n个边才能构成连通图

                  (5)判断有向图是否有环用深度优先遍历和拓扑排序

                  (6)关键路径是图中源点到汇点的最长路径

                  (7)关键路径中的某一个活动延长后必将延长整个活动完成时间，但是若某个活动时间缩短则不一定缩短整个活动完成时间

                  (8)图的深度优先遍历算法类似于二叉树的先序遍历，广度优先算法类似于层序遍历

                  (9)无向图邻接矩阵不相连的边用0表示，有向图用∞表示

3.图的遍历与连通(掌握)

         ①BFS广度优先遍历(和层序遍历类似)

                  (1)无论何种存储方式,都需借助一个辅助队列每个顶点需入队一次所以空间复杂度O(V)

                  (2)采用邻接表存储   搜索结点为O(V),搜索边为O(E),所以时间复杂度O(V+E)

                  (3)采用邻接矩阵存储 查找每个顶点的邻接点都需要O(V),所以时间复杂度O(V²)

         ②DFS深度优先遍历(和前序遍历类似)

                  (1)需要借助一个工作栈,所以空间复杂度为O(V)

                  (2)采用邻接表存储   搜索结点为O(V),搜索边为O(E),所以时间复杂度O(V+E)

                  (3)采用邻接矩阵存储 查找每个顶点的邻接点都需要O(V),所以时间复杂度O(V²)

         ③补充考点

                  (1)非强连通分量调用一次BFS和DFS不能访问到该连通分量所有顶点

                  (2)判断有向图是否存在回路：拓扑排序 无向图用：深度优先遍历★★★

                  (3)DFS和BFS的邻接表形式时间复杂度都为O(V+E)，邻接矩阵形式时间复杂度都为O(V²)，注意和用的存储方式有关

4.最小生成树(Prim和Kruskal) (掌握)

         ①思想很简单,但是严蔚敏书上写的太难懂了

         ②看我的程序里面的, 我每一行都注释了

         ③考点

                  (1)Prim和Kruskal算法都只针对于无向图

                  (2)Prim时间复杂度O(v^2)适合稠密图,即点少边多

                  (3)Kruskal时间复杂度O(eloge)适合稀疏图,即点多边少

                  (4)什么样的图最小生成树唯一？ 答：如果途中所有边权值都不相等，则最小生成树唯一

5.拓扑排序(掌握)

         ①概念

                  (1)DAG图:有向无环图(拓扑排序是针对DAG图的) 

                  (2)AOV网:用DAG图表示的工程

                  (3)拓扑排序:由有向无环图组成的顶点序列 满足以下条件:

                          1.每个顶点出现一次

                          2.若顶点A在B前,则图中没有B到A的路径

                  (4)时间复杂度O(V+E)

         ②求解过程和算法

                  (1)从AOV网中选一个没有前驱的点(也就是入度为0的点),输出这个点

                  (2)删除这个点,删除这个点发出的所有有向边

                  (3)重复前两步,直到网中没有点或者只剩回路

         ③补充考点★★

                  (1)AOV网和AOE网都是有向无环图DAG

                  (2)AOV网是活动在顶点上的网，顶点表示活动、边无权值、边代表活动的先后顺序

                  (3)AOE网是活动在边上的网，    边表示活动、边有权值、边代表活动持续时间

6.关键路径(掌握)

         ①概念介绍

                  (1)AOE网

                          1.只有某顶点所代表事件发生后,从该顶点出发的活动才能开始

                          2.只有在指向某顶点的各有向边所代表的活动都已经结束时,该顶点所代表的事情才能发生  

                          3.(AOE网只有一个入度为0的点,也只有一个出度为0的点)

                  (2)关键路径:从原点到汇点具有最大路径长度的路径，(图中最长路径、整个工期所完成的最短时间)

                  (3)关键活动:关键路径上的活动称为关键活动

                  (4)完成整个工程的最短时间就是关键路径的长度,也就是关键路径上各活动花销总和

                  (5)★重点★   顶点表示事件,边表示活动

         ②关键路径的计算

                  (1)事件Vk最早发生时间ve(k)：源点到顶点k的路径的最长者

                          1.先算出指向顶点k的那几条边分别加上各自起点的最早发生时间

                          2.再根据算出的结果取最大的那个即为顶点k的最早发生时间。

                          3.这是一个递归的过程,要从第一个算到最后一个,顺序算。第一个边的最早发生时间为0

                          4.备注：实质上，只有所有指向顶点k的所有活动发生后，顶点k的事件才能开始。

                  (2)事件Vk最迟发生时间vl(k)：不推迟整个工期完成前提下该时间最迟必须发生的时间

                          1.顶点k最晚发生的时间,从最后一个点往回推,vl(最后点)=ve(最后点)

                          2.顶点k最晚发生的时间=vl(最后点) -顶点k到汇点的最长路径(即计算顶点k到汇点的所有路径的长度，取最大值)

                  (3)活动ai的最早开始时间e(i)：就是该活动起点对应事件的最早发生时间

                          1.指该活动的起点k所表示的事件最早发生时间

                  (4)活动ai的最迟开始时间e(i)：就是该活动终点对应事件的最迟发生时间减去该活动耗时

                          1.指该活动的终点k所表示的事件最迟发生时间 – 该活动所需时间

                  (5)一个活动ai的最迟开始时间 –  ai的最早开始时间 d(i) = l(i) – e(i)

                          1.指该活动完成的时间余量,即不增加工期总时间的情况下,这个活动能拖延的最长时间,如果d(i)=0,那么说明这个活动不能拖延(关键路径上所有活动d(i)=0)

                  (6)所有d(i)=0的活动构成关键路径,或者说e(i)=l(i)的活动构成关键路径

         ③图示说明

         ④补充考点(真题考过)

                  (1)事件的最早发生时间就是由这个事件所发出的活动的最早发生时间

                  (2)事件的最迟发生时间减去以该事件为结束点的活动的持续时间就是活动的最迟发生时间

                  (3)求关键路径是以拓扑排序为基础的

7.最短路径(掌握,考纲没说但是考过)

         ①迪杰斯特拉算法(Dijkstra)：从一个点求到所有点的最短路径

                  (1)只对一个点求最短路径的时间复杂度是O(V^2)

                  (2)对所有点求时间复杂度是O(V^3)

                  (3)不适用于边带负权值的情况

         ②佛罗伊德算法(Floyd)：求每一对顶点间的最短路径

                  (1)时间复杂度也是O(V^3)，但是形式上简单，实际效率也很高

                  (2)可以允许途中带负权值点但是不能带回路。

第九节 查找

1. 数据表的静态查找方法(顺序、二分、索引 ) (掌握)

PS 引入哨兵的意义:不用判断数组是否会越界

         ①顺序查找:从表的最后一个记录开始,逐个进行关键字比对

         ②折半查找:又称为二分法,不适合链式

         ③分块查找:又称索引顺序查找。一个索引表

         最大关键字

         起始地址

2.B树和B+树(了解)

         ①B树的阶:B树中所有结点中 孩子结点数的最大值称为B树的阶

②B树的概念

         一颗m阶B数或为空树,或为满足如下特性

         1.树中每个结点最多有m颗子树(即最多m-1个关键字)

         2.若根结点不是终端结点,则至少有2颗树

         3.除根结点外,所有非叶结点 至少有上界[m/2]颗子树

③B+树

         多一个条件:每个结点的子树 数目必须等于关键字

3.数据表的动态查找方法(二叉排序树和平衡二叉树)(掌握)

         ①二叉排序树:也称二叉查找树。要么是空树,要么具有如下特性

                                      ①若左子树不为空,则左子树所有结点均小于根结点

                                      ②若右子树不为空,则右子树所有结点均大于根节点

                                      ③它的左右子树都是二叉排序树

                  对于高度为H的二叉排序树分析

①插入删除时间复杂度为O(H)

②查找的时间复杂度和二分法一样

③ :和二分法一样

                  PS当有序表是静态表宜采用顺序存储,动态表宜采用二叉排序树作为逻辑结构

         ②平衡二叉树:为防止树高度增加过快,降低二叉树的性能,所以规定在插入删除时要保证任意结点的左右子树高度差不超过1,这样的树称为AVL树

                            所以AVL要么是空树,要么具有左右子树都是平衡二叉树

         ③AVL的调整:需要完全掌握LL、RR、RL、LR的调整方法

                  (1) http://blog.csdn.net/lemon_tree12138/article/details/50393548 这个博客写的很不错,一直往下翻看图

4.哈希表的概念和应用方法(掌握)

         ①介绍

(1)以前的查找是关键字之间不存在确定关系,所以查找时要进行一系列比较。这类查找是建立在比较的基础上,效率取决于比较次数

(2)散列函数:一个把表中关键字映射成该关键字所对应地址的函数,其中两个或以上关键字映射到同一地址称为冲突,这些不同关键字称为同义词

(3)散列表:根据关键字而直接访问的数据结构,理想情况下时间复杂度O(1)

         ②散列函数构造方法

                  (1)备注:定义域包括所有关键字,计算的地址尽量均匀,函数尽量简单

                  (2)不同构造方法比较

         ③处理冲突方法

                  PS:任何函数都不可能绝对避免冲突,必须考虑发生冲突时找下个空的Hash地址

                  (1)开放定址法

                           m表示散列表长,di为增量

                           可存放新表项的空闲地址既向它同义词表项开放,又向它的非同义词表项开放

                           通常有四种取法

                                   (1)线性探测法:当 =1,2,3,4…….,m-1时候,方法思想:当发生冲突就顺序查看下一个单元,直到找出一个空闲单元,但是会大大降低查找效率

                                   (2)平方探测法:当 =1^2,(-1)^2,(2)^2,(-2)^2………k^2,(-k)^2,其中k<=m/2,m必须可以表示为4k+3的一个质数,又称二次探测法。这是种较好的处理冲突方式,可以避免堆积问题,虽然不能探测到所有单元,但是可以探测一半的

                                   (3)再散列法:当 时,又称双散列法。最多经过m-1次散列就可以遍历所有位置,回到H0

                                   (4)伪随机法:当 伪随机数序列时

                                   PS:在开放定值情况下不能随便删除物理表中已有元素,否则会截断其他元素的查找标记。若一定要删除,可以做一个删除标记,逻辑删除

                  (2)拉链法

         对冲突的同义词存放在一个线性链表中,王道P255,这个线性表由其散列地址唯一标识(有空在看)

         ④散列查找性能分析

                  (1)散列查找和构造散列表过程基本一致

                  (2)装填因子 ,定义为一个表满的程度,即

                  (3)散列表的平均查找长度依赖于装填因子， 越小越好

6.补充重点(掌握)

         ①平均查找长度详细汇总(特别重点！)

                  (1)思想

                          ①顺序查找

                                   1.对于有n个元素的表，对第i个元素需要进行n-i+1次比较

                                   2.一般默认每个元素查找概率都为

                          ②折半查找(二分查找)

                                   1.仅适用于有序的顺序表(考点)

                                   2.思想不难，看书

                          ③分块查找(索引查找)

                                   1.分块查找分2步①在索引表中确定待查记录的块(顺序或折半)②在块内顺序查找

                                   2.把线性表分为若干块，块内可以无序，但是块间必须有序

                  (2)查找长度对比(重点考点)

         ②选择题常考

                  (1)堆积：用线性探测法处理冲突时,当表中i,i+1,i+2个位置上都有数据时,下一个散列地址如果是i,i+1,i+2和i+3都会要求填入i+3的位置,多个第一个散列地址不同的记录争夺同一个后继散列地址。

                  (2)链地址法不会产生堆积现象！

                  (3)堆积现象无法完全避免！所以在处理冲突时不可能避免产生聚集现象

                  (4)平衡二叉树的平衡因子可以取-1,0,1(注意可以取负一)

第十节 内部排序

1.掌握内部排序的方法(掌握)

         在程序里面有

2.内部排序算法的比较(掌握)

         ①考纲一般按照 时空复杂度 算法稳定性 算法过程特征 考察

         ②各种比较

                  (1)单看稳定性,最简单(冒泡、直接插入)和最复杂(归并、基数)稳定,其他的都不稳定

                  (2)但看空间复杂度,除了快速排序、归并排序、基数排序,其他的空间复杂度都是O(1)

                  (3)交换类和选择类每趟都有一个关键字到位★★★

                  (5)交换类排序排序趟数和原始序列状态有关

                  (6)简单选择排序是在后面找一个最小的和前面的交换，直接插入排序是在后面先找一个，再到前面找一个合适位置插入

         ③备注

                  (1)快速排序的2种方法

                          ①复杂版：把基数x提出来,先从右边找比x小的数放到x位置这时就空下一个位置,再从左边找一个比x大的数填上刚才的空位,这时又空了一个,就这样一直找,到最后x插入空的位置

                          ②简单版：基数x不动,从右边找一个比x小的再从左边找一个比x大的交换,一直交换下去,最后当左右指针相遇,交换当前位置的值和x,需要注意的是右先动左后动

第十一节 常考易错易混题目总结

①计算机算法指什么？ 答：解决问题的有限运算序列

②一棵树转换为二叉树形态唯一！