线性表的定义和基本操作

线性表的特点

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表的基本操作

InitList(&L)：初始化表。
Length(L)：求表长。
LocateElem(L, e)：按值查找。查找给定关键字值的元素
GetElem(L, i)：按位查找。获取第i个位置的元素的值
ListInsert(&L, i, e)：插入操作。在第i个位置上插入指定元素e。
ListDelete(&L, i, &e)：删除操作。删除第i个位置的元素，并用e返回删除元素的值。
PrintList(L)：输出操作。顺序输出所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间

线性表的顺序表示

顺序表的定义

线性表的顺序存储又称顺序表。它的特点是表中元素的逻辑顺序与其物理顺序相同。

静态分配

#define MaxSize 50           // 线性表最大长度
typedef struct {
    ElemType data[MaxSize];  // 顺序表的元素
    int length;              // 顺序表的当前长度
} SqList;

动态分配

#define InitSize 100     // 表长度的初始定义
typedef struct {
    ElemType *data;      // 指示动态分配数组的指针
    int MaxSize;         // 数组的最大容量
    int length;          // 数组的当前长度
} SeqList;

C语言的初始动态分配语句为
1
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
C++的初始动态分配语句为
1
L.data = new ElemType[InitSize];

顺序表的特点

顺序表最主要的特点是随机访问，即通过首地址和元素符号可在时间$O(1)$内找到指定的元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

顺序表上基本操作的实现

插入操作

注意：在顺序表的第i个位置插入新元素e，此时下标应该是i-1

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)
        return false;
    if (L.length >= MaxSize)
        return false;
    int j;
    for (j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

顺序表插入算法的平均时间复杂度为$O(n)$。

删除操作

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length + 1)
        return false;
    e = L.data[i - 1];
    int j;
    for (j = i; j < L.length; j++) {
        L.data[j] = L.data[j + 1];
    }
    L.length--;
    return true;
}

顺序表删除算法的平均时间复杂度为$O(n)$。

按值查找（顺序查找）

注意：若查到下标为i的是结果，则返回的位序是i+1

int LocateElem(SqList L, ElemType e) {
    int i;
    for (i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1;
    }
    return 0;
}

顺序表按值查找算法的平均时间复杂度为$O(n)$。

线性表的链式表示

单链表的定义

每个链表结点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。

| data | next |

data为数据域，存放数据元素；next为指针域，存放其后继节点的地址。

单链表中节点类型的描述如下

typedef struct LNode {
    ElemType data;        // 数据域
    struct LNode *next;   // 指针域
} LNode, *LinkList;

单链表的元素离散地分布在存储空间中，是非随机存取的存储结构。

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但由于单链表附加指针域，也存在浪费存储空间的缺点。

单链表上基本操作的实现

头插法建立单链表

LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
    L->next = NULL; // 初始为空链表
    scanf("%d", &x); // 输入结点的值
    while (x != 9999) { // 终止条件
        s = (LNode*)malloc(sizeof(LNode)); // 创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s; // 将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

注意：

头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。
每个结点插入的时间为$O(1)$，则总时间复杂度为$O(n)$。

尾插法建立单链表

LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L; // r为表尾指针
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode*)malloc(sizeof(LNode)); // 创建新结点
        s->data = x;
        r->next = s;
        r = s; // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL; // 尾结点指针置空
    return L;
}

注意：

生成的结点的次序和输入数据的顺序一致，但需要增加一个尾指针r，使其始终指向当前链表的尾结点。
时间复杂度与头插法相同。

按序号查找结点值

LNode *GetElem(LinkList L, int i) {
    int j = 1;             // 计数器，初始为1
    LNode *p = L->next;    // 头结点的指针赋给p
    if (i == 0)
        return L;          // 若i=0，返回头结点
    if (i < 1)             // 若i<1，说明无效，返回NULL
        return NULL;
    while (p && j < i) {   // 从第1个结点开始找，查找第i个结点
        p = p->next;
        j++;
    }
    return p;              // 返回第i个结点的指针，若i大于表长则返回NULL
}

时间复杂度为$O(n)$。

按值查找表结点

LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p; // 找到后返回该结点指针，否则返回NULL
}

时间复杂度为$O(n)$。

插入结点

bool ListInsert(LinkList &L, int i, ElemType e) {
    LNode *p = GetElem(L, i - 1); // 查找插入位置的前驱结点
    if (p == NULL) {  // 插入失败
        return false;
    }
    else {            // 插入成功
        LNode *s = (LinkList)malloc(sizeof(LNode));  //创建新结点
        s->data = e;
        s->next = p->next;
        p->next = s;  // 将新结点插入表中
        return true;
    }
}

注意

本算法主要的时间开销在于查找第i-1个元素，时间复杂度为$O(n)$。若在给定的结点后面插入新结点，则时间复杂度仅为$O(1)$。

删除结点

bool DeleteInsert(LinkList &L, int i, ElemType &e) {
    LNode *p = GetElem(L, i - 1);
    LNode *q;
    if (p == NULL) {        // 删除失败
        return false;
    }
    else {                  // 删除成功
        q = p->next;
        p->next = q->next;  // 删除结点
        e = q->data;        // e为被删除结点的值
        free(q);            // 释放结点
        return true;
    }
}

时间复杂度与插入算法相同

求表长

int Length(LinkList L) {
    LNode *p = L->next;
    int length = 0;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

注意：
单链表的长度是不包括头结点的

双链表

由于单链表结点中只有一个指向其后继的指针，使得其只能从头结点依次顺序地向后遍历。当要访问某个节点的前驱结点（插入、删除操作时），只能从头开始遍历，导致访问后继节点的时间复杂度为$O(1)$，而访问前驱结点的时间复杂度为$O(n)$。

为了克服单链表的上述缺点，引入双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。

双链表中结点类型的描述如下：

typedef struct DNode {
    ElemType data;              // 数据域
    struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinklist;

注意：
双链表在单链表的结点中增加了一个指向其前驱的prior指针，按值查找和按位查找操作与单链表相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同，关键是要对prior指针做出修改，保证不断链。双链表的插入和删除操作的时间复杂度为$O(1)$。

双链表的插入操作

bool ListInsert(DLinkList &L, int i, ElemType e) {
    DNode *p = GetElem(L, i - 1); // 查找插入位置的前驱结点
    if (p == NULL) {  // 插入失败
        return false;
    }
    else {            // 插入成功
        DNode *s = (DLinkList)malloc(sizeof(DNode));  //创建新结点
        s->data = e;
        s->next = p->next;
        p->next->prior = s; // 相对于单链表的插入操作新增的语句
        s->prior = p;       // 相对于单链表的插入操作新增的语句
        p->next = s;        // 将新结点插入表中
        return true;
    }
}

双链表的删除操作

bool DeleteInsert(DLinkList &L, int i, ElemType &e) {
    DNode *p = GetElem(L, i - 1);
    DNode *q;
    if (p == NULL) {        // 删除失败
        return false;
    }
    else {                  // 删除成功
        q = p->next;
        p->next = q->next;  // 删除结点
        q->next->prior = p; // 相对于单链表的删除操作新增的语句。
        e = q->data;        // e为被删除结点的值
        free(q);            // 释放结点
        return true;
    }
}

循环链表

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头节点，从而整个链表形成一个环。

循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针
循环单链表的插入、删除算法与单链表几乎一样
循环单链表可以从表中的任意一个结点开始遍历整个链表。
有时对单链表的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅设尾指针，从而使操作效率更高。原因是，若设的是头指针，对表尾进行操作需要$O(n)$的时间复杂度，而若设尾指针r，r->next即为头指针，对于表头和表尾进行操作都只需要$O(1)$的时间复杂度。

循环双链表

循环双链表中，头结点的prior指针还要指向表尾结点。

在循环双链表L中，某结点*p为尾结点时，p->next==L；当循环双链表为空表时，其头结点的prior域和next域都等于L。

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的地址空间。

静态链表结构类型的描述如下：

#define MaxSize 50 // 静态链表的最大长度
typedef struct {
    ElemType data; // 存储数据元素
    int next;      // 下一个元素的数组下标
} SLinkList[MaxSize];

静态链表以$next==-1$作为其结束标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但是在一些不支持指针的高级语言（如Basic）中，这是一种非常巧妙的设计方法。

顺序表和链表的比较

存取（读写）方式

顺序表仅需一次访问，而链表则需从表头开始依次访问i次。

逻辑结构与物理结构

顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻；链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。

查找、插入和删除操作

对于按值查找，顺序表无序时，二者时间复杂度均为$O(n)$；顺序表有序时，可采用折半查找，此时时间复杂度为$O(log_{2}n$)。

空间分配

顺序存储

静态存储时，若存储空间预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成内存溢出。
动态存储时，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。

链式存储

结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

王理庚的博客

数据结构--线性表