数据结构第九章2009.ppt

第九章 查 找;基本概念和术语 查找表：是由同一类型的数据元素(或记录)构成的集合。 　 　由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。 ;对查找表经常进行的操作:;仅作查询和检索操作的查找表。;是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。;是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 是数据结构中讨论的基本单位 一个数据元素可由若干个数据项组成。; 数据项：;数据元素类型的定义为: typedef struct { keyType key; // 关键字域 … … // 其它属性域 } ElemType ; , TElemType ; typedef int keyType…/* 关键码字段，可以是整型、字符串型、构造类型等*/; 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。; 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。;9.1 静 态 查 找 表;9.1.1 顺序表的查找;ST.elem;int location( SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { k = 1; p = L.elem; while ( k=L.length !(*compare)(*p++,e))) k++; if ( k= L.length) return k; else return 0; } //location 从第一元素开始，逐一查找;ST.elem;int Search_Seq(SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值为 // 该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq; 定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 　 ， Ci为找到该记录时，曾和给定 值比较过的关键字的个数。; 在等概率查找的情况下， 顺序表查找的平均查找长度为： ; 若查找概率无法事先测定，则查找过程采取的改进办法之一：在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。; 查找不成功时，关键码的比较次数总是n+1次。 则等概率的情况下： ASL=3(n+1)/4 特点： 1、顺序查找缺点是当n很大时，平均查找长度较大，效率低； 2、优点是对表中数据元素的存储没有要求。 3、对于线性链表，只能进行顺序查找。 ;9.1.2 有序表的查找;ST.elem;int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid +