23_顺序表和单链表的对比分析

关键词：List中的find函数、顺序表使用条件、单链表使用条件

1. 补充： 线性表中的find操作

在List.h中增加一个查找操作

virtual int find(const T& e) const =0;

参数e： 待查找的数据元素
返回值：
>=0： 数据元素在线性表中第一次出现的位置
-1： 数据元素不存在

在SeqList.h中实现

    int find(const T& e) const
    {
        int ret = -1;

        for(int i=0; i<m_length; i++)
        {
            if( m_array[i] == e)
            {
                ret = i;
                break;
            }
        }

        return ret;
    }

在LinkList.h中实现

    int find(const T& e) const
    {
        int ret = -1;
        int i = 0;
        Node* node = m_header.next;

        while( node )
        {
            if( node->value == e )
            {
                ret = i;
                break;
            }
            else
            {
                node = node->next;
                i++;
            }
        }

        return ret;
    }

当插入的为类类型时，需要将类类型继承自Object类

2. 顺序表和单链表时间复杂度对比分析

3. 问题：顺序表的整体时间复杂度比单链表要低，那么单链表还是有使用价值吗？

效率的深度分析：
1） 实际工程开发中，时间复杂度只是效率的一个参考指标
对于内置基础类型，顺序表和单链表的效率不相上下
对于自定义类类型，顺序表在效率上低于单链表
2） 插入和删除：
顺序表：涉及大量数据对象的复制操作，因此对于自定义的复杂类类型插入和删除操作效率低
单链表：只涉及指针操作，效率与数据对象无关
3） 数据访问：
顺序表：随机访问，可直接定位数据对象
单链表：顺序访问，必须从头访问数据对象，无法直接定位
4） 工程开发中的选择：
顺序表：
数据元素的类型相对简单，不涉及深拷贝；
数据元素相对稳定，访问操作远多于插入和删除操作
单链表：
数据元素的类型相对复杂，复制操作相对耗时的类型
数据元素不稳定，需要经常插入和删除，访问操作较少

4. 小结

• 线性表中元素的查找依赖于相等比较操作符（==）
• 顺序表适用于访问需求量较大的场合（随机访问）
• 单链表适用于数据元素频繁插入删除的场合（顺序访问）
• 当数据类型相对简单时，顺序表和单链表的效率不相上下

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4