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

2018-01-26 10:30:13来源:https://www.jianshu.com/p/a1d61df323a9作者:jacob2359人点击

分享

关键词:


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






最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台