数据结构期末复习笔记

数据结构期末复习-笔记

・第一节：高等数据结构(上)

•数组、字符串/Array&String

•链表/Linked-list

•栈/Stack

•队列/Queue

•双端队列/Deque

•树/Tree

・数组、字符串

力扣242

・优点：根据下标随机访问某个元素

・缺点：查询某个元素是否存在时需遍历整个数组；删除/添加元素时，需0(n)时间

•链表

力扣25

•结题技巧

・利用快慢指针(有时要三个)

・构建T虚假的链表头

・栈

力扣20、739

•可以用一个单链表来实现

•算法基本思想

・只关心上一次的操作

•处理完上一次的操作后，能在0(1)时间内查找到更前一次的操作

・队歹u

力扣239

・用在：需要一定的顺序处理数据，且处理的数据在不断变化

・基本实现

•可以用f双链表来实现

Null<*4-[A][B[^^）^4-[C]Null

头指针在队头删除数据，尾指针在队尾添加数据

・常用场景：

・实现一个长度动态变化的窗口或连续区间（滑动窗口）

・广度优先搜索

•树

力扣250、230

・第二节：高等数据结构（下）

•优先队列/PriorityQueue

•图/Graph

•前缀树/Trie

・线段树/SegmentTree

•树状数组/FenwickTree/BinaryIndexedTree

本节课总结

优先队列常见面试考点,实现过程比较繁琐。在解决面试中的问题时,实行“拿来主义"即可

图：被广泛运用的数据结构，如大数据问题都得运用图论

>在社交网络里，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示

，在地图上，要求解从起始点到目的地，如何行驶会更快捷，需要运用图论里的最短路径算法

前维树：出现在面试的难题中，要求能熟练地书写它的实现以及运用

线段树和树状数组应用场合比较明确

如果要求在一幅图片当中修改像素的颜色,求解任意矩形区间的灰度平均值,则需要采用二维的线段恻

•优先队列

力扣347

•与普通队列的区别

•保证每次取出的元素是队列中优先级最高的

•优先级别可自定义（比如指小的优先级高）

•最常用的场景

・从杂乱无章的数据中按照一定的II质序(或者优先级)筛选数据(取出前k大的数)

•本质

012345

•二叉堆的结构，堆在英文里叫Binaryheap

•利用一个数组结构来实现完全二叉树

・特性

・数组里的第一个元素array[0]拥有最高的优先级

•给定一下标i,那么对于元素array【i】而言

・父节点对应的元素下标是(i-1)/2

•左侧子节点对应的元素下标是2*i+l

・右侧子节点对应的元素下标是2*i+2

•数组中每个元素的优先级都必须要高于它两侧子节点

•其基本操作为以下两个(都需O(logk))

・向上筛选(siftup/bubbleup)

・加入新节点时，将节点添加到数的底部(数组最后一个元素)，然后根据节点的优先级，

顺着树爬上去，直到树稳定

•向下筛选(siftdown/bubbledown)

・删除根节点时，用树的最后一个节点代替根节点的位置，然后根据节点的优先级，顺着

树向下比较，直到树稳定

・另一个最重要的时间复杂度：优先队列的初始化

・看似时间复杂度是O(n*logk),实际上是O(n)

・图

必需熟练掌握的知识点

图的存储和表达方式：邻接矩阵、邻接链表

图的遍历：深度优先、广度优先

二部图的检测(Bipartite)、树的检测、环的检测：有向图、无向图

拓扑排序

联合-查找算法(Union-Find)

最短路径：Dijkstra、Bellman-Ford

力扣785

力扣212

•也称字典树

・这种数据结构被广泛地运用在空醺我当中

・什么是字典杳找？

・例如:给定一系列构成字典的字符串，要求在字典当中找出所有以"ABC"开头的字符

串

•方法一:暴力搜索法

・时间复杂度：0(MN)

•方法二:前缀树

・时间复杂度：0(M)

•重要性质

•每个节点至少包含两个基本属性

・children:数组或者集合,罗列出每个分支当中包含的所有字符

・isEnd:布尔值，表示该节点是否为某字符串的结尾

・根节点是空的

•除了根节点，其他所有节点都可能是单词的结尾，叶子节点一定都是单词的结尾

・最基本的操作

•创建

•遍历一遍输入的字符串,对每个字符串的字符进行遍历

•从前缀树的根节点开始，将每个字符加入到节点的children字符集当中

•如果字符集已经包含了这个字符，跳过

•如果当前字符是字符串的最后一个，把当前节点的isEnd标记为真

・搜索

•从前缀树的根节点出发，逐个匹配输入的前缀字符

・如果遇到了，继续往下一层搜索

・如果没遇到，立即返回

・线段树

力扣315

•一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和

・例如要求一段大区间，则对应是各个小区间的和(不相交)

•先从一个例题出发

・假设我们有一个数组array(O..n-1],里面有n个元素，现在我们要经常对这个数组做

两件事：

•1,更新数组元素的数值

・2,求数组任意一段区间里元素的总和(或者平均值)

•方法一：遍历一遍数组

•时间复杂度：0(n)

・方法二：线段树

•时间复杂度：0(logn)

・方法三：树状数组

・树状数组

力扣308

・重要的基本特征

・利用数组来表示多叉树的结构，和优先队列有些类似

•优先队列是用数组来表示完全二叉树，而树状数组是多叉树

•树状数组的第一个元素是空节点

•如果节点tree[y]是tree冈的父节点，那么需要满足y=x-(x&(-x))

・第三节：排序算法

基本的排序算法【简单直接助你迅速写出没有bug的代码】

•冒泡排序/BubbleSort

•插入排序InsertionSort

常考的排序算法【解决绝大部分涉及排序问题的关键】

•归并排序/MergeSort

•快速排序/QuickSort

・拓扑排序/TopologicalSort

其他排序算法【掌握好它的解题思想能开阔解题思路】

•堆排序/HeapSort

•桶排序/BucketSort

•冒泡算法

•两两比较

voidsort(int[]nums){

booleanhasChange=true;

for(inti=;i<nums.length-&&hasChange;i++){

hasChange=false;

for(intj=;j<nums.length--i;j++){

if(nums[j]>nums[j+]){

swap(nums,j,j+i);

hasChange=true;

}

}

}

)

•复杂度

空间复杂度：0(1)

假设数组的元素个数是"整个排序的过程中,直接在给定的数组里进行元素的两两交换。

时间复杂度：0(”2)

,情景一给定的数组按照顺序已经排好

只需要进行次的比较，两两交换次数为0,时间复杂度是0(n),这是最好的情况。

，情景二给定的数组按照逆序排列

需要进行n(n-1)/2次比较,时间复杂度是0(标2),这是最坏的情况。

，情景三给定的数组杂乱无章

在这种情况下，平均时间复杂度是0(口人2)。

•插入排序

力扣147

•待排数据与有序区最外围数据进行比较

voidsort(int[]nums){

for(inti=,j,current;i<nums.length;i++){

current=nums[i];

for(j=i-1;j>=&&nums[j]>current;j--){

nums[j+]=nums[j]]

}

nums[j+]=current;

}

•复杂度

空间复杂度：0(1)

假设数组的元素个数是m整个排序的过程中，直接在给定的散组里进行元素的两两交换。

时间复杂度：0(22)

•情景一：给定的数组按照顺序已经排好

只需要进行次的比较，两两交换次数为0,时间复杂度是0(n),这是最好的情况。

，情景二：给定的数组按照逆序排列

需要进行n(n-1)/2次比较，时间复杂度是0("2),这是最坏的情况。

，情景三给定的数组杂乱无章

在这种情况下,平均时间复杂度是0(M2).

•归并排序

•分治的思想

•归并排序的核心思想是分治，把一个复杂问题拆分成若干个子问题来求解。

•归并排序的算法思想

/\/\

•把数组从中间划分成两个子数组；

・递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素；

•依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

•主体函数

/**归并排序的主体函数7

voidsort(int[]A,intlo,inthi){

if(lo>=hi)return;

intmid=lo+(hi-lo)/2;

sort(A,lo,mid);

sort(A,mid+,hi);

merge(A,lo,mid,hi);

}

voidmerge(int[]nums,intlo,intmid,inthi){

int[]copy=nums.clone();

intk=lo,i=lo,j=mid+;

while(k<=hi){

if(i>mid){

nums[k++]=copy[j++];

}elseif(j>hi){

nums[k++]=copy[i++];

}elseif(copy[j]<copy[i]){

nums[k++]=copy[j++];

}else{

nums[k++]=copy[i++];

)

)

)

•复杂度

时间复杂度：T(n)

归并算法是一个不断递归的过程，假设数组的元素个数是n.

时间复杂度是T(n)的函数：T(n)=2'T(n/2)+O(n)

怎么解这个公式呢？

对于规模为n的问题,一共要进行log(n)层的大小切分；

每一层的合并复杂度都是CXn);

所以整体的复杂度就是Onlogn)。

空间复杂度：05)

由于合并n个元素需要分配一个大小为n的额外数组，合并完成之后，这个数组的空间就会被释放。

•快速排序

力扣215

•快速排序的算法思想

2589

/\/\

2■■■5I^MI8■■■9

•快速排序也采用了分治的思想；把原始的数组筛选成较〃坏口较大的两个子数组，然后递归

地排序两个子数组；

・在分成较小和较大的两个子数组过程中，如何选定一个基准值尤为关键。

・主体函数

/**快速排序的主体函数*/

voidsort(int[]nums,intlo,inthi){

if(lo>=hi)return;

intp=partition(nums,lo,hi);

sort(nums,lo,p-1);

sort(nums,p+,hi);

}

intpartition(int[]nums,intlo,inthi){

swap(numsjrandRange(10jhi),hi);

inti,j;

for(i=lo,j=lo;j<hi;j++){

if(nums[j]<=nums[hi]){

swap(nums,i++,j);

}

}

swap(nums,i,j);

returni;

}

•复杂度

最优情况下的时间复杂度

T(n)=2*T(n/2)+0(n)

0(n)是怎么得出来的呢？

把规模大小为n的问题分解成n/2的两个子问题；

和基准值进行n-1次比较，n-1次比较的复杂度就是0(n)；

快速排序的复杂度也是O(nlogn)。

最复杂的情况

每次在选择基准值的时候；

都不幸选择了子数组里的最大或最小值；

其中一个子数组长度为1；

另一个长度只比父数组少1。

空间复杂度：O(logn)

和归并排序不同，快速排序在每次递归的过程中；

只需要开辟0(1)的存储空间来完成交换操作实现直接对数组的修改；

而递归次数为logn,所以它的整体空间复杂度完全取决于压堆栈的次数。

•拓扑排序

•应用场合

・拓扑排序就是要将图论里的顶点按照相连的性质进行排序

•前提

•必须是有向图

•图里没有环

・先计算入度，删除节点后更新入度

・代码

voidsort(){

Queue<Integer>q=newLinkedList();

for(intv=0；v<V;v++){

if(indegree[v]==)q.add(v);

}

while(!q.isEmpty()){

intv=q.poll();

print(v);

for(intu=;u<adj[v].length;u++){

if(--indegree[u]==){

q.add(u);

}

)

}

}

广度优先搜索队列q保存入度为0的顶点

•复杂度

时间复杂度：O(n)

统计顶点的入度需要0(n)的时间；

接下来每个顶点被遍历一次，同样需要0(n)的时间。

・数据结构

•时间复杂度

•线性表

•顺序表

•插入，删除：0(n)

•直接插入排序、简单选择排序、快速排序的算法以及时间复杂度

・直接插入排序、简单选择排序的平均时间复杂度：T(n)=O(n2)

•快速排序时间复杂度

・平均情况(每次总是选到中间值作枢轴)T(n)=O(nlog2n)

•最坏情况(每次总是选到最小或最大元素作枢轴)T(n)=O(M)

・排序

・1.数据结构和算法的基本概念

•(1)数据、数据元素、数据逻辑结构、数据存储结构、数据类型、抽象数据类型等

・数据：集合

•存储数据时，不仅要存储各元素的值，而且要存储数据元素之间的关系

•数据元素：数据的基本单位

・数据项：构成数据元素的最小单位

一个学生就是个数据元素，数据项包含学号、姓名等

•数据结构

・定义了一组按某些关系组合起来的数据元素

・三要素

•数据逻辑结构

・指数据元素间的逻辑关系，与存储结构无关

・数据存储结构

・指数据结构在计算机中的映像（存储方式）

•顺序存储

・逻辑上相连的元素存储在物理位置上也连续的单元中

・链式存储

・利用地址链接各元素，不要求物理位置连续

•散列存储（哈希存储）

・根据元素关键字计算出元素的存储地址

・索引存储

•建立索引表

・索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）

・其优点是检索速度快，缺点是索引表额外耗费空间

•运算集

・扩展

•数据的逻辑结构抽象于（独立于）存储结构

・如III好表、哈希表、单链表，即表示逻辑结构，又表示存储结构

・而有序表只表示逻辑结构

・栈是一种抽象数据类型，可采用顺序存储戳链式存储，只表示逻辑结构

•而循环队列是用II同序表表示的队列

・数据类型

•不仅定义了一组带结构的数据元素，还在其上定义了一组操作

•扩展

・1)原子类型。其值不可再分的数据类型

•2)结构类型。其值可以再分解为若干成分(分量)的数据类型。

•3)抽象数据类型。抽象数据组织及与之相关的操作

•抽象数据类型(ADT)

•描述了数据的逻辑结构和抽象运算

•仅仅是一组逻辑特性的描述与其在计算机内的实现无关

•用三元组(数据对象,数据关系，基本操作集)来表示，从而构成一个完整的数据

结构定义

•(2)算法、算法设计的要求、算法效率的度量、算法存储空间的需求等

•算法概念

・算法是对特定问题的求解步骤

•算法的计算量大小称为计算的：复杂性

•算法设计的要求

・正确性：每一个步骤有确定的含义

•健壮性：对非法数据能进行处理

・算法效率的度量

•

•用f(n)计算时间复杂度，T(n)为频度之和，0(n)是T(n)的数量级(n为问题的规模)

・时间复杂度为。(标2),说明算法的执行时间与M2成正比

•最内层语句被执行的次数

常见的渐近时间复杂度为

23

0(1)<O(log2n)<O(n)<O(nlog2n)<0(n)<O(n)<0(2")<O(n!)<0("")

•空间复杂度

・指算法所耗费的存储空间

・开辟a[n][m],空间复杂度。(n*m)

・算法原地工作，空间复杂度0(1)

・

IJ*IMJ11IJ

・2.线性数据结构

・（1）栈、队列和线性表的定义和基本概念

•线性表

•顺序表

•链表

•循环链表

图2Y单箱环链表示意图

•判断空链表:head->next==head

•判断是否尾节点:p->next==head

・双向链表

•插入过程

PP

1Fbciau-ru-..............

ssT|^

口e||[I♦I'l

图2—9双向链表的

插入_

・先右后左

•s->next=p->next

•p->next->prior=s

•p->next=s

•s->prior=p

•循环链表和双向链表从任意节点出发都可访问任意节点

・栈

•顺序栈

•结构

•top:指向栈顶

•bottom:指向栈底

•操作

•判断空栈：top==bottom

•top指向位置有兀涝

・动态JI同学栈

可以根据需要增大栈的空间

•bottem指向位置有元素

•top指向位置不放元素

・共享栈

・利用了栈底位置不变，栈顶位置动态变化的特性

•栈底在两端（0和M-1）

•top[0]和top[l]是两个栈顶指示器

•链栈

top-----►Atop

空栈

非空栈

链栈存储形式

•多栈运算

・队列

•顺序队列

•插入：rear位置插入元素，后+1

•删除：front位置删除，后+1

•初始化：front=rear=0

«队空：rear==front

・队满:rear==MAX_QUEUE_SIZE-1

•循环队列

・队满：front==(rear+1)%MAX_QUEUE_SIZE

•rear指向元素的后一

・链队列

链队列结点示意图

•结构

•front:队头指针，在此删除元素

•rear:队尾指针，在此添加元素

•操作

•队空：front==rear

•添加/删除元素

（a｝空从药

(b)xAfk

（c）y再入队

同x出队

队雉作及指针变化

・（2）栈、队列和线性表的实现，包括顺序和链式存储结构

・（3）栈、队列和线性表的应用

・线性表

・已知元素个数时，使用III页序存储更节省时间，因为链式存储需要存储额外的指针

・删除单链表中值相同的节点

48〃删除单链表中值相同的节点

49voidDelete__Node_value(LNode*L){

50LNode*p=L->next,*q,*ptr;

51(p!=NULL){

52q=p;

53ptr=p->next;

54(ptr!=NULL){

55(ptr->data==p->data){

56q->next=ptr->next;

57free(ptr);

58ptr=q->next;

59}else{

60q=ptr；

61ptr=ptr->next;

62}

63}

64p=p->next;

65)

66)

•串

•串；字符的有限序列

・空串：长度为0的串

空串所任意串的子串

•空白串（空格串）：所有字符都是空格的串

・串长：所含字符长度

・串的存储方式

•定长存储：字符数组

•堆分配：长度动态变化的字符数组

・块链存储：链式存储，一个块包含若干个字符

•在串未填上不属于串值的特殊字符，表示串的总结

・串的模式匹配算法

・模式匹配：指子串值主串中的定位，匹配成功表在主串S中能找到模式串T

・BF

*

•求串的next函数值

I01234567891011

abcaabbabcab

next[|]400011201234

rmtvalU-100-1102-100-1I4|

•next数组

•首字符从-1开始

若从答案从0开始，则整体数组+1得结果

・匹配第i个字符，看0~i-1的字符间（头和尾）是否有相同子串

・有：写上子串长度

•无：写0

・nextval数组

・辅助步骤：先根据next数组值，写下对应的字符

•首字符从-1开始

•比对第i位字符和辅助字符是否相同

•不同：nextval的值即为next的值

•相同:看next的值为多少,为k则取nextval[k]

.数组

・定义的下标从1开始

•数组的存储

•两种类型：按行存储/按列存储

・三角矩阵

•分上三角、下三角

・带状矩阵

・以对角线为中心，三条元素

•稀疏矩阵

•三元组表示法

•十字链表

・3.排序基础

・（1）排序的概念与分类

・内部排序

・插入排序

・直接插入排序

•直接插入排序

1typedefintDataType;

2〃直接插

3voidInsertSort(DataTypeL[],intlen){

4inti，3；

5DataTypetemp;

6for(i=l;i<len;i++){〃len个数比较lenT趟,第一个数有序

7temp=L[i];//5[合temp

8j>=0;j--){

9if(temp<L[j])L[j+1]=L[j];

10elsebreak;〃数据移位

11}

12L[j+1]=temp;

13}

14}

・思想：数据分为两个区一有序区和无序区；每次都取最靠近有序区的数

插入到有序区中（没有选择的过程！！）

插入排序过程

30」。5。4025

20i=l2030504025

I

1

50i=22030504025

i

I-

40i=32030405025

_i

25i=42025304050

•初始时，有序区元素个数为1

•直插是稳定排序

・直接插入排序、简单选择排序的平均时间复杂度：T(n)=O(n2)

・折半插入排序

•希尔排序

•思想

・序列增量作为分组间隔，分为若干组，组内进行直接插入排序

一般第一次取的增量为n/2

・不断缩小增量，直到为1

・步骤

楙而而第轮组耦*了仙讨郴布

时”和精"魄段T为推而楙

tHtiifft…播耀2ttfttitfi

・交换排序

・冒泡排序

・冒泡排序

//冒泡排序：对n个数，要排n-1趟，第j趟要交换向次

voidbubble_sort(inta[],intn){

inttemp=0;

for(inti=0;i<n;i++){

for(intj=0;j<n-j;j++){

if(a[j]>a[j+l]){〃交换

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

?

}

}

}

・快速排序

•快速排序

1typedefintDataType;

2//快速排序

3voidQuicksort(DataTypeR[],ints,inte){

4intlow=s,high=e;

DataTypex=R[s];

6?.hile(low<high){

(low<high&&R[high]>=x)high--;

R[low]=R[high];

(low<high&&R[low]<x)low++;

10R[high]=R[low];彳大数放在右恻大数序列中

11}〃循环结束时low、high合

12R[low]=x;

13if(s<high-1)

14QuickSort(R,s,high-1);

15if(high+1<e)

16Quicksort(R,high+1,e);〃对右例大数序列进行递归划分

”1

・思想：每次取第一个数为枢轴，从另一边开始取数进行比较，若大于枢轴

贝怀变，小于则将那个数放到枢轴的位置。high和low的指针重合的地

方就是枢轴该呆的地方，枢轴一旦确立后其位置不变

[练习】写出序列{31,68,45,90,23,39,54,12,87,76}

以“31”为枢轴的一次划分结果。

12,23^1,90,45,39,54,68,87,76

・快速排序是不稳定的！！

・快速排序时间复杂度

・平均情况(每次总是选到中间值作枢轴)T(n)=O(nlog2n)

•最坏情况(每次总是选到最小或最大元素作枢轴)T(n)=O(n2)

・选择排序

・简单选择排序

•直接选择排序

1typedefintDataType;

2〃直接选择排序

3voidSelectSort(DataTypeL[],intlen){

4inti,j,min;

5DataTypetemp)

6(i=0;i<len-l;i++){

7min=i;

8for(j=i+l;j<len;j++){〃求i后的第1个数到末尾的min

9(L[j]<L[min])min=j;

10)

11(min!=i){

12temp=L[i];

13L[i]=L[min];

14L[min]=temp;

15}

16}

17}

・思想：数据分为两个区一有序区和无序区；每次都在无序区中取一个最

小的数送到有序区中(比较+交换)

选择排序过程

3020504025

t__T

第i=l趟结果：2030504025

t_______~

第i=2趟结果：20255040独

1_____T

第i=3趟结果：2025304050

第i二4趟结果：2025304050

初始时，有序区为空

直选是不稳定的！！

・直接插入排序、简单选择排序的平均时间复杂度：T(n)=O(n2)

•堆排序

•归并排序

・过程

初始关键字：[23][38][22][45]

L_rJLn_J

一趟归并后：[2338][2245]

II

I

二趟归并后：[22233845]

I_______.

I

三趟归并后：[15222323

四趟归并后：[15222323

图1511归并排序过程

•代码

・基数排序

•外部排序

•多路归并排序

•(2)直接插入排序、希尔排序与基数排序

•4.哈希表

•(1)哈希表的构造

・设计哈希函数：y=h（k）

y为求得的哈希地址，h为求地址使用的函数，k是自变量（或称关键字，即一个个数据）

・直接定值法

•定义：y=k+b（b为偏移量）

•适用场合：k值连续

・缺点：易于浪费空间

・除留余数法

•定义：y=k%n（n为存储空间个数）

•适用场合：大部分

•Ps:n值一般取小于或等于存储空间的素数

•设计哈希函数方法拓展

・直接定值法

•定义：y=k+b（b为偏移量）

•适用场合：k值连续

・缺点：易于浪费空间

・数字分析法

・定义：杳看数字的各位，取其值相差较大的某几位作为关键字k

•平方取中法

・定义：将一个数平方后取其中间几位作为k

•原理：平方后中间的数值一般相差较大

・折叠移位法

・移位叠加法

・定义：将一个数拆为位数相同的若干块，并将这些块相加，舍弃进位，结

果作为k

•间界叠加法

•定义：与移位叠加法类似，但其取其中的一位前后颠倒（如584变成485）

后相加，舍进位，结果为k

•解决冲突方法

冲突：对不同的关键字取到同一个地址,即引起冲突

•开放定址法

•定义：y=（（k%n）+di）%n（以除留余数法为例）

・di取值的不同可分为以下几类

•线性探索法(最常用！)

・di取21的正整数并递增(1,2,3,4,...)

・平方探查法

•di为线性探索法的平方

•冲突解决方法拓展

・开放定址法

•定义：y=((k%n)+di)%n(以除留余数法为例)

・di取值的不同可分为以下几类

•线性探索法(最常用！)

・di取21的正整数并递增(123,4,...)

・平方探查法

・di为线性探索法的平方

・链地址法

h(20)=20%ll=9；散列表：。A

T121Al

h(30)=30%ll=8；1A-

h(70)=70%ll=4；2A

h(15)=15%ll=；JA

A~~~-OITOQ-OJSE]

h(8)=8%ll='；5A

h(12)=12%ll=l；6A

h(18)=18%ll=7；7A-[

h(63)=63%U=；:A~~

-o|2SP^

A-

h(19)=19%ll=；ioA

•定义：以链表洞诸存数据，将冲突了的关键字连接在同一地址的上一个关键字后

•构造哈希表

•已知散列表地址区间为0~10,给定关键字序列(20,30,70,15,8,12,18,63,

19)。哈希函数为h(k)=k%ll,分别采用线性探查法和链地址法处理冲突，构造散列

表。要求写出各自的计算过程并画出对应的散列表

・线性探查法

h（20）=20%ll=9；h（63）=63%H=f,冲突;

h（30）=30%ll=8；%d

h（70）=70%ll=4；儿=（8+1）%11=9,冲突；

h=（8+2）%ll=10,冲突;

h（15）=15%ll=4,冲突;2

h=（8+3）%11=0；

h（）=43

%=（4+1）%11=5；h（19）=19%U=：,冲突;

h（8）=8%ll=8,冲突；%=8

hj=（8+1）%11=9,冲突；

h=8

0h=（8+2）%ll=10,冲突;

%=（8+1）%11=9,冲突；2

h=（8+3）%11=0,冲突；

h=（8+2）%11=10；3

2%=（8+4）%11=1,冲突；

h（12）=12%ll=l；%=（8+5）%11=2。

h（18）=18%ll=7；

0123456789

散列表：应112|19||70115|118|30|20|

・链地址法

h（20）=20%ll=9；散列表。A___

h（30）=30%ll=8；