数据结构—双向带头循环链表的实现
创始人
2025-05-28 04:41:18
0

640?wx_fmt=gif

 

目录

前言:

1、带头+双向+循环链表的实现

1.1、malloc结点

1.2、链表初始化ListNode* ListInit();

1.3、链表的打印void ListPrint(ListNode* phead);

1.4、链表尾插

void ListPushBack(ListNode* phead, LTDataType x)

1.5、链表头插

void ListPushFront(ListNode* phead, LTDataType x);

1.6、链表尾删

void ListPopBack(ListNode* plist);

1.7、双向链表头删void ListPopFront(ListNode* phead);

1.8、双向链表查找ListNode* ListFind(ListNode* phead, LTDataType x);

1.9、双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x);

1.10、双向链表删除pos位置的结点void ListErase(ListNode* pos);

1.11、求链表的长度int ListSize(ListNode* phead);

1.12、双向链表的销毁void ListDestory(ListNode* phead);

2、oj题目

3、顺序表和链表的区别


前言:

可知链表的结构非常多样,以下情况组合起来就有八种链表结构:

1.单向带头循环链表

2.单向带头不循环链表

3.单向不带头循环链表

4单向不带头不循环链表

5.双向带头循环链表

6.双向带头不循环链表

7.双向不带头循环链表

8.双向不带头不循环链表

 双向带头循环链表:结构复杂、操作简单,为最优链表

1、带头+双向+循环链表的实现

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}listNode;

1.1、malloc结点

ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

1.2、链表初始化
ListNode* ListInit();

初始化哨兵位的头结点

ListNode* ListInit()
{ListNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

1.3、链表的打印
void ListPrint(ListNode* phead);

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

1.4、链表尾插

void ListPushBack(ListNode* phead, LTDataType x)

不需要传二级指针,因为我们不需要改变哨兵位的头
//而是改变头指针指向里面的结构

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

1.5、链表头插

void ListPushFront(ListNode* phead, LTDataType x);

void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}

1.6、链表尾删

void ListPopBack(ListNode* plist);

// 双向链表尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;tail->prev->next = phead;phead->prev = tail->prev;free(tail);
}

1.7、双向链表头删
void ListPopFront(ListNode* phead);

void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* del = phead->next;phead->next = phead->next->next;phead->next->prev = phead;free(del);del = NULL;
}

1.8、双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);

ListNode* ListFind(ListNode* phead, LTDataType x)
{ListNode* cur = phead->next;if (phead->next == NULL){return NULL;}while (phead->next->data != x){phead = phead->next;if (phead->next == cur){return NULL;}}return phead->next;return NULL;
}

1.9、双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x);

void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = BuyListNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}

头插可以直接复用,ListInsert( phead -> next, x )

尾插也可以复用,因为是循环,哨兵位前一个便是尾,所以再哨兵位之前插入就可以

ListInsert( phead , x )

1.10、双向链表删除pos位置的结点
void ListErase(ListNode* pos);

void ListErase(ListNode* pos)
{pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}

头删可以直接服用,ListErase( phead -> next )

尾删,ListErase( phead -> prev )

1.11、求链表的长度
int ListSize(ListNode* phead);

int ListSize(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;int size = 0;while (cur != phead){++size;cur = cur->next;}return size;
}

1.12、双向链表的销毁
void ListDestory(ListNode* phead);

void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;int size = 0;while (cur != phead){ListNode* next = cur->next;ListErase(cur);cur = next;}free(phead);
}

2、oj题目

给定一个链表,每个结点包含一个额外增加的随机指针,该指针可以指向链表中的任何结点 或空结点。 要求返回这个链表的深度拷贝。

Loading Question... - 力扣(LeetCode)https://leetcode.cn/problems/copy-list-with-random-pointer/description/

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。 

深拷贝应该正好由 n 个 全新节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。

每个节点用一个 [val,random_index] 表示:

val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。
你的代码 只接受原链表的头节点 head 作为传入参数。

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//1.链接while(cur){struct Node* copy = ( struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next= copy;cur = copy->next;}//控制randomcur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random ->next;}cur = copy->next;}cur = head;struct Node* copyHead = NULL,*copyTail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyTail == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}cur->next = next;cur = next;}return copyHead;
}

3、顺序表和链表的区别

   不同点                                 顺序表                                                                链表

存储空间上                       物理上一定连续                                  逻辑上连续,但物理上不一定 连续

随机访问                              支持:O(1)                                                       不支持:O(N)           

任意位置插入

            |                   可能需要搬移元素,效率低 O(N)                               只需修改指针指向

或者删除元素 

插入                         动态顺序表,空间不够时需要 扩容                             没有容量的概念

应用场景                        元素高效存储+频繁访问                                    任意位置插入和删除频繁

缓存利用率                                      高                                                                      低 

备注:缓存利用率参考存储体系结构 以及 局部原理性。

 与程序员相关的CPU缓存知识 | 酷 壳 - CoolShellicon-default.png?t=N176https://coolshell.cn/articles/20793.html

相关内容

热门资讯

2011年出生农历10月28早... 2011年出生农历10月28早上7点08分的女孩子名字好听姓杨杨琴雯 杨思雯 杨成雅 杨瑷烨 杨琳园...
健康保险的保障范围有哪些呢? 健康保险的保障范围有哪些呢?健康保险是针对可能得的重大疾病的保险,一个健康保险是否“好”,主要取决于...
勉励孩子读书的诗句或名言 勉励孩子读书的诗句或名言勉励孩子读书的句子有:1、万般皆下品,唯有读书高!——孔子2、学好靠信心,求...
家教同人反苏,听说家教反苏文很... 家教同人反苏,听说家教反苏文很多可是我偏偏一本没看过(貌似),求!可以只给名字,越多越好,质量稍微好...
民办高校的宿舍条件,是不是比公... 民办高校的宿舍条件,是不是比公办高校要好一些呢?也不一定。民办高校有的比公办高校宿舍条件好,有的还不...
千城胜景|广西昭平桂江:水墨画...   在广西贺州市昭平县,桂江的烟雨日常令人陶醉。清晨时分,如烟似雾的水汽漫过江面,轻柔地笼罩着两岸青...
《小舍得》养娃焦虑引争议,你觉... 《小舍得》养娃焦虑引争议,你觉得为孩子买豪车有没有必要?我觉得没必要。主要看个人家庭条件吧,有些家庭...
古代选君王继承人是一件大事,朱... 古代选君王继承人是一件大事,朱棣为何会传位给残疾皇子?首先,朱高炽是朱棣的长子,长子继位更名正言顺。...
成都哪点能看到大熊猫,或者看大... 成都哪点能看到大熊猫,或者看大熊猫的最佳地点?成都动物园或者成都大熊猫繁育研究基地。成都动物园里面大...
寻书 一本女主穿到书中的小说 ... 寻书 一本女主穿到书中的小说 女主出车祸醒来发现自己到了一本书里的世界 但她忘了自己怎么来男主他男主...
偶像练习生中,你最喜欢谁? 偶像练习生中,你最喜欢谁?我最喜欢《偶像练习生》中的林彦俊和尤长靖。林彦俊颜值很高而且很会讲冷笑话,...
杨氏之子是一个怎样的孩子 杨氏之子是一个怎样的孩子最佳答案结合《杨氏之子》原文,杨氏之子有如下特点:1、从文中“梁国杨氏子九岁...
怎样成为一名优秀的教师 读后感 怎样成为一名优秀的教师 读后感 读了《只有一个地球》这篇文章后,我知道了:地球是人类的母亲,是生...
火影忍者里的止水为什么被称为“... 火影忍者里的止水为什么被称为“瞬身止水”瞬身止水是指止水会瞬身术移动速度快,别天神不是止水的术,而是...
五行相生相克 求详细解释,金有... 五行相生相克 求详细解释,金有巽和离。金生水,水有坎和乾 巽应该是对应坎还是乾? 反之相克也是五行相...
怪物猎人曙光耐绝珠3怎么解锁 怪物猎人曙光耐绝珠3怎么解锁在怪物猎人崛起游戏中,提供珠应该怎么解锁呢?解锁后这个提供珠有什么作用呢...
求本好看的小说, 大侠们进来帮... 求本好看的小说, 大侠们进来帮忙邪气凛然我在网上看了8年左右,感觉他是最好看的一本完本小说。我说好不...
恐龙战队中有一集是队员都被怪兽... 恐龙战队中有一集是队员都被怪兽控制,不停的跳舞是哪一集来?最好发视频上来,谢了恐龙战队第3季31集,...
马嘉祺张真源参加中戏艺考,中戏... 马嘉祺张真源参加中戏艺考,中戏培养出来的优秀艺人都有哪些?中戏培养出来的优秀艺人有很多啊,比如:邓超...
我喜欢的小动物这篇作文应怎么写 我喜欢的小动物这篇作文应怎么写我喜欢的小动物是小白兔,因为我家就养了一只小兔子,它有一身像雪花一样白...