[数据结构与算法] 数据结构

反映魔偶个客体数据信息的集合，是该客体的属性值的集合。

文件中存储数据的基本单位；

物理记录与逻辑记录间的关系：

一个物理记录存放一个逻辑记录；

一个物理记录包含多个逻辑记录；

多个物理记录表示一个逻辑记录；

对于确定的硬件设备和操作系统，物理记录的大小不变，而逻辑记录的大小由用户根据客体信息的逻辑概念来定义；

文件

命名的同类客体的记录值的集合。

同类客体 —— 具有相同属性定义的客体；

定长记录文件 —— 内部每条记录的信息长度相等（定长记录）

不定长记录文件 —— 内部记录长度不等且不确定；

通常文件包含的数据量很大，因而数据一般放在外部存储器（外存）上；

关键字

文件的属性或属性组；

用以标识（区分）文件的不同记录；

可唯一标识 —— 主关键字

标识若干记录 —— 次关键字

当记录中只有一个属性时，其关键字即为该记录的值；

文件的逻辑结构

文件中逻辑记录之间的逻辑关系，即逻辑记录按某种次序呈现给用户的一种线性结构；

在文件的逻辑结构中，第1个记录只有一个后继记录，最后一条记录只有一个前驱记录，其余记录分别有一个前驱记录和一个后继记录；

文件的物理（存储）结构

文件的逻辑记录在存储介质上的组织方式；

基本的组织方式：

连续组织方式

链接组织方式

随机组织方式

一个线性逻辑结构在存储介质中可以有多种物理结构；

文件的存储介质

磁带

磁盘

......

文件的基本操作

文件的查找

根据用户需求在文件中确定相应记录的操作过程

3种方式

查找下一个记录

查找第i个记录

按关键字值查找

简单条件匹配 —— 查找关键字值等于给定值的记录

区域匹配 —— 查找某关键字值属于某个范围内的记录

函数匹配 —— 给定关键字的某个函数，查找符合条件的记录

组合条件匹配 —— 给出多个条件，用布尔运算组合起来进行查找

查找结果

成功 —— 文件中存在符合查找条件的记录，返回记录的位置或数据信息

失败 —— 符合条件的记录不存在，返回表示不存在的反馈信息

查找操作不会改变文件

衡量一个查找算法优劣的重要指标 —— 平均查找长度

计算公式

$$
ASL = (1 / n) * \Sigma_{i=1}^{n}p_{i}c_{i}
$$
?

若查找每个记录的概率均等，则该公式可以简化为

$$
ASL = (1 / n) * \Sigma_{i=1}^{n}c_{i}
$$

记录的插入

在文件中指定位置增加一个新的记录；

记录的删除

删除文件中指定的记录或者满足条件的记录；

通常有以下两种情况：

删除第i个记录；

删除符合给定条件的记录；

记录的修改

对符合给定条件的记录的某些属性值进行修改

文件的插入、删除、修改操作都需要先找出符合给定条件的记录的位置 —— 查找操作是数据文件最基本的操作之一；

文件的排序

按关键字值的大小递增或递减顺序对文件的记录进行重新排列的过程；

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表

针对连续顺序文件

基本思想：顺序查找也称为线性查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败；

复杂度分析：　

查找成功时的平均查找长度为：（假设每个数据元素的概率相等）

ASL = (1 / n) * (1 + 2 + 3 + … + n) = (n + 1) / 2；

当查找不成功时，需要n+1次比较，时间复杂度为O(n)；

因此，时间复杂度为 O(n)

代码实现

// 顺序查找
int sequenceSearch(int a[], int value, int n) {
 ? ?int i;
 ? ?for(i = 0; i < n; i++)
 ? ? ? ?if(a[i] == value)
 ? ? ? ? ? ?return i;
 ? ?return -1;
}

折半查找

元素必须是有序的，如果是无序的则要先进行排序操作。

仅适用于排序连续文件

基本思想：属于有序查找算法。将给定值k先与中间结点的关键字值比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为log_2 (n+1)，且平均时间复杂度为 O(log_2 n)；

判定树的构造

折半查找过程可以借助于一颗二叉树来描述；

判定树不一定为二叉树，而折半查找中的判定树必为二叉树；

查找任意一个记录的过程 —— 经过一条从根结点到与该记录对应结点的路径；

与关键字的比较次数 —— 该节点在判定树中所在的层次数(深度)；

因此，查找成功所进行的比较次数一定不超过判定树的深度；深度即为最大查找次数；

代码实现

// 折半查找
// 1. 非递归
int binSearch(int a[], int value, int n) {
 ? ?int low, high, mid;
 ? ?low = 0;
 ? ?high = n - 1;
 ? ?while(low <= high) {
 ? ? ? ?mid = (low + high) / 2;
 ? ? ? ?if(a[mid] == value)
 ? ? ? ? ? ?return mid;
 ? ? ? ?else if(a[mid] > value)
 ? ? ? ? ? ?high = mid - 1;
 ? ? ? ?if(a[mid] < value)
 ? ? ? ? ? ?low = mid + 1;
 ?  }
 ? ?return -1;
}
?
// 2. 递归
int binSearch_rec(int a[], int low, int high, int value) {
 ? ?int mid;
 ? ?if(low <= high) 
 ? ? ? ?return -1;
 ? ?else {
 ? ? ? ?mid = (low + high) / 2;
 ? ? ? ?if(a[mid] == value)
 ? ? ? ? ? ?return mid;
 ? ? ? ?else if(a[mid] > value)
 ? ? ? ? ? ?return binSearch_rec(a, low, high - 1, value);
 ? ? ? ?else
 ? ? ? ? ? ?return binSearch_rec(a, low + 1, high, value);
 ?  }
}

散列文件

散列表的构造

散列表

哈希表（Hash table，也叫散列表），是根据关键字值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表；

设计的3 个内容

确定散列表的地址空间范围，即确定散列函数值域；

构造合适的散列函数，该散列函数要保证所有可能元素的散列函数值均在指定的值域内，并且使得冲突发生的可能性尽可能小；

选择处理冲突的有效方法；

散列函数的构造

直接定址法

取关键字或关键字的某个线性函数值为哈希地址：

H(key) = key 或 H (key) = a * key + b

其中a和b为常数，这种哈希函数叫做自身函数；

适用情况：关键字值的分布基本连续或者关键字具有一定规律；

数字分析法

当关键字值得位数大于散列地址码的位数时，对关键字值的各位数字进行分析，从中取出与散列地址位数相同的位；

适用情况：所有关键字可能出现的值都已知；

平方取中法

先计算关键字值的平方，然后有目的地选取中间的若干位作为散列地址。具体位数及取值位置由实际情况确定；

具有较好的分散性，散列地址也具有较好的随机性；

适用情况：关键字中每一位取值都不够分散，或者相对比较分散的位数小于散列地址所需要的位数；

叠加法

把关键字值分割成位数相同的几个部分（最后一个位数不够则可补），然后叠加这几个部分来求和（舍去进位）作为散列地址；

适用情况：位数很多，位值分布均匀，而所需的散列地址位数较少，关键字中每一位的取值又比较集中；

2种方案

移位叠加法

折叠叠加法（偶数号部分逆转）

基数转换法

设关键字原来位十进制数，认为视作q进制数，再转换成十进制数作为散列地址；

除留余数法

又称取模法；

取关键字被某个不大于散列表表长m的数p (p <= m)除后所得的余数为散列地址。即 H(key) = key mod p；

p 的取值

常取一个小于或等于散列表长m 的最大素数；

k 为字符串时

设法转换为一个整数，再用该整数对表长取模所得余数作为散列地址；

计算比较简单，使用范围也较广，是一种最常用的构造散列函数的方法；

随机数法

选择一个随机函数，取关键字的随机函数值为其散列地址；

适用情况：关键字长度不等；

散列函数构造的原则

计算散列函数所需时间；

关键字的长度；

散列表的大小；

关键字的分布情况；

记录的查找概率；

散列冲突

基本概念

由于元素k的值可能来自一个庞大的集合，因此，可能会出现对于不同的关键字值得到相同的函数值的情况，即当 k1 != k2，而H(k1) = H(k2)，这种现象称为散列冲突现象。一般把具有相同散列函数值的关键字称为同义词；

处理冲突的方法

开放定址法

线性探测再散列

容易造成元素的“聚集”（clustering）；

只能对散列表进行逻辑删除；

二次探测再散列

不能够探查到散列表中所有的位置；

伪随机探测再散列

?

再散列法

在发生冲突时，用不同的散列函数再求得新的散列地址，直到不再发生冲突为止；

实际应用中有较大的局限性；

增加时间开销；

要求事先构造多个散列函数；

链地址法(按桶散列方法)

把具有相同散列地址的元素(或记录)用一个线性链表链接在一起，每个线性链表称为"桶"；

局限

需要指针空间的开销；

给新纪录分配链地址也需要时间开销；

建立一个公共溢出区

假若散列函数的值域为 [0, m - 1]，则设置一个向量 HashTablel[0..m —1]，称之为基本表，每个分量存放一个记录，另外再设置一个向量Over Table[0..v]，称为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们通过散列函数计算得到的散列地址是什么，一旦发生散列冲突，都将填入溢出表；

散列表的查找

在散列文件中查找记录的过程与建立散列文件的过程相似。通常按照以下步骤进行：

根据给定的关键字值k，计算出散列地址 H(k)；

若该地址为空，则表中没有要查找的记录，查找失败；否则进行步骤3；

若该地址中的关键字值与k相等，则查找成功，结束查找；否则进行步骤4；

根据处理冲突的方法求得“下一个散列地址”，转执行步骤2；
若采用二次再散列法处理冲突，则查找算法如下：
int hashSearch(HashList HT, int M, KetType k) {
 ? ?int i, di, D;
 ? ?i = H(k);           // 计算散列地址
 ? ?D = i;
 ? ?di = 1;
 ? ?
 ? ?while (HT[D] != Empty && HT[D] != k) {
 ? ? ? ?D = (i + di * di++) % M;    // 修正散列地址
 ? ? ? ?if (D == i) {
 ? ? ? ? ? ?return -1;          // 查找失败
 ? ? ?  }
 ?  }
 ? ?
 ? ?if (HT[D] == k)
 ? ? ? ?return D;               // 查找成功
 ? ?return -1;                  // 查找失败
}

平均查找长度的运算

此部分以实例为主线

例一

现有长度为11 且初始为空的散列表 HT，散列函数H(key) = key % 7，采用线性探查法解决冲突。将关键字序列87，40，30，6，11，22，98，20依次插入HT后，HT的查找失败的平均长度是多少呢？查找成功的平均查找长度又是多少呢？ ① 首先，通过散列函数并且利用线性探测法给他们每个字划分好自己的位置； ② 记录每个字冲突的次数，后面在计算查找成功的平均长度会用到； ③ 查找失败计算每个查找失败对应地址的查找次数，即从所查位置开始往后查直至查到空位置位置； ④ 其实，后面熟悉过程之后，在列出下面的每个关键字对应地址的表格之后就可以得到结果；

查找失败时对应的地址在这个题目，只能是 7 即 0 ~ 6 ；

ASL 查找失败 = (9 + 8 + 7 + 6 + 5 + 4 + 3 ) / 7 = 6

ASL 查找成功 = (1 + 1 + 1 + 1 + 1 + 1 + 1 + 2) / 8 = 9 / 8

散列地址	0	1	2	3	4	5	6	7	8	9	10
关键字	98	22	30	87	11	40	6	20
冲突次数	0	0	0	0	0	0	0	1

例二

将关键字序列（7，8，30，11，18，9，14）散列存储到散列表中。散列表的存储空间是从0开始的一维数组，散列函数为H(key) =（3 * key）mod 7,处理冲突采用线性探测法，要求装填因子为0.7。（1）画出所构造的散列表。（2）分别计算等概率情况下的查找成功和不成功的平均查找长度。

（1）数组大小 = 7 / 0.7 = 10