数据结构高分攻略：期末期中速成秘籍保证过!

大致考点解析

有序和降序

二分查找

时间复杂度是多少

冒泡排序

从第三个数开始, 是前两个数的和

设计函数斐波那契数列计算第n项的程序

先序中序后续遍历

有向图和无向图的顶点的度的计算

二叉树五个基本性质

完全二叉树

KMP算法

算法的五大要点

数据结构的三要素

队列: 先进先出, 在队头队尾实现操作 (类似地铁)

栈: 先进后出, 只能在栈顶实现操作 (类似箱子)

栈和队列的特点

什么是逻辑结构和物理结构

考点

大题10分

编程题

统计40分

总共4题

每题10分

应用题

统计20分

总共10题

每题2分

填空题

统计30分

总共15题

每题2分

选择题

数据结构基本概念

Data_Structure=(D, S), (D, R)中的R指的是数据关系

相互之间存在一种或多种特定关系的数据元素的集合

数据结构

一个数据元素可由若干个数据项组成

构成数据元素的不可分割的最小单位

数据项

数据的基本单位

数据元素

数据结构

数据的运算

哈希存储

散列存储

索引表

索引存储

借助指示元素存储地址的指针

链式存储 (适用于大量数据的插入和删除)

逻辑上相邻的元素存储在物理位置也相邻的存储单元中

顺序存储 (常用)

存储结构 (物理结构)

图形结构或网状结构

存在一对多的关系

树形结构

集合

非线性结构

一般线性表, 栈, 队列, 串, 数组

线性表

线性结构

逻辑结构

算法的五大特征

输出

输入

可行性

确定性

有穷性

算法分析的目的

分析算法的效率以求改进

好算法的特征

效率与低存储量需求

健壮性

可读性

正确性

时间复杂度

计算出算法的执行次数, 然后只观察n的算术式

线性表的定义

除最后一个元素外, 每个元素有且仅有一个直接后继

除第一个元素外, 每个元素有且仅有一个直接前驱

具有相同数据类型的 n(n ≥ 0) 个数据元素的有限序列

定义

顺序表的结构

基本操作

InitList(&L): //初始化表 Length(L): //求表长 LocateElem(L, e): //按值查找操作 GetElem(L, i): //按位查找操作 ListInsert(&L, i, e): //插入操作 ListDelete(&L, i, &e): //删除操作 PrintList(L): //输出操作 Empty(L): //判空操作 DestroyList(&L): //销毁操作 

线性表的顺序存储类型描述

// 静态分配 #define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int length; }SqList; //typedef将这个结构体改名为SqList // 动态分配 #define InitSize 100 typedef struct{ ElemType *data; int MaxSize, length; }SeqList; L.data = (ElemType*) malloc (sizeof(ElemType) * InitSize); // 这是C语言的初始动态分配语句 

存储密度大

顺序表逻辑上相邻的元素物理上也相邻, 所以插入和删除操作需要移动大量元素

顺序表最主要的特点是随机存取

顺序表的特点

顺序表的实现

插入操作

bool ListInsert(Sqlist &L, int i, ElemType e){ if(i < 1 || i > L.length + 1) return false; for(int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1]; L.data[i - 1] = e; L.length++; return true; } // 插入操作的时间复杂度为 O(n) // 总共有 n 个元素, 往第 i 个元素位置插入元素需要移动 n - (i - 1) 次 

删除操作

bool ListInsert(Sqlist &L, int i, ElemType e){ if(i < 1 || i > L.length + 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) // 总共有 n 个元素, 往第 i 个元素位置插入元素需要移动 n - i 次 

按值查找操作

int LocateElem(Sqlist L, Elemtype e){ int i; for(i = 0; i < L.length; i++) if(L.data[i] == e) return i + 1; return 0; } // &L代表可读可写, L表示只可读 

按位查找操作

int GetElem(Sqlist L, int i){ if(i < 1 || i > L.length) return 0; return L.data[i - 1]; } // &L代表可读可写, L表示只可读 

将两个有序顺序表A, B合并为一个新的有序顺序表C, 并用函数返回结果顺序表

例题

bool Merge(SqList A, SqList B, SqList &C){ if(A.length + B.length > C.MaxSize) return false; int i = 0, j = 0, k = 0; while(i < A.length && j < B.length){ if(A.data[i] <= B.data[j]) C.data[k++] = A.data[i++]; else C.data[k++] = B.data[j++]; } while(i < A.length) C.data[k++] = A.data[i++]; while(j < B.length) C.data[k++] = B.data[i++]; C.length = k; return true; } 

单链表的结构

单链表结点类型的描述

typedef struct LNode{ ElemType data; // 表示数据域 struct LNode *next; // 表示指针域 }LNode, *LinkList; 

单链表的实现

按序号查找结点值

LNode *GetElem(LinkList L, int i){ int j = 1; LNode *p = L -> next; if(i == 0) return L; if(i < 0) return NULL; while(p && j < i){ p = p -> next; j++; } return p; } // 时间复杂度为 O(n) 

按值查找表结点

LNode *GetElem(LinkList L, ElemType e){ LNode *p = L -> next; while(p != NULL && p -> data != e) p = p -> next; return p; } // 时间复杂度为 O(n) 

插入结点操作 (在p结点后插入新结点)

p = GetElem(L, i -1); s -> next = p -> next; p -> next = s; 

前插操作 (后插操作)

s -> next = p -> next; p -> next = s; temp = p -> data; p -> data = s -> data; s -> data = temp; 

删除操作 (将p结点后的q结点删除)

p = GetElem(L, i - 1); q = p -> next; p -> next = q -> next; free(q); 

双链表 (有指针 prior 和 next)

双链表结点类型的描述如下:

typedef struct DNode{ ElemType data; struct DNode *prior, *next; }DNode, *DLinkList; 

插入操作 (在p结点后插入新结点)

s -> next = p -> next; p -> next -> prior = s; s -> prior = p; p -> next = s; // 第一行和第二行必须第四行前面 

删除操作 (将p结点后的q结点删除)

p -> next = q -> next; q -> next -> prior = p; free(q); 

循环链表

循环单链表

L -> next = L; // 循环链表中的每一个元素都有后继 // 循环链表中不会出现NULL 

循环双链表

L -> next = L; L -> prior = L; // 循环链表中的每一个元素都有后继 // 循环链表中不会出现NULL 

栈的基本概念

栈的基本操作

n个不同元素进栈, 出栈元素不同排列的个数为1n+1C2nn\dfrac{1}{n+1} C_{2n}^{n}n+11​C2nn​

大招

卡特兰数通项公式

先进后出

特性

InitStack(&S) // 初始化一个空栈 StackEmpty(S) //判断一个栈是否为空 Push(&S, x) //进栈 Pop(&S, &x) //出栈 GetTop(S, &x) //读取栈顶元素 DestroyStack(&S) //销毁栈, 并释放栈S占用的存储空间 

栈的存储结构

栈的顺序存储类型可描述为:

顺序栈的实现

#define MaxSize 50 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; else return false; } // 进栈, 先移动栈顶指针, 再存入元素 bool Push(SqStack &S, ElemType x){ if(S.top == MaxSize - 1) return false; S.data[++S.top] = x; return true; } // 出栈, 栈非空时, 先取栈顶元素值, 再将栈顶指针 - 1 bool StackEmpty(SqStack &S, ElemType &x){ if(S.top == -1) return false; x = S.data[S.top--]; return true; } // 读取栈顶元素 bool StackEmpty(SqStack &S, ElemType &x){ if(S.top == -1) return false; x = S.data[S.top]; return true; 

栈的链式存储类型可描述为

便于多个栈共享存储空间和提高其效率, 且不存在栈满上溢的情况

链栈的优点

栈的链式结构

共享栈

typedef struct LinkNode{ ElemType data; struct LinkNode *next; }*LiStack; 

队列的基本概念

队列的基本操作

front指向队首指针, rear指向队尾元素的下一个位置

先进先出

特性

InitQueue(&Q) // 初始化队列 QueueEmpty(Q) // 判队列空 EnQueue(&Q, x) // 入队 DeQueue(&Q, &x) // 出队 GetHead(Q, &x) // 读队头元素 

队列的存储结构

队列的顺序存储类型可描述为:

#define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front, rear; }SqQueue; 

队列的顺序存储

// 初始状态 Q.front = Q.rear = 0; // 判空状态 Q.front == Q.rear == 0; // 进队操作 // 队不满时, 先送值到队尾元素, 再将队尾指针 + 1 // 出队操作 // 队不空时, 先取队头元素值, 再将队头指针 + 1 

循环队列

// 初始状态 Q.front = Q.rear = 0; // 队首指针进1 Q.front = (Q.front + 1) % MaxSize; // 队尾指针进1 Q.rear = (Q.rear + 1) % MaxSize; // 队列长度 (队列中的元素个数) (Q.rear + MaxSize - Q.front) % MaxSize; 

循环队列

// 队空条件 Q.front == Q.rear; // 队满条件 (Q.rear + 1) % MaxSize == Q.front 

队列的链式存储结构

串的基本概念

串的基本操作

数据元素可以是一个字符

特性

串中任意个连续的字符组成的子序列

子串

由零个或多个字符组成的有限序列

StrCopy(&T, S) StrEmpty(S) StrCompare(T, S) StrLength(S) SubString(&Sub, S, pos, len) Concat(&T, S1, S2) Index(S, T) 

串的简单模式匹配算法

矩阵的压缩存储

具有许多相同矩阵元素或零元素, 并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵

特殊矩阵

稀疏矩阵

三角矩阵

对称矩阵

为多个值相同的元素只分配一个存储空间, 对零元素不分配存储空间, 其目的是为了节省存储空间

压缩存储

树的基本概念

具有 n 个结点的 m 叉树的最小高度为 log⁡m(n(m−1)+1)\log_m \bigl( n(m-1) + 1 \bigr)logm​(n(m−1)+1)

高度为 h 的 m 叉树至多有 (mh−1)/(m−1)(m^h - 1)/(m - 1)(mh−1)/(m−1) 个结点

度为 m 的树中第 i 层上至多有 mi−1m^{i-1}mi−1 个结点

树中的结点数等于所有结点的度数 + 1

树的性质

路径, 路径长度

第六部分

交换后一样就是无序树, 反之亦然

有序树, 无序树

第五部分

树中结点的最大层数\

深度, 高度

第四部分

有相同双亲的结点

兄弟

度 = 0 的结点

叶子结点 (终端结点)

度 > 0 的结点

分支结点 (非终端结点)

第三部分

树中结点的最大度数

树的度

该结点的孩子个数

结点的度

第二部分

祖先, 双亲, 孩子

第一部分

基本术语

n(n ≥ 0)个结点的有限集

二叉树

用链表结点来存储二叉树中的每一个结点

在含有 n 个结点的二叉链表中, 含有 n + 1 个空链域, 含有 n - 1 个非空链域

链式存储结构

指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素，即将完全二叉树上编号为 i 的结点元素存储在一维数组下标 (i一1) 的分量中

顺序存储结构

二叉树的存储结构

具有 n(n > 0) 个结点的完全二叉树的高度为 log2(n+1)log_2 {\bigl(n + 1\bigr)}log2​(n+1) 或 log2n+1log_2 n + 1log2​n+1, 向下取整

完全二叉树

高度为 h 的二叉树至多有 2h−12^h - 12h−1 个结点

非空二叉树上第 k 层上至多有 2k−12^{k-1}2k−1 个结点

非空二叉树上的叶子结点数等于度为 2 的结点数 + 1, 即 n0=n2+1n_0 = n_2 + 1n0​=n2​+1

二叉树的性质

树上任一结点的左子树和右子树的深度之差绝对值不超过 1

平衡二叉树

二叉排序树

完全二叉树

满二叉树

类型

n(n ≥ 0)个结点的有限集合

typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 

二叉树的遍历

代码实现

先序遍历右子树

先序遍历左子树

访问根结点

先序遍历 (NLR)

按某条搜索路径访问树中的每一个结点, 使得每一个结点均被访问一次, 而且仅被访问一次

void PreOrder(BiTree T){ if(T != NULL){ visit(T); PreOrder(T -> lchild); PreOrder(T -> rchild); } } 

代码实现

中序遍历右子树

访问根结点

中序遍历左子树

中序遍历 (LNR)

void InOrder(BiTree T){ if(T != NULL){ InOrder(T -> lchild); visit(T); InOrder(T -> rchild); } } 

代码实现

访问根结点

后序遍历右子树

后序遍历左子树

后序遍历 (LRN)

void PostOrder(BiTree T){ if(T != NULL){ PostOrder(T -> lchild); PostOrder(T -> rchild); visit(T); } } 

层次遍历

void LevelOrder(BiTree T){ InitQueue(Q); BiTNode *p = T; EnQueue(Q, p); while(!lsEmpty(Q)){ DeQueue(Q, p); visit(p); if(p -> lchild != NULL) EnQueue(Q, p -> lchild); if(p -> rchild != NULL) EnQueue(Q, p -> rchild); } } 

树和森林

先子树后根

中序遍历

先根后子树

先序遍历

森林的遍历

先子树后根

后根遍历 (二叉树的中序遍历)

先根后子树

先根遍历 (二叉树的先序遍历)

用某种方式访问树中的每个结点, 且仅访问一次

概念

树的遍历

反之亦然

二叉树转换为树的画法

反之亦然

二叉树转换为森林的画法

以第一棵树的根为轴心顺时针旋转 45°

每棵树的根也可视为兄弟结点, 在每棵树之间加一根连线

将森林中的每一棵树都转化为相应的二叉树

森林转换为二叉树的画法

以树根为轴心, 顺时针旋转 45°

对每个结点, 只保留它与第一个孩子的连线, 抹去与其他孩子的连线

在兄弟结点之间加一条线

树转换成二叉树的画法

孩子兄弟表示法

孩子表示法

双亲表示法

树的存储结构

二叉排序树 (二叉查找树)

若结点有一棵左, 右两棵子树, 则令该结点的直接后继 (直接前驱) 代替该结点, 然后从二叉排序树中删去这个直接后继 (直接前驱), 这样就转换成了前两种情况

若结点只有一棵左子树或者右子树, 则让该结点的子树成为其父结点的子树

若被删除的结点是叶子结点, 则直接删除

二叉排序树的删除

二叉排序树的伪造

若关键字大于根结点值, 则插入到右子树

若关键字小于根结点值, 则插入到左子树

二叉排序树的插入

插入一个新结点, 一定会成为二叉排序树的一个叶子结点

采取中序遍历可得到升序的结果

哈夫曼树

重复步骤 2 和 3 , 直至剩下一棵树为止

从中删除刚才选出的两棵树, 同时将新得到的树加入森林中

构造一个新结点, 从中选取两棵根结点权值最小的树作为新结点的左, 右子树, 并且将新结点的权值置为左, 右子树上根结点的权值之和

将所有结点分别作为仅含一个结点的二叉树

构造哈夫曼树的步骤

带权路径长度最小的二叉树

哈夫曼树简介

树中所有叶节点的带权路径长度之和, 记为 WPL=∑i=1nwiliWPL = \sum_{i=1}^{n} w_i l_iWPL=∑i=1n​wi​li​

树的带权路径长度 WPL

从树的根到任意结点的路径长度与该结点上权值的乘积

结点带权路径长度

树中结点常被赋予一个代表某种意义的数值

权

图的基本概念

路径, 路径长度, 回路

边的权和网

有向图的全部顶点的入度之和 = 出度之和 = 边数

顶点的度 = 入度 + 出度

入度是以顶点 v 为终点的有向边的数目, 出度是以顶点 v 为起点的有向边的数目

有向图

无向图的全部顶点的度的和 = 边数 × 2

无向图

顶点的度, 入度和出度

边数 = 顶点数 - 1

包含图中全部顶点的一个极小连通子图

生成树

既要保持图连通又要使得边数最少的子图

极小连通子图

图中任意两个顶点都是连通的

连通图

连通, 连通图, 极小连通子图

子图, 生成子图

对于有向图, 任意两个顶点之间都存在方向相反的两条弧 n×(n−1)n × (n - 1)n×(n−1)

对于无向图, 任意两个顶点之间都存在边 n×(n−1)/2n × (n - 1)/2n×(n−1)/2

完全图 (简单完全图)

多重图

不存在顶点到自身的边

不存在重复边

简单图

无向图

有向图

基本类型

图的存储结构

邻接多重表法

十字链表法

n 个结点, e 条边的无向图邻接表中, 有 n 个头结点和 2e 个表结点

在有向图的邻接表表示中, 求一个给定的顶点的出度只需计算其邻接表中的结点个数

图的邻接表表示不唯一

对于稀疏图而言, 采用邻接表法表示能极大的节省存储空间

邻接表法

n 个顶点的无向连通图用邻接矩阵表示时, 至少有 2(n−1)2(n - 1)2(n−1) 个非零元素

跟顶点有关, 跟边数无关

邻接矩阵法

图的遍历

深度优先搜索 (类似于树的先序遍历)

广度优先搜索 (类似于二叉树的层次遍历算法)

搜索方式

从图中的某一顶点出发, 按照某种搜索方式沿着图中的所有顶点访问一次且仅访问一次

最小生成树

3. 重复步骤二, 直至图中所有顶点都并入

2. 选边 (权最小, 且不构成回路)

1. 去掉所有边

Kruskal算法

3. 重复步骤二, 直至图中所有顶点都并入

2. 选择一个与当前顶点集合距离最近的顶点, 并将该顶点和相应的边加入进来, 同时不能形成回路

1. 任取一顶点, 去掉所有边

Prim算法

构造最小生成树

带权连通无向图中, 所有生成树中权值之和最小的生成树

概念

最短路径

画表格, 一步接着一步就行, 找出最短权值路径便是答案

d(u, u) = 0, 当u, v不相邻, d(u, v) = +∞+\infty+∞

dijkstra算法

拓扑排序

重复步骤一和步骤二直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止

从网中删除该顶点和所有以它为起点的有向边

从 AOV 网中选择一个没有前驱的顶点并输出

拓扑排序的算法讲解

若存在一条从顶点 A 到顶点 B 的路径, 则在排序中顶点 B 出现在顶点 A 的后面

每个顶点出现且仅出现一次

拓扑排序

顶点表示活动

AOV 网

关键路径

最终将所有的关键活动路径连接形成关键路径

求 AOEAOEAOE 网中所有活动的差额 d()d()d(), 找出所有 d()=0d() = 0d()=0 的活动构成关键路径,即最迟开始时间 - 最早开始时间

根据 vl()vl()vl() 值求所有弧的最迟开始时间 l()l()l(),即该弧的汇点的最迟发生时间 - 权值

根据 ve()ve()ve() 值求所有弧的最早开始时间 e()e()e(),即该弧的源点的最早发生时间

令 vl(汇点)=ve(汇点)vl(汇点) = ve(汇点)vl(汇点)=ve(汇点), 求最迟发生时间 vl()vl()vl(),即 veveve(汇点) - 路径权值, 取较小值

令 ve(源点)=0ve(源点) = 0ve(源点)=0, 求最早发生时间 ve()ve()ve(),即权值最大的路径权值

求关键路径算法解析

d(i)=0d(i) = 0d(i)=0 的活动 aia_iai​ 是关键活动

d(i)=l(i)−e(i)d(i) = l(i) - e(i)d(i)=l(i)−e(i)

一个活动 aia_iai​ 的最迟开始时间 l(i)l(i)l(i) 和其最早开始时间 e(i) 的差额

<vk,vj><v_k, v_j><vk​,vj​> 中 l(i)=vl(j)−Weight(vk,vj)l(i) = vl(j) - Weight(v_k, v_j)l(i)=vl(j)−Weight(vk​,vj​)

指的是该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差

活动 aia_iai​ 的最迟开始时间

<vk,vj><v_k, v_j><vk​,vj​> 中 e(i)=ve(k)e(i) = ve(k)e(i)=ve(k)

指的是该活动弧的起点所表示的事件的最早发生时间

活动 aia_iai​ 的最早开始时间

vl(k)=Min[vl(j)−Weight(vk,vj)]vl(k) = Min[vl(j) - Weight(v_k, v_j)]vl(k)=Min[vl(j)−Weight(vk​,vj​)]

vl(汇点)=ve(汇点)vl(汇点) = ve(汇点)vl(汇点)=ve(汇点)

公式

指的是在不推迟整个工程完成的前提下, 即保证它的后续事件 vjv_jvj​ 在其最迟发生时间 vl(j)vl(j)vl(j) 能够发生时, 该事件最迟必须发生的时间

事件 vkv_kvk​ 最迟发生时间 vl(k)vl(k)vl(k)

ve(k)=Max[ve(j)+Weight(vj,vk)]ve(k) = Max[ve(j) + Weight(v_j, v_k)]ve(k)=Max[ve(j)+Weight(vj​,vk​)]

ve(源点)ve(源点)ve(源点) = 0

公式

指的是从源点 v1v_1v1​ 到顶点 vkv_kvk​

事件 vkv_kvk​ 最早发生时间 ve(k)ve(k)ve(k)

关键路径上的活动

关键活动

从开始顶点 (源点) 到结束顶点 (汇点) 的所有路径中, 具有最大路径长度的路径

关键路径

以顶点表示事件, 以有向边表示活动, 以边上的权值表示完成该活动的开销

AOEAOEAOE 网

相关概念

查找

所有查找过程中进行关键字的比较次数的平均值 ASL=∑i=1nPiCiASL = \sum_{i=1}^{n}P_iC_iASL=∑i=1n​Pi​Ci​

平均查找长度

关键字可以唯一地标识一个记录

主关键字

数据元素中某个数据项的值, 用它可以标识一个数据元素

关键字

用于查找的数据集合

查找表 (查找结构)

相关概念

在数据集合中, 寻找满足某种条件的数据元素的过程

顺序查找

对于线性链表只能进行顺序查找

若查找到表的另一端, 仍未找到符合给定条件的元素, 则返回查找失败的信息

若查找到某个元素的关键字满足条件, 则查找成功, 返回该元素在线性表中的位置.

从线性表的一端开始, 逐个检查关键字是否满足给定的条件

基本思想

typedef struct{ ElemType *elem; int TableLen; }SSTable; int Search_Seq(SSTable ST, ElemType key){ ST.elem[0] = key; for(i=ST.TableLen; ST.elem[i] != key; --i); return i; } 

顺序查找不成功的平均查找长度为 ASL不成功=n+1ASL_{不成功} = n + 1ASL不成功​=n+1

采用顺序查找方法查找长度为 n 的顺序表时, 查找成功的平均查找长度为 ASL成功=∑i=1nPiCi=n+12ASL_{成功} = \sum_{i=1}^{n}P_iC_i = \frac{n + 1}{2}ASL成功​=∑i=1n​Pi​Ci​=2n+1​

折半查找 (二分查找)

代码

仅适用于有序的顺序表

int Binary_Search(Seqlist L, ElemType key) { int low = 0, high = L.TableLen - 1, mid; while(low <= high) { mid = (low + high) / 2; if(L.elem[mid] == key) return mid; else if(L.elem[mid] > key) high = mid - 1; else if(L.elem[mid] < key) low = mid + 1; } } 

二分查找的时间复杂度为 O(log2n)O(log_2 n)O(log2​n)

查找成功的平均查找长度是 ASL=1n∑i=1nli≈log2(n+1)−1ASL = \frac{1}{n}\sum_{i=1}^{n}l_i \approx log_2(n + 1) - 1ASL=n1​∑i=1n​li​≈log2​(n+1)−1

散列表

α 越大, 表示装填的记录越"满", 发生冲突的可能性越大

散列表的平均查找长度依赖于散列表的装填因子 α , 不直接依赖于 n 或 m

装填因子α=表中记录数n/散列表长度m装填因子 α = 表中记录数 n / 散列表长度 m装填因子α=表中记录数n/散列表长度m

装填因子

求查找不成功的平均查找长度

求查找成功的平均查找长度

为了避免非同义词发生冲突, 把所有的同义词存储在一个线性链表中

拉链法

di=Hash2(key)d_i = Hash_2(key)di​=Hash2​(key)

再散列法

di=02,12,−12,22,−22,...,k2,−k2d_i = 0^2, 1^2, -1^2, 2^2, -2^2, ..., k^2, -k^2di​=02,12,−12,22,−22,...,k2,−k2 (k≤m2k ≤ \frac{m}{2}k≤2m​)

平方探测法

di=0,1,2,...,m−1d_i = 0, 1, 2, ..., m - 1di​=0,1,2,...,m−1

线性探测法

did_idi​增量取法

Hi=[H(key)+di]H_i = [H(key)+ d_i]Hi​=[H(key)+di​] % ppp

数学递推公式

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

开放定址法

解决同义词中出现冲突的方法

散列函数可能会把两个或两个以上的不同关键字映射到同一地址

同义词

平方取中法

数字分析法

取一个不大于但最接近或等于 m 的质数 p, H(key)H(key)H(key) = keykeykey % ppp

除留余数法

H(key)=key,H(key)=a×key+bH(key) = key, H(key) = a × key + bH(key)=key,H(key)=a×key+b

直接定址法

散列函数 Hash(key)=AddrHash(key) = AddrHash(key)=Addr

排序的基本概念

指在排序期间元素无法全部同时存放在内存中, 必须在排序的过程中根据要求不断地在内, 外存之间移动的排序

外部排序

基数排序

归并排序

选择排序

交换排序

插入排序

指在排序期间元素全部存在内存中的排序

内部排序

相对位置保持不变

稳定性

性质

插入排序

稳定

稳定性

O(n2)O(n^2)O(n2)

时间效率 (平均时间复杂度)

O(1)O(1)O(1)

空间效率 (平均时间复杂度)

代码

对于 n 个元素而言经过 n - 1 次直接插入排序即可成功

直接插入排序

基本思想: 每次将一个待排序的记录按照其关键字大小插入到前面已排好序的子序列中, 直到全部记录插入完成

void InsertSort(ElemType A[], int n){ int i, j; for(i = 2; i <= n; i++) if(A[i] < A[i - 1]){ A[0] = A[i]; for(j = i - 1; A[0] < A[j]; --j) A[j + 1] = A[j]; A[j + 1] = A[0]; } } 

不稳定

稳定性

因为增量不确定, 故不考虑时间效率

时间效率 (平均时间复杂度)

O(1)O(1)O(1)

空间效率 (平均时间复杂度)

把相隔某个增量 ddd 的记录组成一个子表, 对各个子表分别进行直接插入排序, 当整个表中的元素已呈基本有序时, 再对全体记录进行一次直接插入排序

希尔排序(直接插入排序的升级款)

交换排序

稳定

稳定性

O(n2)O(n^2)O(n2)

时间效率 (平均时间复杂度)

O(1)O(1)O(1)

空间效率 (平均时间复杂度)

代码

对于 n 个元素而言经过 n - 1 次排序即可成功

基本思想是: 从后往前 (或者从前往后) 两两比较相邻元素的值，若为逆序，则进行交换，直到序列比较完，第一趟冒泡结束，结果是将最小的元素交换到待排序列的第一个位置 (或将最大的元素交换到待排序列的最后一个位置)

冒泡排序

void BubbleSort(ElemType A[], int n){ for(i = 0; i < n - 1; i++) flag = false; for(j = n - 1; j > i; j--) if(A[j - 1] > A[j]){ swap(A[j - 1], A[j]); flag = true; } if(flag == false) return; } 

快速排序不适用于原本有序或基本有序的记录序列进行排序

快速排序是所有内部排序算法中平均性能最优的排序算法

不稳定

稳定性

O(nlog2n)O(nlog_2 n)O(nlog2​n)

时间效率

O(log2n)O(log_2 n)O(log2​n)

空间效率

基本思想是: 在待排序表 L[1...n]L[1...n]L[1...n] 中任取一个元素 pivotpivotpivot 作为枢轴(通常取首元素) 通过一趟快速排序将待排序表划分为独立的两部分 L[1...k−1]L[1...k - 1]L[1...k−1] 和L[k+1...n]L[k + 1...n]L[k+1...n]，pivotpivotpivot 放在了最终位置 L[k]L[k]L[k] 中

快速排序(冒泡排序的升级款)

选择排序

不稳定

稳定性

O(n2)O(n^2)O(n2)

时间效率 (平均时间复杂度)

O(1)O(1)O(1)

空间效率 (平均时间复杂度)

代码

对于 n 个元素而言经过 n - 1 次排序即可成功

基本思想: 假设排序表为 L[1...n]L[1...n]L[1...n], 第 iii 趟排序即从 L[i...n]L[i...n]L[i...n] 中选择关键字最小的元素与 L[i]L[i]L[i] 交换

简单选择排序

void SelectSort(ElemType A[], int n){ for(i = 0; i < n - 1; i++){ min = i; for(j = i + 1; j < n; j++) if(A[j] < A[min]) min = j; if(min != i) swap(A[i], A[min]); } } 

不稳定

稳定性

O(nlog2n)O(nlog_2 n)O(nlog2​n)

时间效率 (平均时间复杂度)

O(1)O(1)O(1)

空间效率 (平均时间复杂度)

代码

插入元素操作

删除元素操作

构造大根堆

大根堆: 双亲都是比孩子大的, 同时最大的元素放在根结点上的

小根堆: 双亲都是比孩子小的, 同时最小的元素放在根结点上的

堆的概念

堆排序 (两个算法都是不稳定的)

归并排序

稳定

稳定性

O(nlog2n)O(nlog_2 n)O(nlog2​n)

时间效率 (平均时间复杂度)

O(n)O(n)O(n)

空间效率 (平均时间复杂度)

代码

二路归并排序

基本思想: 将两个或两个以上的有序数组组成一个新的有序表

基数排序

稳定

稳定性

O(d(n+r))O(d(n + r))O(d(n+r))

时间效率 (平均时间复杂度)

O(r)O(r)O(r)

空间效率 (平均时间复杂度)

代码

基本思想: 基数排序不基于比较和移动进行排序, 而基于关键字各位 (个位, 十位, 百位…) 的大小排序

各种排序算法的比较