顺序存储线性表的分析(八)-创新互联

       我们在前面讲解了 SeqList  线性表的相关特性,下来我们来分析下它的效率。如下

沙湾网站制作公司哪家好,找创新互联建站!从网页设计、网站建设、微信开发、APP开发、响应式网站开发等网站项目制作,到程序开发,运营维护。创新互联建站公司2013年成立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联建站
template < typename T >
class SeqList : public List
{
protected:
    T* m_array;        // 顺序存储空间
    int m_length;      // 当前线性表长度
public:
    bool insert(int i, const T& e);    // O(n)
    bool remove(int i);                // O(n)
    bool set(int i, const T& e);       // O(1)
    bool get(int i, T& e) const;       // O(1)
    int length() const;                // O(1)
    void clear();                      // O(1)
    
    // 顺序存储线性表的数组访问方式
    T& operator[] (int i);             // O(1)
    T& operator[] (int i) const;       // O(1)
    
    // 顺序存储空间的容量 
    virtual int capacity() const = 0;
};

       那么问题来了,两个长度相同的 SeqList ,插入和删除操作的平均耗时是否相同呢?插入操作的大O表示法是 O(n + 5),等价于O(n);而删除操作是 O(n-1) ,等价于 O(n)。从时间复杂度上来说,它们是相同的。我们再来想下,插入一个 int 类型的数字和插入一个 string 类型的字符串,两个效率能一样吗?数字肯定是效率非常高的,但是字符串就涉及到字符串的 copy 了,因此效率肯定肯定没有数字的高。

       接下来我们来看看下面代码正确吗?为什么?

StaticList s1;
StaticList s2;

for(int i=0; i

       我们咋一看,感觉这段代码没问题。申请了两个 StaticList 类型的指针数组,然后再在 s1 中插入元素,将 s1  赋值给 s2,最后删除两个指针数组。我们仔细想想,在 s1 赋值给 s2 的时候,s2 同时也指向了 s1 数组的地址,再次进行两个相同地址的释放,难道代码不会出错吗?肯定会啊。我们再来看看下面这段代码正确吗?

void func()
{
    DynamicList d1(5);
    DynamicList d2 = d1;
    
    for(int i=0; i

       我们在定义 d2 的时候,进行了拷贝构造,那么后面的插入操作便会出现问题。会将 d2 的操作覆盖掉 d1 的结果,因此会出现我们不想看到的结果。

       那么对于容器类型的类,我们可以考虑禁用,方法是将它们都声明为 protected 属性就行。那么我们之前的 List 类代码就可以优化为这样

template < typename T >
class List : public Object
{
protected:
    List(const List&);
    List& operator= (const List&);
public:
    List() {}
    virtual bool insert(const T& e) = 0;
    virtual bool insert(int i, const T& e) = 0;
    virtual bool remove(int i) = 0;
    virtual bool set(int i, const T& e) = 0;
    virtual bool get(int i, T& e) const = 0;
    virtual int length() const = 0;
    virtual void clear() = 0;
};

       将拷贝构造和赋值操作声明为 protected,那么就不会出现上面的问题了。我们来看看下面的代码正确吗?

int main()
{
    StaticList list;
    
    for(int i=0; i

       在这份代码中,我们将线性表当成数组来使用了,线性表必须先插入元素,才能使用操作符 [] 访问元素。顺序存储结构线性表提供了数组操作符重载,通过重载能够快捷方便的获取目标位置处的数据元素,再具体的使用方式上类似数组,但是由于本质不同,不能代替数组使用。那么我们就有必要来开发一个数组类了。数组类的结构如下所示

顺序存储线性表的分析(八)

       通过今天的学习,总结如下:1、线性表作为容器类,应该避免拷贝构造和拷贝赋值;2、顺醋存储线性表可能被当成数组误用。


网站题目:顺序存储线性表的分析(八)-创新互联
URL地址:http://scyanting.com/article/dedhee.html