数据结构第三轮

以看严蔚敏老师的教材为主，辅以其他辅导书：王道，新编数据结构，学校讲义

线性结构：线性表、串、队列、栈、数组和广义表

树形结构、网状结构：图

查找、排序

动态内存管理和文件

绪论

8-29

数据：在计算机科学中能输入到计算机中并被计算机程序处理的符号都叫数据。

字符：

字节、字符和字节序列_字节字符-CSDN博客https://blog.csdn.net/2401_87316040/article/details/149878580?spm=1001.2014.3001.5502

文字字符：用于记录语言的核心符号，如中文的 “的、了、在”，英文的 “the、is”，日文的 “の、は” 等。
数字字符：表示数量或顺序的符号，包括阿拉伯数字（0-9）、罗马数字（Ⅰ、Ⅴ、Ⅹ）等。
标点符号：辅助表达语气或停顿，如逗号（,）、句号（.）、感叹号（!）、引号（“”）等。
特殊符号：用于特定场景的功能性符号，如数学符号（+、=、√）、货币符号（$、€、￥）、表情符号（😂、👍）、空格符等。

数据元素（data element）是数据的基本单位

数据项是数据的不可分割的最小单位

一个数据元素可由若干个数据项（data item）组成

记录：数据元素在数据库中被称为记录

数据元素是数据项的集合

学号（数据项）	姓名（数据项）	年龄（数据项）	专业（数据项）
2023001	张三	20	计算机
2023002	李四	21	数学

每一个单元格都是数据项，每一列，每一行都是一个数据元素/记录

整个表格是数据（集）

数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集，比如{1,2,3,4,a,23,f}

字母字符数据对象就是集合{a,f}，数字字符数据对象就是{1,2,3,4,23}

严蔚敏老师对数据结构的定义：data structure 是相互之间存在一种或多种特定关系的数据元素的集合。

结构：数据元素相互之间的关系称为结构（structure）

4类基本结构：集合；线性结构；树形结构；网状结构或图状结构

tips:后面常用的是数据关系

数据结构的形式定义：二元组

Data_Structure=(D，S)

D是数据元素的有限集，S是D上关系的有限集

S又叫逻辑结构

物理结构/存储结构：数据结构在计算机中的表示，数据结构在计算机中的像（映像），称为称为数据的物理结构，又称为存储结构。

在计算机中，用一个由若干位组合起来形成的一个位串（一串二进制数）表示一个数据元素

称这个位串为元素（element）或结点（node）。（不要看这个）

tips：这个定义明显不行，都是啥啊，映像？高数中，有原像和像，映射/像，按照她前面对数据结构的形式定义，一个是数据元素的集合，另一个是关系，在离散数学中，可以短暂的认为映像就是关系，也就类似于深度学习/机器学习的加工厂是一个抽象的概念，你说是像还差不多，映像明显不行

记住两个就可以了：顺序映像和非顺序映像，顺序存储结构和链式存储结构

本书的存储结构是数据结构是数据结构在C虚拟处理器中的表示，这里称为虚拟存储结构

数据类型（data type）：直接跳转c语言

分为：基本数据类型、构造类型、指针、空指针

抽象数据类型（Abstract Data Type，ADT）：指一个数学模型和定义在该模型上的一组操作

细分：原子类型、结构类型（固定聚合类型和可变聚合类型）

形式定义：三元组

(D，S，P)

D数据对象，S是D上的关系集，P是对D的基本操作集

本书的类C语言，伪代码

算法和算法分析

算法（alogorithm）：是对特定问题求解步骤的一种描述，它是指令的有限序列，每一条指令表示一个或多个操作

5个重要特性：有穷性、确定性、可行性、输入、输出

好的算法：正确性、可读性、健壮性、效率与低存储量需求

算法效率的度量：跳转

时间复杂度和空间复杂度-CSDN博客https://blog.csdn.net/2401_87316040/article/details/150720336?spm=1001.2014.3001.5501

第二章线性表

2.1

线性结构的特点

存在唯一的一个被称作“第一个”的数据元素
存在唯一的一个被称作“最后一个”的数据元素
除第一个之外，集合中每个数据元素均只有一个前躯
除最后一个之外，集合中每个数据元素均只有一个后继

线性表（liner_list）：一个线性表是n个数据元素的有限序列

像是姓名列，学号列都可以叫数据元素或者记录（record），王小林、陈红行也都可以叫数据元素或者记录（record），由若干个数据项（data item）组成

含有大量记录的线性表又称为文件（file）

同一线性表中的元素同属于一个数据对象（性质相同的数据元素的集合），相邻数据元素之间存在着序偶关系

将线性表记为：

线性表中元素的个数n(n>=0)称为线性表的长度，n=0时称为空表

非空表中，a1是第一个数据元素，an是最后一个数据元素，ai是低i个数据元素

i称为数据元素ai在线性表中的位序

2.2 线性表的顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素。

线性表的顺序存储也称顺序表。

顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序（重点可能突出的是先后次序这种关系）相同。

另一种表述：逻辑关系上相邻的两个元素在物理位置上也相邻。

线性表第i个数据元素ai的存储位置为

LOC(ai)=LOC(a1)+(i-1)*l

l为每个元素所需要的存储单元

存储结构的定义

通常用数组来描述数组中的顺序存储结构

静态分配的顺序表存储结构

静态分配在声明一个顺序表时，就已经为其分配了数组空间。

//静态内存分配的存储结构
#define  MaxSize 50//定义线性表的最大长度
typedef struct{ElemType data[MaxSize];int lengh;//顺序表当前长度
}Sqlist;

动态分配的顺序表存储结构

#define LIST_INIT_SIZE   100//线性表存储空间的初始分配量#define LISTNCREMEMT     10//用于之后的扩容，线性表的分配增量，在工程实践中，直接写数字的方式有明显缺陷，尤其是当代码规模变大、需要长期维护时，这些缺陷会被放大。typedef struct{Elemtype*elem;//存储空间基址int length;//当前长度int listsize;//当前分配的存储容量}Sqlist;

宏定义常量的好处：提升代码的可维护性、可读性和拓展性。只需修改宏定义，所有用到的地方都会同步变化。

直接写数字的缺点：可读性差：别人不知道数字的具体含义；维护困难，如果要调整初始容量，就要全局搜索数字并作修改，容易漏改或改错。

顺序表的基本操作

1.初始化INITLIST

顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度length置0

动态分配的初始化

//动态分配的顺序表的初始化
Status InitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//指针悬空就分配失败L.length=0;L.listsize=LIST_INIT_SIZE;;return OK;
}

静态分配的初始化

//静态分配在声明一个顺序表时，就已经为其分配了数组空间。因此，初始化1时只需要将顺序表的当前长度置0
void InitList(SqList &L){L.length=0;
}

2.插入操作

2.3线性表的链式表示和实现

逻辑结构

线性表的链式存储结构：用一组任意的存储单元存储线性表的数据元素。

结点node:数据元素本身的信息+其直接后继的存储位置

包含两个域：数据域和指针域

单链表、双链表、静态链表、循环链表

可以用指针实现，也可以数组

只要满足指针域里面存储下一个结点的存储位置（数组中的相对地址（数组下标），也称游标）就行了

单链表/线性链表

每个结点只包含一个指针域的链表，叫做线性链表或单链表

--线性表的单链表存储结构--

typedef struct  LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;

静态链表

静态链表是用数组来描述线性表的链式存储结构。其实，只能算线性链表的一个“子集”

指针是结点在数组中的相对地址（数组下标），也称游标

#define MaxSize 50//静态链表的最大长度
typedef struct{ElemType data;int next;
}SLinkList[MaxSize];

循环链表

表中最后一个元素的指针域指向头结点，使整个链表形成一个环。

单链循环链表，多重链的循环链表

循环链表的判空操作

带头结点

head.next==head（头结点的指针域指向自身）

不带头结点

head==null

双向链表

存储结构

--线性表的双向链表存储结构--

typedef struct DulNode{ElemType data;struct DulNode *prior;struct DulNode *next;
}DulNode,*DulLinkList;

双向链表的操作

ListLength、GetElem、LocateElem等仅需涉及一个方向的指针，和线性链表相同

插入、删除就不一样了

链表在其他数据结构中的应用

这个比较重要，所以单独拿了出来,多重链的链表（有多个指针域）

2.4 一元多项式的表示及相加

书上大致就是说，采用顺序存储结构，指数隐含在下标里，就要把所有系数项（包括系数为0的）的都存进去，造成空间浪费

但是只存储非零系数项就要同时存储相应的指数，就是

((p1，e1)........)

[PTA] 一元多项式的加法（数组实现链表实现）_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1eL411g7Xt/?spm_id_from=333.337.search-card.all.click&vd_source=cdc2a34485eb016f95eae1a314b1a620

第三章栈和队列

栈和队列是操作受限的线性表

3.1 栈

逻辑结构

栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。

表尾端，称为栈顶（top），进行插入或删除操作。

表头端，称为栈底（bottom）。

不含元素的空表称为空栈。

S=(a1,a2,a3,....,an)称a1为栈底元素，an为栈顶元素。

栈又称后进先出（last in first out，LIFO）的线性表。

栈的基本操作：在栈顶进行插入和删除、栈的初始化、判空、取栈顶元素等。5个

物理结构

顺序存储

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

动态分配

typedef struct{SElemType  *base;//栈底指针SElemType  *top;//栈顶指针int stacksize;//当前可使用的最大容量
}SqStack;

静态分配

#define MaxSize 50
typedef struct{Elemtype data[MaxSize];//存放栈中元素int top;//栈顶指针
}SqStack;

链式存储

//链栈的定义
typedef struct Linknode{ElemType data;            //数据域struct Linknode*next;     //指针域
}*LiStack;

基本操作

3.2 栈的应用举例

数制转换

括号匹配检验

行编辑程序

迷宫求解

表达式求值

3.3 栈与递归的实现

一个汉诺塔一个八皇后

3.4 队列

逻辑结构

队列（queue）是一种先进先出（first in first out,缩写为FIFO）的线性表。

它只允许在表的一端进行插入，而在另一端删除元素。

允许插入的一端叫做队尾（rear）

允许删除的一端叫做队头（front）

q=(a1,a2,....,an)，a1是队头元素，an是队尾元素

双端队列（deque）:两端都可以进行插入和删除操作

变种：

输出受限的双端队列：一端允许插入和删除操作，另一端只允许插入操作

输入受限的双端队列：一端允许插入和删除操作，另一端只允许删除操作

物理结构

队列的链式表示和实现——链队列

//---单链队列——队列的链式存储结构----
typedef  strcut QBNode{QElemType data;struct QNode *next;
}QNode,*QueuePtr;
typedef struct{QueuePtr front;//队头指针QueuePtr rear;//队尾指针
}LinkQueue;
//----基本操作---
Status InitQueue(LinkQueue&Q);//初始化，构造一个空队列
Status DestroyQueue(LinkQueue&Q);//销毁队列
Status ClearQueue(LinkQueue&Q);//清空队列
Status QueueEmpty(LinkQueue Q);//队列判空
int QueueLength(LinkQueue Q);//返回队列中元素的个数，即队列的长度
Status GetHead(LinkQueue Q,QElemType &d);//若队列不空则e返回Q的队头元素，并返回OK,否则返回ERROR
Status EnQueue(LinkQueue&Q,QElemType e);//入队
Status DeQueue (LinkQueue &Q,QElemType &e);//出队
Status QueueTraverse(LinkQueue Q,visit());

队列的顺序表示和实现和循环队列

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队首指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置。（王道）

静态分配存储空间

//队列的顺序存储
//静态数组/静态分配
#define MaxSize 50  //队列中元素的最大个数
typedef struct{ElemType data[MaxSize];//数组存放队列元素int front,rear;//队首、队尾指针
}SqQueue;
SqQueue.data[rear++]=

动态分配存储空间&&初始化

//队列的顺序存储
//动态数组//动态分配
#define MAXQSTZE  100//最大队列长度，malloc()会用到
typedef strcut{QElemType *base;int front;int rear;
}SqQueue;
Status InitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSTZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//动态内存分配失败Q.front=Q.rear=0;return OK;
}

3.5 离散事件模拟（银行排队模拟）

懒猫老师-数据结构-(12)队列应用：银行排队模拟(离散事件模拟)_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1nE411u7n4/?spm_id_from=333.337.search-card.all.click&vd_source=cdc2a34485eb016f95eae1a314b1a620很难，之后在学，最好把c++的类给学了

第四章串

就两个，一个是串类型的定义，一个是串的模式匹配（朴素算法、KMP，next数组，二进制进行优化）

计算机上非数值处理的对象基本上是字符串数据

坑：非数值处理

串或字符串（string）是零个或多个字符组成的有限序列

记为

s='a1a2a3...an' n>=0

s是串名，单引号括起来的字符序列是串的值

ai可以是字母、数字或其他字符

串中字符的数目n称为串的长度。零个字符的串称为空串（null string），长度为0

子串：串中任意连续的字符组成的子序列称为该串的字串

主串：包含子串的串称为主串，也就是说一个子串可以有多个主串，反之亦然

子序列：是指从一个原始序列中，通过删除部分元素（也可一个不删）但不改变剩余元素相对顺序得到的新序列。

字符在串中的位置：指字符在序列中的序号为该字符在串中的位置

子串在主串中的位置：子串的第一个字符在主串中的位置来表示

两个串相等，当且仅当这两个串的值相等

由一个或者多个空格组成的串' '称为空格串(blank string)

串类型的最小操作子集：串赋值StrAssign、串比较StrCompare 、求串长StrLength、串连接Concat、求子串SunString

4.2 串的表示和实现

4.3串的模式匹配算法

4.4 串操作应用举例

文本编辑

建立词索引表

第七章图

第七章图-CSDN博客https://blog.csdn.net/2401_87316040/article/details/149668447?sharetype=blogdetail&sharerId=149668447&sharerefer=PC&sharesource=2401_87316040&spm=1011.2480.3001.8118

第八章动态存储管理

无论是外存还是内存，数据的存储形式都是二进制，但是源代码二进制不等于可执行二进制，外存中是源代码的二进制，编译器在内存中工作

编译器首先在内存中工作，读取外存中的源代码文件
直接在内存中完成从高级语言到低级语言（机器码或汇编语言）的翻译
最终将生成的目标代码（低级语言）保存到外存（如.exe 文件）

编译器在内存中工作，将从外存中读取的源代码（二进制形式存储在外存中），读入内存，然后为读进来的数据分配到固定的区域内。

主内存（RAM）的逻辑分区：

	存储内容	分配方式		生命周期	访问速度
代码区（Code Segment）	程序的 “机器指令”（编译后的二进制代码）	操作系统自动分配（程序加载时）	程序退出后操作系统回收	整个程序运行期间	极快（接近 CPU 缓存）
常量区（Constant Segment）	只读常量（如字符串常量`"hello"`、`const`修饰的全局常量）	操作系统自动分配（编译时确定）	程序退出后操作系统回收	整个程序运行期间	快
全局 / 静态区（Data Segment）	全局变量（定义在函数外的变量）、静态变量（`static`修饰的变量）	操作系统自动分配（编译时确定）	程序退出后操作系统回收	整个程序运行期间	快
栈（Stack）	函数参数、局部变量（定义在函数内的普通变量）、函数调用上下文（返回地址、寄存器状态）	编译器自动分配（函数调用时）	编译器自动释放（函数返回时）	随函数调用创建，函数结束销毁	非常快（栈是 “连续内存块”，操作仅需修改栈指针）
堆（Heap）	动态分配的数据（如程序运行中按需创建的数组、对象）	程序员手动分配（如`malloc`/`new`）	程序员手动释放（如`free`/`delete`）	随分配创建，释放后销毁	较慢（需遍历链表找空闲内存，易产生碎片）

RAM（Random Access Memory,随机存取存储器）：临时数据存储

分为：SRAM（静态随机存取器）：晶体管构成和DRAM（动态随机存取存储器）电容器存储的电荷构成

动态内存管理是将堆中的空间分配给变量，常量等

在系统运行初期，堆区被分成两部分，占用块和空闲块，一段时间后，有的内存块变成了空闲块，

我们重点研究的是系统运行若干时间后，堆区呈现犬牙交错的状态，我们该如何进行内存分配。

两种策略：第一种，就是继续在高地址区的空闲块中分配空间，而不去管，前面的空闲块，等高地址区全都占用完，然后再去考虑，显然，书本这样说是非常不好的，什么叫，再去考虑？不就来到了第二种策略了？那么，在实际应用中，是两种策略交替使用，还是啥，都没有进行叙述。

第二种策略就是给空闲块做标记：目录表：空闲&占用都记录下来

链表：只记录空闲块，被占用，就直接给删除。后面一节叫可利用空间表。又称存储池。

8.2 可利用空间表（链表）及分配方法

第一种，系统运行期间所有用户请求分配的存储量大小相同。做法是，在系统运行开始时，全是空闲的，就给他全部链起来。实质是链栈。

第二种，系统运行期间，用户请求分配的存储量有若干大小的规格。做法是，相同规格的存储量链在一起。每个结点的大小相同。

第三种，系统运行期间，分配的内存块大小不能提前知道，（操作系统中比较常见），做法有三种，首次拟合法，最佳拟合法、最差拟合法

首次拟合法：从表头开始遍历，将找到的第一个大小不小于n的空闲块的一部分分配给用户，剩余部分仍然留在链表中。

最佳拟合法：将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给用户。对可利用空间表的要求：空闲块大小，自小至大有序。回收要求：要将释放的空闲块插入到合适的位置上去。

最差拟合法：将可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户。对可利用空间表的要求：空闲块大小：自大至小有序；每次分配无需查找，只需从链表中删除第一个结点，并将其中一部分分配给用户，剩余部分作为新的结点插入到表中。

从时间上看，最佳拟合法，分配时需要遍历直到第一个小于的前一个空闲块，回收时，也要进行排序比较进行插入。最耗时间。

考虑结点合并，分配和回收后，有可能出现地址相邻的空闲块，此时就要考虑结点合并

8.3 边界标识法

64位计算机中，1字=8字节

32位计算机中，1字=4字节

先给了可用空间表的结构定义，然后讲了分配算法和回收算法

8.4 伙伴系统

10分钟速通伙伴系统算法！（含例题）_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV11BxDegEwb/?spm_id_from=333.337.search-card.all.click&vd_source=cdc2a34485eb016f95eae1a314b1a620找第一个比要分配空间大的2的i次幂，不存在就继续升次，2的k次存在，就划分k次空间区分链

8.5 无用单元收集

无用单元或叫悬挂访问：用户疏漏或系统纰漏时没有回收

8.6 存储紧缩

引入了堆指针

两种做法，第一，一旦有用户释放存储块即进行回收紧缩

另一种是，直到可利用空间不够分配或堆指针指向最高地址时才进行存储紧缩

然后就是对占用块进行标志

第九章查找

查找表也是一种数据结构。

查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。

查找表的基本操作

查询某个特定的数据元素是否在查找表中
检索某个特定的数据元素的各种属性
在查找表中插入一个数据元素
从查找表中删去某个数据元素

只有1&&2，称为静态查找表（Static Search Table），包含3||4称为动态查找表（Dynamic Search Table）

查找：在查找表中找出某个”特定的“数据元素（记录）。

关键字（Key）是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。

主关键字，次关键字，当数据元素中只有一个数据项时，其关键字即为数据元素的值

查找操作的性能分析

以”关键字和给定值进行过比较的记录个数的平均值“作为衡量查找算法好坏的依据。

平均查找长度：待查找的记录和给定值进行比较次数的期望值称为查找算法在查找成功时的平均查找长度（Average Search Length）

在实际应用中，大多情况下，可以只考虑查找成功时的平均查找长度

不能忽略时

查找算法的平均查找长度=查找成功时的平均查找长度+查找不成功时的平均查找长度

9.1 静态查找表

顺序表的查找

顺序查找（Sequential Search）:从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功

//---静态查找表的顺序存储结构---
typedef struct{ElemType *elem;//数据元素存储空间基址int length;//表长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,KeyType key){ST.elem[0].key=key;//哨兵写法for(int i =ST.TableLen;ST.elem[i]!=key;--1)return i;
}

顺序查找的性能分析

平均查找长度（假设每个记录的查找概率相等）

ASL=(n+1)/2

有序表的查找

折半查找(Binary Search)：mid值和key比较

int Binary_Search(SSTable 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{low=mid+1;}return -1;}
}

折半查找的性能分析

折半查找判定树

静态树表的查找

难啊

一个是静态最优查找树，另一个是阉割版，次优查找树

次优查找树这个还可以模拟模拟，只要入门，那就比较简单

索引顺序表的查找

就一个分块查找，再去看看左程云的分块分治

分块查找，又称索引顺序查找

9.2 动态查找表

二叉排序树

BST,binary search tree

左子树结点值<根结点值<右子树结点值

可以用中序遍历得到一个递增的序列

二叉排序树的查找

递归实现

//递归实现，在二叉排序树中查找值为key的结点（递归实现）
BSTNode *BSTSearch(BSTree T,int key){if(T==NULL)return NULL;else if(key <T->key){return BSTSearch(T->left,key);}return BSTSearch(T->right,key);
}

非递归实现

BSTNode *BSTSearch(BSTree T,int key){while(T!NULL&&key!=T->key){if(key<T->key){T=T->lchild;}elseT=T->rchild;}return T;
}

平衡二叉树

AVL树

在二叉排序树的基础上加了一个左右子树的深度之差的绝对值不超过1，{1，0，-1}

结点的平衡因子（BF,balance factor）=该结点的左子树的深度-它的右子树的深度

//二叉排序树的类型定义，及左旋、右旋操作
typedef struct BSTNode
{ElemType data;int bf; //结点的平衡节点struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
void L_Rotate(BSTree&p){BSTree rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;
}
void R_Rotate(BSTree&p){BSTree  lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;
}

B(B-)树

B-树是一种平衡的多路查找树

B+树

键树

红黑树

9.3 哈希表

像是java的hashmap,python的dict/set，c++的unordered_map,unordered_set，都封装好了

哈希表的思想

f(key)=哈希索引

哈希表在各个语言中的实现，这才是重点

哈希函数的构造方法，哈希冲突的处理

综上，等几年再看

第十章内部排序

第十章内部排序-CSDN博客https://blog.csdn.net/2401_87316040/article/details/150273937?sharetype=blogdetail&sharerId=150273937&sharerefer=PC&sharesource=2401_87316040&spm=1011.2480.3001.8118

第十一章外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，在排序过程中需要进行多次内、外存之间的交换。

计算机一般有两种存储器：内存储器（主存）和外存储器（辅助存储器（辅存）、二级存储器）。

内存的信息可以随机存取，且存取速度快，但是价格贵、容量小

外存储器包括磁带和磁盘（或磁鼓）、更新：固态U盘、移动固态硬盘（便携式固态硬盘PSSD，贵）、机械移动硬盘、

PSSD

磁带是顺序存取，磁盘是随机存取

磁带应用场景：生成式ai训练产生的数据，约60%最终归档至磁带，医疗影像、监控录像、金融交易记录等长期不访问的数据。

市场中磁盘占据绝对份额

10.2 外部排序

外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间

采用多路归并可以减少归并躺数，从而减少磁盘I/O（读写）次数

k越大，r越小，归并趟数越少，读写磁盘次数越少

多数归并带来的负面影响：

k路归并时，需要开辟k个输入缓冲区，内存开销增加

没挑一个关键字需要对比关键字（k-1）次，内部归并所需时间增加

减少初始归并段数量：通过增加初始归并段的长度，则可减少初始归并段数量r

利用败者树减少关键字对比次数

利用”置换-选择排序“进一步减少初始归并段数量

10.3 败者树

10.4 置换-选择排序

10.5 最佳归并树

外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。

外排就是多路平衡归并排序，败者树、置换-选择排序、最佳归并树

第十二章文件

称存储在主存储器（内存储器）中的记录的集合为表

称存储在二级存储器（外存储器、辅助存储器）中的记录的集合为文件

12.1

文件（file），是由大量性质相同的记录组成的集合。

按记录的类型不同可以分为：操作系统的文件和数据库文件

操作系统中的文件仅是一维的连续的字符（这里的字符指的是存储在存储设备中的二进制字符）序列，无结构，无解释

数据库中的文件是带有结构的记录的集合。

定长记录文件：文件中每个记录含有的信息长度相同，称为定长记录文件

不定长记录文件：文件中含有信息长度不等的不定长记录，称为不定长记录文件

数据库文件：单关键字文件（只有一个主关键字），多关键字文件（一个主关键字和若干个次关键字）

记录的逻辑结构和物理结构：太绕了，

文件的操作（运算）：检索和修改

文件的检索：顺序存取、直接存取、按关键字存取

文件的修改：包括一个记录的插入、删除和更新操作

文件的组织方式：顺序组织、随机组织、链组织

12.2 顺序文件

顺序文件（Sequential File）：物理记录的顺序和逻辑记录的顺序是一致的。

逻辑次序相继的两个物理记录在存储介质上的存储位置是相邻的，则称为连续文件

不相邻（指针相链表示），称为串联文件

顺序文件的特点：

存取第i个记录，必须先搜索在它之前的i-1个记录
插入新的记录时只能加在文件的末尾
若要更新文件中的某个记录，则必须将整个文件进行复制

优点：连续存取的速度快，主要用于只进行顺序存取、批量修改的情况

典型的顺序存取设备：磁带

f-主文件

g-事物文件

h-新主文件

12.3 索引文件

称文件本身为数据区

索引表：一张指示逻辑记录和物理记录之间一一对应关系的表

包括数据区和索引表的文件称为索引文件

索引文件只能是磁盘文件

稠密索引：对每个记录建立一个索引项，如此建立的索引表称之为稠密索引。用于数据文件中记录不按关键字顺序排列

非稠密索引：对一组记录建立一个索引项，这种所以表就叫做非稠密索引。用于数据文件中的记录按关键字顺序有序。

就是归并排序那张图

12.4 ISAM文件和VSAM文件

索引顺序存取方法（Indexed Sequential Access Method，ISAM）

它是专门为磁盘存取设计的文件组织方式（文件的分类、存储、索引和管理的结构化方法）

磁盘是盘组、柱面和磁道三级地址存取的设备

虚拟存储存取方法（Virtual Storage Access Method，VSAM）

利用操作系统的虚拟存储器的功能，对用户来说，文件只有控制区间和控制区域等逻辑存储单位，

用户在存取文件中的记录时，不需要考虑这个记录的当前位置是否存在内存，也不需要考虑任何执行对外存进行“读/写”的命令

由索引集、顺序集和数据集三部分组成

12.5 直接存取文件（散列文件）

直接存取文件指的是利用哈希(Hash)法进行组织的文件。

根据文件中关键字的设计特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。称为散列文件。

在散列文件中，每个存储单元叫做桶（Bucket）

12.6 多关键字文件

多重表文件

倒排文件

c++标准模板库

c++标准模板库-CSDN博客https://blog.csdn.net/2401_87316040/article/details/150989090?sharetype=blogdetail&sharerId=150989090&sharerefer=PC&sharesource=2401_87316040&spm=1011.2480.3001.8118