数据结构--静态查找表

超、凢脫俗 2021-12-11 08:15 354阅读 0赞

### 文章目录 ###

*  顺序查找表----顺序查找法
 *   *  性能
 *  有序查找表----折半查找法

静态查找表：仅作查询和检索操作的查找表。

查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。

# 顺序查找表----顺序查找法 #

此处以存储结构为顺序表的顺序查找表为例。所谓顺序查找法即是对数组进行遍历，当找到所要的元素后返回其下标。

--------------------

还可以用“设置哨兵”的方法进行遍历。

int linearSearch(int[] arr, keyword){
    	//假设数组第0号位置没有元素，将要查找的元素放进0号位置，这就是设置哨兵
    	arr[0] = keyword;
    	for(int i=arr.length; i>0; i--){
    		if(arr[i] == keyword){
    			return i;
    		}
    	}
    }

哨兵的作用就是确保一定能在数组中查到元素，也确保了返回的数值是逻辑上的顺序而不是下标。

## 性能 ##

定义： 查找算法的平均查找长度(Average Search Length) 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值.  
![在这里插入图片描述][20190710110810278.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

# 有序查找表----折半查找法 #

上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

[20190710110810278.png]: /images/20211211/b09c7336e79c427e8d37a0768557c014.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20211211/ef746f9a64f74489b6296888decb0413.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20211211/1cc70536699040f2a94845a50916dce2.png