数据结构小结（七）查找

ゝ一世哀愁。 2022-08-18 12:22 141阅读 0赞

## 几种查找算法 ##

1.顺序查找

2.折半查找

3.分块查找

4.基于树的查找

## 平均查找长度 ##

为确定某元素在查找表中的位置需要和给定值进行比较的关键字个数的期望值，称为该查找算法查找成功时的平均查找长度。

## 基于线性表的查找 ##

很简单，时间复杂度为O（N）。 这里只说那个改进的线性表查找好了。

int Seqsearch(SeqRlist L,KeyType K){
        L.r[0].key = K;
        i = L.length;
        while(L.r[i].key != K){
            i--;
        }
        returni;
    
    }

## 折半查找 ##

这是另一种查找的方法，但是有2个要求：

1.这个序列必须是有序的

2.必须基于顺序查找

非递归实现
    int binsrch(seqlist L,keytype K){
    
        int low = 1;
        int high = L.length;
        int mid;
        while(low <= high){
            mid = (low + high)/2;
            if(K == L.r[mid].key){
                return mid;
            }else if(K < L.r[mid].key){
                high = mid -1;
            }else{
                low = mid + 1;
            }
        }
    
        return 0;
    
    }
    
    
    递归实现
    
    int bin_search(int key[],int low,int high,int k){
        int mid;
        if(low > high){
            return -1;
        }else{
    
            mid = (low + high)/2;
            if(key[mid] == k){
                return mid;
            }
            if(k > key[mid]){
                return  bin_search(key,mid+1,high,k);
            }else{
                return  bin_search(key,low,mid-1,k);
            }
       }
    
    }

时间复杂度： ASL = log2(n+1)-1

关于这折半查找我还要说一点，就是折半查找树和成功与失败的计数。 根据有序的数列建立的一棵树。 以中间元素作为根结点。

然后它的左子树的数值都要比有子树的数值小，这是一个递归适用的定义。

容我搞个截图

1，2，3，4，5，6，7，8，9，10

[![find\_tree][find_tree]][find_tree_find_tree]

可以建立这样一棵查找树，我们需要做的就是计算ASL的值，成功与失败两种情况。

例如我们需要查找 4 这个元素

ASL（成功） = (1*1 + 2*2 +3*4 + 4*3)/10

ASL(失败） = （ 5*3 + 6*4 ）/11 失败主要根据空叶子结点计算出结果

## 索引查找 ##

索引查找是在索引表和主表(即线性表的索引存储结构)上进行的查找。索引查找的过程是：首先根据给定的索引值K1，在索引表上查找出索引值等于K1的索引项，以确定K1对应的子表在主表中的开始位置和长度，然后再根据给定的关键字K2，在对应的子表中查找出关键字等于K2的元素(结点)。 对索引表或子表进行查找时，若表是顺序存储的有序表，则既可进行顺序查找，也可进行二分查找。否则只能进行顺序查找。

基本思想：

1.把线性表分成若干块，每一块包含若干个记录，在每一块中记录的存放是任意的，但是块与块之间必须是有序的。

2.建立一个索引表，把每块中的最大关键字值以及每一块的记录在表中的位置和最后一个记录在表中的位置存放在索引项中，所以索引表是一个有序表。

## AVL ##

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

## 图解 ##

东西太多感觉不好说了，直接图解吧。

[![tu][]][tu 1]

## 伸展树 ##

伸展树（Splay Tree，事实上在国内OI界常常被称作Spaly Tree，与此同理的还有Treap），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造，后者对其进行了改进。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

## 二叉排序树 ##

二叉排序树（BST）也就是二叉查找树。满足以下性质的特殊二叉树。

1.如果左子树不为空，则左子树上的所有结点的值均小于根结点的值。

2.如果右子树不为空，则右子树上的所有结点的值均大于根结点的值。

3.它的左，右子树也都是二叉排序树，毕竟树的一个基本属性就是递归性。

### 关于二叉排序树的性能分析 ###

二叉排序树的查找最差情况于顺序查找相同，ASL=(n+1)/2 .

最好的情况与折半查找相同，ASL = log2N .

### 关于二叉排序树的一些操作 ###

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define  MAXSIZE  1000
    
    typedef int  KeyType;
    
    typedef struct Node{
    
        KeyType obj;
        struct Node *rchild;
        struct Node *lchild;
    
    }Node,*Bstree;

查找

Node *SearchBST(Node *bst,KeyType K){
    
        Node *q;
        q = bst;
        while(q){
            if(q->obj == K){
                return q;
            }else if(K < q->obj){
                q = q->lchild;
            }else{
                q = q->rchild;
            }
        }
    
        return NULL;
    }
    
    Node *SearchBST_B(Node *bst,KeyType K){
    
        if(!bst){
            return NULL;
        }else if(bst->obj == K){
            return bst;
        }else if(K < bst->obj){
            return SearchBST_B(bst->lchild,K);
        }else if(K > bst->obj){
            return SearchBST_B(bst->rchild,K);
        }
    }

插入

void InsertBST(Node **bst,KeyType K){
    
        Node *s;
        if(*bst == NULL){
            s = (Node *)malloc(sizeof(struct Node));
            s->obj = K;
            s->lchild = NULL;
            s->rchild = NULL;
            *bst = s;
            //printf("%d\n",bst->obj);
        }else if((*bst)->obj > K){
            InsertBST(&(*bst)->lchild,K);
        }else if((*bst)->obj < K){
            InsertBST(&(*bst)->rchild,K);
        }
    
    }

创建

Node ** Created_bst(Node **bst){
        KeyType key;
        *bst = NULL;
        int count ;
        printf("please enter count\n");
        scanf("%d",&count);
        while(count > 0){
            printf("please enter the num \n");
            scanf("%d",&key);
            printf("%p\n",bst);
            InsertBST(bst,key);
    
            count--;
        }
    
        return bst;
    }
    
    
    遍历：
    void show(Node *root){
        if(root){
            show(root->lchild);
            printf("%d ",root->obj);
            show(root->rchild);
    
        }else{
    
            return ;
    
        }
    }

### 删除 ###

Node * Delete(Node * node,KeyType K){
        Node *p,*f,*s,*q;
        p = *node;
        f = NULL;
        while(p){
            if(p->obj == K){
                break;
            }
            f = p;
            if(p->obj > K){
                p = p->lchild;
            }else{
                p = p->rchild;
            }
        }
        if(p == NULL)
            return bst;
        if(p->lchild == NULL){
            if(f == NULL){
                bst = p->rchild;
            }else if(f->lchild == p){
                f->lchild = p->rchild;
            }else{
                f->rchild = p->rchild;
            }
            free(p);
        }else{
            q = p;
            s = p->lchild;
            while(s->rchild){
                q = s;
                s = s->rchild;
            }
            if(q == p){
                q->lchild = s->lchild;
            }else{
                q->rchild = s->rchild;
            }
            p->obj = s->obj;
            free(s);
        }
        return node;
    
    }

## 散列（哈希） ##

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre
    -image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，
    也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散
    列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数
    。

## 基本概念 ##

*  若结构中存在和关键字K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个事先建立的表为散列表。
 *   
 *   
 *  对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称碰撞。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。
 *  若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

### 一般使用的哈希函数 ###

1.线性探测再散列

每次线性的探测+1.

2.二次探测再散列

每次线性的+-(n^2).

3.随机探测再散列

使用伪随机函数.

### 几种哈希表的ASL ###

线性探测法 1/2(1+1/(1-a))

1/2[1+1/(1-a)^2]

二次线性探测法 (1/a)ln(1-a)

1/(1-a)

链地址法 1+a/2

a+e^(-a)

### 一个简单的实现 ###

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define HASHSIZE 11
    #define DEL      -1
    
    
    typedef struct {
    
        int key;
    
    }Datatype;
    
    typedef struct {
    
        Datatype data;
        int times;
    
    }Hashtable[HASHSIZE];

int HashFunc(int key){
    
        return key % HASHSIZE;
    }
    
    int Collision(int di){
    
        return (di + 1) % HASHSIZE;
    }
    
    
    int HashSearch(Hashtable ht,Datatype x){
        int address;
        address = HashFunc(x.key);
    
        while(ht[address].data.key != 0 && ht[address].data.key != x.key)
            address = Collision(address);
    
        if(ht[address].data.key == x.key){
            return address;
        }else{
            return -1;
        }
    
    }
    
    int HashInsert(Hashtable ht,Datatype x){
    
        int address;
        address = HashFunc(x.key);
        if(address >= 0){
            return 0;
        }
        ht[-address].data = x;
        ht[-address].times = 1;
    
        return 1;
    
    }
    
    
    void Createht(Hashtable ht,Datatype L[],int n){
        int i;
        for(i = 0;i < HASHSIZE;i++){
    
            ht[i].data.key = 0;
            ht[i].times = 0      ;
        }
        for(i = 0;i < n;i++)
            HashInsert(ht,L[i]);
    }
    
    int HashDel(Hashtable ht,Datatype x){
    
        int address;
        address = HashFunc(x.key);
        if(address >= 0){
            ht[address].data.key = DEL;
            return 1;
        }
    
        return 0;
    }

[find_tree]: https://img-blog.csdnimg.cn/img_convert/0f2dd231ef428cda88fb1958cb63e779.png
[find_tree_find_tree]: https://github.com/zmr961006/DSAA/blob/master/chap7_tree_plus/find_tree.png
[tu]: /images/20220731/79076520f257406aabe0bc4d5812c725.png
[tu 1]: https://github.com/zmr961006/DSAA/blob/master/chap7_tree_plus/AVL.jpg