文章目录

查找

查找-平均查找长度

顺序查找算法及分析

折半查找算法及分析

分块查找

Hash表

Hash 冲突

常见Hash函数

冲突处理方法

Hash表的实现

Hash表的创建

Hash表的插入

Hash表的查找

排序

相关概念

插入排序

交换排序

快速排序

写在最后

查找

设记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k，在表L中确定key=k的记录的过程，称为查找。

若表L中存在一个记录Ri的key=k，记为Ri.key=k，则查找成功，返回该记录在表L中的序号i(或Ri 的地址)，否则(查找失败)返回0(或空地址Null)。

查找方法有顺序查找、折半查找、分块查找、Hash表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用场合选择相应的查找算法。

查找-平均查找长度

对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越差（即T(n)量级越高），故用“比较次数”刻画算法的T(n)。

一般以“平均查找长度”来衡量T(n)。

平均查找长度ASL（Average Search Length）：对给定k，查找表L中记录比较次数的期望值(或平均值)，即：

顺序查找算法及分析

算法思路 设给定值为k，在表(R1 R2……Rn)中，从Rn开始，查找key=k的记录。

int sqsearch(sqlist r, keytype k)  
  {   int i;
                r.data[0].key = k;  //k存入监视哨//
       i = r.len;  //取表长//
      while(r.data[i].key != k) i--;  
      return (i);
  }

故ASL = O(n)。而查找失败时，查找次数等于n+l，同样为O(n)。

对查找算法，若ASL=O(n)，则效率是很低的，意味着查找某记录几乎要扫描整个表，当表长n很大时，会令人无法忍受。

折半查找算法及分析

算法思路

对给定值k，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。

设两个游标low、high，分别指向当前待查找表的上界(表头)和下界(表尾)。mid指向中间元素。

时间复杂度类似于一颗查找树，所以是O(logn)

分块查找

设记录表长为n，将表的n个记录分成b=⌈ n / s ⌉ \lceil n/s \rceil⌈n/s⌉个块，每块s个记录（最后一块记录数可以少于s个），即：

且表分块有序，即第i（1≤i≤b-1）块所有记录的key小于第i+1块中记录的key，但块内记录可以

无序。

分块查找(索引顺序查找）

分块索引查找分两步进行：

1.由索引表确定待查找记录所在的块；

2.在块内顺序查找。

Hash表

理想的查找方法是：对给定的k，不经任何比较便能获取所需的记录，其查找的时间复杂度为常数级O©。

这就要求在建立记录表的时候，确定记录的key与其存储地址之间的关系f，即使key与记录的存放地址H相对应：k e y ⟶ f H : 记 录 key \stackrel{f}{\longrightarrow} H:记录key

⟶

f

H:记录

当要查找key=k的记录时，通过关系f就可得到相应记录的地址而获取记录，从而免去了key的比较过程。

这个关系f就是所谓的Hash函数（或称散列函数、杂凑函数），记为H(key)。

它实际上是一个地址映象函数，其自变量为记录的key，函数值为记录的存储地址（或称Hash地址）。

Hash 冲突

不同的key可能得到同一个Hash地址，即当keyl≠key2时，可能有H(key1)=H(key2)，此时称key1和key2为同义词。这种现象称为“冲突”或“碰撞”，因为一个数据单位只可存放一条记录。

一般，选取Hash函数只能做到使冲突尽可能少，却不能完全避免。这就要求在出现冲突之后，寻求适当的方法来解决冲突记录的存放问题

常见Hash函数

选取（或构造）Hash函数的方法很多，原则是尽可能将记录均匀分布，以减少冲突现象的发生。以下介绍几种常用的构造方法。

直接地址法

平方取中法

叠加法

保留除数法

随机函数法

其中最常见的是保留除数法：

又称质数除余法，设Hash表空间长度为m，选取一个不大于m的最大质数p，令： H ( k e y ) = k e y H(key)=key%pH(key)=key

一般选取除数为质数可以得到相对较好的散列效果

冲突处理方法

冲突是指：表中某地址j∈[0，m-1]中己存放有记录，而另一个记录的H(key)值也为j。

处理冲突的方法一般为：在地址j的前面或后面找一个空闲单元存放冲突的记录，或将相冲突的诸记录拉成链表。

在处理冲突的过程中，可能发生一连串的冲突现象，即可能得到一个地址序列H1、H2……Hn，Hi∈[0，m-l]。H1是冲突时选取的下一地址，而H1中可能己有记录，又设法得到下一地址H2……直到某个Hn不发生冲突为止。这种现象称为聚积，它严重影响了Hash表的查找效率。

还有一个因素是表的装填因子α，α=n/m，其中m为表长，n为表中记录个数。一般α在0.7～0.8之间，使表保持一定的空闲余量，以减少冲突和聚积现象。

开放地址法

当发生冲突时，在H(key)的前后找一个空闲单元来存放冲突的记录，即在H(key)的基础上获取下一地址：

di为地址增量,m为表长。di的取法有多种：

di=1，2，3，……(m-1)——称为线性探查法；

di=12，-12，22，-22，……——称为二次探查法。

链地址法

生冲突时，将各冲突记录链在一起，即同义词的记录存于同一链表。

链地址法解决冲突的优点：无聚积现象；删除表中记录容易实现。

应用广泛

Hash表的实现

H(key)=key

Hash表的创建

hash *hash_create(){
       hash * HT;
       if((HT = (hash *) malloc (sizeof(hash))) == NULL){
               printf("malloc failed\n");
               return NULL;
       }
       memset(HT,0, sizeof(hash));
       return HT;
}

Hash表的插入

int hash_insert(hash *HT, datatype key){
       linklist p, q;
       if(HT == NULL){
               printf("HT is NULL\n");
               return -1;
       }
       if((p = (linklist)malloc(sizeof(listnode))) == NULL){
               printf("malloc failed\n");
               return -1;
       }
       p->key = key;
       p->value = key % N;
       p->next = NULL;
       q = &HT->data[key % N];
       while (q->next && q->next->key < p->key){
               q = q->next;
       }
       p->next = q->next;
       q->next = p;
       return 0;
}

Hash表的查找

linklist hash_search(hash *HT, datatype key){
       linklist p;
       if(HT == NULL){
               printf("HT is NULL\n");
               return NULL;
       }
       p = &HT->data[key % N];
       while(p->next && p->next->key != key){
               p = p->next;
       }
       if( p->next == NULL)
               return NULL;
       else
               return p->next;
}

排序

相关概念

稳定排序和非稳定排序

若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它没有破坏原本已有序的次序。

内排序和外排序

若待排文件f在计算机的内存储器中，且排序过程也在内存中进行，称这种排序为内排序。

若排序中的文件存入外存储器，排序过程借助于内外存数据交换（或归并）来完成，则称这种排序为外排序。

内排序的方法：

插入排序

交换排序

选择排序

归并排序

插入排序

直接插入排序

折半插入排序

链表插入排序

Shell（希尔）排序

直接插入排序

排序方法

先将文件中的（R1）看成只含一个记录的有序子文件，然后从R2起，逐个将R2至Rn按key插入到当前有序子文件中，最后得到一个有序的文件。插入的过程上是一个key的比较过程，即每插入一个记录时，将其key与当前有序子表中的key进行比较，找到待插入记录的位置后，将其插入即可。

时间复杂度T(n)=O(n2)

折半插入排序

先将（R[1]）看成一个子文件，然后依次插入R[2]……R[n]。但在插入R[i]时，子表[R[1]……R[i-1]]已是有序的，查找R[i]在子表中的位置可按折半查找方法进行，从而降低key的比较次数。

其实就是查找的时候采用折半查找罢了

链表插入排序

交换排序

“起泡”排序（Bubble Sort）

“快速”排序（Quick Sort）

快速排序

设记录的key集合k={50，36，66，76，36，12，25，95}，每次以集合中第一个key为基准的快速排序。

#include <stdio.h>
#include <stdlib.h>
#define N 15
int quick_sort(int *data, int low, int high);
int partion(int *data, int low, int high);
int main(int argc, const char * argv[]){
        int data[N] = {0};
        int i;
        srandom(10);
        for(i = 0;i < N; i ++){
                data[i] = random() % 100;
        }
        for(i = 0;i < N; i ++){
                printf("%d ", data[i]);
        }
        puts("");
        quick_sort(data, 0, N-1);
        for(i = 0;i < N; i ++){
                printf("%d ", data[i]);
        }
        puts("");
        return 0;
}
int partion(int *data, int low, int high){
        int temp = data[low];
        while(low < high){
                while(low < high && temp <= data[high]) high--;
                data[low] = data[high];
                while(low < high && temp >= data[low]) low++;
                data[high] = data[low];
        }
        data[low] = temp;
        return low;
}
int quick_sort(int *data, int low, int high){
        int t;
        if(data == NULL)
                return -1;
        if ( low >= high)
                return 0;
        t = partion(data, low, high);
        quick_sort(data, low, t-1);
        quick_sort(data, t+1, high);
        return 0;
}

写在最后

数据结构完结了！！！！但是我感觉这个专题最后俩写的太垃圾了，我尽量更新算法笔记，回头我放参考链接，我尽量一天一更，大家和我一起变强呀！明天开始文件IO，，最后三连即可提高学习效率！！！

另外我在更新的就是算法笔记的一些例题笔记，这个系列是用于提高我的算法能力，如果有兴趣对算法领域感兴趣找不到合适的入门文章也可以追更，如果我更新的太慢了请大家点赞收藏，一键三连才能更有更新的动力呀0.0