1、数据结构与算法查找赵颖 中南大学，赵颖 中南大学目录n 查找基本概念n 静态查找 顺序查找 二分查找赵颖 中南大学查找基本概念n 查找操作十分常见 在英汉字典中查找某个英文单词的中文解释； 在新华字典中查找某个汉字的读音、含义； 邮递员送信件要按收件人的地址确定位置等等。可以说查找是为了得到某个信息而常常进行的工作。n 计算机的查找 计算机、计算机网络使信息查询更快捷、方便、准确。要从计算机、计算机网络中查找特定的信息，就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释，就需要存储类似英汉字典这样的信息表，以及对该表进行的查找操作。 查找是许多程序中最消耗时间的
2、一部分。因而，一个好的查找方法会大大提高运行速度。 本章将讨论的问题即是 “信息的存储和查找 ”。赵颖 中南大学查找基本概念n 查找表 用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。n 关键字 关键字是数据元素中的某个数据项。 唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字； 若查找表中某些元素的关键字值相同，称这种关键字为次关键字。 例如，银行帐户中的帐号是主关键字，而姓名是次关键字。 赵颖 中南大学查找基本概念n 查找 在数据元素集合中查找满足某种条件的数据元素的过程称为查找。 最简单且最常用的查找条件是 “
3、关键字值等于某个给定值 ”。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。n 查找表的存储结构 对于不同的存储结构的查找表，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构，比如：线性结构（顺序存储、链式存储）、树形结构、哈希表结构等等n 查找算法的时间效率 查找过程的主要操作是关键字的比较，所以通常以 “平均比较次数 ”来衡量查找算法的时间效率。赵颖 中南大学查找基本概念n 静态查找表 静态查找表在查找过程中查找表本身不发生变化，只对查找表进行如下两种操作：n （ 1）在查找表中查看某个特定的数据元素是否在查找表中n （ 2）检索
4、某个特定元素的各种属性，则称这类查找表为静态查找表。 对静态查找表进行的查找操作称为静态查找。n 动态查找表 动态查找表在查找过程中查找表可能会发生变化n 在查找过程中可以将查找表中不存在的数据元素插入n 或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。 对动态查找表进行的查找操作称为动态查找。赵颖 中南大学目录n 查找基本概念n 静态查找 顺序查找 二分查找赵颖 中南大学顺序查找n 顺序查找的基本思想 顺序查找是一种最简单的查找方法。 其基本思想是：n 将查找表作为一个线性表，可以是顺序表，也可以是链表n 依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较n 若某个
5、记录的关键字值与给定值相等则查找成功，返回该记录的位置n 反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。 下面讲解n 顺序表的顺序查找n 链式表的顺序查找赵颖 中南大学顺序查找n 顺序表的类型定义： #define MAX_NUM 100 /用于定义表的长度 typedef struct elemtype keytype key; anytype otheritem; Se_ListMAX_NUM,Se_Item;n 顺序表的顺序查找算法： int seq_search (Se_List a， keytype k)n /在顺序表中查找关键字值等于 k的记
6、录 ， 若查找成功，返回该记录的位置下标序号，否则返回 0n i=1; /假设在查找表中，数据元素个数为 n（ nMAX_NUM），数组下标为 a1ann while (i=n n if (i=n) retrun i;n else return 0;n 很简单，容易理解还能改进吗？赵颖 中南大学顺序查找n 顺序表的顺序查找算法（改进版）：n int seq_search2 (Se_List a， keytype k) /设置了监视哨的顺序表查找，查找关键字值等于指定值 k的记录 i=n ; /从后往前查找 a0.key=k ; /a0为监视哨，算法中监视哨的作用是为了在 while循环中省去判定防止下标越界的条件 in，从而节省比较的时间。 while ( ai.key != k) i-; return ( i ) ;
