线性表的顺序存储——顺序存储的分析

1,对性能和功能两个方面的分析;

2,效率分析:

      

       1,O 表示法;

       2,最耗时的操作是插入和删除操作,因为要移位;

       3,长度相同的两个 SeqList,插入和删除操作的平均耗时是否相同?

              1,可能不相同,因为线性表存储的数据类型可能不同,比如字符串插入比整型插入耗时的多;

       4,分析代码或算法的效率,不能单纯的只看时间复杂度,其只是参考指标,但是并不是绝对的,还要看当前的代码或者算法是不是在效率上真的符合需求的,要具体情况具体分析;

       5,顺序存储链表不适合类类型的元素存储,适合存储基本类型;

      

3,效率分析:

       

  1,插入整型和字符串之间的操作耗时是有很大区别的;

4,静态链表和动态链表之间赋值操作带来的问题:

       1,静态链表之间的赋值(指针指向同一个对象,并被释放两次):           

  2,动态链表之间的赋值(指向同一个对象,并被释放两次):          

      

5,如何避免链表指向同一个对象并被释放两次,分析:

  1,对于容器类型的类,可以考虑禁用拷贝构造函数和赋值操作(第八课已经实现了):

             

              1,生活中两个水杯倒水,生活中没有办法对容器里面的内容进行复制;

              2,面相对象:将生活中的概念平行的搬移到程序设计里面;

  2,拷贝构造是声明的时候直接赋初始值;

    1,DynamicList<int> l(5);

          DynamicList<int> n = l;

  3,赋值操作符是对声明的变量赋值:

    1,DynamicList<int> l(5);

          DynamicList<int> n(5);

          n = l;

6,线性表误操作为数组使用: 

       1,线性表必须先插入元素,才能使用操作符 [] 访问元素,这里可以作为左值使用:

             

  2,顺序存储结构线性表提供了数组操作符重载,通过数组操作符重载能够方便快捷的获取目标位置处的数据元素,再具体的使用形式上类似数组,但由于本质不同,不能代替数组使用;

      

7,小结:

       1,顺序存储线性表的插入和删除操作存在重大效率隐患;

       2,线性表作为容器类,应该避免拷贝构造和拷贝赋值;

       3,顺序存储线性表可能被当成数组误用;

       4,工程开发中可以考虑使用数组类代替原生数组使用;

原文地址:https://www.cnblogs.com/dishengAndziyu/p/10921556.html