18_顺序存储线性表的分析

关键词：顺序存储线性表的效率分析、长度相同的两个SeqList，插入和删除操作的平均耗时是否相同？、对于容器类型的类，可以考虑禁用拷贝构造和赋值操作

1. 效率分析

2. 问题：长度相同的两个SeqList，插入和删除操作的平均耗时是否相同？

SeqList<int> sli; 其大小为5
SeqList<string> slis; 其大小为5

上述两个SeqList，一个类型为int的sli，一个类型为string的slis，由于类型的不同会引起效率的不同。如当对string类型进行插入操作时，其for循环内的赋值操作效率较低，因为将前一个元素赋值给后一个元素时，会调用string类中的strcpy。因此相同长度的SeqList插入和删除操作耗时需要看其类型，而不是仅仅参考大O表示法。

3. 下面的代码正确吗？为什么？

两个delete释放了同一片堆内存空间。

d2 = d1 调用了拷贝构造函数， d1 和 d2这两个对象的内部指针会指向同一片堆内存空间，当调用析构函数时，会释放同一片内存空间。

总结： 对于容器类型的类，可以考虑禁用拷贝构造和赋值操作。

4. 下面代码正确吗？为什么？

对于线性表操作符[]只有在线性表中有元素的时候才能访问，不能作为赋值时候使用。
顺序存储结构线性表提供了数组操作符重载，通过重载能够快捷方便的获取目标位置处的数据元素，在具体的使用形式上类似数组，但是由于本质不同，不能代替数组使用

5. 小结

• 顺序存储线性表的插入和删除操作存在重大效率隐患
• 线性表作为容器类，应该避免拷贝构造和赋值操作
• 顺序存储线性表可能被当作数组误用

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