线性表这一章是考研命题的重中之重，以及各学校自主命题的算法设计题都是基于线性表（顺序表或单链表）的；这类算法实现起来可能比较容易，并且代码量不多，但是却都要求具有最优的性能（时间复杂度和空间复杂度）才能获得满分。因此，应牢固掌握线性表的基础知识与基本操作。
线性表基本知识
线性表是具有相同数据类型的n个数据元素的有限序列，n=0时，线性表是一个空表。
线性表具有逻辑特性：除了第一个元素以外，每个元素有且仅有一个直接前驱；除最后一个元素以外，每个元素有且仅有一个直接后继。
线性表中的数据元素类型相同，即每个元素占有相同大小的存储空间。
线性表中的元素具有逻辑上的顺序性，在序列中各元素排列有先后次序。
线性表的顺序表示即顺序表，用地址连续的存储单元来依次存储线性表中的数据元素。所以顺序表的特点是：表中元素的逻辑顺序与其物理顺序相同。
线性表存储数组时可以是静态分配，也可以是动态分配。
C的初始动态分配语句：
L.data=(Elemtype*)malloc(sizeof(ElementType)*InitSize);
动态分配并不是链式存储，同样还属于顺序存储。其物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。
顺序表的性质与操作
1.性质：①随机访问（查找快，直接定位）②存储密度高，只存储数据元素③插入、删除操作需要大量移动元素(插入平均移动个元素，删除平均移动个元素)
2.顺序表的插入：时间复杂度：O(n);空间复杂度：O(1)
3.顺序表的删除：时间复杂度：O(n);空间复杂度：O(1)
4.顺序表的访问：时间复杂度：O(1)（基于随机访问）
随便练习
线性表的顺序存储结构是一种（）
A.随机存取的存储结构
B.顺序存储的存储结构
C.索引存取的存储结构
D.散列存取的存储结构
对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为（）
A.O(n),O(n)
B.O(n),O(1)
C.O(1),O(n)
D.O(1),O(1)
我是解析1.A.本题容易误选B。顺序表是一种支持随机存取的顺序存储结构，根据起始地址加上元素的序号，可以很方便地访问到任一元素，即随机存取的概念。注意L顺序存取是一种读写方式，不是存储方式，有别于顺序存储。
2.C.顺序表中，第i个元素的物理地址可以通过起始地址和序号直接计算出，即可在O(1)时间内访问。在第i个位置插入一个元素，需要移动n-i+1个元素，时间复杂度为O(n)。
转载于程序员内参
预览时标签不可点收录于话题#个上一篇下一篇