本篇主要介绍线性表相关理论及实例，包括线性表增删操作，顺序存储结构，本篇中量代码。

线性表

线性表，全名为线性存储结构。是数据结构中很重要的一种，最常用也最简单。

线性表定义

零个或多个数据元素的有限序列

        线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

        注意1：这句话只适用大部分线性表，而不是全部。比如，循环列表（后文会提）逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

        注意2：回顾之前所说，数据元素不一定是最小单位，数据元素可以由若干数据项组成。

        注意3：线性表中元素的个数n定义为线性表长度，当n=0时，称为空表。

线性表抽象数据类型

知道了线性表的定义，那么线性表药局有什么样的操作呢？常见基本操作我们可以先熟悉一下：（大致了解即可，收藏文章，随用随看）

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的首地址

线性表顺序存储结构

线性表的物理结构有两种，这里我们先讲简单的顺序存储。

定义

用一段地址连续的存储单元，依次存储线性表的数据元素。

将具有 一对一 逻辑关系的数据按照次序连续存储到一整块物理空间上的存储结构就是顺序存储结构。

顺序存储方式

来看顺序存储结构代码：

#define MAXSIZE 20          /* 存储空间初始分配量 */
typedef int ElemType;       /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
    ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
    int length;             /* 线性表当前长度 */
}SqList;

所以，数组长度不一定等于线性表长度。线性表长度应该小于等于数组长度。

/* 初始化顺序线性表 */
Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{ 
	if(L.length==0)
		return TRUE;
	else
		return FALSE;
}

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{ 
    L->length=0;
    return OK;
}

/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
	return L.length;
}

顺序存储结构操作

获得元素

/* 初始条件：顺序线性表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;
}

展示元素

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
	int i;
    for(i=0;i<L.length;i++)
            visit(L.data[i]);
    printf("\n");
    return OK;
}

插入操作

我们先一起理一下思路：

1. 线性表长度不能大于数组
2. 插入不合理的异常要可以处理
3. 插入位置后面的元素都要向后移动
4. 插入元素
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;
}

进阶操作

将所有的在线性表Lb中但不在La中的数据元素插入到La中

结合上面的操作大家思考一下，代码如下：

void unionL(SqList *La,SqList Lb)
{
	int La_len,Lb_len,i;
	ElemType e;                        /*声明与La和Lb相同的数据元素e*/
	La_len=ListLength(*La);            /*求线性表的长度 */
	Lb_len=ListLength(Lb);
	for (i=1;i<=Lb_len;i++)
	{
		GetElem(Lb,i,&e);              /*取Lb中第i个数据元素赋给e*/
		if (!LocateElem(*La,e))        /*La中不存在和e相同数据元素*/
			ListInsert(La,++La_len,e); /*插入*/
	}
}