查找根据给定的某个值,在查找表中确定一个其关键 字等于给定值的数据元素或(记录) 若查找表中存在这样一个记录,则称查找成功查找结果: 给出整个记录的信息或指示该记录在查找表中的位置 否则称查找不成功查找结果:给出空记录或空指针。 如何进行查找?查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律 因此不便于查找。为了提高查找的效率,需要在查找表 中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表
查找表 Search Table:是一种以集合为逻辑结构 以查找为核心运算的数据结构。 静态查找表:只对查找表进行查询某个特定的数 据元素或某个特定数据元素的各种属性的操作。 如:查询成绩表中是否有某学生或该学生某门课 程的成绩。 动态查找表:对查找表进行插入或删除某个数据 元素的操作。如:修改某个学生某门课程的成绩 衡量查找算法的标准: (1)平均查找长度; (②)算法所需要的存储量和算法的复杂性等
平均宣找长度 定义:为确定记录在表中的位置,需和给定值进 行比较的关键字的个数的期望值叫查找算法在查 找成功时的平均查找长度。 对含有n个记录的表,ASL= 2PC 其中:为查找表中第计个元素的概率∑P=1 c为找到表中第i个元素所需比较次数 物理意义:假设每一元素被查找的概率相同,则查找每 一元素所需的比较次数之总和再取平均,即为ASL 显然,ASL值越小,时间效率越高
基操作 Create(&sT, n) 操作结果:构造一个含n个数据元素的静态查找表ST Destroy(&st); 初始条件:静态查找表ST存在; 操作结果:销毁表ST。 Search(sT, kval; 初始条件:静态查找表ST存在,kwal为和查找表中元素的关键字 类型相同的给定值; 操作结果:若ST中存在其关键字等于kval的数据元素,则函数 值为该元素的值或在表中的位置,否则为“空” Traverse(ST, VisitO); 初始条件:静态查找表ST存在,Ⅴsi是对元素操作的应用函数; 操作结果:按某种次序对ST的每个元素调用函数vsi0次且仅 一次,一旦Ⅴisit失败,则操作失败
8。|静恋宣找表 、顺序查找( Linear search,又称线性查线) 顺序查找:用逐一比较的办法顺序查找关键字。 冷对顺序结构如何线性查找? 心对单链表结构如何线性查找? 对非线性树结构如何顺序查找?借助各种遍历操作! 顺序表的机内存储结构: typedef struct t Elem Type *elem;∥表基址,0号单元留空 int length;表长 I SSTable, typedef struct i key Type key;∥关键字域 ∥/其它属性域 F Elem Type