本章主要介绍了下线性表的两种存储结构——顺序存储和链式存储，然后引入了大量的练习题来巩固这两种存储方式。 继续使用[第1章线性表 ](http://blog.csdn.net/u013595419/article/details/50461712)中的配图来比较下顺序表和链表。  ## 一.顺序表和链表的比较 ### 1.1存取方式 > - 顺序表既可以顺序存取，又可以随机存取； > - 链表只能从表头到表尾顺序存取。 ### 1.2逻辑结构与物理结构（存储方式） > - 顺序表中，逻辑上相邻的元素，其对应的物理位置亦相邻； > - 链表中，逻辑上相邻的元素，物理位置不一定相邻，其对应的逻辑关系是通过指针链接形成的。 **注：**此处应注意区别存储方式和存取方式的基本定义。 　　存取方式指的是读取数据的方式，比如随机存取，离散存取等； 　　存储方式指的是数据的物理结构，比如顺序存储，离散存储等。 ### 1.3基本操作 ### 1.3.1查找操作 - 按值查找 > 顺序表无序的情况下，查找时间复杂度为O(n)；若有序，查找时间复杂度为O(1)。 链表无论是否有序，查找时间复杂度均为O(n)。 - 按序号查找 > 顺序表支持随机访问，时间复杂度为O(1)； 链表需要从表头遍历到表尾，时间复杂度为O(n)。 ### 1.3.2插入删除操作 > 顺序表需要移动大量元素，时间复杂度为O(n)； 链表只需修改节点的指针域即可，时间复杂度为O(1)。 ### 1.4空间分配 > 顺序表在创建时就要求分配足够大的存储空间。 　采用静态分配时，若分配空间过大，则会造成浪费严重；若分配过小，则会造成溢出； 　采用动态分配时，扩充需要移动大量元素，造成操作效率低下； 链表仅在需要的时候申请分配，只要内存空间足够便可完成分配。 ## 二．顺序表和链表在现实生活中的选择 根据上述顺序表和链表的比较，使得我们更加熟悉了线性表的基本操作。对此我们变可以根据自身的需求来选择合适的线性表结构。下面说明几点参考标准： ### 2.1基于存储的考虑 对于线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度比较低，显然采用链式存储的线性表存储密度是小于1的。 ### 2.2基于运算的考虑 当我们在线性表操作中涉及到大量的按序号查找值的操作时，采用顺序表无疑是一种不错的选择，顺序表因为可以实现离散存取，时间复杂度仅为O(1)；而链表因为必须使用顺序存取，时间复杂度为O(n)。 如果实际使用中使用到了大量的插入和删除操作时，顺序表平均需要移动表中一半的元素，最坏时间复杂度为O(1)；而链表做相同的操作时，时间复杂度仅为O(1)。明显，我们会选择链表。 ### 2.3基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型；而链表的操作是基于指针的，有些高级语言中并不具备指针。 总之，究竟选择顺序表还是链表还是需要根据自身需要来确定，只有合适的才是最好的。