C语言数据结构之双链表&循环链表&静态链表详解

2022-11-13 17:11:12 静态 数据结构 链表

单链表 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语言链表的资料请关注其它相关文章!

相关文章