数据结构与算法复习笔记——查找
程序员文章站
2024-01-17 18:51:46
...
静态查找表(线性表)
静态查找表的组织方式是以线性表阻值的,存储结构可以是数组或链表。
查找方式包括顺序查找、二分查找等
二分查找
while(low<=high){
mid = (low+high)/2;
if(L.elem[mid].key==x) return mid;
else if(L.elem[mid.key]<x) low=mid+1;
else high=mid-1;
}
索引顺序表
将顺序表分成若干块。
动态查找表
二叉排序树
左子树上的值均小于结点,右子树上的值均大于结点。
二叉排序树的中序遍历递增有序,可以用来判段一棵树是否为二叉排序树
查找
while(p!=NULL){
if(p->key==x) return p;
else if(p->key>x) p=p->lc;
else p=p->rc;
}
删除
- 被删结点为叶结点:直接删除
- 被删结点只有左/右子树:用左右子树代替被删结点
- 被删结点既有左子树,又有右子树:用该结点的最大左孩子或最小右孩子替代。
平衡二叉树(AVL树)
何为平衡二叉树:
- 树中每个结点的左、右子树高度之差绝对值不大于1。
插入
插入结点之后可能导致原来的二叉树不平衡,需要进行旋转。
B-树
何为m阶B-树?
- 每个结点最多m棵子树
- 根结点至少2棵子树。
- 除根之外所有非叶结点至少【m/2】棵子树
B+树
既可以进行缩小范围的查找,也可以进行顺序查找。
哈希表
设定哈希函数作为处理冲突的方法,将关键字映像到连续的地址上。
直接定址法
h(key)=key或h(key)=a*key+b
数字分析法
根据关键字数字特征确定地址。
冲突处理方法
开放定址法
设定地址探测序列,按照探测序列顺序为发生冲突的数据寻找存放位置。
hi=(h(key)+di)MOD m
其中,di为增量,增量有三种取法
- 线性探测再散列:di=i
- 平方(二次)探测再散列:di=1,-1,4,-4,…
- 随机探测再散列:di为一组伪随机数
再哈希法
在发生冲突的时候,使用不同的哈希函数确定地址。
链地址法
将所有哈希地址相同的数据链接在同一链表中,链表插入采用头插法。
上一篇: python数据结构与算法(一)
下一篇: AIX启动Oracle多个实例的方法