（期末考试prepare）数据结构（C语言版）第七章——查找（顺序表、树表、哈希表）·附习题

数据结构期末复习系列 · 持续更新：

图的深度遍历和广度遍历 图的邻接矩阵和邻接表表示 串的基本知识及操作 数据结构期末考试提纲（重点复习知识汇总） 期末考试 | 数据结构第五章 | 树和二叉树·附习题 期末考试 | 数据结构第七章 | 查找（顺序表、树表、哈希表）·附习题 期末考试 | 数据结构第八章 | 内部排序（插入/选择/冒泡/快排/堆排序/基数排序） 稀疏矩阵的三种表示方法·转置矩阵·矩阵相乘·十字链表表示法·数组的基本操作 栈的简单应用：数制转换·括号的匹配检验·行编辑·迷宫求解·表达式求值·递归调用 队列的基本概念·循环队列·银行排队场景驱动管理 线性表和链表的基本操作：初始化·定位查询·插入元素·删除·查找·双向链表

一、顺序表 1.顺序表(静态查找)表示

typedef struct{
KeyType key;//关键字（数据项）
InfoType info;//数据元素的其他属性，为简化算法通常忽略此数据项
}ElemType;//数据类型

typedef struct{
ElemType *elem;//数据元素储存基址，0号单元留空
int length;
}STable;//顺序表

2.顺序查找

顺序表或者链表都适合

int SeqSearch(STable ST,KeyTpe key){
ST.elem[0]=key;//设置0号为监视哨，就不用了多次比较i是不是越界，因为在最后0号哨上一定能配对成功。所以比较时候要从后往前
for(i=ST.length;;i- -){
if(ST.elem[i].key=key) return i;
}
}

对n个元素顺序查找，若查找成功，则比较关键字的次数最多为（n）次； 当使用监视哨时，若查找失败，则比较关键字的次数为（n+1）

3.折半查找（二分查找）

必为有序表first,且顺序表（链表no） 时间复杂度O(log2n) 平均查找长度：

int BinSearch(STable ST,KeyType key){
low=1;
high=ST.length;
while(lowlchild; }
return p;
}
}

改成递归：

BiTree BSTSearch(BiTree BT,KeyType key){
if((!BT)||key==BT->elem.key) return BT;
else if(keyelem.key) return (BSTSearch(BT->lchild,key));
else return(BSTSearch(BT->rchild,key));
}

哇用递归能少写好多代码~

二叉排序树构造的代码也可以简单一看，很简单，就是申请一个新结点然后找位置插进去就行了。二叉树删除的代码也太长了，应该不会考⑧。。。

二叉排列树习题： ①以下序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(C) A（100，80， 90， 60， 120，110，130） B（100，120，110，130，80， 60， 90） C（100，60，80， 90， 120，110，130） D (100，80， 60， 90， 120， 130，110) 析：

②将元素{38，27,64,12,61,83,19}插入生成二叉排序树，查找值为61的结点所需要比较次数：3 析：从某种程度上来说，二叉排列树的查找方式很类似于二分 ③二叉排序树删除一个结点后，仍是二叉排序树 析：这句话是出的判断，答案是√ 但我感觉只是说叶子结点吧，还要考虑根结点情况，对非叶子、非根结点删除它和它子树比较合适叭。赶脚不太严谨

④二叉查找树的效率与（树型）有关，当（呈单枝树）时效率最低。 所以才提出了底下平衡二叉树的概念

2.平衡二叉树(AVL树)

定义：高度平衡的二叉排列树 （填空）

为了降低二叉排序树的平均查找长度，使得每个结点的两个子树深度不要太大，而引入平衡二叉树，即左子树和右子树的深度之差绝对值小于1. 结点的平衡因子（BT）（该结点的左子树深度减去右子树深度）只能为0、-1、1

插入新结点后构建：LL型，RR型，LR型，RL型

3.B-树（B树）

前面所讨论的查找对象都是可以全部保存在内存中的数据结构，比如二叉排列树、平衡二叉树等。 当数据量增大后，一般会以文件的形式存储在外存（如硬盘）上。这样，执行查找操作时，必须多次访问硬盘。 与内存相比，硬盘的存取速度很低。应用B-树这种多路平衡查找树，可以提高查找效率，减少查找过程中对磁盘的存取次数。 所以B-树是一种适合在磁盘等直接存取设备上组织动态的查找表。

B+树 既能索引查找 也能顺序查找

讲真课本的老大一大串概念定义都没大看懂ε=(´ο｀*)))唉，找不出啥考点，先pass掉叭

三、Hash（散列）表查找

每个关键字通过哈希函数f（自己规定）的变换，搞出一个唯一的存储地址 因为是1vs1的，so可快速插入、删除，时间复杂度可达常数级O(1)

负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。 Hash表的平均查找长度不随表中结点数目的增加而增加，而与装填因子有关。 理解一下基本概念，搞两道习题凑活下吧。这块应该只能出选择填空⑧

散列函数有一个共同的性质，即函数值应当以(同等概率)取其值域的每个值

笔者有陆续更新的数据结构每章、每块知识点的复习笔记及题型实练~ 希望大家共同进步，期末加油！！！ 点点关注不迷路呦 ~