C语言中如何实现双链表的数据结构？

本文共计2783个文字，预计阅读时间需要12分钟。

目录+单链表+双链表+双链表的初始化（带头结点）+双链表的插入+双链表的删除+双链表的遍历+循环单链表+循环双链表+循环双链表的初始化+循环双链表的插入+循环双链表的删除

目录

• 单链表 VS 双链表
• 双链表
• 双链表的初始化（带头结点）
• 双链表的插入
• 双链表的删除
• 双链表的遍历
• 循环单链表
• 循环双链表
• 循环双链表的初始化
• 循环双链表的插入
• 循环双链表的删除
• 静态链表
• 什么是静态链表
• 定义静态链表
• 基本操作的实现

单链表 VS 双链表

我们都知道，单链表只有一个指向下一个结点的指针，当我们想要找到前一个结点时就比较麻烦，而双链表拥有两个指针

总的来说：

• 单链表 —— 无法逆向检索，有时候不太方便
• 双链表 —— 可进可退，存储密度更低一丢丢

定义双链表结点类型

typedef struct DNode{ ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist;

双链表

双链表的初始化（带头结点）

定义一个 InitLinklist 函数，参数为双链表的引用，加引用是因为要改变这个双链表

注意：头结点的前驱指针永远指向 NULL

#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct DNode{ ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 }DNode, *DLinklist; //初始化双链表 bool InitLinklist(DLinklist &L) { L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点 if (L == NULL) return false; //内存不足，分配失败 L->prior = NULL; //头结点的 prior 永远指向 NULL L->next = NULL; //头结点之后暂时还没有结点 return true; } //判断双链表是否为空（带头结点） bool Empty(DLinklist L) { if (L->next == NULL) return true; else return false; } void testDLinklist() { //初始化双链表 DLinklist L; InitLinklist(L); }

双链表的插入

后插法

//在p结点之后插入s结点 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; }

学会了后插操作，我们也就学会了按位序插入和前插法，大概思路为找到目标结点的前驱结点，然后对其进行后插操作

双链表的删除

//删除p结点的后继结点 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(p); //释放结点空间 return true; } //销毁双链表 void DestoryList(DLinklist &L) { //循环释放各个数据结点 while (L->next != NULL) { DeleteNextDNode(L); } free(L); //释放头结点 L = NULL; //头指针指向NULL }

双链表的遍历

由于双链表不可随机存取，所以按位查找、按值查找等操作都只能用遍历的方式实现，时间复杂度为 O(n)

//后向遍历 while (p != NULL) { //对结点p做相应处理，比如打印 p = p->next; } //前向遍历 while (p != NULL) { //对结点p做相应处理 p = p->prior; } //前向遍历（跳过头结点） while (p->prior != NULL) { //对结点p做相应处理 p = p->prior; }

循环单链表

我们都知道，单链表的表尾结点的 next 指针是指向 NULL，顾名思义，循环单链表的表尾结点的 next 指针就是指向头结点的

循环单链表的优点：从一个结点出发可以找到其他任何一个结点

typedef int ElemType; typedef struct LNode{ ElemType 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) { if (L->next == L) return true; else return false; } //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L, LNode *p) { if (p->next == L) return true; else return false; }

循环双链表

双链表：

• 表头结点的 prior 指向 NULL
• 表尾结点的 next 指向 NULL

循环双链表

• 表头结点的 prior 指向表尾结点
• 表尾结点的 next 指向头结点

循环双链表的初始化

#include <stdio.h> #include <stdlib.h> typedef int ElemType; 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 = L; //头结点的 prior 指向头结点 L->next = L; //头结点的 next 指向头结点 return true; } //判断循环双链表是否为空 bool Empty(DLinklist L) { if (L->next == L) return true; else return false; } //判断结点p是否为循环双链表的表尾结点 bool isTail(DLinklist L, DNode *p) { if (p->next = L) return true; else return false; } void testDLinklist() { //初始化双链表 DLinklist L; InitDLinklist(L); }

循环双链表的插入

//在p结点之后插入s节点 bool InsertNextDNode(DNode *p, DNode *s) { s->next = p->next; p->next->prior = s; s->prior = p; p->next = s; return true; }

循环双链表的删除

//删除p的后继结点q p->next = q->next; q->next->prior = p; free(q);

静态链表

什么是静态链表

单链表：各个结点在内存中星罗棋布、散落天涯

静态链表：分配一整片连续的内存空间，各个结点集中安置，0 号结点充当 “头结点”，下一个结点的数组下标（也称为游标）充当 “指针”，游标为 -1 时表示已经到达表尾

静态链表是用数组的方式来实现的链表，其优点为 —— 增、删操作不需要大量移动元素；缺点为 —— 不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

定义静态链表

#define MaxSize 10 //静态链表的最大长度 struct Node{ ElemType data; //存储数据元素 int next; //下一个元素的数组下标 };

或者

#define MaxSize 10 //静态链表的最大长度 typedef struct { ElemType data; //存储数据元素 int next; //下一个元素的数组下标 } SLinkList[MaxSize];

SLinkList a 相当于 struct Node a[MaxSize]

基本操作的实现

初始化

把 a[0] 的 next 设置为 -1

把空的结点的 next 设置为 -2

查找

从头结点出发依次往后遍历结点

插入位序为 i 的结点

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

删除某个结点

• 从头结点出发找到前驱结点
• 修改前驱结点的游标
• 被删除结点的 next 设置为 -2

顺序表和链表的比较

从逻辑结构来说，顺序表和链表都属于线性表，都是线性结构

从存储结构来说，顺序表采用顺序存储，而链表采用链式存储

顺序表

优点：支持随机存取，存取密度高

缺点：大片连续空间分配不方便，改变容量不方便

链表：

优点：离散的小空间分配方便，改变容量方便

缺点：不可随机存取，存储密度低

从基本操作来看

创

• 顺序表需要预分配大片连续空间，若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源。如果采取静态分配的方式，则容量不可改变；如果采取动态分配的方式，则容量可改变，但需要移动大量元素，时间代价高
• 链表只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

销

• 对链表来说，你只需扫描整个链表，依次删除（free）各个结点即可
• 对顺序表来说，首先你需要修改 length = 0，如果是采用静态分配的方式，当静态数组的生命周期结束时，系统会自动回收空间；如果是采用动态分配的方式，用 malloc 申请的空间是属于内存中的堆区，在堆区的内存空间不会由系统自动回收，需要我们手动 free

增删

• 对顺序表来说，插入或删除都要讲后续元素全部后移或前移，时间复杂度为 O(n)，时间开销主要来自移动元素
• 对链表来说，插入或删除元素只需要修改指针即可，时间复杂度为 O(n)，时间开销主要来自查找目标元素
• 虽然时间复杂度一样，但是结合实际因素，链表增删的效率要比顺序表高得多

查

• 对顺序表来说，按位查找的时间复杂度为 O(1)；按值查找的时间复杂度为 O(n)，如果表内元素有序，可采用折半查找等方法在 O(log2n) 时间内找到
• 对链表来说，按位查找的时间复杂度为 O(n)；按值查找的时间复杂度也为 O(n)

综上所述

• 表长难以预估、经常要增加或删除元素 —— 链表
• 表长可预估、查询操作较多 —— 顺序表

以上就是C语言数据结构之双链表&循环链表&静态链表详解的详细内容，更多关于C语言链表的资料请关注自由互联其它相关文章！