数据结构-线性表

线性表（Linear List）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用$n$表示，$n≥0$。当$n=0$时，表示线性表是一个空表。

设序列中第$i$个元素为$a_i (1≤i≤n)$（$i$表示逻辑序号）。线性表$L$可以表示为： $$ L=(a_1,a_2,…a_i,a_{i+1},…,a_n) $$ 其中$a_1$为第一个元素，又称做表头元素，$a_2$为第二个元素，$a_n$为最后一个元素，又称做表尾元素。例如，以下的线性表： $$ (1,4,3,2,8,10) $$

$1$为表头元素，$10$为表尾元素。

线性表$L$中的元素是与位置有关的，即第$i$个元素$a_i$处在第$i-1$个元素$a_{i-1}$的后面和第$i+1$个元素$a_{i+1}$的前面。这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构。

顺序表

顺序表是线性表的顺序存储结构，把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。

假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（即字节数）为sizeof(ElemType)，整个线性表所占用存储空间的大小为:

n * sizeof(ElemType)	// n表示线性表的长度。

类型定义

#define ElemType int               // 元素类型
#define MaxSize 10                 // 最大长度
typedef struct
{
    ElemType data[MaxSize];        // data用于存放元素
    int length;                    // 顺序表的实际元素个数
} SqList;                          // 顺序表结构体类型

由于C/C++中数组的下标从$0$开始，线性表的第$i$个元素$a_i$存放在顺序表的第$i-1$个位置上。

将$a_i$在逻辑序列中的位置称为逻辑序号，而在顺序表中的位置称为物理序号（指数组下标）。

基本运算

初始化顺序表

// 初始化顺序表
void initList(SqList *&L)
{
    L = (SqList *) malloc(sizeof(SqList));
    L->length = 0;
}

初始化非空顺序表

// 根据数组拷贝建立非空顺序表
void createList(SqList *&L, ElemType a[], int n)
{
    if (a == NULL || n < 0 || n >= MaxSize) return;
    L = (SqList *) malloc(sizeof(SqList));
    for (int i = 0; i < n; ++i)
    {
        L->data[i] = a[i];
    }
    L->length = n;
}