► 数据结构教程 第二十九课 静态查找表(一)顺序表的查找数据结构教程 第二十九课 静态查找表(一)顺序表的查找教学目的:掌握查找的基本概念,顺序表查找的性能分析教学重点:查找的基本概念教学难点:顺序表查找的性能分析授课内容:一、查找的基本概念查找表:是由同一类型的数据元素(或记录)构成的集合。查找表的操作:1、查询某个“特定的”数据元素是否在查找表中。2、检索某个“特定的”数据元素的各种属性。3、在查找表中插入一个数据元素;4、从查找表中刪去某个数据元素。静态查找表对查找表只作前两种操作动态查找表在查找过程中查找表元素集合动态改变关键字是数据元素(或记录)中某个数据项的值主关键字可以唯一的地标识一个记录次关键字用以识别若干记录查找根据给定的某个值,在查找表中确定一个其关键字等于给定的记录或数据元素。若表中存在这样的一个记录,则称查找是成功的,此时查找的结果为给出整个记录的信息,或指示该记录在查找表中的位置;若表中不存在关键字等于给定值的记录,则称查找不成功。一些约定:典型的关键字类型说明:typedeffloatKeyType;//实型typedefintKeyType;//整型typedefchar*KeyType;//字符串型数据元素类型定义为:typedefstruct{KeyTypekey;//关键字域...}ElemType;对两个关键字的比较约定为如下的宏定义:对数值型关键字#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))对字符串型关键字#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)二、静态查找表静态查找表的类型定义:ADTStaticSearchTable{数据对象D:D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同,可唯一标识数据元素的关键字。数据关系R:数据元素同属一个集合。基本操作P:Create(&ST,n);操作结果:构造一个含n个数据元素的静态查找表ST。Destroy(&ST);初始条件:静态查找表ST存在。操作结果:销毁表ST。Search(ST,key);初始条件:静态查找表ST存在,key为和关键字类型相同的给定值。操作结果:若ST中在在其关键字等于key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。Traverse(ST,Visit());初始条件:静态查找表ST存在,Visit是对元素操作的应用函数。操作结果:按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败,则操作失败。}AD
数据结构教程第二十九课静态查找表(一)顺序表的查找 来自淘豆网www.taodocs.com转载请标明出处.