第一种查找方法:也是我们经常用的查找方法。
/*确实伪代码很难看,但是还是要训练。*/
int SequentialSearch(statictable *Tbl,ElementType k) { /*在表Tbl[1]~Tbl[n]中查找关键字为K的数据元素*/ int i; Tbl->Element[0]=k//建立哨兵(后面应该有大用处吧。这里了解一下!) for(i=Tbl->Length;Tbl->Element[i]!=k;i--)
; return i;/*查找成功的话返回单元下标,不成功的话返回0*/ }
这个时间复杂度为O(n)很差劲的时间复杂度。 下面带上二分查找瞪大眼睛。
二分查找(数学上咱们应该就有所了解了)
然后联想了一下,,,发现不现实,为什么呢? 从中间看 怎样知道 要查找的数字在哪一边?
所以要求数字要按序存放。
/*二分查找, 对应的时间复杂度为 O(logN) 很小的时间复杂度 */ int binarysearch(StaticTable *Tbl,ElementType k) { int left,right,mid,NoFound=-1; left=1; // 初始化 左边界 right=Tbl->length //初始化 右边界 while(left<=right) { mid=(left+rigth)/2; //计算中间的坐标。 if(k<Tbl->Element[mid]) right=mid-1; //调整右边界。 else if(k>Tbl->Element[mid]) left=mid+1; //调整左边界 else return mid; //查找成功 返回位置。 } return NotFound; //查找不成功。 /*查找的数字里面没有*/ }
层次化的储存数据类似于上面的二叉树,插入数据删除数据也十分的方便。并且可以高效的找到某一个元素
所以 二叉树 应该在以后的工作中很重要。下面附上图示
原文:http://www.cnblogs.com/A-FM/p/5141191.html