线性表是一个由N个相同元素组成的有序序列。 一般来说，线性表主要分为顺序表、单链表、循环单链表、双链表和循环双链表。 线性表主要可以解决一系列数据的线性存储，而它的存储方式又分为顺序储存和链式储存，以此可以实现数据的输入输出、插入、查找等操作。

现在，我们把这八种基本操作细分到不同的结构中进行讨论

顺序表是线性表采用顺序储存结构在计算机内存中的储存方式，它由多个储存单元组成，每个储存单元存放一个元素，逻辑上相邻的元素在线性表中表示也是相邻的。所以顺序表又称为线性表的直接映射 我们假定线性表的数据元素的类型为ElemType（这样写主要是为了方便我们之后定义变量）

顺序表的存储是通过结构体来实现的：

我们在顺序表结构体中用一个数组data来存放顺序表的数据，存储方式和一般数组存储方式无异。MaxSize表示这个顺序表可以存放的最大数据量（注意：一般做题的时候MaxSize的值最好开大一点）length表示这个顺序表的实际长度（一般不等于MaxSize）。

在之前的内容中已经指出，线性表的基本运算大概有8类，下面给出基于顺序表实现的线性表功能算法 1. 顺序表的基本算法 初始化顺序表的length为0，并且data数据清空

本算法的时间复杂度为 O ( 1 ) O(1) O(1)

2. 销毁顺序表算法 可以发现，顺序表变量L是一个自动变量，其内存空间是系统自己分配的，程序结束后系统会自动释放空间，所以销毁函数不含任何语句

补充问题：复习一下内存空间的问题

给变量分配内存空间分为静态内存分配和动态内存分配。静态内存分配属于编译时给变量分配的空间，动态内存分配属于在程序运行时给变量分配的空间。静态分配属于栈分配(stack)，动态分配属于堆分配(heap)。

静态内存分配是在程序编译或者运行过程中，按事先规定的大小分配内存空间的分配方式，他的前提的必须事先知道所需内存空间的大小，它的内存分配在栈区和全局变量区。

动态内存分配是按输入信息的大小分配所需要的内存单元，他的特点是按需分配，内存分配在堆区。 int a[10] 属于静态分配 int a[n]; int *a; a = (int *)malloc(sizeof(a))属于动态分配 一般情况下我们使用malloc和free组合进行动态分配和释放空间。

栈存储：

堆存储

3. 求线性表的长度算法 其实就是返回顺序表的length

本算法的时间复杂度为 O ( 1 ) O(1) O(1) 4. 求线性表中的第i个元素算法 为了避免我们的逻辑序号i是一个无效值，我们在函数开头加一个判断语句（注意：很重要！不能忽略）

本算法的时间复杂度为 O ( 1 ) O(1) O(1) 5. 按值查找算法 我们要求在顺序表中查找第一个值为x的函数，找到后返回其序号，否则返回0。

本算法的时间复杂度 O ( n ) O(n) O(n) 6. 插入元素算法 要求实现将新元素x插入到顺序表中编号为i的位置，如果i无效则返回0。

这个算法的操作分两种情况：