2.1 线性表概述

线性表是具有相同数据类型的n个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构。两者属于不同层面的概念，因此不要混淆。

2.2 线性表的顺序表示和实现

概念

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

顺序表最主要的特点是随机访问（随机存取），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。但插入和删除操作需要移动大量元素。

顺序表的存储密度高，每个结点只存储数据元素。

顺序表插入操作

最好情况：在表尾插入，元素后移语句不执行，时间复杂度为O(1)

最坏情况：在表头插入，元素后移语句将执行n次，时间复杂度为O(n)

平均情况：平均时间复杂度为O(n)

顺序表删除操作

最好情况：删除表尾元素，无需移动元素，时间复杂度为O(1)

最坏情况：删除表头元素，需要移动除第一个元素外的所有元素，时间复杂度为O(n)

平均情况：平均时间复杂度为O(n)

顺序表按值查找（顺序查找）

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)

最坏情况：查找的元素在表尾或不存在时，需要比较n次，时间复杂度为O(n)

平均情况：平均时间复杂度为O(n)

2.3 线性表的链式表示和实现

概念

链式存储线性表时，不需要使用地址连续的存储单元，即它不要求逻辑上相邻的两个元素在物理位置上也相邻，对线性表的插入和删除不需要移动元素，只需要修改指针。

单链表是非随机存储的存储结构，即不能直接找到表中某个特定的结点。

头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。

采用头插法建立单链表

从一个空表开始，生成新结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)。

采用尾插法建立单链表

将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。时间复杂度为O(n)。

按序号查找结点值

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。

时间复杂度为O(n)。

按值查找表结点

从单链表第一个结点出发，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针，否则返回NULL。

时间复杂度为O(n)。

插入结点操作

先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。

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

删除结点操作

先检查删除位置的合法性，然后找到待删除位置的前驱结点，即第i-1个结点，再将其删除。时间复杂度为O(n)。

双链表

双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。双链表中执行按值查找和按位查找的操作和单链表相同，但双链表插入、删除操作的时间复杂度仅为O(1)。

循环单链表

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

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

2.4 静态链表

静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，这里的指针是结点的相对地址（数组下标），又称为游标。

2.5 顺序表和链表的比较

1. 存取方式：顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。

2. 逻辑结构与物理结构：采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻。

3. 查找、插入和删除操作：对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O(n)；而当顺序表有序时，可采用折半查找，时间复杂度为O(logn)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。链表插入、删除较优，只需修改相关结点的指针域即可。

4. 空间分配：链式存储的结点空间只在需要的时候申请分配。

通常较稳定的线性表选择顺序存储，而频繁做插入、删除操作的线性表（即动态性较强）宜选择链式存储。

2.6 线性表的基本运算

顺序表的运算

#include <stdio.h>#include <stdlib.h>#define Size 5typedef struct {    int* head; //定义一个名为head的长度不确定的数组，也叫“动态数组”    int length; //记录当前顺序表的长度    int size; //记录顺序表的存储容量}Table;//创建顺序表void initTable(Table* t) {    //构造一个空的顺序表，动态申请存储空间    t->head = (int*)malloc(Size * sizeof(int));    //如果申请失败，作出提示并直接退出程序    if (!t->head)    {        printf("初始化失败");        exit(0);    }    //空表的长度初始化为0    t->length = 0;    //空表的初始存储空间为Size    t->size = Size;}//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置void insertTable(Table* t, int elem, int add){    int i;    //如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入的位置本身不存在，程序作为提示并自动退出    if (add > t->length + 1 || add < 1) {        printf("插入位置有问题\n");        return;    }    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请    if (t->length == t->size) {        t->head = (int*)realloc(t->head, (t->size + 1) * sizeof(int));        if (!t->head) {            printf("存储分配失败\n");            return;        }        t->size += 1;    }    //插入操作，需要将自插入位置之后的所有元素全部后移一位    for (i = t->length - 1; i >= add - 1; i--) {        t->head[i + 1] = t->head[i];    }    //后移完成后，直接插入元素    t->head[add - 1] = elem;    t->length++;}//删除函数void delTable(Table* t, int add) {    int i;    if (add > t->length || add < 1) {        printf("被删除元素的位置有误\n");        return;    }    //删除操作    for (i = add; i < t->length; i++) {        t->head[i - 1] = t->head[i];    }    t->length--;}//查找函数int selectTable(Table t, int elem) {    int i;    for (i = 0; i < t.length; i++) {        if (t.head[i] == elem) {            return i + 1;        }    }    return -1;}//更改函数void amendTable(Table* t, int elem, int newElem) {    int add = selectTable(*t, elem);    if (add == -1) {        printf("顺序表中没有找到目标元素\n");        return;    }    t->head[add - 1] = newElem;}//输出顺序表中的元素void displayTable(Table t) {    int i;    for (i = 0; i < t.length; i++) {        printf("%d ", t.head[i]);    }    printf("\n");}int main() {    int i,add;    Table t = { NULL,0,0 };    initTable(&t);    for (i = 1; i <= Size; i++) {        t.head[i - 1] = i;        t.length++;    }    printf("原顺序表：\n");    displayTable(t);    printf("删除元素1:\n");    delTable(&t, 1);    displayTable(t);    printf("在第2的位置插入元素5:\n");    insertTable(&t, 5, 2);    displayTable(t);    printf("查找元素3的位置:\n");    add = selectTable(t, 3);    printf("%d\n", add);    printf("将元素3改为6:\n");    amendTable(&t, 3, 6);    displayTable(t);    return 0;}

运行结果如下：

链表的基本运算

#include <stdio.h>#include <stdlib.h>//链表中节点的结构typedef struct link {    int  elem;    struct link* next;}Link;Link* initLink() {    int i;    //1、创建头指针    Link* p = NULL;    //2、创建头结点    Link* temp = (Link*)malloc(sizeof(Link));    temp->elem = 0;    temp->next = NULL;    //头指针指向头结点    p = temp;    //3、每创建一个结点，都令其直接前驱结点的指针指向它    for (i = 1; i < 5; i++) {        //创建一个结点        Link* a = (Link*)malloc(sizeof(Link));        a->elem = i;        a->next = NULL;        //每次 temp 指向的结点就是 a 的直接前驱结点        temp->next = a;        //temp指向下一个结点（也就是a),为下次添加结点做准备        temp = temp->next;    }    return p;}//p为链表，elem为目标元素，add为要插入的位置void insertElem(Link* p, int elem, int add) {    int i;    Link* c = NULL;    Link* temp = p;//创建临时结点temp    //首先找到要插入位置的上一个结点    for (i = 1; i < add; i++) {        temp = temp->next;        if (temp == NULL) {            printf("插入位置无效\n");            return;        }    }    //创建插入结点c    c = (Link*)malloc(sizeof(Link));    c->elem = elem;    //① 将新结点的 next 指针指向插入位置后的结点    c->next = temp->next;    //② 将插入位置前结点的 next 指针指向插入结点；    temp->next = c;}//p为原链表，elem 为要删除的目标元素int delElem(Link* p, int elem) {    Link* del = NULL, *temp = p;    int find = 0;    //1、找到目标元素的直接前驱结点    while (temp->next) {        if (temp->next->elem == elem) {            find = 1;            break;        }        temp = temp->next;    }    if (find == 0) {        return -1;//删除失败    }    else    {        //标记要删除的结点        del = temp->next;        //2、将目标结点从链表上摘除        temp->next = temp->next->next;        //3、释放目标结点        free(del);        return 1;    }}//p为原链表，elem表示被查找元素int selectElem(Link* p, int elem) {    int i = 1;    //带头结点，p 指向首元结点    p = p->next;    while (p) {        if (p->elem == elem) {            return i;        }        p = p->next;        i++;    }    return -1;//返回-1，表示未找到}//p 为有头结点的链表，oldElem 为旧元素，newElem 为新元素int amendElem(Link* p, int oldElem, int newElem) {    p = p->next;    while (p) {        if (p->elem == oldElem) {            p->elem = newElem;            return 1;        }        p = p->next;    }    return -1;}//输出链表中各个结点的元素void display(Link* p) {    p = p->next;    while (p) {        printf("%d ", p->elem);        p = p->next;    }    printf("\n");}//释放链表void Link_free(Link* p) {    Link* fr = NULL;    while (p->next)    {        fr = p->next;        p->next = p->next->next;        free(fr);    }    free(p);}int main() {    Link* p = initLink();    printf("初始化链表为：\n");    display(p);    printf("在第 3 的位置上添加元素 6：\n");    insertElem(p, 6, 3);    display(p);    printf("删除元素4：\n");    delElem(p, 4);    display(p);    printf("查找元素 2：\n");    printf("元素 2 的位置为：%d\n", selectElem(p, 2));    printf("更改元素 1 的值为 6：\n");    amendElem(p, 1, 6);    display(p);    Link_free(p);    return 0;}