线性表是 n 个元素的 有限集合,其中 n 必须大于等于 0。日常生活中字母表就是一个线性表,阿拉伯数字 0 到 9 也是一个线性表。线性表的关系可以看成是一种有序对的集合,其中 ai-1 称为 ai 的先行元素,ai 是 ai-1 的后继元素。对于简单的线性表可以写成 (a1,a2,a3,…,an) 。线性表定义总结如下:
先行表常见的运算操作如下:
线性表在计算机中按照内存存储方式可分为 静态数据结构 和 动态数据结构 。
- 静态数据结构
静态数据结构称为 密集表 ,使用连续分配的内存空间存储有序表中的数据。在编译时会给相关变量分配好内存空间,因此必须事先声明要占用的内存空间大小,所以容易造成内存浪费。优点是设计时简单,并且读取和修改任意位置上的元素所用事件是一样的,但是删除和加入数据时需要移动大量的数据。常见的静态数据结构是数组。
- 动态数据结构
动态数据结构称为 链表 ,使用不连续的内存空间存储线性表。好处是在数据插入和删除的时候不需要大量移动数据,并且因为在程序运行时才分配内存因此不需要事先声明,节省了内存。缺点是设计数据结构的时候很麻烦,并且读取数据时必须按顺序查找元素,直到找到元素为止。常见的动态数据结构是 List。
题目
- 密集表在什么情况下不适用?
- 某密集表中有 n 项数据,那么插入一项新数据平均需要移动几项数据?