jtahstu的博客

root@jtahstu.com   Github   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 数据结构之查找

数据结构之查找

查找
本章重点:
1、顺序表的查找
2、有序表的查找:折半查找法
3、二叉排序树及其查找过程(动态)
4、二叉排序树的插入(动态)
5、平衡二叉树、B-和B+树的结构
6、哈希表即哈希函数的构造方法了解

查找表:
静态查找表(查询)
动态查找表(查询、插入、删除 )
主关键字 次关键字

平均查找长度:ASL=sum(Pi*Ci)
为提高ASL,需要人为增加数据元素的关系,以便按照某种规则查找。

    9.1 静态查找表
    9.1.1顺序表的查找
顺序表表示:
typedef int KeyType;  
typedef struct  
{  
    KeyType key;  
    InfoTypedata;  
}NodeType;  
typedef NodeType SeqList[MAXL]  

顺序查找
int SeqSearch(SeqList R, int n, KeyType k)  
{  
    int i = 0;  
    while (i <n && R[i].key != k)  
        i++;  
    if (i >=n)  
        return 0;  
    else  
        return i+ 1;  


    9.1.2有序表的查找
1、折半查找
int BinSearch(SeqList R, int n, KeyType k)  
{  
    int low = 0,high = n - 1, mid;  
    while (low<= high)  
    {  
        mid =(low + high) / 2;  
        if(R[mid].key == k)  
            returnmid + 1;  
        if(R[mid].key > k)  
            high= mid - 1;  
        else  
            low =mid + 1;  
    }  
    return 0;  
}
2、斐波那契查找:按照斐波那契数列分段查找
3、插值查找:根据给定值key确定进行比较的关键字R[i].key的查找方法
    i=(key-R[i].key)/(R[h].key-R[l].key)*(h-l+1)
    适用于关键字均匀分布的表

    9.1.4索引顺序表的查找
1、分块查找,索引顺序查找
int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)  
{  
    intlow=0,high=m-1,mid,i;  
    intb=n/m;              //b为每块的记录个数  
    while(low<=high)       //在索引表中进行二分查找,找到的位置存放在low中  
    {  
        mid=(low+high)/2;  
        if(I[mid].key>=k)   
            high=mid-1;  
        else  
            low=mid+1;  
    }  
    //应在索引表的high+1块中,再在线性表中进行顺序查找  
    i=I[high+1].link;  
    while(i<=I[high+1].link+b-1 && R[i].key!=k) i++;  
    if(i<=I[high+1].link+b-1)  
        return i;  
    else  
        return-1;  
}  
 
    9.2动态查找算法(树表的查找)
    9.2.1二叉排序树和平衡二叉树
1、二叉查找树(二叉排序树)及其查找过程
2、二叉排序树的查找
3、二叉排序树的插入算法(递归算法)
int InsertBST(BSTNode *&p,KeyType k)     
{  
   if (p==NULL)                        //原树为空,新插入的记录为根结点  
    {  
        p=(BSTNode*)malloc(sizeof(BSTNode));  
        p->key=k;  
        p->lchild=p->rchild=NULL;  
        return 1;  
    }  
    else if(k==p->key)                 //树中存在相同关键字的结点,返回0  
        return 0;  
    else if(k<p->key)  
        returnInsertBST(p->lchild,k);  //插入到*p的左子树中  
    else   
        returnInsertBST(p->rchild,k);  //插入到*p的右子树中  
}

4、二叉排序树的生成算法
BSTNode *CreateBST(KeyType A[],int n)   //返回BST树根结点指针  
{  
    BSTNode*bt=NULL;                   //初始时bt为空树  
    int i=0;  
    while(i<n)  
    {  
        InsertBST(bt,A[i]);             //将关键字A[i]插入二叉排序树T中  
        i++;  
    }  
    returnbt;                          //返回建立的二叉排序树的根指针   


5、二叉排序树的查找算法(递归)
BSTNode *SearchBST(BSTNode *bt,KeyType k)    
{  
    if (bt==NULL|| bt->key==k)         //递归终结条件  
        returnbt;    
    if(k<bt->key)  
        returnSearchBST(bt->lchild,k);  //在左子树中递归查找  
    else
        return SearchBST(bt->rchild,k);  //在右子树中递归查找

    9.3 哈希表
1、确定的对应关系f
2、对应关系f就是哈希函数
3、哈希函数是一个映象,构造哈希函数的方法:
直接定址法、除留余数法、数字分析法、平方取中法、折叠法
4、冲突现象和解决冲突的方法
当k1!=k2时,f(k1)=f(k2)
开放定址法
(1)线性探测法
(2)平方探测法
拉链法

---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

73 + 17 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……