本章重点

线性表的定义和特点

概述：线性表是具有相同特性的数据元素的一个有限序列，数据元素之间的关系是线性关系。
范例：
范例分析

• 其中a1表示线性起点(起始结点)，且无前驱。
• 其中an表示线性终点(终端结点)，且无后继。
• 其他元素就是该线性表的数据元素。
• 并且可以发现除了首尾外每个内部结点都有且只有一个直接前驱和一个直接后继。
• 每一个数据元素都有各自的下标，表示元素在表中的位置。
• n为元素的总个数，即表长。n=0时为空表
• 这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。

案例引入

【案例】一元多项式的运算：实现两个多项式的加减乘运算

这样的多项式怎么在计算机存储呢？
我们可以把这个线性表中每一项的系数拿出来，把他存成一个线性表，然后每一项的指数，就用系数的下标来隐含的表示。
例如：
用数组来表示：int arr[5] = { 10,5,-4,3,2 };，数组的下标刚好是对应的指数。

当我们进行多项式的运算时，如：
我们只需要把两个多项式的每一项依次相加即可：

稀疏多项式
比较特殊的是这种稀疏多项式

如果把指数用系数的下标表示，这才3个元素，却要用几万个下标，占用一大片内存，未免也太浪费了。
所以我们都可以如图这样来表示

所以我们在程序中就可以这么表示它们

int A[4][2] = { {7,0},{3,1},{9,8},{5,17} };
int B[3][2] = { {8,1},{22,7},{-9,8} };

这两个线性表的运算，我们可以这么做

• 创建一个新数组C
• 分别从头遍历比较A和B的每一项
  • 指数相同，对应系数相加，若其和不为0，则在C中增加一个新项。
  • 指数不相同，则将指数较小的项复制到C中。
• 一个多项式遍历完毕时，将另一个剩余项依次复制到C中。

那么数组C应该分配多大的空间合适呢？最坏的情况下需要8个空间，最好的情况下需要0个空间，这种不确定性就容易让我们的程序浪费一些空间。
顺序存储结构存在问题

• 存储空间分配不灵活
• 运算的空间复杂度高

这时我们就可以使用链式存储方式，如下图

总结

• 线性表中数据元素的类型可以为简单类型，也可以是复杂类型。
• 许多实际应用问题所涉的基本操作由很大相似性，不应为每个具体应用单独编写一个程序。
• 从具体应用中抽象出共性的逻辑结构和基本操作(抽象数据类型)，然后实现其存储结构和基本操作。

线性表的类型定义

抽象数据类型线性表的定义如下

基本操作含义

InitList(&L)

• 操作结果：构造一个空的线性表L

DestroyList(&L)

• 初始条件：线性表L已经存在
• 操作结果：销毁线性表L

ClearList(&L)

• 初始条件：线性表L已经存在
• 操作结果：将线性表L重置为空表

ListEmpty(L)

• 初始条件：线性表L已经存在
• 操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE。

ListLength(L)

• 初始条件：线性表L已经存在
• 操作结果：返回线性表L中的数据元素个数

GetElem(L,i,&e)

• 初始条件：线性表L已经存在，且1<=i<=ListLength(L)
• 操作结果：用e返回线性表L中第i个数组元素的值。

LocateElem(L,e,compare())

• 初始条件：线性表L已经存在，compare()是数据元素判定函数。
• 操作结果：返回L中第一个与e满足compare()的数据元素的位序，若这样的数据元素不存在则返回值为0。

PriorElem(L,cur_e,&pre_e)

• 初始条件：线性表L已经存在
• 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无意义。

NextElem(L,cur_e,&next_e)

• 初始条件：线性表L已经存在
• 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无意义。

ListInsert(&L,i,e)

• 初始条件：线性表L已经存在，且1<=i<=ListLength(L)+1
• 操作结果：在L的第i个位置之前插入新的元素e，L的长度+1。

ListDelete(&L,i,&e)

• 初始条件：线性表L已经存在，且1<=i<=ListLength(L)。
• 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1。

ListTraverse(&l,visited())

• 初始条件：线性表L已经存在
• 操作结果：依次对线性表中每个元素调用visited()

操作算法中用到的预定义常量和类型

#define MAXSIZE 20
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef int ElemType;

以上所提及的运算是逻辑结构上定义的运算，只要给出这些运算的功能是”做什么”，至于”如何做”等实现细节，只有待确定了存储结构之后才考虑
后续课程中将学习线性表的存储以及存储结构上个操作的实现。

• 线性表的顺序表示和实现
• 线性表的链式表示和实现

线性表的顺序表示和实现

概述

线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
在C语言中就数组就是线性表很好的体现，元素与元素之间，逻辑上相连，物理上也相连。
线性表的第一个数据元素a1的存储位置，称作线性表的起始位置或基地址。

顺序存储结构

线性表如(1,2,3,4,5)的存储结构：

• 必须是依次存储，地址连续—中间没有空出存储单元
• 线性表顺序存储结构占用一片连续的存储空间，知道某个元素的存储位置就可以计算其他元素的存储位置。

顺序线性表元素存储位置计算

如果每个元素占用8个存储单元，设ai存储位置是2000单元，则ai+1的存储位置必是2008单元。
假设线性表的每个元素需占l个存储空间，，则第i+1个数据元素的存储位置和第i个元素的存储位置之间满足关系：

由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

顺序表的存储表示

可以发现顺序表有以下的特点：

但是C语言的数组只能是常量，不能是变量，所有数组的长度是不可动态定义的，和线性表长度可变的性质发生冲突。

所以我们一般额外定义一个变量来存储顺序表的长度属性：

#define MAXSIZE 70    //线性表存储空间初始分配量
typedef int Status;
typedef int ElemType;
typedef struct {
    ElemType arr[MAXSIZE];    //存储空间起始位置
    int length;        //线性表当前长度
}SqList;

所以我们案例引入中的例子就可以定义这么一个线性表

#defined MAXSIZE 70    //多项式可能达到的最大长度
typedef struct {    //多项式非零项的定义
    float p;        //系数
    int e;            //指数
} Polynomial;
typedef struct {
    Polynomial* elem;    //存储空间的基地址
    int length;            //多项式中当前项的个数
}Sqlist;                //多项式的顺序存储结构类型为Sqlist

顺序表基本操作的实现

顺序表的基本算法

【InitList】线性表L的初始化

Status InitList(SqList* L) {
    L->arr = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    L->length = 0;
    return OK;
}

【DestoryList】销毁线性表

Status DestoryList(SqList* L) {
    if (L->arr) {
        free(L);
    }
    return OK;
}

【ClearList】清空线性表

Status ClearList(SqList* L) {
    int i = 0;
    for (i = 0; i < MAXSIZE; i++) {
        L->arr[i] = 0;
    }
    L->length = 0;
    return OK;
}

【ListLength】求线性表L的长度

Status ListLength(SqList L) {
    return L.length;
}

【ListEmpty】线性表是否为空

Status ListEmpty(SqList L) {
    if (L.length == 0) return TRUE;
    return FALSE;
}

顺序表的查找、插入、删除算法

【GetElem】用e返回线性表L中第i个元素的值

Status GetElem(SqList L, int i, ElemType* e) {
    if (L.length == 0 || i < 1 || i>L.length) {
        return ERROR;
    }
    *e = L.arr[i - 1];
    return OK;
}

【LocateElem】在线性表L中查找指定值e相同的数据元素的位置

Status LocateElem(SqList L, ElemType e) {
    int left = 0;
    int right = L.length - 1;
    while (left < right) {
        if (L.arr[left] == e) {
            return left + 1;
        }
        if (L.arr[right] == e) {
            return right + 1;
        }
        left++;
        right--;
    }
    return ERROR;
}

【ListInsert】在线性表L的第i个位置插入e

Status ListInsert(SqList* L, int i, ElemType e) {
    if (i >= L->length + 1 || i < 1 || L->length == MAXSIZE) {
        return ERROR;
    }
    int j;
    for (j = L->length - 1; j >= i-1; j--) {
        L->arr[j + 1] = L->arr[j];
    }
    L->arr[i-1] = e;
    L->length++;
    return OK;
}

【ListDelete】把线性表L的第i个位置元素删除，并用e返回删除元素

Status ListDelete(SqList* L, int i, ElemType* e) {
    if (L->length == 0 && i > L->length && i < 1) {
        return ERROR;
    }
    int j;
    *e = L->arr[i - 1];
    for (j = i - 1; j < L->length; j++) {
        L->arr[j] = L->arr[j + 1];
    }
    L->length--;
    return OK;
}

顺序表总结

顺序表的特点

1. 利用数据元素的存储位置表示线性表中相邻元素之间的前后关系，即线性表的逻辑结构与存储结构一致。
2. 在访问线性表时，可以快速的计算出任何一个数据元素的存储地址，因此可以粗略的认为，访问每个元素所画的时间相等
3. 这种存取元称为随机存取法。

顺序表的操作算法分析
时间复杂度

• 查找、插入、删除算法的平均时间复杂度为O(n)

空间复杂度

• 顺序表操作算法的空间复杂度为S(n)=O(1)，即没有占用辅助空间。

顺序表的优点和缺点
优点

• 存储密度大(结点本身所占存储量 / 结点结构所占存储量)。
• 可以随机存取表中任一元素。

缺点

• 在插入、删除某一元素时，需要移动大量元素。
• 浪费存储空间。
• 属于静态存储形式，数据元素的个数不能自由扩充。

线性表的链式表示和实现

概述

链式存储结构：结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
线性表的链式表示又称为非顺序映像或链式映像。

示例
有这么一个线性表：(赵、钱、孙、李、周、吴、郑、王)
顺序表存储方式

链表存储方式

如例子中的链表存储方式，就不依靠物理上数据的链接，而是依据存储下一结点地址来表示逻辑上的链接。当最后一个结点后没有元素了，通常就把该结点的指针域设为空(NULL或^)。
例子中数据表示的就是数据域，下一结点地址就是地址域，两者结合构成一个结点。
数据域：存储元素的数值数据
指针域：存储直接后继结点的存储位置
链表：n个结点由指针链组成一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构。

那么我们怎么记录第一个元素的存储地址呢？

• 通常我们会先存储第一个结点的地址，存储第一个结点地址的指针就叫做头指针。
• 单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。

单链表、双链表、循环链表

• 结点只有一个指针域的链表，称为单链表或线性链表。
• 结点有两个指针域的链表，称为双链表(一个指向直接前趋，一个指向直接后继)
• 首位相接的链表称为循环链表(最后一个结点的指针域指向第一个结点地址)

头指针、头结点和首元结点

头指针：是指向链表的第一个结点的指针
头结点：是在链表的首元结点之前附设的一个结点
首元结点：是指链表中存储第一个数据元素a1的结点

链表的存储结构有以下两者形式

• 不带头节点：头指针直接存储第一个数据元素的地址。
• 带头节点：头指针指向头结点，头结点的指针域存储第一个数据元素的地址。

常见问题

讨论1：如何表示空表？

• 无头结点时，头指针为空时表示空表。
• 有头结点时，头结点的指针域为空时表示空表。

讨论2：在链表中设置头结点有什么好处？

1. 便于首元结点的处理

• 首元结点的地址保存在头节点的指针域中，索引在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理。

1. 便于空表和非空表的统一处理

• 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也统一了。

讨论3：头结点的数据域内装的是什么？
头节点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表的长度。

链表(链式存储结构)的特点

1. 结点在存储器中的位置时任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花的时间不等
3. 这种存储元素的方法称为顺序存取法。

链表的存储表示

typedef struct Node {    //声明结点的类型和指向结点的指针类型
    ElemType data;        // 结点的数据域
    struct Node *next;    // 结点的指针域
}Node, *LinkList;        // LinkList为指向结构体Node的指针类型

为什么结点的指针域要是struct Node类型呢，因为下一个结点类型是这个结构体本身，所以指针域的指针也要是这个类型，这种叫做结构体的自引用。
注意：第4行的Node和LinkList两者的含义是不同的，Node是这个结点的类型，和struct Node是同样的。而LinkList为指向结构体Node的指针类型。
定义链表：LinkList L;
定义结点指针p：`Node p; 或 LinkList p;`

示例
需求：存储学生的学号、姓名、成绩的单链表结点类型定义如下：

typedef struct Student {
    char stu_num[8];
    char name[8];
    int score;
    struct Student *next;
}Node, *LinkList;
LinkList L; //需要指向第一个结点地址,L为头节点

但是上面的方法用的不多，为了统一链表的操作，通常这么定义：

typedef struct {
    char stu_num[8];
    char name[8];
    int score;
} ElemType;
typedef struct Node {
    ElemType data;
    struct Student *next;
}Node, *LinkList;

链表的基本操作实现

链表的基础算法

【InitList】单链表L的初始化
【算法步骤】

1. 生成新结点作为头结点，用头指针L指向头节点。
2. 将头结点的指针域置空。

【代码实现】

Status InitList(LinkList L) {
    L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
    return OK;
}

【ListEmpty】判断链表L是否为空

Status ListEmpty(LinkList L) {
    if (L->next) {
        return FALSE;
    }
    return TRUE;
}

【DestroyList】销毁单链表L

Status DestroyList(LinkList *L) {
    LinkList* p;
    while (L) {
        p = L;
        *L = (*L)->next;
        free(*p);
    }
    return OK;
}

【ClearList】清空链表L

Status ClearList(LinkList* L) {
    LinkList p, q;
    p = (*L)->next;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

【ListLength】求单链表L的表长

Status ListLength(LinkList* L) {
    LinkList p = (*L)->next;
    int len = 0;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

阶段总结

类型定义：
typedef struct Node {
    ElemType data;
    struct Node* next;
}Node,LinkList;
变量定义：
LinkList L;    // 定义头指针L
Node *p,*s; // 指向此类型结点的指针
重要操作：
p = L;    // p指向头结点
s = L->next; // s指向首元结点
p = p->next; // p指向下一结点

链表的查找、插入、删除算法

【GetElem】获取单链表L第i个元素，并用e返回。

Status GetElem(LinkList* L, int i, ElemType* e) {
    int count = 1;
    LinkList p = (*L)->next;
    while (p && count < i) {
        p = p->next;
        count++;
    }
    if (!p || count > i) {
        return ERROR;
    }
    *e = p->data;
    return OK;
}

【LocateElem】获取单链表L的参数e在单链表L中的位置，返回结点或位置序号。

// 找到之后返回结点
Node* LocateElem(LinkList* L, ElemType e) {
    LinkList p = (*L)->next;
    for (; p && p->data != e; p = p->next);
    return p;
}
// 找到之后返回位置序号
int LocateElem_i(LinkList* L, ElemType e) {
    LinkList p = (*L)->next;
    int i = 1;
    while (p && p->data != e) {
        i++;
        p = p->next;
    }
    if (p) return i;
    return ERROR;
}

【ListInsert】在单链表L中的第i个位置插入值为e的新结点

Status ListInsert(LinkList* L, int i, ElemType e) {
    LinkList p = *L;
    int count = 0;
    while (p && count < i - 1) {
        p = p->next;
        count++;
    }
    if (!p || count > i - 1) return ERROR;
    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

【ListDelete】删除单链表L的第i个结点，并将第i个结点的数据用e返回

Status ListDelete(LinkList* L, int i, ElemType* e) {
    LinkList p, q;
    p = *L;
    int count = 0;
    while (p && count < i - 1) {
        p = p->next;
        count++;
    }
    if (!(p->next) || count > i - 1) return ERROR;
    q = p->next;
    p->next = q->next;  // 或者 p->next = q->next->next
    *e = q->data;
    free(q);
    return OK;
}

注意：因为算法需要获取ai-1个元素，所有插入算法和删除算法的需求都是从头节点开始的，即p = *L;，而前面的算法只需要获取a结点就好，从首元结点开始查找，即p = (*L)->next;

单链表的查找、插入、删除算法的时间效率分析
查找

• 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。

插入和删除

• 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度是O(1)。
• 但是，如果我们不知道需要插入或删除的位置，由于要从头查找前驱结点，所耗时间复杂度为O(n)。

链表的创建

单链表的建立

• 头插法
• 尾插法

头插法——元素插入在链表头部，也叫做前插法

1. 从一个空表开始，重复读入数据
2. 生成一个新结点，将读入的数据存放到新结点的数据域中
3. 从最后一个结点开始，依次将各结点插入到链表前端

【代码示例】重点是第9-10行的操作

void CreateLink_H(LinkList* L,int length) {
    // 创建头节点，并开辟一段内存
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->data = length;
    (*L)->next = NULL;
    for (int i = 1; i <= length; i++) {
        LinkList p = (LinkList)malloc(sizeof(Node));
        p->data = i;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

算法的时间复杂度是O(n)。

尾插法——元素插入在链表尾部，也叫后插法

1. 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾节点。
2. 初始时，r同L均指向头结点，每读取一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

【代码示例】重点是第10-11行的操作

void CreateLink_R(LinkList* L, int length) {
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->data = length;
    (*L)->next = NULL;
    LinkList r = *L;
    for (int i = 1; i <= length; i++) {
        LinkList p = (LinkList)malloc(sizeof(Node));
        p->data = i;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

算法的时间复杂度是O(n)。

循环链表

循环链表：是一种头尾相接的链表(即表中最后一个结点的指针域指向头结点，整个链表形成一个环)。
优点：从表中任一结点出发均可找到表中其他结点。
注意：
由于循环链表没有NULL指针，故涉及遍历操作时，其终止条件不再像非循环链表那样判断p或p->next是否为空，而是判断它们是否等于头指针。
循环条件：
非循环链表：p != NULL 或 p->next != NULL
循环链表： p != (L) 或 p->next != (L)

由于表的操作常常是在表的首尾位置上进行的，所以在循环链表中，从a**1到an**有两种形式：
头指针表表示单循环链表：

• 找a1的时间复杂度为O(1)
• 找an的时间复杂度为O(n)
• 不方便

尾指针表示单循环链表：

• a1的存储位置是：R->next->next
• an的存储位置是：R
• 这两者的时间复杂度都是O(1)

举例：将两个带尾指针的循环链表合并(将Tb合并在Ta之后)

如图所示，可以发现有4步操作：

1. 定义一个遍历p存放Ta表头结点。如：LinkList p = (*Ta)->next;
2. Tb表头(b1)连接到Ta表(an)表尾，如：(*Ta)->next = (*Tb)->next->next;
3. 释放Tb表头结点，如：free((*Tb)->next);
4. 修改指针，如：(*Tb)->next = p;

【代码示例】

LinkList Connect(LinkList* Ta, LinkList* Tb) {
    if ((*Ta)->next == *Ta && (*Tb)->next == *Tb) {
        return NULL;
    }
    LinkList p = (*Ta)->next;
    (*Ta)->next = (*Tb)->next->next;
    free((*Tb)->next);
    (*Tb)->next = p;
    return (*Tb);
}

算法的时间复杂度是O(1)。

双向链表

之前使用单链表时，可以发现单链表中查找某节点的后继结点的时间复杂度是O(1)，而查找某结点的前驱结点，由于需要遍历链表，所以时间复杂度是O(n)，所以有人就想到了双向链表。
双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针与prior，这样链表中就形成了有两个不同方向的链，故称为双向链表。
双向链表的结构可定义如下：

typedef struct DouNode {
    ElemType data;
    struct DuLNode *prior,*next;
}DouNode,*DouLinkList;

双向循环链表
和单链循环链表类似，双向链表也可以有循环表

• 让头结点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点

双向链表结构的对称性(设指针p指向某一结点)：

在双向链表中有些操作(如ListLength、GetElem等)，因仅涉及一个方向的指针，故它们算法与线性链表相同。但在插入、删除时，则需要修改两个方向上的指针，两者的时间复杂度皆为O(n)。

双向链表的插入和删除操作

【ListInsert】插入算法

【代码】

Status ListInsert(DouLinkList* L, int i, ElemType e) {
    DouLinkList p = (*L)->next;
    int j;
    for (j = 1; j < i; j++) {
        p = p->next;
    }
    if (!p || j > i) return ERROR;
    DouLinkList s = (DouLinkList)malloc(sizeof(DouNode));
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

【ListInsert】删除算法

【代码】

Status ListDelete(DouLinkList* L, int i, ElemType* e) {
    DouLinkList p = (*L)->next;
    int j;
    for (j = 1; j < i; j++) {
        p = p->next;
    }
    if (!p || j > i) return ERROR;
    *e = p->data;
    p->prior->next = p->next;
    if (p->next)
        p->next->prior = p->prior;
    free(p);
    return OK;
}

顺序表和链表的比较

链式存储结构优点：

• 结点空间可以动态申请和释放
• 数据元素的逻辑次序靠结点的指针来表示，插入和删除时不需要移动数据元素。

链式存储结构缺点：

• 存储密度小，每个结点的指针域需要额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大
• 
• 一般的，存储密度越大，存储空间的利用率就越高，显然，顺序表的存储密度为1(100%)，而链表的存储密度小于1。
• 链式存储结构是非随机存取结构，对任一结点的操作都要从头指针依指针链查找到该结点，增加了算法的时间复杂度。

顺序表和链表的区别如图示：

线性表的应用

线性表的合并

问题描述：假设利用两个线性表La和Lb分别表示两个集合A和B，要求一个新的集合A = A U B。
结果示例：La = { 2,4,6,8 }; Lb = { 1,3,5,7,8 } ==> La = { 1,2,3,4,5,6,7,8 }
算法操作

void merge(SqList* La, SqList* Lb) {
    int La_len = ListLength(*La);
    int Lb_len = ListLength(*Lb);
    int i, e;
    for (i = 1; i <= Lb_len; i++) {
        GetElem(*Lb, i, &e);
        if (!LocateElem(*La, e))
            ListInsert(La, ++La_len, e);
    }
}

有序表的合并

问题描述：已知线性表La和Lb中的数据元素按值非递减有序排列，先要求将La和Lb归并为一个新的线性表Lc，且Lc中的元素仍按值非递减有序排列。
结果示例：La={ 1,7,8 } Lb = { 2,4,6,8,10,11 } ==> Lc = { 1,2,4,6,7,8,8,10,11 }
算法步骤

1. 创建一个空表Lc
2. 依次从La或Lb中摘取元素值较小的结点插入到Lc表的最后，直至其中一个表变空为止。
3. 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后

顺序表的实现

void sort_merge(SqList* La, SqList* Lb, SqList* Lc) {
    // 指针pa和pb分别指向两个表的第一个元素
    ElemType* pa = La->data;    
    ElemType* pb = Lb->data;
    // 新表的长度为两表长度之和
    Lc->length = La->length + Lb->length;
    // 分配初始空间
    Lc->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    // pc指向新表的第一个元素
    ElemType* pc = Lc->data;
    // 指针pa_last和pb_last分别指向两表的最后一个元素
    ElemType* pa_last = La->data + La->length - 1;
    ElemType* pb_last = Lb->data + Lb->length - 1;
    while (pa <= pa_last && pb <= pb_last) {    // 两个表都非空
        if (*pa <= *pb)        // 依据大小依次摘取两表中较小值结点
            *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }
    // 判断哪个表还有剩余结点，添加到Lc中
    while (pa <= pa_last) *pc++ = *pb++;
    while (pb <= pb_last) *pc++ = *pb++;
}

时间复杂度为O(ListLength(La) + ListLength(Lb))
空间复杂度为O(ListLength(La) + ListLength(Lb))
链表的实现

void sort_merge(LinkList* La, LinkList* Lb, LinkList* Lc) {
    LinkList pa = (*La)->next;    // pa指向La的首元结点
    LinkList pb = (*Lb)->next;  // pb指向Lb的首元结点
    LinkList pc = *Lc = *La;    // 将La的头节点作为Lc的头结点
    while (pa && pb) {    // 依据大小插入在pc后插入结点，当某一个结点为空结束循环        
        if (pa->data > pb->data) {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        else {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
    }
    pc->next = pa ? pa : pb;    // 插入剩余段
    free(*Lb);     // 释放不需要的空间
}

时间复杂度为O(ListLength(La) + ListLength(Lb))
空间复杂度为O(1)，不需要额外空间

案例分析

前面案例中的多项式就可以用顺序表的方式进行处理：

那么稀疏多项式怎么实现呢？稀疏多项式的计算方法可以看上面稀疏多项式部分，以下为算法步骤：
多项式相加——【算法步骤】

1. 指针p1和p2初始化，分别指向pa和pb的首元结点。
2. p3指向和多项式的当前结点，初值为pa的头节点。
3. 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指向结点对应的指数值(p1->expn与p2->expn)，有下列3种情况：
   • 当p1->expn==p2->expn时，则将两个结点中的系数相加。若和不为0，则修改p1所指结点的系数值，同时删除p2所指结点；若和为0，则删除p1和p2所指结点。
   • 当p1->expnexpn时，则应摘取p1所指结点到”和多项式”链表中去。
   • 当p1->expn>p2->expn时，则应摘取p2所指结点到”和多项式”链表中去。
4. 将非空多项式的剩余段插入到p3所指结点之后。
5. 释放pb的头结点