10.2顺序查找表 顺序表的查找 静态查找表的顺序存储结构为 typedef struct ElemType*elem;∥元素存储空间基址,0号单元留空 int length;∥/表长度 } SSTable;/顺序查找表类型 顺序查找( Sequential Search)的算法思想 从表中最后一个元素开始,把给定值与元素的关键字逐个作 相等比较,若有某元素的关键字与给定值相等,则査找成功 ,返回其位置序号;否则返回0
10.2 顺序查找表 一. 顺序表的查找 静态查找表的顺序存储结构为 typedef struct{ ElemType *elem; //元素存储空间基址，0号单元留空 int length; // 表长度 }SSTable; //顺序查找表类型 顺序查找（Sequential Search）的算法思想： 从表中最后一个元素开始，把给定值与元素的关键字逐个作 相等比较，若有某元素的关键字与给定值相等，则查找成功 ，返回其位置序号；否则返回0
10.2顺序查找表 int seqsrch(ssTable ST, KeyType key STele0=key;/没置“哨兵” for(I= STlength;:EQ( STele[i∴key,key);i-);/从后往前找 return i;/找不到时,i为0 M//search 1.查找过程:从n开始,依次与k进行比较,若相等则查找 成功;否则,继续进行,直到与r[0key比较为止 2.算法分析 (1)算法结构应由一个循环构成; (2)循环结束有两种可能: 查找成功 STelemi.key=key 查找不成功
10.2 顺序查找表 1. 查找过程:从n开始,依次与k进行比较, 若相等则查找 成功; 否则, 继续进行,直到与r[0].key比较为止. 2. 算法分析: (1) 算法结构应由一个循环构成; (2) 循环结束有两种可能： • 查找成功 ST.elem[i].key = key • 查找不成功 i = 0 int seqsrch(SSTable ST， KeyType key) { ST.elem[0]=key;//设置“哨兵” for (I=ST.length;!EQ(ST.elem[i].key,key);i--);//从后往前找 return i；//找不到时，i为0 }//seqsrch
10.2顺序查找表 (2)循环结束有两种可能 查找成功s! .elemi]. key=key条件控制 查找不成功i=0计数控制式 这两种可能形成两种不同类型的循环控制: 条件循环 while条件循环体 do循环体 while条件 ·计数循环or(I= STength;!EQST: elemi key, key);-); 常规解决办法: (1)条件循环为主 i=STlength; while(EQ(STelem(i]. key, key))i=i-1 (2)计数循环为主 for (i=sTlength; !EQ(STelemi. key, key); i--;
10.2 顺序查找表 (2) 循环结束有两种可能： • 查找成功 ST.elem[i].key = key 条件控制式 • 查找不成功 i = 0 计数控制式 这两种可能形成两种不同类型的循环控制： • 条件循环 while 条件 循环体 do 循环体 while 条件 • 计数循环 for (I=ST.length;!EQ(ST.elem[i].key,key);i--); 常规解决办法: (1) 条件循环为主 i=ST.length; while (!EQ(ST.elem[i].key,key)) i=i-1; (2) 计数循环为主 for (i=ST.length;!EQ(ST.elem[i].key,key);i--);
10.2顺序查找表 3. STelem0声监视哨作用 4.查找方向可换 int seqsrchI(ssTable sT, KeyType key) STelem stlength+1}=key;/没置“哨兵” for(i=1;!EQ( STelemi. key,key);i+);/从前往后找 if(i!= STength+1) return0;/找不到时,i为 STength+1 return 1; int seqsrch(ssTable st, KeyType key) y//segsrchl &STelema]=key; for (ISTlength; EQ(ST.elemij key, key); i--) return i;)//seqsrch
10.2 顺序查找表 int seqsrch1(SSTable ST， KeyType key) { ST.elem[ST.length+1]=key;//设置“哨兵” for (i=1;!EQ(ST.elem[i].key,key);i++);//从前往后找 if (i!= ST.length+1 ) return 0；//找不到时，i为ST.length+1 return i; }//seqsrch1 4. 查找方向可换 int seqsrch(SSTable ST， KeyType key) { ST.elem[0]=key; for (I=ST.length;!EQ(ST.elem[i].key,key);i--); return i；}//seqsrch 3. ST.elem[0]起监视哨作用
10.2顺序查找表 平均查找长度(ASL 查找过程中,给定值需与关键字比较的次数的期望值 ASL=∑PCi 其中:P;为查找第个记录的概率 C为找到第个记录时,已比较的次数. 顺序查找的平均查找长度 ASLSS-=np1+(n-1)p2+…pn 当p=1/n时,ASLs=∑PAC:=(n+1)/2 i=1
10.2 顺序查找表 平均查找长度(ASL): 查找过程中, 给定值需与关键字比较的次数的期望值. n ASL=∑PiCi i =1 其中: Pi 为查找第i 个记录的概率; Ci 为找到第i 个记录时, 已比较的次数. 顺序查找的平均查找长度ASLss=np1+(n-1)p2+……+pn n 当pi=1/n时, ASLss=∑PiCi =(n+1)/2 i =1