计算机软件及应用查找PPT学习教案.pptx

会计学
1
计算机软件及应用查找
Page 2
2021/6/3
重点和难点
重点：理解查找表的结构特点及其各种表示方法的特点和适用场合。
知识点
顺序表、有序表、索引顺序表
二叉查找树、二叉平衡树
哈希表
第1页/共118页
第2页/共118页
第3页/共118页
第4页/共118页
第5页/共118页
Page 7
2021/6/3
静态查找表
抽象数据类型静态查找表的定义
ADT StaticSearchTable {
数据对象：D是具有相同特性的数据元素的集合。每个数据元素含有类 型相同的关键字，可唯一标识数据元素。
数据关系：D中所有数据元素同属一个集合。
基本操作：
CreateTable(&ST, n); 操作结果：构造一个含 n 个数据元素的静态查找表 ST。
DestroyTable(&ST); 初始条件：静态查找表 ST 存在； 操作结果：销毁查找表 ST。
第6页/共118页
Page 8
2021/6/3
Search(ST, kval);初始条件：静态查找表 ST 存在，kval 为和查找表中元素的关键字 类型相同的给定值；操作结果：若ST中存在其关键字等于 kval 的数据元素，则函数值 为该元素的值或在表中的位置，否则为“空”。
Traverse(ST, visit());初始条件：静态查找表 ST 存在，visit 是对元素操作的应用函数；操作结果：按某种次序对ST的每个元素调用函数 visit() 一次且仅 一次，一旦 visit() 失败，则操作失败。
} ADT StaticSearchTable
第7页/共118页
Page 9
2021/6/3
顺序表的查找
适用情况
查找表用顺序存储结构存放。
查找过程
从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较；
若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；
反之，若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
第8页/共118页
Page 10
2021/6/3
0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92

顺序表的类型描述：
typedef struct{ElemType *elem; // 数据元素存储空间基址，建表 // 时按实际长度分配，0号单元留空int length; // 表中元素个数} SSTable;
i
找64
64
监视哨
i
i
i
i
比较次数=5

第9页/共118页