在计算机中，数据并不是孤立的，而是具有一定内在联系的数据集合，这种联系就是数据结构，说明数据如何被组织在一起的。下面我们从最简单的线性表开始讲起。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
线性表——List，零个或多个数据元素的有限序列。
首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
当线性表元素的个数n(n>=0)定义为线性表的长度时，如果n=0，则说明该线性表是个空表。
## 线性表的抽象数据类型(ADT)定义
线性表的抽象数据类型定义如下：
```
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,....an},每个元素的类型均为DataType.其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系.
Operation
InitList(*L):初始化操作，建立一个空的线性表
ListEmpty(L):若线性表为空,返回true,否则返回false.
ClearList(*L):将线性表清空.
GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e
LocateElem(L,e):在线性表L中查找给定值e相等的元素，若查找成功，返回该元素在表中的序号表示成功，否则，返回0表示失败.
ListInsert(*L,i,e):在线性表L中的第i个位置插入元素e.
ListDelete(*L,i,*e):删除线性表L中第i个位置元素,并用e返回其值.
ListLength(L):返回线性表L的元素个数.
EndADT
```
对于不同的应用，线性表的基本操作是不同的，但是上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂的操作，完全可以用这些基本操作的组合来实现。
举个例子，假设La表示集合A，Lb表示集合B，现在要得到一个集合A使得A=AUB:
```c
void unionL(SqList *La,SqList Lb)
{
int La_len,Lb_len,i;
ElemType e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for (i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if (!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}
```
这里，union的操作用到了ListLength,GetElem,LocateElem,ListInsert等基本方法。
#### 线性表的定义
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构的代码如下：
```c
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素,最大值为MAXSIZE */
int length; /* 线性表当前长度 */
}SqList;
```
这里，我们发现描述顺序存储结构需要三个属性：
1. 存储空间的起始位置——数组data，它的存储位置就是存储空间的存储位置。
2. 线性表的最大存储容量——数组长度MAXSIZE
3. 线性表的当前长度length
注意：线性表的长度应该小于等于数组的长度。
下面的程序定义线性表并初始化一些随机数：
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素,最大值为MAXSIZE */
int length; /* 线性表当前长度 */
}SqList;
//顺序表的初始化
SqList Init()
{ //构造一个空的线性表L，时间复杂度O(1)
SqList L; //定义一个顺序表
L.length = 0; //顺序表的长度为0
return L; //返回空顺序表
}
//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
L.data[i] = rand()%100;
L.length++;
}
return L;
}
int main()
{
SqList nmList;
nmList = Init();
nmList = Create(nmList);
int i;
for(i=0; i < nmList.length; i++)
{
printf("%d ", nmList.data[i]);
}
}
```
## 查找
查找线性表是最基本的操作之一，比如根据序号查找元素的值，或者根据值查找该值是否在线性表中，如果在，那么序号是几等等。
我们来看下面一段代码：
```c
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
```
以上代码就是用来获得某一元素的操作。
## 插入
有了以上的基础，我们就能对顺序存储结构的插入与删除做一个讲解了。首先，我们来了解下插入操作。
1. 如果插入的位置不合理，那么就抛出异常。
2. 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量。
3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
4. 将要插入的元素填入位置i处。
5. 表长加1。
```c
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* 顺序线性表已经满 */
return ERROR;
if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i<=L->length) /* 若插入数据位置不在表尾 */
{
for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e; /* 将新元素插入 */
L->length++;
return OK;
}
```
## 删除
然后，我们一起看看删除操作。还是从思路开始说：
1. 如果删除位置不合理，抛出异常
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
4. 表长减1.
```c
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* 线性表为空 */
return ERROR;
if (i<1 || i>L->length) /* 删除位置不正确 */
return ERROR;
*e=L->data[i-1];
if (i<l->length) /* 如果删除不是最后位置 */
{
for(k=i;k<l->length;k++)/* 将删除位置后继元素前移 */
L->data[k-1]=L->data[k];
}
L->length--;
return OK;
}
</l-></l->
```
分析上述插入和删除两段代码和更早的获取元素代码，我们可以发现，线性表的顺序存储结构，在存/读数据时，不管是哪个位置，时间复杂度O(1)，而插入或删除时，时间复杂度都是O(n)。
说完了顺序存储结构，我们可以总结下它的优缺点了，喜欢先听优点还是先听缺点呢？
好吧，从优点开始说。当我们在使用线性表的时候，我们不需要为表中元素之间的逻辑关系而增加额外的存储空间，而且可以快速的存取表中任意位置的元素。接下来谈谈缺点。如我们所见，如果我们要插入或者删除的元素是在第一个位置，那么无疑的，我们需要移动大量的元素来完成这样的操作，而且限于线性表长度必须小于数组长度，如果我们需要插入大量数据，那么很难保证空间是否充足，而如果我们要删除大量数据的时候，无疑又会造成空间的浪费。
下面附上本例的完整代码：
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素,最大值为MAXSIZE */
int length; /* 线性表当前长度 */
}SqList;
//顺序表的初始化
SqList Init()
{ //构造一个空的线性表L，时间复杂度O(1)
SqList L; //定义一个顺序表
L.length = 0; //顺序表的长度为0
return L; //返回空顺序表
}
//顺序表的建立
SqList Create(SqList L)
{
int i;
srand((unsigned)time(NULL));
for(i=0; i < 10; i++)
{
L.data[i] = rand()%100;
L.length++;
}
return L;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
ElemType GetElem(SqList L,int i)
{//
if(i < 1 || i > L.length)
{
printf("查找位置错误！\n");//检查查询位置是否合法
return 0;
}
else
return L.data[i-1];
}
//顺序表的插入
SqList SqListInsert(SqList L, int i, ElemType x)
{ //在顺序表中的第i个位置插入元素x
if(L.length == MAXSIZE)
printf("表已经满了\n");//插入时，必须检查表是否已经满了。否则会出现溢出错误
else if(i < 1 || i > L.length)
printf("插入位置错误\n");//判断插入位置的有效性
int j;
for(j = L.length-1; j >= i - 1; j--)//第i个位置元素逐个后移
L.data[j+1] = L.data[j];
L.data[i-1] = x; //插入元素x
L.length++; //顺序表长度增1
return L;
}
SqList SqListDelete(SqList L,int i)
{//删除顺序表中的第i个位置的元素
if(i < 1 || i > L.length)
printf("删除位置错误\n"); //检查删除位置是否合法
int j;
for(j = i-1; j < L.length; j++)
L.data[j] = L.data[j+1]; //将第i个位置之后的元素前移
L.length--; //顺序表长度-1
return L;
}
int main()
{
SqList nmList;
nmList = Init();
nmList = Create(nmList);
int find;
int found;
int pos;
ElemType value;
char opp;
int i;
printf("顺序表初始化为：");
for(i=0; i < nmList.length; i++)
{
printf("%d ", nmList.data[i]);
}
printf("\n1.查看顺序表 \n2.查找 \n3.插入 \n4.删除 \n0.退出 \n请选择你的操作：\n");
while(opp != '0'){
scanf("%c",&opp);
//printf("\n 1.查找 \n 2.插入 \n 3.排序 \n 0.退出 \n 请选择你的操作：\n");
switch(opp){
case '1':
printf("\n查看顺序表：");
for(i=0; i < nmList.length; i++)
{
printf("%d ", nmList.data[i]);
}
printf("\n");
break;
case '2':
printf("\n进入查找功能，请问需要查找第几个元素：");
scanf("%d",&find);
printf("%d",find);
found = GetElem(nmList, find);
printf("第%d个值为%d ", find, found);
printf("\n");
break;
case '3':
printf("进入插入功能，请输入插入元素位置：");
scanf("%d",&pos);
printf("请输入插入元素的值：");
scanf("%d",&value);
nmList = SqListInsert(nmList,pos,value);
printf("\n插入元素后顺序表为：");
for(i=0; i < nmList.length; i++)
{
printf("%d ", nmList.data[i]);
}
printf("\n");
break;
case '4':
printf("进入删除功能，请输入删除元素位置：");
scanf("%d",&pos);
nmList = SqListDelete(nmList,pos);
printf("\n删除元素后顺序表为：");
for(i=0; i < nmList.length; i++)
{
printf("%d ", nmList.data[i]);
}
printf("\n");
break;
case '0':
exit(0);
}
}
}
```
