数据结构查找章节总结之一

深碍√TFBOYSˉ_ 2022-04-04 09:29 151阅读 0赞

# 查找章节总结之一 #

## 1.前言 ##

花了一上午的时间来从头开始学习查找，来总结下自己所学到的一点点东西。

## 2.关于静态查找表 ##

就是很简单的数组的线性查找，需要从头开始一个个去找（即为**遍历**）那么这种查找方法的平均查找长度在查找概率相同的情况下为  
 A S S s = 1 n ∑ i = 1 n ( n − i + 1 ) ASS\_s=\\frac\{1\}\{n\}\\sum\_\{i=1\}^n(n-i+1) ASSs=n1i=1∑n(n−i\+1)

A S S s = n + 1 2 ASS\_s=\\frac\{n+1\}\{2\} ASSs=2n\+1  
关于查找的一个小技巧

typedef struct list 
    {
    	int length;
    	int *elem;
    }list;
    
    int search(list test, int key)
    {
    	test.elem[0] = key;//最开始用list的时候0位置处置空不用
        //这一个语句的作用是设置一个哨兵，当表中没有元素的时候直接返回0
    	for（int i = test.elem.length; i >= 0; i--)
    	{
    		if (test.elem[i] == key)
    		return i;
    	}
    }

## 3.有序表的查找 ##

对于有序表我们肯定是十分熟悉的了,我们可以采用二分查找的方式去找,其实就是我们平时用的**二分法**嘛

typedef struct list 
    {
    	int *elem;//沿用上次的结构
    	//不过此时请注意，这个时候的数组为有序数组
    	int length;
    }list;
    
    int search(list test,int left, int right, int key) 
    {
    	if (key<test.elem[left] || key>test.elem[right])
    		return ERROR;
    	else 
    	{
    		int mid = left + (right - left) / 2;//也表示的是求平均值的意思，不过可以防止爆精度
    		if (key > test.elem[mid]) 
    		{
    			search(test, mid + 1, right, key);
    		}
    		else if(key==test.elem[mid])
    		{
    			return mid;
    		}
    		else 
    		{
    			search(test, left, mid - 1, key);
    		}
    	}
    }

那么折半的平均查找长度为多少呢?我们可以将整个查找的过程视为一个在二叉树上搜索的过程,二叉树的根节点为这个有序数组的中点.对整个二叉树进行中序遍历,可以得到我们原来的有序数组.假设查找每一个节点的概率相同,假设是一个满二叉树,那么第一层节点有一个,第二层有两个…第n层有2(n-1)个,那么查找第一个点的次数为1次,查找第二层节点的次数为两次,个数为2…查找第n层的节点次数为n次,一共有2n-1个.我们假设一共有k个节点,那么这k个节点所能生成二叉树的层数至多为

n=log2(k+1).

那么平均查找长度就为  
 A S L s = 1 k ∑ i = 1 n i ∗ 2 i − 1 ASL\_s=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{n\}i\*2^\{i-1\} ASLs=k1i=1∑ni∗2i−1

A S L s = k + 1 k l o g 2 ( k + 1 ) − 1 ; ASL\_s=\\frac\{k+1\}\{k\}log\_2(k+1)-1; ASLs=kk\+1log2(k\+1)−1;  
k比较大的时候我们可以近似认为  
 A S L s = l o g 2 ( n + 1 ) − 1 A S L s = l o g 2 ( n + 1 ) − 1 ASL\_s=log\_2(n+1)-1ASL\_s=log\_2(n+1)-1 ASLs=log2(n\+1)−1ASLs=log2(n\+1)−1  
所以线性折半查找的效率要远远高于顺序查找,但它只能适用于顺序存储结构,和有序表.

前面较为简单的部分就先总结到这里,之后会更新更后面的章节,感觉都是硬骨头.