上一节讲了在数组中查找元素,但是数组有一个很大的弊端就是它的长度受限,后期可能会超过MAXSIZE,而如果我们使用向量(vector)这个问题就能很好的解决,关于vector我之前在学习经验—c++目录下我写过一篇快速入门的文章,可以先去了解一下vector再来看这篇文章。

而向量就是一个c++里面的一个抽象数据类型,先来解释一下size_t,它是一个存放关于长度的类型,是一个unsigned int类型。

size_t LinearSearch (int k , const vector <int>& v)
{
    for(size_t pos = 0 ; pos < v.size() ; ++pos)
        if(v[pos] == k)
            return pos;
    reuturn v.size();
}

有序则难变

关于查找,我们还可以使用排序之后再使用二分查找,但是如果后期在向量的末尾添加元素,就又需要再排序一次,这样时间复杂度就会变慢。

当然也可以使用插入操作,保证整体的有序性,但是插入操作也是很浪费时间的。

考虑到这里,如果我们使用LinkedList(链表)就可以很好的解决,但是链表不能实现二分查找,因为链表要找到元素的下标是非常麻烦的。

查变难两全

引入二叉查找树:

位于根节点左侧的元素都比根节点要小,位于根节点右侧的元素都比根节点要大,所以我们查找就可以从根节点开始往左或者往右。

ADT视角

1、首先我们需要实现什么样的功能(插入,删除,查找)
2、分析性能(算法)
3、分析优化
4、实现(数组,链表,树)

立志成为一名攻城狮
最后更新于 2019-09-22