软件设计（十二）数据结构(下)

软件设计（十一）数据结构(上)

五、查找

查找分为 静态查找表 和 动态查找表。

1、静态查找表

顺序查找 成功的平均查找长度为 (n+1)/2，也就是说查找的平均次数约为表长的一半，优点就是算法简单适应面广，对查找的表结构没什么要求，缺点就是查找长度太长效率低下。

折半查找 效率要比顺序查找高很多，但必须要求表的数据按顺序存储才能使用，因此删除和插入需要移动大量数据。所以折半查找适合表不易表动又经常查的情况。

分块查找 介于顺序查找和折半查找之间，又称为索引顺序查找，是对顺序查找的一种改进。

2、动态查找表

二叉排序树 又叫 二叉查找树：

1）左子树非空的话，所有值小于根节点。

2）右子树非空的话，所有值大于根节点。

3）左右子树本身就是二叉排序数。

二叉排序树查找过程，给定一个值，与根节点比较，相等则返回，小于则左子树查找，大于则右子树查找。

二叉排序树的插入节点过程，若是空二叉树，则新节点是根节点，若不是，则与根节点比较，小于则放在左子树，大于放在右子树。

二叉排序树删除过程较为复杂，分为三种情况，因为删除一个节点，不能把这个根节点上的树全部删除，且删完后，整个树还要保证有序性。

平衡二叉树(AVL树)

他左右子树都是平衡二叉树，且左子树右子树深度不会差超过1。只要有树上节点的平衡因子的绝对值大于1，则绝对不是平衡二叉树。

B-树

b-树的定义：一颗m阶的b-树，或为空树，或者满足：

1）树中每个节点最多m棵子树。

2）若根节点不是叶子节点，则至少两棵子树。

3）所有叶子节点都出现在同一层次上，并且不带信息。

...

3、哈希表

哈希表定义：根据设定的哈希函数和处理冲突的方法，将一组关键字映射到一个有限连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置。

哈希函数如何构造：常用哈希函数构造方法有 直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。

处理冲突方法：常见处理冲突的方法有 开放地址法、链地址法、再哈希法、建立一个公共溢出区。

六、排序

内部排序：指待排序记录全部存放在内存中的排序过程。

外部排序：指待排序记录的数量很大，以至于内存不能容纳全部记录，再排序过程中尚需对外存进行访问的过程。

简单排序 有直接插入排序，冒泡排序，简单选择排序。

1、希尔排序

希尔排序又叫缩小增量排序，是对直接插入排序方法的改进。先分组，在把分组合并在一起排序。

2、快速排序

快速排序基本思想：通过一趟排序将待排序的记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分小，然后在对这两部分记录进行排序。

若初始关键字有序或者基本有序时候，则会退化成冒泡排序。复杂度为O(n的二次方)

3、归并排序

指两个或者两个以上的有序文件合并成一个新的有序文件。

归并排序是把一个有n个记录的无序文件看成由n个长度为1的有序文件组成的文件，然后两个归并，如此重复，最后形成一个包含n个记录的有序文件为止。