数据结构 —— 线性表

数据结构 —— 线性表

线性表（有序表 - Ordered List），它是数学概念应用在计算机科学中一种相当基本的数据结构。简单来说就是 N 个元素的有限序列（N >= 0），例如 26 个英文字表就是一个线性表。线性表数据元素可以是任何一种类型，同一线性表中的元素必须属于同一类型。 1. 有序列表可以空集合（n = 0 时称为空表），或者可以写成（X1, X2, X3, ... ,Xn-1, Xn） 2. 存在唯一的第一个元素 X1 与唯一的最后一个元素 Xn 3. 除了第一个元素 X1 外，每个元素都有一个唯一的前驱； 除了最后一个元素 Xn 外每个元素都有一个唯一的后继 【也就是元素间是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（循环链表除外）】

在数据结构中，按存储的方式分为 静态数据结构 和 动态数据结构 。

静态数据结构（密集表），它是一种将有序列表的数据使用连续分配空间的形式来存储的。其优点是读取与修改数据相当简单，因为列表中任一元素都是固定的。 而缺点则是当在删除或插入数据时需要做大量的数据移动。还有就是静态数据结构是在编译时进行内存分配的，必须分配内存给相关的变量。我们常用的数组类型就是静态数据结构，创建数组时就必须声明做大可能的储存空间，故容易造成内存的浪费。 动态数据结构（链接列表），它是一种将线性表的数据使用不连续的存储空间来存储。其优点是在删除或插入数据时相当方便，不需要移动大量的数据。（与静态数据结构相反） 缺点就是查找与读取数据无法做到像静态数据结构那般简单，必须顺序找到该数据为止。指针就是一种典型的动态数据结构。

基本操作

1、MakeEmpty(L) 这是一个将L变为空表的方法 2、Length（L） 返回表L的长度，即表中元素个数 3、Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n） 4、Prior（L，i） 取i的前驱元素 5、Next（L，i） 取i的后继元素 6、Locate（L，x） 这是一个函数，函数值为元素x在L中的位置 7、Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置 8、Delete（L，p） 从表L中删除位置p处的元素 9、IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false 10、Clear（L）清除所有元素 11、Init（L）同第一个，初始化线性表为空 12、Traverse（L）遍历输出所有元素 13、Find（L，x）查找并返回元素 14、Update（L，x）修改元素 15、Sort（L）对所有元素重新按给定的条件排序 16、strstr(string1,string2)用于字符数组的求string1中出现string2的首地址

比较：

空间上静态数据结构需要一个长度固定的数组，因此会有部分数组元素被浪费。而动态数据结构是动态分布的，因此不会空间浪费。但是需要额外的空间为每个节点存储指针，因此要牺牲一部分空间。 时间上静态数据结构使用连续分配空间的形式来存储，支持随机存取。因此在读取、修改时性能很好。 而动态数据结构采用不连续的存储空间来存储（指针），因此在插入、删除元素时性能要好。