数据结构学习6

21、哈希查找表

①哈希表的基本概念 哈希表的概念 哈希表：即散列存储结构 散列存储的基本思想:建立关键码与存储位置对应关系,或者说由关键码的值决定数据的存储的地址。 优点:查找速度极快,查找效率与元素个数无关 例1:若将学生信息按如下方式存入计算机,如: 将2001011810201的所有信息存入V[01]单元; 将2001011810202的所有信息存入V[02]单元; 将2001011810231的所有信息存入V[31]单元。 欲查找学号为2001011810216的信息，便可直接访问V[16]！

哈希方法：选取某个函数,依该函数按关键字计算元素的存储位置并按此存放;查找时也由同一个函数对给定值k计算地址,将k与地址内容进行比较,确定查找是否成功。 哈希函数：哈希方法中使用的转换函数称为哈希函数 哈希表:按上述思想构造的表称为哈希表数的同义词 同义词:具有相同函数值的两个不同的关键字称哈希函 冲突:通常关键码的集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同的关键码映射到同一哈希地,址上，这种现象称为冲突。

在哈希查找方法中，冲突是不可避免的，只能尽可能减少。所以用哈希方法必须解决以下问题: 1.构造好的哈希函数 (a)所选函数尽可能简单,以便提高转换速度中并大致均匀，以减少空间浪费。 (b)所选函数对关键码计算出的地址,应在哈希地址内集 2.指定一个好的解决冲突的方案

②哈希函数的构造方法

哈希函数的构造 要求1:散列查找是以空间换时间,但仍要做到散列的地址空间尽量小。 要求2：尽量均匀存放，避免冲突 常用的构造方法: 1.直接定址法 2.除留余数法 3.数字分析法 4.平方取中法 5.折叠法 6.随机数法

直接定址法 Hash(key) = a-key + b(a、b为常数) 优点:以关键码key的某个线性函数值为哈希地址,不会产生冲突. 缺点:要占用连续地址空间,空间效率低。 例:关键码集合为{100, 300, 500, 700, 800, 900},选取哈希函数为Hash(key)=key/100, 则存储结构（哈希表）如下：

除留余数法 Hash(key) = key mod p (p是一个整数) 特点:以关键码除以p的余数作为哈希地址 关键：如何选取合适的p? 技巧:若设计的哈希表长为m,则一般取p<=m且为质数

数字分析法 特点:选用关键字的某几位组合成哈希地址。选用原则应当是:各种符号在该位上出现的频率大致相同。

平方取中法 特点:对关键码平方后,按哈希表大小,取中间的若干位作为哈希地址。 例: 2589的平方值为6702921,可以取中间的029为地址。

折叠法 特点:将关键码自左向右分成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按哈希表表长，取后几位作为哈希地址 适用于：每一位上各符号出现概率大致相同的情况 法1：移位法--将各部分按最后一位对齐相加 法2： 间界叠加法--从一端向另一端分割界来回折叠后，最后一位对齐相加。 例:元素42751896,用法1: 427+518+96-1041 用法2: 427 518 96-> 427+815+96=1338

随机数法 Hash(key)=random(key) (random为随机函数) 适用于:关键字长度不等的情况。造表和查表都很方便。

③冲突处理方法

常见的冲突处理方法 1.开放定址法 2.链地址法 3.再哈希法（双哈希函数法） 4.建立一个公共溢出区

开放定址法 设计思想：有冲突时就去寻找一下空的哈希地址，只要哈希表足够大,空的哈希地址总能找到,并将数据元素存入 具体实现： 1.线性探测法 H,=(Hash(key)+di) mod m (1<i<m) 其中： Hash(key)为哈希函数 m为哈希表长度 di为增量序列1, 2, ...m-1,且d=i 含义：一旦冲突，就找附近（下一个）空地址存入。

线性物探法的优点:只要哈希表未被填满,保证能找到一个空地址单元存放有冲突的元素 线性物探法的缺点:可能使第i个哈希地址的同义词存入第i+1个哈希地址,这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词,因此,可能出现很多元素在相邻的哈希地址上“堆积”起来,大大降低了查找效率 解决方案:可采用二次探测法或伪随机探测法,以改善“堆积”问题

链地址法(拉链法) 基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表,然后用一个数组讲m个单链表的表头指针存储起来,形成一个动态的结构。

再哈希法（双哈希函数法） H=RH(key) i=1, 2, ..., k RH均是不同的哈希函数,当产生冲突时就计算另一个 哈希函数,直到冲突不再发生。 优点：不易产生聚集； 缺点：增加了计算时间。

再建立一个公共溢出区 思想:除设立哈希基本表外,另设立一个溢出向量表 所有关键字和基本表中关键字为同义词的记录,不管它们由哈希函数得到的地址是什么,一旦发生冲突,都填入溢出表

④哈希表的查找

查找过程

22、插入交换排序

①排序概述

排序概述 1.什么是排序? 将一组杂乱无章的数据按一定的规律顺次排列起来 2.排序的目的一便于查找 3.排序算法的好坏如何衡量 时间效率---排序速度（即排序所花费的全部比较次数) 空间效率-占内存辅助空间的大小 稳定性-若两个记录A和B的关键字值相等,排序后A、B的先后次序保持不变,则称这种排序算法是稳定的 4.什么是内部排序？ 若待排序记录都在内存中,称为内部排序 若排序的过程中依赖外部存储器,称外部排序 5.内部排序的算法有哪些 插入排序 交换排序 选择排序 归并排序

②插入排序

概述 1,插入排序的基本思想是:每步将一个待排序的对象按其关键码大小,插入到前而已经排好序的一组对象的适当位置上,直到对象全部插入为止

简言之,边插入边排序,保证子序列中随时都是排好序的 插入排序的2种具体实现的算法： 1）直接插入排序 2）希尔（shell）排序

直接插入排序 1.新元素插入到哪里？在已经形成的有序表中线性查找，并在适当的位置插入，把原来位置上的元素向后移动

typedef struct
{
    int r[MAXSIZE+1]:/*用于存储要排序数组, r[0]用作哨兵或临时变量*/
    int length:/*记录师序表的长度*/
}SqList;
/*对顺序表L作直接插入排序*/
void InsertSort(SqList "L)
{
    int i,j;
    for(i=2;i<=L->length;i++)
    {
        if (L->r[i]<L->r[i-1])/*需将L->r[i]间插入有序子表*/
        {
            L->r[0]=L->r[i]:/* 设置哨兵*/
            for(j=i-1;L->r[j]>L->r[0];j--)
                L->r[i+1]=L->r[]];/* 记录后移*/
            L->r[j+1]=L->r[O];/* 插入到正确位置 */
        }
     }
}

希尔(Shell)排序 1.基本思想: 先将整个待排序记录序列分割成若干子序列，分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序

技巧:子序列的构成不是简单的“逐段分割”,而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短(例如依次取5,3,1），直到dk=1为止 优点:让关键字值小的元素能很快前移,且序列若基本有序时,再用直接插入排序处理,时间效率会高很多。

2.实现代码：

/* 对顺序表L作希尔排序*/
void ShellSort(SqList *L)
{
    int i,j,k=0;
    int increment=L->length;
    
    do
    {
        increment=increment/3+1;/* 增量序列*/
        for(i=increment+1;i<=L->length;i++)
        {
            if (L->r[i]<L->r-increment])/*需将L->ri]插入有序增量子表*/
            {
                L->r[0]=L->r[i]; /* 暂存在L->r[0]*/
                for(j=i-increment;j>0 && L->r[0]<L-r[i];j-=increment)
                    L->r[i+increment]=L->r[j];/* 记录后移，查找插入位置*/
                L->r[]+increment]=L->r[0]; /* 插入*/
            }
        }
        
        printf("第%d趟排序结果:",++k);
        print(*L);
    }
    while(increment>1);
}

③交换排序

基本思想： 两两比较待排序的记录的关键码,如果发生逆序(即排序顺序与排序后的次序正好相反）.则交换之，直到所有记录都排好序为山。 交换排序的主要算法有： 1)冒泡排序 2)快速排序

冒泡排序 基本思想： 每趟不断将记录两两比较,并按“前小后太”(或“前太后小”)规则交换。 优点： 每趟结束时,能挤出一个最大值到最后面位置，一旦一趟没有交互发生还可以提前结束排序。 前提： 顺序存储结构

算法实现：

/*对顺序表L作改进冒泡算法*/
void BubbleSort2(SqList *L)
{
    int i,j;
    Status flag=TRUE;/* flag用来作为标记*/
    for(i=1;i<L->length && flag;i++)/*若flag为true说明有过数据交换，否则停止循环*/
    {
        flag=FALSE;
        for(j=L->length-1;j>=i;j-)  /*初始为False*/
        {
            if(L->r]]>L->r[+1])
            {
                swap(L,j.j+1);/*如果有数据交换,则flag为true */
                flag=TRUE;/*交换L->r[]]与L->r[j+1]的值*/     
            }
        }   
    }
}

快速排序 基本思想:从待排序列中任取一个元素(例如取第一个)作为中心,所有比它小的元素一律前放,所有比它大的元素一律后放，形成左右两个子表。

然后再对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩下一个。此时便为有序序列了 优点:因为每趟可以确定不止一个元素的位置,而且呈指数增加，所以特别快！ 前提：顺序存储结构

算法实现

/*交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置*/
/*此时在它之前（后）的记录均不大（小）手它。*/
int Partition(SqList *L,int low,int high)
{
    int pivotkey;
    
    pivotkey=L->r[low];/*用子表的第一个记录作枢轴记录*/
    while(low<high)/*从表的两端交替地向中间扫描*/
    {
        while(low<high&&L->[high]>=pivotkey)
            high--;
        swap(L,low.high):/*将比枢轴记录小的记录交换到低端*/
        while(low<high&&L->r[low]<=pivotkey)
            low++,
        swap(L.low.high);/*将比枢轴记录大的记录交换到高端*/
    }
    return low;/*返回枢轴所在位置*/
}
​

  /*对顺序表L中的子序列L->r[low..high]作快速排序*/
  void QSort(SqList *L,int low,int high)
  {
    int pivot;
    if(low<high)
    {
        pivot=Partition(L,low,high); /*将L->r[low..high]一分为二,算出枢轴值pivot*/
        QSort(L,low,pivot-1);     /*对低子表递归排序*/
        QSort(L,pivot+1,high);  /* 对高子表递门排序 */
    }
  }
  
  
    /*对顺序表L作快速排序*/
    void QuickSort(SqList *L)
    {
      QSort(L,1,L->length);
    }

23、选择排序

概述 1.基本思想：每一趟在后面n-i个待排记录中选取关键字最小的记录作为有序序列中的第i个记录。 选择排序包含如下实现算法： a)简单选择排序 b)堆排序

简单选择排序 思路异常简单:每经过一趟就找出一个最小值,与待排序列最前面的位置互换即可。 -----首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置; .如此进行下去,直到全部有序为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构

算法实现：

/*对顺序表L作简单选择排序*/
void SelectSort(SqList *L)
{
    int i,j,min;
    for(i=1;i<L->length;i++)
    {
        min = i;        /*将当前下标定义为最小值下标*/
        for (j= i+1;j<=L->length;j++)/*循环之后的数据*/
        {
            if (L->r[min]>L->ri]) /*如果有小于当前最小值的关键字*/
            min =j;     /*将此关键字的下标赋值给min*/
        }
        if(i!=min)/*若min不等于i,说明找到最小值,交换*/
            swap(L,i,min);/*交换L->r[i]与L->r[min]的值*/
    }   
}

堆排序 要解决的问题： 1.什么是堆 2.怎么建立堆 3.怎样进行堆排序

什么是堆： 堆是一棵顺序存储的完全二叉树。 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。 其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。 举例来说,对于n个元素的序列{R1, ..., Rn)当且仅当满足下列关系之一时, 称之为堆： (1) Ri <= R2i且Ri <=R2i+1(小根堆) (2) Ri >= R2i 且 Ri >= R2i+1 (大根堆) 其中i=1,2，...，n/2向下取整；

怎么建立堆: 步骤:从最后一个非终端结点开始往前逐步调整,让每个双亲大于（或小于）子女，直到根结点为止。 终端结点（即叶子）没有任何子女、无需单独调整

怎样进行堆排序： 难点:将堆的当前顶点输出后,如何将剩余序列重新调整为堆？ 方法：将当前顶点与堆尾记录交换,然后仿建堆动作重新调整,如此反复直至排序结束。

算法实现：

/*已知L->r[s.m]中记录的关键字除L->r[s]之外均满足堆的定义, */
/*本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L,int s,int m)
{
    int temp,j;
    temp=L->r[s];
    for(j=2*s;j<=m;j*=2) /*沿关键字较大的孩子结点向下筛选*/
    {
        if(j<m && L->r[j]<L->r[j+1])
            ++j; /*j为关键字中较大的记录的下标*/
        if(temp>=L->r[j])
            break;/* rc应插入在位置s上 */  
        L->r[s]=L->r[i];
        s=j;
    }
    L->r[s]=temp; /* 插入*/
}
​
/* 对顺序表L进行堆排序 */
void HeapSort(SqList*L)
{
    int i;
    for(i=L->length/2;i>0;i--)/*把L中的r构建成一个大根堆 */
        HeapAdjust(L,i,L->length);
    for(i=L->length;i>1;i--)
    {
        swap(L,1,i); /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/
    }   
    HeapAdjust(L,1,i-1);/*将L->r[1..i-1]重新调整为大根堆*/
}

归并排序 基本思想:将两个(或以上)的有序表组成新的有序表。 可以把一个长度为n的无序序列看成是n个长度为1的有序子序列，首先做两两归并,得到[n/21个长度为2的有序子序列;再做两两归并, …如此重复,直到最后得到一个长度为n的有序序列。

算法实现:

/*将SR[s..t]归并排序为TR1[s..t]*/
void MSort(int SRD,int TR1],int s, int t)
{
    int m;
    int TR2[MAXSIZE+1];
    if(s==t)
        TR1[s]=SR[s];
    else
    {
        m=(s+t)/2;/*将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
        MSort(SR,TR2,s,m);/*递归地将SR[s.m]归并为有序的TR2[s..m]*/
        MSort(SR,TR2,m+1,t);/*递归地将SR[m+1..t]归并为有序的TR2[m+1..t]*/
        Merge(TR2,TR1,s,m,t);/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]*/
    }
}
​
​
/*将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/
void Merge(int SR],int TR[],int i,int m,int n)
{
    int j,k,l;
    for(j=m+1,k=i;i<=m && j<=n;k++)/*将SR中记录由小到大地并入TR*/
    {
        if (SR[i]<SR[j])
            TR[k]=SR[i++];
          else
            TR[k]=SR[j++];
    }
    if(i<=m)
    {
        for(l=0;l<=m-i;l++)TR[k+l]=SR[i+];/* 将剩余的SR[i..m]复制到TR*/
    }
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)TR[k+]=SR[j+];/*将剩余的SRIj..n]复制到TR*/
    }
}