数组结构 -- 线性表知识

线性表是 n 个元素的 有限集合，其中 n 必须大于等于 0。日常生活中字母表就是一个线性表，阿拉伯数字 0 到 9 也是一个线性表。线性表的关系可以看成是一种有序对的集合，其中 a~i-1~ 称为 a~i~ 的先行元素，a~i~ 是 a~i-1~ 的后继元素。对于简单的线性表可以写成 (a~1~,a~2~,a~3~,...,a~n~) 。线性表定义总结如下：

1. 有序表可以是空集合，或者可以写成 (a~1~,a~2~,a~3~,...,a~n~)；

2. 存在唯一的一个元素 a~1~ 与存在唯一的最后一个元素 a~n~；

3. 除了第一个元素 a~1~ 外，每一个元素都有唯一的先行元素，比如 a~i~ 的先行元素是 a~i-1~ （i $\ne$ 1）；

4. 除了最后一个元素 a~n~ 外，每一个元素都有唯一的后继元素，比如 a~i~ 的后记元素是 a~i+1~ （i $\ne$ n）；

先行表常见的运算操作如下：

1. 计算线性表长度；

2. 取出元素并修正；

3. 插入一个新元素到第 i 项，使得原来的 i,i+1,..,n 项变为了 i+1,1+2,..,n+1 项，其中 1 $\le$ i $\le$ n；

4. 删除第 i 项的元素，使得原来的 i,i+1,..,n 项变为了 i,1+i,..,n-1 项，其中 1 $\le$ i $\le$ n；

5. 从左到右或从右到左读取线性表的元素；

6. 将第 i 项的存入新值，并取代旧值，其中 1 $\le$ i $\le$ n

7. 复制线性表；

8. 合并线性表

线性表在计算机中按照内存存储方式可分为 静态数据结构 和 动态数据结构 。

1. 静态数据结构静态数据结构称为 密集表 ，使用连续分配的内存空间存储有序表中的数据。在编译时会给相关变量分配好内存空间，因此必须事先声明要占用的内存空间大小，所以容易造成内存浪费。优点是设计时简单，并且读取和修改任意位置上的元素所用事件是一样的，但是删除和加入数据时需要移动大量的数据。常见的静态数据结构是数组。

2. 动态数据结构动态数据结构称为 链表 ，使用不连续的内存空间存储线性表。好处是在数据插入和删除的时候不需要大量移动数据，并且因为在程序运行时才分配内存因此不需要事先声明，节省了内存。缺点是设计数据结构的时候很麻烦，并且读取数据时必须按顺序查找元素，直到找到元素为止。常见的动态数据结构是 List。

题目

1. 密集表在什么情况下不适用？

2. 某密集表中有 n 项数据，那么插入一项新数据平均需要移动几项数据？