@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