数据结构-查找和排序.pdf

微动嵌入式培训-数据结构之查找和排序 主讲人:微动嵌入式培训 Email:wikore@  查 找 • 查找(Search) ： 确定一个已给的数据是否出现在某个数据元 素集合中。 • 查找(Searching)的定义是： 给定一个值K，在含有n个结点的表中找出关 键字等于给定值K的结点。若找到，则查找成 功，返回该结点的信息或该结点在表中的位 置；否则查找失败，返回相关的指示信息。 • 查找的方法 1. 顺序查找 2. 二分查找（折半查找） 3. 分块查找 4. 二叉树查找(BST、B-树、B+树、B*树) 5. 哈希查找 • 按查找表的结构可将查找表分为静态查找 表和动态查找表两类。 • 静态查找静态查找表是仅仅进行查询和检 索操作，不改变查找表中数据元素间的逻 辑关系的查找。静态查找法主要有：顺序 查找，折半查找，分块查找等。 • 动态查找动态查找表是除了进行查询和检 索操作外，还对查找表进行插入、删除操 作的查找，动态地改变查找表中数据元素 之间的逻辑关系。动态查找法主要有：二 叉树查找，哈希查找。 顺序查找 • 基本思想 从表的一端开始，顺序扫描线性表，依次将扫 描到的结点关键宇和给定值K相比较。若当前 扫描到的结点关键字与K相等，则查找成功； 若扫描结束后，仍未找到关键字等于K的结点 ，则查找失败。 • 例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4} 的 线性表查找关键字为6的元素。 顺序查找过程如下： 开始: 3 9 1 5 8 10 6 7 2 4 第1次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第2次比较: 3 9 1 5 8 10 6 7 2 4 i=1 第3次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第4次比较: 3 9 1 5 8 10 6 7 2 4 i=3 第5次比较: 3 9 1 5 8 10 6 7 2 4 i=4 第6次比较: 3 9 1 5 8 10 6 7 2 4 i=5 第7次比较: 3 9 1 5 8 10 6 7 2 4 i=6 查找成功,返回序号6 • 顺序查找顺序结构的类型定义 #define MAXSIZE 100 typedef int key_type; typedef char elem_type[10]; typedef struct{ key_type key; //存放关键字,KeyType为关键字类型 elem_type data;//其他数据, ElemType为其他数据的类型 } line_list; 被查找的数组R定义为 line_list R[MAXSIZE]; • 顺序查找算法实现 int SeqSearch(LineList R[],int n,KeyType k) {