第一节 线性表的存储实现

一、知识回顾

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

• 记法：L = (a₁, a₂, a₃, …, aᵢ₋₁, aᵢ, aᵢ₊₁, …, aₙ)
• 特点：每个元素有且仅有一个前驱和一个后继（首元素无前驱，尾元素无后继）

二、线性表的顺序存储

1. 基本概念

顺序存储是用一组地址连续的存储单元依次存放线性表中的数据元素。这种存储方式的特点是：逻辑关系上的相邻元素，其物理地址也相邻。顺序表可以随机访问表中任一元素，存储位置可以用一个简单、直观的公式表示。

2. 地址计算公式

设线性表的起始地址（基地址）为Loc(a₁)，每个元素占用k个存储单元，则第i个元素的存储地址为：

例如：基地址为2000，每个元素占8个存储单元，则第7个元素的地址为：

Loc(a₇) = 2000 + (7-1)×8 = 2048

3. 顺序存储结构的C语言描述

#define MAXSIZE 1000  // 线性表存储空间的分配量
typedef struct {
    ElemType data[MAXSIZE];  // 存储数据元素的数组
    int length;              // 当前长度
} SqList;                   // 顺序表类型定义

4. 顺序表的读取操作

顺序表L中的第i个元素存储在数组下标为i-1的存储单元中。这种存储方式的最大特点是支持随机访问，即可以在O(1)时间内访问任意位置的元素。

算法思路：

1. 判断给定的位序i值是否合法（1 ≤ i ≤ L.length）
2. 若不合法，则算法结束
3. 否则，取下标为i-1的数组元素作为顺序表中第i个元素

三、线性表的链式存储

1. 基本概念

链式存储是用一组任意的存储单元存放线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。链式存储中，逻辑关系上的相邻元素，其物理地址不一定相邻。

每个结点包含两个部分：

• 数据域：存储数据元素信息
• 指针域：存储直接后继的存储位置

2. 链式存储结构的C语言描述

typedef struct LNode {
    ElemType data;        // 数据域
    struct LNode *next;   // 指针域
} LNode, *LinkList;      // 单链表类型定义

3. 单链表的读取操作

链式存储的特点是顺序访问，要访问第i个元素，必须从头指针开始，顺着指针域依次向后查找，直到找到第i个结点为止。

算法思路：

1. 声明一个指针p从单链表L的第一个结点开始查找，记录位序的变量j初值为1
2. 循环：指针p顺着单链表中每个结点的next域向后查找，直到p指向第i个结点，或p指向空
3. 如果p非空且j等于i，表明第i个结点存在，则取第i个结点的数据域data的值；否则，第i个结点不存在，取操作失败

---

第二节 顺序表的基本操作

一、顺序表的遍历操作

遍历顺序表就是一次且仅一次地访问顺序表中的每个元素。遍历操作是许多其他操作的基础，如查找、统计、输出等。

1. 算法思路

1. 定义变量j，记录顺序表L中数据元素的位序值，初值为1
2. 循环执行以下操作：判断j是否合法，j小于等于L.length，则访问顺序表L对应数组下标为j-1中的数据元素；否则循环结束，退出循环，算法结束

2. 算法描述

void ListTraverse(SqList L) {
    for (j=1; j<=L.length; j++)  // 从低下标向高下标方向遍历
        visit(L.data[j-1]);       // 访问下标j-1的元素
}

二、顺序表的查找操作

在顺序表L中查找给定值为e的数据元素是否存在，如果存在，返回其在顺序表L中的位序，否则返回0。

1. 算法思路

1. 定义变量j，记录顺序表L中数据元素的位序值，初值为1
2. 循环执行以下操作：判断j是否合法，j小于等于L.length，并且待查元素e与L.data[j-1]的数据元素相等，则查找成功，程序结束，返回位序值j
3. 否则，循环结束，在整个顺序表L中都没有找到与待查元素e相等的数据元素，查找失败，程序返回0，算法结束

2. 算法描述

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

三、算法性能分析

情况	时间复杂度	说明
最好情况	O(1)	要查找的元素在表头位置，与表长无关
最坏情况	O(n)	要查找的元素在表尾或不存在，与表长有关
平均情况	O(n)	平均查找次数为(n+1)/2，与表长有关

---

第三节 顺序表的插入和删除

一、顺序表的插入操作

1. 问题分析

在一个线性表L的第i个位置插入新元素e，表中元素的逻辑结构变化如下：

由 <aᵢ₋₁, aᵢ> 改变为 <aᵢ₋₁, e> 和 <e, aᵢ>

在顺序表中实现插入操作，需要将第i个元素到最后一个元素依次后移一个位置，然后在空出的第i个位置上插入新元素e。

2. 算法思路

1. 检查顺序表L的合法性，i的范围是1到L.length+1
2. 将第i个元素到最后一个元素依次后移一个位置，注意移动的方向性（必须从最后一个元素开始，依次向前移动）
3. 在空出的第i个位置上插入新元素e
4. 表长增1

3. 算法描述

Status ListInsert(SqList &L, int i, ElemType e) {
    if (i>=1 && i<=L.length+1) {
        for (j=L.length; j>=i; j--)  // 元素循环后移
            L.elem[j] = L.elem[j-1];
        L.elem[i-1] = e;  // 插入e
        L.length++;       // 表长增1
        return OK;
    } else return ERROR;
}

4. 关键思考

二、顺序表的删除操作

1. 问题分析

在线性表L中删除第i个元素，元素逻辑结构的变化如下：

由 <aᵢ₋₁, aᵢ> 和 <aᵢ, aᵢ₊₁> 改变为 <aᵢ₋₁, aᵢ₊₁>

在顺序表中实现删除操作，需要将第i+1个元素到最后一个元素依次前移一个位置，覆盖被删除元素的位置。

2. 算法思路

1. 检查顺序表L的合法性，i的范围是1到L.length
2. 取出顺序表L中的第i个元素
3. 从顺序表中第i+1个元素到最后一个元素顺序前移（注意这里与插入不同，需要正向移动）
4. 顺序表L的长度减小1

3. 算法描述

Status ListDelete(SqList &L, int i, ElemType &e) {
    if (i>=1 && i<=L.length) {
        e = L.elem[i-1];  // e保存被删元素
        for (j=i+1; j<=L.length; j++)  // 元素前移
            L.elem[j-2] = L.elem[j-1];
        L.length--;  // 表长减1
        return OK;
    } else return ERROR;
}

三、算法性能分析

操作	平均时间复杂度	最好情况	最坏情况
插入	O(n)	O(1) 表尾插入	O(n) 表头插入
删除	O(n)	O(1) 表尾删除	O(n) 表头删除

• 插入操作平均移动次数：n/2
• 删除操作平均移动次数：(n-1)/2

两种操作的平均时间复杂度都与顺序表的长度有关。

---

第四节 链表的基本操作

一、链表的遍历操作

遍历单链表，就是从单链表中的第一个结点开始，沿着链表结点的next指针域顺次向后访问链表中的每一个结点，且每个结点仅被访问一次。

1. 算法思路

1. 声明指针变量p，初始指向单链表中的第一个结点，即p赋值为L->next
2. 循环判断p指针指向的结点是否存在：若存在则访问p结点的data域，指针p沿next移动指向其直接后继结点
3. 当p移出单链表，则p不存在，退出循环，算法结束

2. 算法描述

void ListTraverse(LinkList L) {
    p = L->next;  // p指向单链表的第一个结点
    while (p) {   // p存在
        visit(p->data);  // 访问p的数据域值
        p = p->next;     // p指针下移
    }
}

二、链表的查找操作

在单链表中查找给定值为e的链表结点是否存在，如果存在值为e的链表结点，返回其在链表中的位序，否则返回0。

1. 算法思路

1. 声明指针变量p，初始指向单链表中的第一个结点，即p赋值为L->next。定义计数器i，记录位序，初值为1
2. 循环执行以下操作：若p存在且p->data不等于e，p指针后移，等于p->next，计数器i加1。否则，退出循环
3. 判断p，若存在则找到值为给定值e的链表结点，程序返回其位序值i，查找成功；否则没有找到值为给定值e的链表结点，程序返回0，查找失败

2. 算法描述

Status ListSearch(LinkList L, ElemType e) {
    p = L->next; i = 1;
    while (p && p->data != e) {
        p = p->next; i++;
    }
    if (p) return i;  // 查找成功
    else return 0;    // 查找失败
}

三、算法性能分析

单链表的遍历算法的时间复杂度为O(n)，与单链表的长度有关。

单链表中查找值为给定值e的查找算法：

• 最好情况：时间复杂度为O(1)，与表长无关
• 最坏情况：时间复杂度为O(n)，与表长有关
• 平均情况：时间复杂度为O(n)，与表长有关

---

第五节 链表的插入和删除

一、链表的插入操作

1. 问题分析

在一个线性表L的第i个位置插入新元素e，表中元素的逻辑结构变化如下：

由 <aᵢ₋₁, aᵢ> 改变为 <aᵢ₋₁, e> 和 <e, aᵢ>

在链表中插入结点只需要修改指针，不需要改变结点的地址。若要在第i个结点之前插入元素，要修改第i-1个结点的next指针。

2. 算法思路

1. 在链表中寻找第i-1个结点p
2. 若未找到，插入失败，算法结束
3. 否则，在p之后插入新元素e：新建结点s，保存数据元素e；在p之后插入s

3. 算法描述

Status ListInsert(LinkList &L, int i, ElemType e) {
    p = L; j = 0;
    while (p && j < i-1) { p = p->next; ++j; }
    if (!p || j > i-1) return ERROR;
    s = new LNode;  // 分配结点空间
    s->data = e;
    s->next = p->next;  // 修改s的next指针
    p->next = s;        // 修改p的next指针
    return OK;
}

4. 关键思考

二、链表的删除操作

1. 问题分析

在线性表L中删除第i个元素，元素逻辑结构的变化如下：

由 <aᵢ₋₁, aᵢ> 和 <aᵢ, aᵢ₊₁> 改变为 <aᵢ₋₁, aᵢ₊₁>

在链表中删除结点只需要修改指针，不需要改变结点的地址。若要删除第i个结点，应修改第i-1个结点的next指针。

2. 算法思路

1. 在链表中寻找第i-1个结点p
2. 若第i个结点不存在，删除失败，算法结束
3. 否则，删除p的后继结点：令q指向p的后继；修改p的next指针；释放q所指的空间

3. 算法描述

Status ListDelete(LinkList &L, int i, ElemType &e) {
    p = L; j = 0;
    while (p->next && j < i-1) { p = p->next; ++j; }
    if (!p->next || j > i-1) return ERROR;
    q = p->next;  // 暂存被删结点地址
    e = q->data;  // 返回被删结点的数据值
    p->next = q->next;  // 修改第i-1个结点的指针
    delete q;  // 释放被删结点的空间
    return OK;
}

三、算法性能分析

操作	寻找位置	插入/删除结点	总体时间复杂度
插入	O(n)	O(1)	O(n)
删除	O(n)	O(1)	O(n)

若已知插入、删除位置，链表中结点的插入、删除操作时间与链表中结点个数无关，时间复杂度为O(1)。当在表头操作时，是最好情况，时间复杂度为O(1)。

链表与顺序表的操作性能比较

存储结构	一般情况	操作表头	操作表尾	操作特点
链表	O(n)	O(1)	O(n)	解链、接链
顺序表	O(n)	O(n)	O(1)	元素搬家

---

第六节 链表的建立

链表是一个动态结构，它不需要预分配空间，因此生成链表的过程是一个个结点逐个插入的过程。根据新结点插入位置的不同，链表的建立方法分为两种：逆序建立和顺序建立。

一、逆序建立单链表

1. 基本思想

新结点插入在头结点的后面，作为重排链表后的第一个结点。这样建立的单链表，其结点顺序与输入顺序相反。

2. 操作步骤

1. 建立一个带头结点的空单链表L
2. 输入数据元素aᵢ，建立新结点p，并把p插入在头结点之后成为第一个结点
3. 重复执行第②步，直到完成单链表的逆序建立

3. 算法描述

void CreateList1(LinkList &L, int n) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;  // 建立带头结点的空链表
    for (i=1; i<=n; i++) {
        p = (LinkList)malloc(sizeof(LNode));
        scanf(&p->data);
        p->next = L->next;  // 新结点插入到头结点后面
        L->next = p;
    }
}

二、顺序建立单链表

1. 基本思想

新结点插入在尾结点的后面，作为重排链表后的最后一个结点。这样建立的单链表，其结点顺序与输入顺序相同。为了提高效率，额外增加一个尾指针r，实时记录尾结点的位置。

2. 操作步骤

1. 建立一个带头结点的空单链表L
2. 输入数据元素aᵢ，建立新结点p，并把p插入在尾结点r之后成为最后一个结点
3. 更新尾指针r指向新的尾结点
4. 重复执行第②③步，直到完成单链表的顺序建立

3. 算法描述

void CreateList2(LinkList &L, int n) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    r = L;  // 尾指针r开始时指向头结点
    for (i=1; i<=n; i++) {
        p = (LinkList)malloc(sizeof(LNode));
        scanf(&p->data);
        p->next = r->next;  // 新结点p的next为NULL
        r->next = p;  // 新结点p插入到尾结点r的后面
        r = p;  // r指向p，作为新的尾结点
    }
}

---

第七节 线性表的应用

一、一元多项式的表示

1. 顺序存储结构直接表示法

使用一维数组存储多项式，数组各分量与多项式各项一一对应。数组的下标对应指数，数组元素值对应系数。

例如：多项式 P(x) = 7 + 3x + 9x⁸ + 5x¹⁷

可以用数组表示为：下标0对应系数7，下标1对应系数3，下标8对应系数9，下标17对应系数5。

这种方法相加时只需两个数组对应分量相加，但对于稀疏多项式会浪费大量空间。

2. 顺序存储结构非零项表示法

使用结构体数组只存储多项式的非零项，每项按指数大小有序存储。每个数组元素包含系数和指数两个数据项。

这种方法节省了存储空间，但加法运算需要比较指数大小，操作相对复杂。

3. 单链表非零项表示法

链表中每个结点存储多项式中的一个非零项，包括系数（coef）、指数（expn）两个数据域以及一个指针域（link）。

typedef struct PNode {
    float coef;       // 系数
    int expn;         // 指数
    struct PNode *link;  // 指针域
} PNode, *Polynomial;

二、一元多项式的相加

1. 顺序存储结构下的相加

从头开始，比较两个多项式当前对应项的指数：相同指数的项系数相加，其余部分进行拷贝。如果指数不同，则将指数较小的项存入结果多项式，并移动对应的指针。

2. 单链表存储结构下的相加

设两个多项式链表的头指针分别为f₁和f₂，相加算法的基本思想是：

• 如果 p1->expn 等于 p2->expn：系数相加，若结果不为0，则作为结果多项式对应项的系数，同时将p1和p2分别指向下一项
• 如果 p1->expn 小于 p2->expn：将p1的当前项存入结果多项式，p1指向下一项
• 如果 p1->expn 大于 p2->expn：将p2的当前项存入结果多项式，p2指向下一项
• 当其中一个链表遍历完后，将另一个链表剩余部分直接链入结果多项式

三、本节小结

线性表在实际应用中非常广泛，一元多项式的表示和运算是其典型应用之一。根据多项式的特点（稀疏程度、运算需求等），可以选择不同的存储结构：

• 顺序存储：适合稠密多项式
• 链式存储：适合稀疏多项式

在实际应用中，需要根据具体问题的特点选择合适的存储结构和算法。