首页 > 知识百科 > 正文

数据结构——双链表(C语言)原创

目录

​编辑

 双链表的初始化:

双链表的打印:

双链表的尾插:

双链表的头插: 

双链表的尾部删:

 

双链表的头删:

双链表pos位置之前的插入:

双链表pos位置的删除:

关于顺序表和链表的区别:


 

上一篇文章给大家讲解了无头单向循环链表,它的特点是:结构简单,一般不会单独用来存储数据。实际中更多是作为其他数据结构子结构,比如哈希桶、图的邻接表等等。但是呢,单链表在笔试中还是很常见的。< strong>今天我给大家讲解一下带头大家链表,它的特点是:结构复杂,一般用在单独的存储数据上。实际中使用的链表结构,都是带头大家循环链表。另外这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势。

举例,这就是今天我为大家讲解了双链表的结构。下面跟随我的思路走下去,希望让你对链表有新的理解。

 


 双链表的初始化:

今天我给大家带来另一种方式改变链表的结构,如果想了解双指针来改变链表的结构,可以参考我的上一篇单链表的博客。思路:我创建了一个节点,然后把节点赋给了phead,再做的上一个位置和下一个位置分别指向它自己,最后返回phead就是我们要的哨兵位的头节点了。
ListNode* ListCreate(ListDateType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc 失败");exit(-1);}newnode->val = x;newnode ->next = NULL;newnode->prev = NULL;return newnode;}
ListNode* ListInit(){ListNode* phead = ListCreate(0);phead->next = phead;phead->prev = phead;return phead;}​​

 


 双链表的打印: 因为要让终端出现下面的样子,我就用了打印的函数。首先,还是老套路,我先断言通道,防止传的参数有问题。 strong>因为这里的phead是一个哨兵位,存放着无效的数据,所以,我就定义了一个cur的节点,用循环打印链表中的所有值

void ListPrint(ListNode* phead){assert(phead);printf("phead<->");ListNode* cur = phead->next;while (cur != phead){printf("%d<->", cur->val);cur = cur->next;}printf("\n");}

 


双链表的尾插出来:

在双链表尾插的时候,它的就证明了优势了,如果是单链表,要尾插的话,是只能遍历找到尾节点的,但是呢,如果是单链表,phead的前一个节点就是尾节点,它就不用找尾,也不需要遍历了。也是双链表的优势之一。尾插思路:先断言一下,然后用tail保存尾节点,创建一个新节点,然后改变尾节点和头节点链接关系,让newnode为新的尾节点。< /strong>

 

void ListPushBack(ListNode* phead,ListDateType x){assert(phead);ListNode * tail = phead->prev;ListNode* newnode = ListCreate(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;} 

 


双链表的头插: 

思路:头插的话,就是先保存一下头节点的位置,然后创建一个新的节点,然后改变他们的链接关系就可以了。我是先保存了它们的位置,所以谁先链接先都可以,如果没有保存的话,要向好逻辑,不要出现找不到头节点的位置了。
void ListPushFront( ListNode* phead, ListDateType x){assert(phead);ListNode* newnode = ListCreate(x);ListNode* 第一个 = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

 


双链表的尾删:

< strong>思路:尾删掉的话,要记录一下尾节点的前一个节点了,然后去改变一下phead和尾节点前一个节点的链接关系。
void ListPopBack(ListNode* phead){assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* tailprev = phead->prev->prev;tailprev->next = phead;phead-> prev = tailprev;free(tail);}

 


双链表的头删:

<英石rong>思路:头删的思路,其实和尾删的办法差不多,只不过这里保存的是phead之后的第二个关系了。然后就是改变链接链接。
void ListPopFront (ListNode* phead){assert(phead);assert(phead != phead->下一个);ListNode* 第一个 = phead->下一个;ListNode* 第二个 = 第一个->下一个;phead->下一个 = 第二个;第二个-> prev = phead;free(first);}

双链表pos位置之前的插入:

思路:如果是插入的话,是不是和尾插和头插差不多呢,我这里保存的是pos前面的节点,然后创建一个新的节点,让pos前面的节点指向新节点,让新节点和pos再建立连接
void ListInsert(ListNode* pos, ListDateType x){assert(pos);ListNode* posprev = pos->prev;ListNode* newnode = ListCreate(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;}

 


双链表pos位置的删除:

思路:pos位置要删除的话,保存pos上一个节点和pos下一个节点,然后free掉pos位置,再改变他们的链接关系。
void ListErase(ListNode* pos){assert(pos);ListNode* posprev = pos->prev;ListNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev; free(pos);}

大家看了pos位置的删除和pos之前的插入,是不是感觉和前面的尾尾插曲删掉和头插头删差不多呢,其实呢,最后的两个函数是可以进行对函数的复用的。

尾插:其实就是在ListInsert函数传phead就可以了,这样就实现了尾插
ListInsert(phead, x);
头插:头插是改变phead之后的位置,所以直接传phead->next就可以了。
ListInsert(phead->next, x);
头删和尾删:因为我写的删除的函数是删除pos位置,所以传要删除的位置就可以了。
 ListErase(phead->prev);
ListErase(phead->next);

 

 


关于顺序表和链表的区别:

存储空间上:顺序表在物理上是连续的,而链表逻辑上是连续的随机访问上:顺序表是支持随机访问的,而链表是不支持的,要访问链表中的节点,是需要遍历的。任意位置的插入和删除:链表有很大的优势了,链表只需要在这里改变指向就可以实现对任意位置的插入和删除。但是对于顺序表来说,可能需要搬运元素,效率太低了。 插入:顺序表因为是连续的,所以在插入的上面,可能会有malloc扩容,但是呢malloc是有消耗的的,如果一次扩二倍,但是用的很少,就会造成对空间的浪费,如果一次扩的空间是+1,可能会面临多次扩容,而malloc的消耗并不低,所以这是不可取的。而链表并没有容器的概念,在这方面有优势。硬盘利用率:顺序表的缓存命中率高,而链表低。

#define _CRT_SECURE_NO_WARNINGS 1#include "DoubleList.h"ListNode* ListCreate(ListDateType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc 失败" );退出(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;返回newnode;}ListNode* ListInit(){ListNode* phead = ListCreate(0);phead ->next = phead;phead->prev = phead;return phead;}​​void ListPrint(ListNode* phead){assert(phead);printf("phead<->");ListNode* cur = phead->next;while (cur != phead){printf("%d<->", cur->val);cur =; cur->next;}printf("\n");}void ListPushBack(ListNode* phead,ListDateType x){assert(phead);//ListNode* tail = phead->prev;//ListNode* newnode = ListCreate( x);//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;ListInsert(phead, x);}void ListPushFront( ListNode* phead, ListDateType x){assert(phead);//ListNode* newnode = ListCreate(x);//ListNode* first = phead->next;//phead->next = newnode;//newnode->prev = phead;//newnode->next = first;//first->prev = newnode;ListInsert(phead->next, x);}void ListPopBack(ListNode* phead){assert(phead);assert(phead-> next != phead);//ListNode* tail = phead->prev;//ListNode* tailprev = phead->prev->prev;//tailprev->next = phead;//phead->prev = tailprev;/ /free(tail);ListErase(phead->prev);}void ListPopFront(ListNode* phead){assert(phead);assert(phead != phead->next);//ListNode*first = phead->next;//ListNode* secondary = first->next;//phead->next = secondary;//second->prev = phead;//free(first);ListErase(phead->next) ;}int ListSize(ListNode* phead){assert(phead);int size = 0;ListNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return大小;}void ListInsert(ListNode* pos, ListDateType x){assert(pos);ListNode* posprev = pos->prev;ListNode* newnode = ListCreate(x);posprev->next = newnode;newnode->prev = posprev ;newnode->next = pos;pos->prev = newnode;}void ListErase(ListNode* pos){assert(pos);ListNode* posprev = pos->prev;ListNode* posnext = pos->next;posprev-> next = posnext;posnext->prev = posprev;free(pos);}

 


 

什么是服务器负载:

关于“Cache Line”,服务器是把数据负载放到自己进的位置,对于CPU来说,CPU是一块存储的。而我们称之为“Chche Line”。

我们所写的程序,其实都会形成不同的指令,然后让CPU执行,但是呢,CPU执行速度快,内存跟不上,所以CPU一般都是把数据放到存储中,对于小一点的字节来说,直接由读取来读取,大的字节会占用三级存储。

简单方面之,数据先被读取,然后侵犯,最后放到主存中,如果没有命令,就继续。

而顺序表呢,它的物理结构是连续的,它可能一开始没有命中,但是一旦缓存命中,它可能就会被连续命中,所以这也是顺序表硬盘利用率高的原因,而链表也是因为他的物理结构,导致硬盘利用率低。

 

下面是双链表的源码:

#define _CRT_SECURE_NO_WARNINGS 1#include "DoubleList.h" ListNode* ListCreate(ListDateType x){ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc 失败");exit(-1);}newnode-> val = x;newnode->next = NULL;newnode->prev = NULL;返回newnode;}ListNode* ListInit(){ListNode* phead = ListCreate(0);phead->next = phead;phead->prev = phead ;返回 phead;}​​void ListPrint(ListNode* phead){assert(phead);printf("phead<->");ListNode* cur = phead->next;while (cur != phead){printf("%d<->", cur-> val);cur = cur->next;}printf("\n");}void ListPushBack(ListNode* phead,ListDateType x){assert(phead);//ListNode* tail = phead->prev;//ListNode * newnode = ListCreate(x);//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;ListInsert(phead, x) ;}void ListPushFront(ListNode* phead, ListDateType x){assert(phead);//ListNode* newnode = ListCreate(x);//ListNode* first = phead->next;//phead->next = newnode;/ /newnode->prev = phead;//newnode->next = first;//first->prev = newnode;ListInsert(phead->next, x);}void ListPopBack(ListNode* phead){assert(phead); assert(phead->next != phead);//ListNode* tail = phead->prev;//ListNode* tailprev = phead->prev->prev;//tailprev->next = phead;//phead->prev = tailprev;//free(tail);ListErase(phead->prev);}void ListPopFront(ListNode* phead){assert(phead);assert(phead != phead->next);// ListNode* first = phead->next;//ListNode* secondary = first->next;//phead->next = secondary;//second->prev = phead;//free(first);ListErase(phead-> next);}int ListSize(ListNode* phead){assert(phead);int size = 0;ListNode* cur = phead->next;while (cur != phead){++size;cur = cur->next; }返回大小;}void ListInsert(ListNode* pos, ListDateType x){assert(pos);ListNode* posprev = pos->prev;ListNode* newnode = ListCreate(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;}void ListErase(ListNode* pos){assert(pos);ListNode* posprev = pos->prev;ListNode* posnext = pos->next;posprev ->next = posnext;posnext->prev = posprev;free(pos);}
#pragma Once#include #include #include typedef int ListDateType;typedef struct ListNode{ListDateType val;struct ListNode* next;struct ListNode* prev;}ListNode;ListNode* ListCreate(ListDateType x); void ListPrint(ListNode* phead);ListNode* ListInit();void ListPushBack(ListNode* phead,ListDateType x);void ListPushFront(ListNode* phead, ListDateType x);void ListPopBack(ListNode* phead);void ListPopFront(ListNode* phead) );int ListSize(ListNode* phead);void ListInsert(ListNode* pos, ListDateType x);void ListErase(ListNode* pos);

 

 

 

 

 

 

 

 

 

 

 

数据结构——双链表(C语言)原创由知识百科栏目发布,感谢您对的认可,以及对我们原创作品以及文章的青睐,非常欢迎各位朋友分享到个人网站或者朋友圈,但转载请说明文章出处“数据结构——双链表(C语言)原创