查找算法相关

顺序查找 typedef struct{//查找表的数据结构(顺序表) int *elem;//动态数组基址 int TableLen;//查找表长度 }SSTable; int Seq_Search(SSTable ST,int key){ ST.elem[0]=key; int i; for (i = ST.TableLen;ST.elem[i]!=key ; i--) {}//从后往前查找,最终返回下标i return i;//返回0说明没找到 } 效率分析 对于长度为n的顺序表,如果查找成功 $$ ASL={\frac{1+2+…+n}{n}}=\frac{n+1}{2} $$ 若果查找失败,则 $ASL=n+1$ 总体上,该算法时间复杂度为 $O(n)$ 优化思路 1.如果使得表中的元素有序存放……,可以构造出一棵查找判定树 此时,查找失败时$ASL=\frac{1+2+…+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$ 优点: 容易查找失败时ASL更小 2.如果各元素被查找的概率不同……,可以把概率大的靠前 优点: 容易查找成功时ASL更小 折半查找 折半查找,又称“二分查找”,仅适用于有序的顺序表。 针对升序排列的顺序表,代码实现如下 typedef struct{//查找表的数据结构(顺序表) int *elem;//动态数组基址 int TableLen;//查找表长度 }SSTable; int BinarySearch(SSTable L,int key){ int low=0,high=L.TableLen-1,mid; while (low<=high) { mid=(low+high)/2; if (L....

Jun 6, 2021 · 2 min · Archai