【数据结构】第二章：线性表

🕗 发布于 2025-01-17 02:31 数据结构 笔记算法

本篇笔记课程来源：王道计算机考研数据结构

一、线性表的定义和基本操作

1. 定义

线性表（Linear List）是具有相同数据类型的 n（n≥0）个数据元素的有限序列，其中 n 为表长，当 n=0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为 $L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)$
- $a_i$ 是线性表中的 “第 i 个” 元素线性表中的位序（从 1 开始）
- $a_1$ 是表头元素， $a_n$ 是表尾元素
- 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

2. 基本操作

InitList(&L)：初始化表。构造一个空的线性表 L，分配内存空间。
DestoryList(&L)：销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。
ListInsert(&L,i,e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e。
ListDelete(&L,i,&e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
LocateElem(L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。

其他常用操作：

Length(L)：求表长。返回线性表 L 的长度，即 L 中数据元素的个数。
PrintList(L)：输出操作。按前后顺序输出线性表 L 的所有元素值。
Empty(L)：判空操作。若 L 为空表，则返回 true，否则返回 false。

二、顺序表

1. 顺序表的定义

顺序表（sequence list）：用顺序存储的方式实现线性表。
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2. 顺序表的实现

静态分配：顺序表的表长确定后就无法更改

#define MaxSize 10// 定义最大长度
typedef struct {
ElemType data[MaxSize];// 用静态的“数组”存放数据元素
int length;// 顺序表的当前长度
} SqList;// 顺序表的类型定义（静态分配方式）

动态分配：使用 malloc 和 free 申请或释放内存空间

#define InitSize 10// 顺序表的初始长度
typedef struct {
    ElemType *data;// 指示动态分配数组的指针
    int MaxSize;// 顺序表的最大容量
    int length;// 顺序表的当前长度
}SeqList;// 顺序表的类型定义（动态分配方式）

3. 顺序表的特点

随机访问，即可以在 O(1) 时间内找到第 i 个元素。
存储密度高，每个节点只存储数据元素
拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
插入、删除操作不方便，需要移动大量的元素

4. 顺序表的插入

ListInsert(&L,i,e)：插入操作。在表 L 中的第 i 个位置（位序）上插入指定元素 e。

// 静态分配实现顺序表的代码省略...

bool ListInsert(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) {        // 判断 i 的范围是否有效
        return false;
    }
    if (L.length == MaxSize) {              // 当前存储空间已满，不能插入
        return false;
    }
    for (int j = L.length; j >= i; j--) {   // 将第 i 个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;                      // 在位置 i 处放入 e
    L.length++;                             // 长度加 1
    return true;
}

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

5. 顺序表的删除

ListDelete(&L,i,&e)：删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。

// 静态分配实现顺序表的代码省略...

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {            // 判断 i 的范围是否有效
        return false;
    }
    e = L.data[i - 1];                      // 将被删除的元素赋值给 e
    for (int j = i; j < L.length; j++) {    // 将第 i 个位置后的元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--;                             // 线性表长度减 1
    return true;
}

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

6. 顺序表的查找

GetElem(L,i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。
```
int GetItem(SqList L, int i) {
    return L.data[i - 1];
}
```
时间复杂度：O(1)

LocateElem(L,e)：按值查找操作。在表 L 中查找具有给定关键字值的元素。
== 仅适用于基本数据类型，结构体需要依次对比各个分量来判断是否相等。

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;   // 数组下标为 i 的元素值等于 e，返回其位序 i+1
        }
    }
    return 0;               // 退出循环，说明查找失败
}

时间复杂度：O(n)

三、单链表

1. 单链表的定义

每个结点除了存放数据元素外，还要存储指向下一个结点的指针
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

2. 单链表的实现

定义单链表

struct LNode{           // 定义单链表结点类型
    ElemType data;      // 每个结点存放一个数据元素
    struct LNode *next; // 指针指向下一个结点
};
// typedef struct LNode LNode;// 重命名
// typedef struct LNode *LinkList;// 重命名，强调这是一个单链表

// 新增一个结点，用 LNode * 强调这是一个结点
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));

初始化不带头结点的单链表

#include <stdbool.h>
#include <stdlib.h>

typedef struct LNode{   // 定义单链表结点类型
    int data;           // 每个结点存放一个数据元素
    struct LNode *next; // 指针指向下一个结点
} LNode, *LinkList;

bool InitList(LinkList &L) {
    L = NULL;           // 空表，暂时还没有任何结点（防止脏数据）
    return true;
}

void test() {
    LinkList L;         // 声明一个指向单链表的指针
    InitList(L);
}

初始化带头结点的单链表

// 省略定义单链表的代码...

bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点
    if (L == NULL) {    // 内存不足，分配失败
        return false;
    }
    L->next = NULL;     // 头结点之后暂时还没有结点
    return true;
}

3. 单链表的插入

带头结点按位序插入：平均时间复杂度 O(n)

bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) return false;
    LNode *p;       // 指针 p 指向当前扫描到的结点
    int j = 0;      // 当前 p 指向的是第几个结点
    p = L;          // L 指向头结点，头结点是第 0 个结点（不存数据）
    while (p != NULL && j < i - 1) {    // 循环找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL) return false;        // i 值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;    // 将结点 s 连到 p 之后
    return true;    // 插入成功
}

不带头结点按位序插入

bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) return false;
    if (i == 1) {       // 插入第 1 个结点的操作与其他结点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;          // 头指针指向新结点
        return true;
    }
    LNode *p;           // 指针 p 指向当前扫描到的结点
    int j = 1;          // 当前 p 指向的是第几个结点
    p = L;              // p 指向第一个结点（不是头结点）
    while (p != NULL && j < i - 1) {    // 循环找到第 i-1 个结点
        p = p->next;
        j++;
    }
    if (p == NULL) return false;        // i 值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;        // 插入成功
}

指定结点的后插操作

bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;    // 内存分配失败
    s->data = e;                    // 用结点 s 保存数据元素 e
    s->next = p->next;
    p->next = s;                    // 将结点 s 连到 p 之后
    return true;
}

指定结点的前插操作：偷天换日

bool InsertPriorNode(LNode *node_p, int data) {
    if (node_p == NULL) return false;
    LNode *new_node = (LNode *)malloc(sizeof(LNode));
    if (new_node == NULL) return false; // 内存分配失败
    new_node->next = node_p->next;
    node_p->next = new_node;            // 新结点 new_node 连到 node_p 之后
    new_node->data = node_p->data;      // 将 node_p 中元素复制到 new_node 中
    node_p->data = data;                // node_p 中元素覆盖为 data
    return true;
}

4. 单链表的删除

带头结点按位序删除：平均时间复杂度 O(n)

bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) return false;
    LNode *p;
    int j = 0;
    p = L;
    while (p->next != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;        // i 值不合法
    if (p->next == NULL) return false;  // 第 i-1 个结点之后已无其他结点
    LNode *q = p->next;     // 令 q 指向被删除的结点
    e = q->data;            // 用 e 返回元素的值
    p->next = q->next;      // 将 *q 结点从链中断开
    free(q);                // 释放结点的存储空间
    return true;            // 删除成功
}

删除指定结点：偷天换日
但是如果要删除最后一个结点，只能从链头开始查找

bool DeleteNode(LNode *p) {
    if (p == NULL) return false;
    LNode *q = p->next;     // 另 q 指向 *p 的后继结点
    p->data = p->next->data;// 和后继结点交换数据域
    p->next = q->next;      // 将 *q 结点从链中断开
    free(q);                // 释放后继结点的存储空间
    return true;
}

5. 单链表的查找

按位查找：平均时间复杂度 O(n)

LNode * GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i) {// 循环找到第 i 个结点
        p = p->next;
        j++;
    }
    return p;
}

按值查找：平均时间复杂度 O(n)

LNode *LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    // 从第一个结点开始查找数据域为 e 的结点
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;   // 找到后返回该结点指针，否则返回 NULL
}

6. 单链表的建立

尾插法：平均时间复杂度 O(n)

LinkList List_TaiInsert(LinkList &L) {// 正向建立单链表
    int x;
    L = (LinkList)malloc(sizeof(LNode));// 建立头结点
    LNode *s, *r = L;// r 为表尾指针
    scanf("%d", &x);
    while (x != 9999) {// 输入 9999 表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;                              // r 指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;                         // 表尾结点指针置空
    return L;
}

头插法：用于链表的逆置

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;
}

四、双链表

双链表：在单链表的基础上，再增加一个指向前驱结点的指针域。

双链表的实现

 typedef struct DNode {
     ElemType data;
     struct DNode *prior, *next;
 } DNode, *DLinklist;

双链表的初始化

bool InitDLinkList(DLinklist &L) {
    L = (DNode *)malloc(sizeof(DNode)); // 分配一个头结点
    if (L == NULL) return false;            // 内存不足，分配失败
    L->prior = NULL;    // 头结点的 prior 永远指向 NULL
    L->next = NULL;     // 头结点之后暂时还没有结点
    return true;
}

双链表的后插操作

bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;
    if (p->next != NULL) {      // 如果 p 结点有后继结点
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}

双链表的后删操作

bool DeleteNextDNode(DNode *p) {
    if (p == NULL) return false;
    DNode *q = p->next;             // 找到 p 的后继节点 q
    if (q == NULL) return false;    // p 没有后继结点
    p->next = q->next;
    if (q->next != NULL) {          // q 结点不是最后一个结点
        q->next->prior = p;
    }
    free(q);
    return true;
}

双链表的销毁操作

void DestoryDLinklist(DLinklist &L) {
    while (L->next != NULL) {   // 循环释放各个数据结点
        DeleteNextDNode(L);
    }
    free(L);    // 释放头结点
    L = NULL;   // 头指针指向 NULL
}

双链表的遍历：链表不具备随机存取特性，查找操作只能通过顺序遍历实现，平均时间复杂度为 O(n)

五、循环链表

在单链表和双链表的基础上进行改进，实现循环单链表和循环双链表。

1. 循环单链表

循环单链表：表尾结点的 next 指针指向头结点。
从一个结点触发可以找到其他任何一个结点。

循环单链表初始化

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode)); // 分配一个头结点
    if (L == NULL) return false;    // 内存不足，分配失败
    L->next = L;    // 头结点 next 指向头结点
    return true;
}

循环单链表判断是否为空

// 判断循环单链表是否为空
bool Empty(LinkList L) {
    return L->next == L;
}

循环单链表判断结点是否为尾结点

bool isTail(LinkList L, LNode *p) {
    return p->next == L;
}

2. 循环双链表

循环双链表：表头结点的 prior 指向表尾结点；表尾结点的 next 指向头结点。

循环双链表初始化

typedef struct DNode {
    int data;
    struct DNode *next,*prior;
} DNode, *DLinklist;

bool InitDLinkList(DLinklist &L) {
    L = (DNode *) malloc(sizeof(DLinklist));
    if (L == NULL) return false;
    L->next = L;    // 头结点的 next 指向头结点
    L->prior = L;   // 头结点的 prior 指向头结点
    return true;
}

循环双链表的判空和判尾和循环单链表一样。
循环双链表的后插和后删操作相较于双链表，不需要考虑前驱和后继是否为 NULL 的情况

六、静态链表

1. 静态链表的定义

静态链表：用数组的方式实现的链表。分配一整片连续的内存空间，各个结点集中安置。在结点中存放数据元素和游标（下一个结点的数组下标）。
0 号结点充当 “头结点”，游标为 -1 表示已经到达表尾。
若每个数据元素 4B，每个游标 4B，每个结点共 8B，起始地址为 addr，则 $e_i$ 的存放地址为 addr + 8 * (i + 1)

#define MaxSize 10
typedef struct {
ElemType data;
int next;
} SLinkList[MaxSize];

应用场景：不支持指针的低级语言；数据元素数量固定不变的场景（如文件分配表 FAT）
优点：增删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始一次往后查找；容量固定不变

2. 静态链表的初始化

把第一个结点的 next 设为 -1
把其他结点的 next 设为一个特殊值表示结点空闲

bool InitSLinkList(SLinkList L) {
    L[0].next = -1;
    for (int i = 1; i < MaxSize; i++) {
        L[i].next = -2;
    }
    return true;
}

3. 静态链表的插入

插入位序为 i 的结点
1. 找到一个空的结点，存入数据元素
2. 从头结点出发找到位序为 i-1 的结点
3. 修改新结点的 next
4. 修改 i-1 号结点的 next

4. 静态链表的删除

从头结点出发找到前驱结点
修改前驱结点的游标
被删除结点 next 设为特殊值

七、顺序表和链表对比

	顺序表（顺序存储）	链表（链式存储）
逻辑结构	都属于线性表，都是线性结构
创建	需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源	只需分配一个头结点或头指针，之后方便拓展
销毁	静态分配系统自动回收空间，动态分配需要手动free	依次删除各个结点
插入和删除	需要将后续元素都后移 / 前移	只需修改指针即可
查找	按位查找T(n)=O(1),按值查找T(n)=O(n)	按位查找和按值查找T(n)=O(n)
优点	支持随机存取、存储密度高	离散的小空间分配方便，改变容量方便
缺点	大片连续空间分配不方便，改变容量不方便	不可随机存取，存储密度低

表长难以预估、经常要增加 / 删除元素，选择使用链表。
表长可预估、查询（搜索）操作较多，选择使用顺序表。

原文地址：https://blog.csdn.net/realoser/article/details/145097791

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：入门网络安全工程师要学习哪些内容【2025年寒假最新学习计划】
下一篇：Docker启动达梦 & rman恢复

嵌入式杂谈——什么是DMA？有什么用？
在嵌入式系统和计算机体系结构中，是一种重要的数据传输技术。它允许外设（如UART、SPI、ADC等）直接与内存进行数据交换，而无需CPU的干预。DMA技术可以显著提高系统的效率和性能，尤其是在需要高速
阅读更多2025-01-18
C#+ckeidtor5实现图片上传
C#+ckeidtor5实现图片上传
阅读更多2025-01-18
R语言绘图
将CSV文件同一在一个路径下，用代码合并。
阅读更多2025-01-18
【Python】深入探讨Python中的单例模式：元类与装饰器实现方式分析与代码示例
单例模式（Singleton Pattern）是一种常见的设计模式，它确保一个类只有一个实例，并提供一个全局访问点。在Python中，实现单例模式的方式多种多样，包括基于装饰器、元类和模块级别的单例实
阅读更多2025-01-18
OpenCV入门学习
cv2.imshow('原图',img1)
阅读更多2025-01-18
使用 ChatGPT 生成和改进你的论文
我是虚竹哥，目标是带十万人玩转ChatGPT。
阅读更多2025-01-18
C# OpenCV机器视觉:区域生长算法
然后呢，算法施展它的魔力，让那些颜色、纹理跟掌门相似的像素点，就像是江湖中的各路豪杰，纷纷投奔而来，慢慢汇聚成一个庞大的门派，哦不，是一片完整的区域。他伸了个大大的懒腰，望向窗外逐渐明亮的天空，心中满
阅读更多2025-01-18
Jenkins-git配置说明！
git是流行的分布式控制系统。在jenkins中有许多插件提供了对git的支持。
阅读更多2025-01-18
记一次数据库连接 bug
MySQL连接错误
阅读更多2025-01-18
【VOS源码解析-2024CVPR-Cutie】2、trainner 结构解析
例如，在一些视觉模型中，像素编码器（backbone）用于提取图像特征，其参数量通常较大，且在训练初期需要较慢的学习速度来稳定地学习通用的特征表示；而一些特定的嵌入层（如位置嵌入、类别嵌入等）则用于为
阅读更多2025-01-18

【数据结构】第二章：线性表

【数据结构】第二章：线性表

一、线性表的定义和基本操作

1. 定义

2. 基本操作

二、顺序表

1. 顺序表的定义

2. 顺序表的实现

3. 顺序表的特点

4. 顺序表的插入

5. 顺序表的删除

6. 顺序表的查找

三、单链表

1. 单链表的定义

2. 单链表的实现

3. 单链表的插入

4. 单链表的删除

5. 单链表的查找

6. 单链表的建立

四、双链表

五、循环链表

1. 循环单链表

2. 循环双链表

六、静态链表

1. 静态链表的定义

2. 静态链表的初始化

3. 静态链表的插入

4. 静态链表的删除

七、顺序表和链表对比

相关文章