资讯

展开

数据结构:链表(双向链表)

作者:快盘下载 人气:

            双向链表的定义

1.双向链表的节点构造在C语言中的创建;

2.双向带头循环链表的创建

3.双向带头循环链表的头插尾插

4.双向带头链表的头删尾删及删除pos位节点


双向链表的定义

上篇文章介绍了单向链表;在这期文章中将学习了解双向链表;回顾一下单向链表的特性以及介绍双向链表的优势

单向链表特点;

可以轻松的浏览下一个节点数据;但缺点是想返回上一个数据节点相对麻烦只能从头开始遍历到尾;或者从尾遍历到头。

双向链表特点;

每次在插入或者删除某个节点时候需要同时处理四个节点的引用;而不是像单链表只需要处理两个节点引用。比较于单链表;因为多出两个节点引用所以占用空间相对于会多一些;但也基本可以忽略不计最大的优势是既可以从头遍历到尾;也可以从尾遍历到头

双向链表定义;

        双向链表一般被简称为双链表;是归属于链表中的一种线性链表;在双向链表中它的每个数据段中都拥有两个指针;分别指向这个数据段的前一个节点以及后一个节点;现简称为前驱节点和后驱节点                                                                                                                                                    所以在双向链表中的任意一个节点段开始;都可以非常轻松的访问该节点的前驱节点或者后驱节点

数据结构:链表(双向链表)

         

        从上图中可以看到;双链表中各节点包括了3部分;

 指针区;用于指向当前节点的前驱节点; 数据区;用于存储数据元素; 指针区;用于指向当前节点的后驱节点;

双向循环链表定义;

        双向链表也可以进行首尾链接;进而变成一个循环链表;一般简称为环                                      在创建链表时只需将首尾链接即可  本文中所介绍的就是双向带头循环链表数据结构:链表(双向链表)


1.双向链表的节点构造在C语言中的创建;

节点结构
typedef struct Listnode{
    struct Node *prev;
    int data;
    struct Node *next;
}LTNode;

2.双向带头循环链表的创建

        和单链表做对比;双向链表仅仅只是各个节点中多了一个指向上一个节点的指针区;所以可以很轻松的在单向链表的基础上创建双向链表

        其中需要注意的是双向链表与单向链表不同的是在每次创建一个新的节点时除了与后驱节点进行链接之外还需要与前驱节点进行链接绑定的两次操作

        将新节点的prev指针指向前驱节点;                                                                                                  将前驱节点中的next后驱节点指向刚创建的新节点;                                                                        以下是创建新节点时创建双向链表的C语言代码;

typedef int SLDataType;
//节点结构
typedef struct ListNode{
    struct Node *prev;
    int data;
    struct Node *next;
}LTNode;

LTNode* LTNodeInit() //初始化双向链表为带头双向链表
{
	LTNode* newNode = BuyLTNode(0);
	return newNode;
}

LTNode* BuyLTNode(SLDataType x) //创建新节点
{
	LTNode* tmp = (LTNode*)malloc(sizeof(LTNode));
	if (tmp == NULL)
	{
		exit(-1);
	}
	tmp->array = x;
	tmp->next = tmp;
	tmp->prev = tmp;
}


void LTNodeInsert(LTNode* psl, SLDataType x)  //节点的创建与对接前后驱节点并在传递的参数值中进行插入
{
	LTNode* src = BuyLTNode(x);
	src->prev = psl->prev;
	src->next = psl;
	psl->prev->next = src;
	psl->prev = src;
}

3.双向带头循环链表的头插尾插

        双向带头循环链表的头插和尾插;分别以两种代码写法来进行体现                                                  第一种是分别以各自场景手动写入添加新节点时 前后节点的对接联系                                              第二种是以LTNodeInsert这个模块来进行处理;只需要在使用时提供对应要插入位置的地址            即可                                                                                                                                                    如;                                                                                                                                                          头插时只需传入带头双向链表头部节点的下一个节点地址;尾插时只需传入尾部节点的            地址即可

void LTNodePopBack(LTNode* psl, SLDataType x)//头插
{
	LTNode* newNode = BuyLTNode(x);
	newNode->prev = psl;
	newNode->next = psl->next;
	psl->next->prev = newNode;
	psl->next = newNode;
	assert(psl);
}

void LTNodePushBack(LTNode* psl, SLDataType x)//尾插
{
	LTNode* newTail = BuyLTNode(x);//创建新节点
	newTail->prev = psl->prev;//将新节点的前驱节点和头结点上一个节点对接(也就是尾节点)
	newTail->next = psl;
	psl->prev->next = newTail;
	psl->prev = newTail;
	assert(psl);
}

//以上两种是最初始的写法;以2中LTNodeInsert的写法 则有一种比较省事的写法

void LTNodePopBack(LTNode* psl, SLDataType x)//头插
{
	assert(psl);
	LTNodeInsert(psl -> next, x);
}

void LTNodePushBack(LTNode* psl, SLDataType x)
{
	assert(psl);
	LTNodeInsert(psl, x);
}
//这两种写法;只需要传递节点某位置的地址即可

4.双向带头链表的头删尾删及删除pos位节点

        对于双向带头循环链表中要进行头删尾删也非常的简单                                                                    单独写一个删除pos位节点的功能模块,这个模块只需要传入要删除的节点地址即可将前后节点自动对接;

void LTNodeErase(LTNode* psl) //删除pos位节点
{
	LTNode* delet = psl;
	if (psl->next != psl)
	{
		psl->prev->next = psl->next;
		psl->next->prev = psl->prev;
		free(delet);
    //psl的下一个节点如果不等于自己 那么它就一定有一个及以上的节点并进行以下操作
    //1.将psl的上一个节点中的next指针指向本节点中的next地址
    //2.将psl下一个节点中的prev指针指向本节点的上一个节点
    //3.释放本节点
    //如果psl->next == psl 那么证明这个链表则没有节点,只有一个做头的头结点
	}
}

void LTNodePopFront(LTNode* psl) //头删
{
	assert(psl);
	LTNodeErase(psl->next);
}

void LTNodePushFront(LTNode* psl) //尾删
{
	assert(psl);
	LTNodeErase(psl->prev);
}

结尾

        实际中链表的结构非常多样;以下情况组合起来就有8种链表结构:                                                    1. 单向或者双向

               数据结构:链表(双向链表)

        2. 带头或者不带头(带哨兵位或不带哨兵位)

数据结构:链表(双向链表)

         3. 循环或者非循环

数据结构:链表(双向链表)

 虽然有这么多的链表的结构;但是实际中最常用还是两种结构:数据结构:链表(双向链表)

 1. 无头单向非循环链表;结构简单;一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构;如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表;结构最复杂;一般用在单独存储数据。实际中使用的链表数据结构;都是带头双向循环链表。另外这个结构虽然结构复杂;但是使用代码实现以后会发现结构会带来很多优势;实现反而简单了;后面代码实现了就知道了。

加载全部内容

相关教程
猜你喜欢
用户评论
快盘暂不提供评论功能!