数据结构：第七章学习小结

xhao

2020-06-28

关注关注

思维导图

数据结构：第七章学习小结

算法小结

1.顺序查找

①基础方法

int Search(SSTable ST, KeyType key) 
{ 
    for(i=1;i<=ST.length;i++)
    {
        if(key==ST.R[i].key) return i;
     }
    return 0;//若未查找到则返回0
}

顺序查找

②设置监视哨方法

//避免查找过程中每次检测整个表是否查找完毕的步骤
//在数据量大能有效减少查找时间
int Search(SSTable ST, KeyType key) 
{
    ST.R[0].key = key; //把待查关键字key存入表头,起监视哨作用
    for(i=ST.length; ST.R[i].key!=key; --i );
    return i; //若查找到则返回其下标，若未查找到则返回0
}

顺序查找(哨兵)

2.二分查找

①递归方法

int Search(SSTable ST, KeyType key, int low, int high) 
{
    if(low <= high){
        mid = (low+high) / 2;
        if(key == ST.R[mid].key) 
              return mid;
        else if(key < ST.R[mid].key)
              return Search(ST,key,low,mid-1);//递归查找左区间
        else 
             return Search(ST,key,mid+1,high);//递归查找右区间
    }
    return 0;//若未查找到则返回0
}

二分查找(递归)

②非递归方法

int Search(SSTable ST, KeyType key) 
{
    int low = 1, high = ST.length;//置查找区间初值
    while(low <= high) 
    { 
        mid = (low+high) / 2; 
        if(key == ST.R[mid].key) 
            return mid;//找到待查元素
        else if(key < ST.R[mid].key) 
            high = mid-1; //继续在前一子表进行查找
        else 
            low = mid + 1; //继续在后一子表进行查找
    }
    return 0; //表中不存在待查元素则返回0 
}

二分查找(非递归)

③分析：设存在有序表a，key为所要查找的元素值，根据mid=(low+high)/2，可得出查找区间为[low, mid-1]或者[mid+1，high]。ⅰ 若存在key，找到a[mid]=key退出即可。ⅱ 若不存在key在查找过程中，low和high将逐渐靠拢、缩小区间，直至low=high=mid，由于循环条件为low<=high(若为low=high，此处将直接结束程序，无法判断当前元素是否等于key)，因此程序将继续进行，low>high，最终退出循环。

3.二叉排序树

①查找算法（利用递归实现）

Tree Search(Tree T, KeyType key) 
{
    if((T==NULL) || key==T->data.key)//若树空或查找到，返回当前结点
        return T; 
    else if(key < T->data.key) //在左子树中继续查找 
        return SearchBST(T->lchild, key); 
    else //在右子树中继续查找 
        return SearchBST(T->rchild, key); 
}

二叉排序树查找算法

②插入算法

若要在树中插入一个关键字值为key的结点*S，根据查找的思路，在树中自根结点往下查找，如果树中不存在值为key的结点则查找失败，在当前位置插入结点，如果存在则查找成功，退出程序。

void Insert(Tree &T, ElemType key ) 
{
    if (T == NULL)
    {//树为空则作为根结点 
        s = new Node; 
        s->data = key; 
        s->lchild = s->rchild = NULL; 
        T = s; 
    }
    
    if (key == T.data) return; //查找成功则退出 
    else if (key < T.data) //小于当前结点值，递归左子树 
        Insert(T -> lchild, key); 
    else if (key > T.data) //大于当前结点值，递归右子树 
        Insert(T -> rchild, key);
}

二叉排序树插入算法

③创建算法（相当于插入n个结点）

4.散列表

设散列表表长为m。

①创造方法：

常用的创造方法为除留余数法，一般被除数可选择小于表长的最大质数。

②冲突处理：

ⅰ 线性探测法：Hi=(H(key)+i)％m 0≤i≤m-1

从H0开始，若H0已被占用，则检索下一个位置H1是否被占用，以此类推，直至找到空位或散列表已满。但该方法易造成”二次聚集”现象，导致非同义词之间可能彼此冲突。

ⅱ 平方探查法：Hi=(H(key)+i*i)％m 0≤i≤m，(此处列举的是正向平方探查法)

此方法能减少堆积的发生，但可能无法探查整个散列表，即不能保证找到不发生冲突的地址。

ⅲ 链地址法：将同义词放在同一个单链表中，再用数组存储每个单链表的头指针。