软件技术基础查找和排序.pptx

1.4 查找和排序 1.4.1 查找（检索） 根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若存在这样一个记录，则查找是成功的，否则是失败的。 查找对象：查找表 查找依据：关键字 查找表 查找表： 同一类待查数据元素（或记录） 构成的集合 关键字 ▲关键字（key)： 可标识（识别）一个数据元素（或记录）的数据项值 主关键字(primary key) ：标识唯一记录 次关键字(secondary key)：标识若干记录 查找结果：成功/不成功 查找效率：依赖数据的组织和存储结构 查找效率标准 ： 平均查找长度ASL(Average Searching Length) 一.简单查找方法 1.顺序查找 顺序/链式存储结构 elemtype S[MAXNUM] [算法] int seq_search(elemtype S[ ], keytype k, int n) { int mark=-1; int i; for(i=0;in;i++) { if (S[i].key==k) { mark=i; break;} } if(mark==-1) printf(“Searching failed”); else printf(“Searching success”); return(mark); } 查找效率 顺序查找效率： 平均查找长度ASL(Average Searching Length) 2.二分查找（折半查找） 查找过程：先确定范围（区间），逐步缩小范围，直到找到/找不到 例：关键字为5,13,19,21,37,56,64,75,80,88,92 查21 [算法27] int bin_search(elemtype S[ ],keytype k, int n) { int low,high,mid; low=0; hig=n-1; while(low=high) { mid=(low+high/2); if(S[mid].key==k) { printf(“Searhing success”); return(mid); } else if(S[mid].keyk) high=mid-1; else low=mid+1; } printf(“searching failed”); return(-1); } 查找效率： 折半查找的判定树是深度为h的满二叉树 (n50) 注意：只对有序表且顺序存储结构 3.分块查找 建立（最大）索引关键字表 步骤：1.二分查找，确定哪一块 2.块内顺序查找 查找方法比较 二.树表查找 弥补二分法不足（顺序存储结构） 采用二叉排序树 例：关键字序列45，12，53，100，61，90，3，24，如果查100 typedef struct node_data { keytype key; … } elemtype; *LC data *RC bs_node bs_node bs_node elemtype typedef struct bs_node { datatype data; struct bs_node *LC; struct bs_node *RC: } bsnode; bsnode *bs_search(bsnode *t, keytype k) { bsnode *S; if(t==NULL) { pintf(“empty tree”); return(NULL); } S=t; if((S--data).key==k) { printf(“Searching success”); return(S); } else if((S--data).keyk) return(bs_search(S--LC,k)); else return(bs_search(S--RC,k)); } 查找效率： 与