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

embedded/2025/1/17 22:59:38/

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

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

  • 一、线性表的定义和基本操作
    • 1. 定义
    • 2. 基本操作
  • 二、顺序表
    • 1. 顺序表的定义
    • 2. 顺序表的实现
    • 3. 顺序表的特点
    • 4. 顺序表的插入
    • 5. 顺序表的删除
    • 6. 顺序表的查找
  • 三、单链表
    • 1. 单链表的定义
    • 2. 单链表的实现
    • 3. 单链表的插入
    • 4. 单链表的删除
    • 5. 单链表的查找
    • 6. 单链表的建立
  • 四、双链表
  • 五、循环链表
    • 1. 循环单链表
    • 2. 循环双链表
  • 六、静态链表
    • 1. 静态链表的定义
    • 2. 静态链表的初始化
    • 3. 静态链表的插入
    • 4. 静态链表的删除
  • 七、顺序表和链表对比

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

1. 定义

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

2. 基本操作

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

其他常用操作：

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

二、顺序表

1. 顺序表的定义

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

2. 顺序表的实现

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

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

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

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

3. 顺序表的特点

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

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 处放入 eL.length++;                             // 长度加 1return 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];                      // 将被删除的元素赋值给 efor (int j = i; j < L.length; j++) {    // 将第 i 个位置后的元素前移L.data[j - 1] = L.data[j];}L.length--;                             // 线性表长度减 1return 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 保存数据元素 es->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 中元素覆盖为 datareturn 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 永远指向 NULLL->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 的后继节点 qif (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 e_i ei​ 的存放地址为 addr + 8 * (i + 1)
#define MaxSize 10
typedef struct {ElemType data;int next;
} SLinkList[MaxSize];
  • 应用场景：不支持指针的低级语言；数据元素数量固定不变的场景（如文件分配表 FAT）
  • 优点：增删操作不需要大量移动元素
  • 缺点：不能随机存取，只能从头结点开始一次往后查找；容量固定不变

2. 静态链表的初始化

  1. 把第一个结点的 next 设为 -1
  2. 把其他结点的 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. 静态链表的删除

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

七、顺序表和链表对比

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

http://www.ppmy.cn/embedded/154787.html

相关文章

如何安装cnpm

如何安装cnpm

今天尝试用npm install安装一个项目的依赖&#xff0c;但是无论如何都不能完成&#xff0c;等待时间非常久&#xff0c;所以同事推荐了cnpm&#xff0c;确实非常好用&#xff0c;所以推荐了出来&#xff0c;希望能给大家带来帮助。 cnpm 是中国淘宝团队提供的一个 npm 镜像工具…
阅读更多...
Linux安装docker，安装配置xrdp远程桌面

Linux安装docker，安装配置xrdp远程桌面

Linux安装docker&#xff0c;安装配置xrdp远程桌面。 1、卸载旧版本docker 卸载旧版本docker命令 yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine现在就是没有旧版本的d…
阅读更多...
告别虚拟机！WSL2安装配置教程！！！

告别虚拟机！WSL2安装配置教程！！！

作者&#xff1a;SkyXZ CSDN&#xff1a;SkyXZ&#xff5e;-CSDN博客 博客园&#xff1a;SkyXZ - 博客园 由于Linux的系统的稳定以及在环境管理方面的优越性&#xff0c;同时Linux对于ROS系统的独占&#xff0c;很多时候我们都乐意在Linux系统下开发我们机器人的算法&#xff0…
阅读更多...
使用 Kubernetes 实现负载均衡

使用 Kubernetes 实现负载均衡

使用 Kubernetes 实现负载均衡&#xff0c;可以通过 Kubernetes 的内置服务&#xff08;Service&#xff09;资源&#xff0c;配合负载均衡器&#xff08;如云平台提供的负载均衡器或 Ingress 控制器&#xff09;来完成。以下是详细的步骤和调优案例。 一、Kubernetes 负载均衡…
阅读更多...
FPGA随记——时钟时序一些基本知识

FPGA随记——时钟时序一些基本知识

原文链接&#xff1a;跨时钟域设计-CSDN博客 前言 CDC&#xff08;clock domain crossing&#xff09;检查&#xff08;跨时钟域的检查&#xff09;是对电路设计中同步电路设计的检查。非同步时钟没有固定的相位关系&#xff0c;这样Setup/Hold不满足而产生了亚稳态是无法避免…
阅读更多...
JAVA实现五子棋小游戏(附源码)

JAVA实现五子棋小游戏(附源码)

文章目录 一、设计来源捡金币闯关小游戏讲解1.1 主界面1.2 黑棋胜利界面1.3 白棋胜利界面 二、效果和源码2.1 动态效果2.2 源代码 源码下载更多优质源码分享 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/145161039 JA…
阅读更多...
检测远程服务器是否与本地连接

检测远程服务器是否与本地连接

要检测远程服务器是否与本地连接&#xff0c;包括网址和端口检测&#xff0c;可以按照以下步骤进行&#xff1a; 1. 使用 ping 命令检测网络连通性 命令: ping <服务器地址>示例: ping example.com说明: 该命令用于检测本地与远程服务器之间的网络连通性。如果服务器响…
阅读更多...
Python Wi-Fi密码测试工具

Python Wi-Fi密码测试工具

Python Wi-Fi测试工具 相关资源文件已经打包成EXE文件&#xff0c;可双击直接运行程序&#xff0c;且文章末尾已附上相关源码&#xff0c;以供大家学习交流&#xff0c;博主主页还有更多Python相关程序案例&#xff0c;秉着开源精神的想法&#xff0c;望大家喜欢&#xff0c;点…
阅读更多...
最新文章

Copyright @ 2022~2023