查找及应用实验.ppt

山东师大信息学院 Zheng Zhihua 实验 查找及其应用 信息管理学院 实验目的 1. 掌握顺序查找、折半查找方法； 2. 进一步理解各查找算法的特点、使用范围和效率，并能够使用高级程序设计语言实现查找算法； 3. 进一步理解哈希表构造算法与哈希查找算法； 实验内容 1.编程实现顺序查找算法（顺序查找、设置监视哨的顺序查找）； 2.比较两种顺序查找算法的不同； 3.编程实现折半查找算法； 4.理解顺序查找算法和折半查找算法的使用范围。 基本知识 1.什么是查找？ 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”。查找结果给出 “空记录”或“空指针”。 基本知识 2.关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称 之谓“次关键字”。 基本知识 3.如何进行查找？ 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，用另外一种结构来表示查找表。 基本知识 4.查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程（基本操作）。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：Average Search Length) 。 基本知识 5.常见的查找表 静态查找表 动态查找表 哈希表 实验步骤 假设静态查找表为顺序存储结构 typedef float KeyType; //#define ElemType float typedef int KeyType; typedef char KeyType； //char * 字符串型 数据元素类型定义： typedef struct { KeyType key; // 关键字域 ...... //其他数据域（数据项） } ElemType; 静态查找表的顺序存储结构的定义 -顺序表 typedef struct { ElemType *elem; //表基址，0号单元留空。 int length; //表长，即表中数据元素个数 }SSTable; 实验步骤 顺序查找：它从表的一端开始，顺序扫描线性表，依次扫描节点关键字，和给定值Key相比，直到找到为止。 常规方法：从表头开始，用给定值K逐个与表中key值比较，若相等则找到，否则继续比较，直到表尾。很显然，每次比较结束，都要判断是否到表尾。 实验步骤 对ST.elem查找k: for(i=1;i=ST.length;++i) if(k==ST.elem[i].key) return i; return i;//当i=n+1时没找到 当n很大时,查找很慢,而判断条件?汇编用三条指令,共用3n条,所以要尽量减少判断,以上程序有两个判断: for循环判断条件 if判断条件 实验步骤 技巧：查找前，把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。 若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！ 当然，也可将key存入顺序表的尾部，从前向后逐个比较 实验步骤 int Search_Seq( SSTable ST , KeyType key ) { //在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0 ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检 测是否查找完毕。当n1000时，查找时间将减少一半。 for( i=ST.length; ST.elem[ i ].key!=key; - - i ) ; //不要用for(i=n; i0; - -i) 或 for(i=1; i=n; i++) // if（ ST.elem[ i ].key==key）return i； return i; //若到达0号单元才结束循环，说明查找不成功，返回0值(i=0)。 成功时则返回找到的那个元素的位置i。 } // Search_Seq 讨论 讨论1 查不到怎么办？ 讨论2 查找效率怎样计算？