数据结 第8章查找表 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第8章查找表 胡建华 2021/2/19 计算机教研室 第 1 页 第 8 章 查找表
@基本概念 ■查找表是由同一类型的数据元素(或记录)构成的集合。 营·由于“集合”中的数据元素之间存在着松散的关系,因 此查找表是一种应用灵便的结构 数对查找表经常进行的操作: 1)查询某个“特定的”数据元素是否在查找表中 2)检索某个“特定的”数据元素的各种属性; 83)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素。 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第2页 基本概念 ▪ 查找表是由同一类型的数据元素(或记录)构成的集合。 ▪ 由于“集合”中的数据元素之间存在着松散的关系，因 此查找表是一种应用灵便的结构。 ▪ 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素
查找表可分为两类 静态查找表 仅作查询和检索操作的查找表。 动态查找表 有时在查询之后,还需要将“查询”结果为“不 在查找表中”的数据元素插入到查找表中;或者,从 查找表中删除其“查询”结果为“在查找表中”的数 据元素。 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第3页 查找表可分为两类 ▪ 静态查找表 仅作查询和检索操作的查找表。 ▪ 动态查找表 有时在查询之后，还需要将“查询”结果为“不 在查找表中”的数据元素插入到查找表中；或者，从 查找表中删除其“查询”结果为“在查找表中”的数 据元素
关键字是数据元素(或记录)中某个数据项的值,用 以标识(识别)一个数据元素(或记录)。 若此关键字可以识别唯一的一个记录,则称之谓“主 关键字”。若此关键字能识别若干记录,则称之谓 “次关键字” .查找根据给定的某个值,在查找表中确定一个其关键 字等于给定值的数据元素。 若查找表中存在这样一个记录,则称“查找成功”。查找结 果给出整个记录的信息,或指示该记录在查找表中的位置; 否则称“查找不成功”。查找结果给出“空记录”或“空指 针 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第4页 • 关键字是数据元素（或记录）中某个数据项的值，用 以标识（识别）一个数据元素（或记录）。 • 若此关键字可以识别唯一的一个记录，则称之谓“主 关键字”。若此关键字能识别若干记录，则称之谓 “次关键字” 。 • 查找根据给定的某个值，在查找表中确定一个其关键 字等于给定值的数据元素。 –若查找表中存在这样一个记录，则称“查找成功”。查找结 果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”。查找结果给出“空记录”或“空指 针”
如何进行查找? 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织 规律,因此不便于查找。 为了提高查找的效率,需要在查找表中的元素之 间人为地附加某种确定的关系,换句话说,用另外 种结构来表示查找表 静态查找表 动态查找树表 哈希表 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第5页 如何进行查找？ • 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织 规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之 间人为地 附加某种确定的关系，换句话说， 用另外 一种结构来表示查找表 – 静态查找表 – 动态查找树表 – 哈希表
@8.1静态查找表 抽象数据类型 ADT StaticSearchTable 数据对象D D是具有相同特性的数据元素的集合。每个数据元素含有类 型相同的关键字,可唯一标识数据元素 数据关系R 数据元素同属一个集合。 基本操作P: Create(&sT, n); Destroy(&st); Search(sT, key); Traverse(st, visito); ADT StaticSearchTable 计算机教研宦 第6页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第6页 8.1 静态查找表 抽象数据类型 ADT StaticSearchTable { 数据对象D： D是具有相同特性的数据元素的集合。每个数据元素含有类 型相同的关键字，可唯一标识数据元素 数据关系R： 数据元素同属一个集合。 基本操作 P： Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit()); } ADT StaticSearchTable
@静态查找表的存储 静态查找表基本上不采用插入和删除操作,因此通常以顺序存储 结构的线形表或有序表存储 假设静态查找表的顺序存储结构为 typedef struct i ElemType *elem //数据元素存储空间基址,建表时按实际 数据结 //长度分配,0号单元留空 int length;//表的长度 SSTable 数据元素类型的定义为: typedef struct i key Type key;//关键字域 //其它属性域 6 ElemType 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第7页 静态查找表的存储 ▪ 静态查找表基本上不采用插入和删除操作，因此通常以顺序存储 结构的线形表或有序表存储 假设静态查找表的顺序存储结构为 typedef struct { ElemType *elem; // 数据元素存储空间基址，建表时按实际 // 长度分配，0号单元留空 int length; // 表的长度 } SSTable; 数据元素类型的定义为: typedef struct { keyType key; // 关键字域 … … // 其它属性域 } ElemType
@8.1.1顺序查找表 以顺序表或线性链表表示静态査找表 回顾顺序表的查找过程 算法25 int Locate Elem Sq(sqlist L, ElemType e) 数据结 ∥在顺序线性表L中查找第1个值与e相等的数据元素, ∥/若找到,则返回其在L中的位序,否则返回0 i=1;∥i的初值为第1个元素的位序 p= L.elen;∥p的初值为第1个元素的存储位置 while(i<= Llength&&*p++!=e)+i;∥依次进行判定 if(i<= Llength) return i;∥找到满足判定的数据元素为第i个元素 else return 0: ∥该线性表中不存在满足判定的数据元素 }∥ LocateElem Sq 计算机教研宦 第8页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第8页 8.1.1 顺序查找表 • 以顺序表或线性链表表示静态查找表 • 回顾顺序表的查找过程： 算法2.5 int LocateElem_Sq( SqList L, ElemType e) { // 在顺序线性表 L 中查找第 1 个值与 e 相等的数据元素， // 若找到，则返回其在L 中的位序，否则返回0 i = 1; // i 的初值为第 1 个元素的位序 p = L.elem; // p 的初值为第 1 个元素的存储位置 while (i <= L.length && *p++ != e ) ++i; // 依次进行判定 if (i <= L.length) return i; // 找到满足判定的数据元素为第i 个元素 else return 0; // 该线性表中不存在满足判定的数据元素 } // LocateElem_Sq
以顺序表或线性链表表示静态查找表 k e STele 数据结 2137881992056456|80753 01234567891011 假设给定值e=64, ST Length 8要求 STelem[ k]=e,问k=? 计算机教研宦 第9页 2021/2/19
Data Structure 数 据 结 构—— 第 8 章 查 找 表 胡建华 2021/2/19 计算机教研室 第9页 • 以顺序表或线性链表表示静态查找表 • 假设给定值 e=64, 要求 ST.elem[k] = e, 问: k = ? 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem k k
@设置“哨兵” STele 642137881992056456807513 01234567891011 ST Length key=64 STele 6021137881992056456807513 01234567891011 ST Length key=60 计算机教研宦 第10页 2021/2/19
Data Structure 数据结构—— 第8章查找表 胡建华 2021/2/19 计算机教研室 第10 页 设置“哨兵” 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length ST.elem i 60 i key=64 key=60 i 64