第九章查找 91静态查找表 q9顺序表的查找 912有序表的查找 u92动态查找表 921二又排序树和二叉平衡树 93哈希( Hashing)表(散列表)
第九章 查找 9.1 静态查找表 9.1.1 顺序表的查找 9.1.2 有序表的查找 9.2 动态查找表 9.2.1 二叉排序树和二叉平衡树 9.3 哈希( Hashing )表(散列表)
第九章查找 查找表( search table) 同一类型数据元素构成的集合。 查找操作 (1)查询某个“特定的”数据元素是否在查找表 中 (2)检索某个“特定的”数据元素的各种属性 (3)在查找表中插入一个数据元素; (4)从查找表中删除某个数据元素 静态查找表:对查找表只作(1)、(2)操作;
第九章 查找 查找表 (search table): • 同一类型数据元素构成的集合。 查找操作: • (1)查询某个“特定的”数据元素是否在查找表 中; • (2)检索某个“特定的”数据元素的各种属性; • (3)在查找表中插入一个数据元素; • (4)从查找表中删除某个数据元素. 静态查找表:对查找表只作(1)、(2)操作； 动态查找表：可以对查找表作(1)-(4)操作
有关查找的“词”的含义 口关键字(KEY 数据元素(或记录)的某个数据项的值,用 以标识一个数据元素(或记录 可以唯一标识一个记录的关键字称为主 关键字( Primary key);香则称为次关键字 (Secondary Key) 可查找 (Searching) 根据给定的值,在查找表中确定一个关键 字等于给定值的记录或数据元素
有关查找的“词”的含义 关键字(KEY): • 数据元素(或记录)的某个数据项的值,用 以标识一个数据元素(或记录). • 可以唯一标识一个记录的关键字称为主 关键字(Primary Key); 否则称为次关键字 (Secondary Key). 查找(Searching) • 根据给定的值,在查找表中确定一个关键 字等于给定值的记录或数据元素
91静态查找表 口可以用顺序表,也可以用线性链表来表示静 态查找表。 顺序表的查找 typedef struct{//静态查找表的顺序存储结杉 ElemType米elem; ele em int length y0 length I SSTable length-1 length
9.1 静态查找表 可以用顺序表，也可以用线性链表来表示静 态查找表。 顺序表的查找 • typedef struct{ //静态查找表的顺序存储结构 • ElemType *elem; • int length; • }SSTable; elem length key 0 1 2 ... length-1 length
顺序查找( Sequential search) int Search Seq sstable ST, KeyType key) ST.elem[0].key=key;//“哨兵” for(i-ST length; !EQ(ST elem[i]. key, key): -i) return 1 性能分析:设P为查找表中第i个记录的概率(取P=1/n); C1为找到第i个记录所需的查找次数。则 ASL=2 P: C:= nP+(n-1)P,+ =[n+(n-1)+...+2+1]*1/n=(n+1)/2 若查找成功与不成功的概率相同,即P:=1/2n, ASL=nP1+(n-1)P2+..+2Pn-1+Pn+(n+1)/2=(n+1)*3/4
顺序查找（Sequential Search） int Search_Seq(SSTable ST, KeyType key){ ST.elem[0].key = key; // “哨兵” for(i=ST.length; !EQ(ST.elem[i].key, key); --i); return i; } 性能分析： 设Pi为查找表中第i个记录的概率(取Pi=1/n)； Ci为找到第i个记录所需的查找次数。则 n ASL = Pi Ci = nP1+(n-1)P2+...+2Pn-1+Pn i=1 = [n+(n-1) +...+2+1]*1/n = (n+1)/2 若查找成功与不成功的概率相同，即Pi=1/2n， ASL = nP1+(n-1)P2+...+2Pn-1+Pn+(n+1)/2 = (n+1)*3/4