线性表是最常用且最简单的一种数据结构（逻辑结构）。简言之，一个线性表是 n 个数据元素的有限序列。

定义

线性表是一个相当灵活的数据结构，它的长度可根据需要曾长或缩短，即对线性表的数据元素不仅可以访问，还可以进行增加和删除等。

特点

  1. 存在唯一的一个被称为“第一个”的数据元素。
  2. 存在唯一的一个被称为“最后一个”的数据元素。
  3. 除第一个之外，集合中的每个数据元素均只有一个前驱。
  4. 除最后一个之外，集合中的每个元素均只有一个后继。

线性表一般有如下操作：

// 比较两个数据元素，相同返回0,不相同返回-1
typedef int (*Compare_T)(ElemType* pElem1, ElemType* pElem2);
typedef void (*Visit_T)(ElemType* pElem);
/*
初始条件：
操作结果：构建一个空的线性表，成功返回0，失败返回-1
*/
extern int init_list(SqList* pList);

/*
初始条件：线性表pList已存在
操作结果：销毁线性表
*/
extern void destroy_list(SqList* pList);

/*
初始条件：线性表pList已存在
操作结果：将线性表pList置为空表
*/
extern void clear_list(SqList* pList);

/*
初始条件：线性表pList已存在
操作结果：若pList为空表，返回1，否则返回0
*/
extern int is_empty_list(SqList* pList);

/*
初始条件：线性表pList已存在
操作结果：获取表中元素个数
*/
extern int get_list_length(SqList* pList);

/*
初始条件：线性表pList已存在，i>=0且i<get_list_length(pList)
操作结果：成功返回0,且pElem中保存获取到的值；失败返回-1。
*/
extern int get_element(SqList* pList, int index, ElemType* pElem);

/*
初始条件：线性表pList已存在, compare是数据元素判定函数。
操作结果：返回pList中第1个与pElem满足关系compare()的数据元素的索引。若不存在或pElem为NULL，则返回-1。
*/
extern int locate_element(SqList* pList, ElemType* pElem, Compare_T elem_compare);

/*
初始条件：线性表pList已存在。
操作结果：若pCurElem是pList的元素且不是第一个，则用pPriorElem返回其前驱，返回值为0；否则返回-1。
*/
extern int prior_element(SqList* pList, ElemType* pCurElem, ElemType* pPriorElem);

/*
初始条件：线性表pList已存在。
操作结果：若pCurElem是pList的元素且不是最后一个，则用pPriorElem返回其后继，返回值为0；否则返回-1。
*/
extern int next_element(SqList* pList, ElemType* pCurElem, ElemType* pNextElem);

/*
初始条件：线性表pList已存在，i>=0且i<get_list_length(pList)
操作结果：在pList中第i个位置插入新元素pElem，且pList的长度曾1，返回0；插入失败返回-1。
*/
extern int insert_element(SqList* pList, int index, ElemType* pElem);

/*
初始条件：线性表pList已存在，i>=0且i<get_list_length(pList)
操作结果：删除pList中第i个位置，pElem存储删除的元素，且pList的长度减1，返回0；插入失败返回-1。
*/
extern int delete_element(SqList* pList, int index, ElemType* pElem);

/*
初始条件：线性表pList已存在
操作结果：一次对pList中的每个元素调用函数visit()。
*/
extern void traverse_list(SqList* pList,Visit_T visit_elem);

顺序表示和实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

假设线性表的每个数据元素需占用 $l$ 个存储单元。并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第 $i+1$ 个数据元素的存储位置 $LOC(a_{i+1})$ 和第 $i$ 个数据元素的存储位置 $LOC(a_i)$ 之间满足下列关系:

$$ LOC(a_{i+1})=LOC(a_i)+l$$

一般来说，线性表的第 $i$ 个数据元素 $a_i$ 的存储位置为

$$LOC(a_i)=LOC(a_1)+(i-1)*l$$

其中 $LOC(a_1)$ 是线性表的第一个元素的 $a_1$ 的存储位置，通常称做线性表的起始位置或基地址。

线性表的这种机内表示称作线性表的顺序存储结构或顺序映像，通常称这种存储结构的线性表为顺序表。

它的特点是为表中相邻的元素 $a_i$ 和 $a_{i+1}$ 赋以相邻的存储位置 $LOC(a_i)$ 和 $LOC(a_{i+1})$。换句话说，以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。

在这种存储结构中，容易实现线性表的某些操作，如随即存取第 $i$ 个数据元素等，而插入和删除元素则比较麻烦，因为要移动大量元素。

顺序表在 C 语言一般可用动态分配的一维数组来表示，如下所示：

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10
typedef struct ElemType
{
    char str[256];
    int iValue;
} ElemType;

typedef struct SqList
{
    ElemType* pElem;
    int length;    // 当前长度
    int listsize;  // 当前分配的存储容量
} SqList;

int init_list(SqList* pList)
{
    int iRet = -1;
    if (pList == NULL)
        return iRet;
    pList->pElem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
    if (pList->pElem != NULL)
    {
        memset(pList->pElem, 0x00, sizeof(ElemType) * LIST_INIT_SIZE);
        pList->length = 0;
        pList->listsize = LIST_INIT_SIZE;

        iRet = 0;
    }
    return iRet;
}

void destroy_list(SqList* pList)
{
    if (pList != NULL)
    {
        if (pList->pElem != NULL)
        {
            free(pList->pElem);
            pList->pElem = NULL;
        }
        pList->listsize = 0;
        pList->length = 0;
    }
}
...

链式表示和实现

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

为了表示每个数据元素 $a_i$ 与其直接后继数据元素 $a_{i+1}$ 之间的逻辑关系，对数据元素 $a_i$ 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的位置）。这两部分信息组成数据元素 $a_i$ 的存储映像，成为结点。

结点包含两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

$n$ 个结点（ $a_i(1\leq i \leq n)$ 的存储映像）链结成一个链表，即为线性表 $(a_1, a_2,…,a_n)$ 的链式存储结构。又由于此链表的每个结点中只包含了一个指针域，故又称线性链表。

用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。 指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。

单链表可由头指针唯一指定，在 C 语言中可用结构指针来描述：

typedef struct ElemType
{
    char str[256];
    int iValue;
} ElemType;

typedef struct LNode
{
    ElemType* pElem;
    struct LNode* next;
} LNode, Link_List_T;

假设L是Link_List_T类型的变量，则L是单链表的头指针，他指向表中的第一个结点。

有时，会在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度之类的附加信息，头结点的指针域存储指向第一个结点的指针。

在单链表中，任何两个元素的存储位置之间没有固定的联系，取得第 $i$ 个数据元素必须从头指针出发寻找，因此，单链表是非随即存取的存储结构。

循环链表

双向链表

应用

一元多项式