27 顺序表 · 链表

目录

一、单链表

（一）概念

1、节点

2、链表的性质

（二）单链表的实现

（三）单链表算法题

1、移除链表元素

2、反转链表

3、链表的中间节点

4、合并两个有序的单链表

5、链表分割

6、链表的回文结构

7、相交链表

8、环形链表 · 是否是环形链表

9、环形链表 · 寻找环形起始点

10、随机链表的复制

二、链表的分类

三、双向链表

（一）概念与结构

（二）双向链表的实现

四、顺序表与链表的分析

一、单链表

（一）概念

        概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

        总结：链表的逻辑结构是线性的，数据是一个接着一个的；物理结构不一定是线性的。

1、节点

        与顺序表不同的是，链表里的每个元素都是独立申请下来的空间，我们称之为“结点”。

        单链表的结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量），也称为数据域和指针域。

        在单链表中需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

2、链表的性质

        ① 链式结构在逻辑上是连续的，在物理结构上不一定连续。

        ② 节点一般是从堆上申请的。（通过动态内存管理进行开辟空间）

        ③ 从堆上开辟的空间，是按照一定策略分配出来的，每次开辟的空间可能连续，也可能不连续。

（二）单链表的实现

        单链表常用名：SingleList，简称SLT；单链表节点常用名字：SLTNode。

        定义链表结构体，其实是在定义节点的结构体，因为链表是由一个个的节点组合起来的。

单链表的编写：

① 头文件：定义单链表的节点结构体，声明要提供的操作（起到目录作用）；

② cpp文件：编写具体实现各种操作（起到内容作用）；

③ 测试文件：测试是否可以正常运行。

        SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<iostream>
using namespace std;typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;//一、创建新节点、打印链表、查找节点
//	(一)创建新节点
SLTNode* create_node(SLTDataType num);
//	(二)打印链表
void SLTPrint(SLTNode* phead);
//	(三)查找节点
SLTNode* find_node(SLTNode* phead, SLTDataType num);//二、插入数据(传过来的单链表可以为空，单一定要创建新节点)
//	(一)尾插
void SLTPushBack(SLTNode*& phead, SLTDataType num);
//	(二)头插
void SLTPushFront(SLTNode*& phead, SLTDataType num);
//	(三)指定位置插
//		1、指定位置之前插
void SLTInsert(SLTNode*& phead, SLTNode* pos, SLTDataType num);
//		2、指定位置之后插
void SLTInsertAfter(SLTNode* pos, SLTDataType num);//三、删除数据(要判断传过来的节点是否为空)
//	(一)尾删
void SLTPopBack(SLTNode*& phead);
//	(二)头删
void SLTPopFront(SLTNode*& phead);
//	(三)指定位置删除
//		1、指定位置删除
void SLTErase(SLTNode*& phead, SLTNode* pos);
//		2、指定位置之后删除
void SLTEraseAfter(SLTNode* pos);
//	(四)销毁单链表
void SLTDestroy(SLTNode*& phead);

        SList.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"//一、创建新节点、打印链表、查找节点
//	(一)创建新节点
SLTNode* create_node(SLTDataType num)
{SLTNode* new_node = (SLTNode*)malloc(sizeof(SLTNode));if (new_node == nullptr){perror("creat_node fail");exit(1);}new_node->data = num;new_node->next = nullptr;
}
//	(二)打印链表
void SLTPrint(SLTNode* phead)
{while (phead){cout << phead->data << " -> ";phead = phead->next;}cout << "nullptr" << endl;
}
//	(三)查找节点
SLTNode* find_node(SLTNode* phead, SLTDataType num)
{while (phead){if (phead->data == num)return phead;phead = phead->next;}
}//二、插入数据(传过来的单链表可以为空，单一定要创建新节点)
//	(一)尾插
void SLTPushBack(SLTNode*& phead, SLTDataType num)
{SLTNode* new_node = create_node(num);if (phead == nullptr)phead = new_node;else{SLTNode* node = phead;while (node->next)node = node->next;node->next = new_node;new_node->next = nullptr;}
}
//	(二)头插
void SLTPushFront(SLTNode*& phead, SLTDataType num)
{SLTNode* new_node = create_node(num);if (phead == nullptr)phead = new_node;else {new_node->next = phead;phead = new_node;}
}
//	(三)指定位置插
//		1、指定位置之前插
void SLTInsert(SLTNode*& phead, SLTNode* pos, SLTDataType num)
{assert(pos);SLTNode* new_node = create_node(num);if (phead == pos){new_node->next = phead;phead = new_node;}else{SLTNode* pre_node = phead;while (pre_node){if (pre_node->next == pos){new_node->next = pre_node->next;pre_node->next = new_node;break;}pre_node = pre_node->next;}}
}
//		2、指定位置之后插
void SLTInsertAfter(SLTNode* pos, SLTDataType num)
{assert(pos);SLTNode* new_node = create_node(num);new_node->next = pos->next;pos->next = new_node;
}//三、删除数据(要判断传过来的节点是否为空)
//	(一)尾删
void SLTPopBack(SLTNode*& phead)
{assert(phead);if(phead->next == nullptr){free(phead);phead == nullptr;}else{SLTNode* pre_node = phead;while (pre_node->next->next)pre_node = pre_node->next;SLTNode* node = pre_node->next;pre_node->next = nullptr;free(node);node = nullptr;}
}
//	(二)头删
void SLTPopFront(SLTNode*& phead)//若不传引用，则会造成二次free
{assert(phead);SLTNode* node = phead->next;free(phead);phead = node;
}
//	(三)指定位置删除
//		1、指定位置删除
void SLTErase(SLTNode*& phead, SLTNode* pos)
{assert(phead && pos);if (phead == pos){phead = phead->next;free(pos);pos = nullptr;}else{SLTNode* pre_node = phead;while (pre_node){if (pre_node->next == pos){pre_node->next = pos->next;free(pos);pos = nullptr;break;}pre_node = pre_node->next;}}
}
//		2、指定位置之后删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* node = pos->next;pos->next = node->next;free(node);node = nullptr;
}
//	(四)销毁单链表
void SLTDestroy(SLTNode*& phead)
{assert(phead);SLTNode* next_noed = phead->next;while (next_noed){free(phead);phead = next_noed;next_noed = next_noed->next;}free(phead);phead = nullptr;
}

        test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void test()
{//SLTNode* re =  create_node(15);SLTNode* plist = nullptr;for (int i = 1; i < 11; i++){SLTPushBack(plist, i);//SLTPushFront(plist, i);}SLTPrint(plist);SLTNode* re = find_node(plist, 5);//SLTInsert(plist, re, 255);//SLTInsertAfter(re, 255);//for (int i = 0; i < 1; i++)//{//	//SLTPopBack(plist);//	//SLTPopFront(plist);//}//SLTErase(plist, re);//SLTEraseAfter(re);SLTDestroy(plist);SLTPrint(plist);
}int main()
{test();return 0;
}

        总结：

        ① 单链表没办法从右向左遍历，只能从左向右遍历，若是对单链表进行操作，需要影响到目标节点的前一个节点时，需要传递头节点进行遍历，找到目标节点的前一个节点进行修改。

        ② 在链表中，没有增容的概念（不使用realloc），需要插入新的数据，直接申请一个节点大小的空间就可以了。

        ③ 判断传参传的是一级指针还是二级指针（使用 “引用” ），就要看是否改变了实参地址指向的空间（这个改变是指实参所指向的空间不会变成另一个地址的空间）。

        比如：

        在尾插中存在两种情况，第一种是存在节点的时候，直接进行尾插，不需要改变传过来的头节点的指针指向；而第二种情况就是头指针指向空的时候，需要把头指针指向空地址改成指向新开辟的空间的地址，这样就改变了实参指向的地址空间，所以在尾插操作中需要传二级指针（使用 “引用” ）。

        而在删除指定节点之后的节点的操作中，并没有改变对指定节点的空间进行改变，所以传一级指针即可。

（三）单链表算法题

1、移除链表元素

        题目链接如下：

                https://leetcode.cn/problems/remove-linked-list-elements/description/

        解题思路：

                创建新链表，然后遍历原链表，把除了【指定移除节点】的其他节点全部复制尾插在新链表后面。

                注意点：需要把新链表最后的节点的next置为空，因为可能会链接着需要删除的节点的地址。

        代码如下：

typedef struct ListNode SLTNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{//创建新链表SLTNode* new_head, * new_tail;new_head = new_tail = NULL;//遍历原链表SLTNode* pcur = head;while(pcur){if(pcur->val != val){if(new_head == NULL)//尾插分为两种情况：①链表为空 ②链表不为空new_head = new_tail = pcur;else{new_tail->next = pcur;new_tail = new_tail->next;}}pcur = pcur->next;}if(new_tail)new_tail->next = NULL;return new_head;
}

2、反转链表

        题目链接如下：

                https://leetcode.cn/problems/reverse-linked-list/description/

        题解思路：

                创建三个指针，第一个指针 p1 指向 nullptr，第二个指针指向头节点，第三个指针指向头节点的下一个节点。然后把第二个指针的指向改成第一个指针所指向的 nullptr，再把第二个指针的地址赋给第一个指针，第三个指针的地址赋给第二个指针，第三个指针向后走一步。

        注意点：

                需要判断第三个指针是否为空：因为在处理最后一个节点的指向的时候，第三个指针的指向已经是空了，所以要判断一下第三个指针是否为空，若为空就不能解引用结构体里面的值把next赋给自己了；

                循环的判断条件为第二个指针是否为空，因为当第二个指针为空的时候，就没有需要改变指向的节点了（画图理解）。

        答案代码如下：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL)return head;else{ListNode* p1, *p2, *p3;p1 = NULL, p2 = head, p3 = head->next;while(p2){p2->next = p1;p1 = p2;p2 = p3;if(p3)p3 = p3->next;}return p1;//p1为反转链表的头指针}
}

3、链表的中间节点

        题目链接如下：

                https://leetcode.cn/problems/middle-of-the-linked-list/description/

        解题思路：

                创建两个指针，起始位置都指向目标链表的第一个节点处；

                一个指针为慢指针，另一个指针为快指针，顾名思义慢指针的移动速度比快指针慢，慢指针走一步，快指针走两步；

                当快指针到达最后一个节点指向的空地址，或者快指针的下一个节点就是空地址的时候，慢指针所指向的节点就是中间节点。

                原理：假设快指针走的路程为n，快指针走的路程是慢指针的两倍，即 2*慢=快；此时慢指针走的路程就是n/2。当链表的长度为5的时候，快指针到达了终点5，而慢指针的路程为2（整形去除小数点），又因为起始位置为1，所以到达的节点是3，为中间节点；当链表的长度为6的时候，快指针到达了终点7，慢指针的路程为3，又因为起始位置为1，所以到达的节点是4，为中间节点。

        注意点：

                while判断的 pfast && pfast->next 的顺序不能换，若换过来判断偶数节点数中间节点的时候，pfast已经为空地址，空地址不能解引用 pfast->next，这样会报错。

        答案代码如下：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* pfast, *pslow;pfast = pslow = head;while(pfast && pfast->next){pfast = pfast->next->next;pslow = pslow->next;}return pslow;
}

4、合并两个有序的单链表

        题目链接如下：

                https://leetcode.cn/problems/merge-two-sorted-lists/description/

        解题思路如下：

                创建一个新的链表，创建两个指针分别指向两个有序的单链表；两个有序单链表的节点开始比较，较小或者相等的节点尾插到新链表中，然后比较时较小链表的指针与新链表中指向为节点的指针都向后走一步，开始循环比较大小；循环结束后若是有一方还存在数据，直接把数据全部插入到新链表中。

        注意点：

                因为每次比较之后都要判断新链表的头尾指针是否为空（为尾插分两种情况），显得代码冗余，可以直接动态申请一个内存给新链表的头尾指针，这样就可以不用检查判断是否为空了。

        答案代码如下：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1 == NULL)return list2;//这里处理了list1为空的情况与list1和list2都为空的情况if(list2 == NULL)return list1;ListNode* new_head , *new_tail;//创建新链表new_head = new_tail = (ListNode*)malloc(sizeof(ListNode));ListNode* p1 = list1, *p2 = list2;//创建指针指向两个数组while(p1 && p2){if(p1->val < p2->val){new_tail->next = p1;new_tail = p1;p1 = p1->next;}else{new_tail->next = p2;new_tail = p2;p2 = p2->next;}}if(p1)new_tail->next = p1;if(p2)new_tail->next = p2;ListNode* node = new_head->next;//释放掉无有效数据的哨兵节点free(new_head);new_head = node;return new_head;
}

5、链表分割

        题目链接如下：

                https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

        解题思路：

                创建两个非空链表，每个链表都要创建哨兵节点，这样不用每次尾插都要检查节点指针是否为空（因为单链表的尾插有两种情况）；然后进行比较数据大小，把小于x的属于与大于或等于x的数据分别插入小链表与大链表；最后把大链表的节点插入小链表中，释放哨兵节点。

        注意点：

                尾插不会改变要插入节点的next，这里原来的节点的next可能还是下一个较小节点的地址，这样打印会造成死循环；大连表尾插进小链表后需要把大链表的最后一个节点的next置空。

        答案代码如下：

class Partition 
{
public:ListNode* partition(ListNode* pHead, int x) {//创建两个非空链表(创建哨兵节点，这样不用每次尾插都要检查节点指针是否为空)ListNode* less_head, * less_tail;less_head = less_tail = (ListNode*)malloc(sizeof(ListNode));ListNode* big_head, * big_tail;big_head = big_tail = (ListNode*)malloc(sizeof(ListNode));//比较数据大小，分别插入大链表与小链表ListNode* pcur = pHead;while(pcur){if(pcur->val < x){less_tail->next = pcur;less_tail = less_tail->next;}else {big_tail->next = pcur;big_tail = big_tail->next;}pcur = pcur->next;}//把大链表的节点插入小链表中//尾插不会改变要插入节点的next//这里原来的节点的next可能还是下一个较小节点的地址，这样打印会造成死循环，需要把大链表的最后一个节点的next置空big_tail->next = nullptr;less_tail->next = big_head->next;//释放哨兵节点ListNode* re = less_head->next;free(less_head);free(big_head);less_head = big_head = nullptr;return re;}
};

6、链表的回文结构

        题目链接如下：

                https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

        解题思路：

                回文数字、字符串：轴对称；

                需要用到的思想为前面题目中的找中间节点与反转链表：设置快慢指针，找到中间节点；设置三个指针，分别指向nullptr、中间节点与中间节点的第二个指针，进行指向反转。最后把反转后的链表与中间节点之前的部分链表从头开始比较，若完全相等就是回文结构。

        答案代码如下：

class PalindromeList {
public:ListNode* fine_mid(ListNode* phead){ListNode* pslow, * pfast;pslow = pfast = phead;while(pfast && pfast->next){pslow = pslow->next;pfast = pfast->next->next;}return pslow;}ListNode* reversal(ListNode* mid){ListNode* p1, *p2, *p3;p1 = nullptr, p2 = mid, p3 = mid->next;while(p2){p2->next = p1;p1 = p2;p2 = p3;if(p3)p3 = p3->next;}return p1;}bool chkPalindrome(ListNode* A) {//一、找中间节点ListNode* mid_node = fine_mid(A);//二、把中间节点后面的数据都反转ListNode* rever_head = reversal(mid_node);//三、把反转之后的节点与原头节点while(rever_head)//循环条件是rever_head是否存在，因为rever_head指向的单链表的最后有nullptr，而A取不符合条件{if(rever_head->val != A->val)return false;rever_head = rever_head->next;A = A->next;}return true;}
};

7、相交链表

        题目链接如下：

                https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

        相交链表的图例如下：

        解题思路：

                首先从两个不同的头节点开始到尾进行遍历，并计算从不同头节点开始的总节点个数，并计算节点个数之差的绝对值；然后设置长链表与短链表，让长链表先走节点差数的步数，再开始分别遍历两个链表，若有相同地址的节点，则返回该节点的地址，若没有相同地址的节点，则返回nullptr。

        注意点：

                求绝对值函数：abs（）。

        答案代码如下：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//遍历链表，找节点差ListNode* node_A = headA;ListNode* node_B = headB;int size_A = 0, size_B = 0;while(node_A){size_A++;node_A = node_A->next;}while(node_B){size_B++;node_B = node_B->next;}int gap = abs(size_A - size_B);//计算节点个数差//设置长短链表ListNode* long_list = headA;ListNode* short_list = headB;if(size_A < size_B){long_list = headB;short_list = headA;}while(gap--)//先让长链表走节点差步long_list = long_list->next;//遍历两链表，有相同地址值就返回节点地址，没有就返回nullwhile(long_list && short_list){if(long_list == short_list)return long_list;long_list = long_list->next;short_list = short_list->next;}return NULL;
}

8、环形链表 · 是否是环形链表

        题目链接如下：

                https://leetcode.cn/problems/linked-list-cycle/description/

        解题思路如下：

                带环链表：从头节点开始遍历链表，遍历不会结束。链表的尾节点next指针不指向空；

                使用的是快慢指针的思想（即慢指针一次走一步，快指针⼀次走两步），两个指针从链表起始位置开始运行，如果链表带环则⼀定会在环中相遇，否则快指针率先走到链表的未尾。

        注意点：

                无论快指针一次走多少步，最终都会与慢指针相遇。并且快指针走了三步及以上步数，就会引入额外的代码步骤，所以一般快指针都是走两步。

        答案代码如下：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fast = head, *slow = head;while(fast && fast->next){if(fast == slow)return true;fast = fast->next->next;slow = slow->next;} return false;
}

9、环形链表 · 寻找环形起始点

        题目链接如下：

                https://leetcode.cn/problems/linked-list-cycle-ii/description/

        解题思路：

                解题原理：让⼀个指针从链表起始位置开始遍历链表，同时让⼀个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

                具体过程：设置快慢指针从环形链表的头节点开始遍历，慢指针走一步，快指针走两步，得到他们的相遇点并记录下来；然后设置两个速度相同的指针，一个从环形链表的头节点开始遍历，另一个从快慢指针的相遇点开始遍历，他们每次都是走一步；最终会在环形链表的循环起始点相遇。

        答案代码如下：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){ListNode* node = head;while(node != slow){node = node->next;slow = slow->next;}return slow;}}return NULL;
}

10、随机链表的复制

        题目链接如下：

                https://leetcode.cn/problems/copy-list-with-random-pointer/description/

        解题思路：

                原链表如下：

                ① 复制旧链表中的val值来创建新节点，插入到旧链表头节点之后的每个节点之间：

                ② 根据旧链表的 random 指针的关系来赋值给新节点的 random 指针：

                node->random = pcur->random->next; 若pcur->random指向空，直接让pcur->random指向空。

                ③ 断开新旧节点之间的联系。

        答案代码如下：

typedef struct Node node;node* Buy_node(int num)
{node* re = (node*)malloc(sizeof(node));re->val = num;re->next = re->random = NULL;return re;
}void Add_node(node* phead)
{node* phead_after = NULL;node* new_node = NULL;while(phead){new_node = Buy_node(phead->val);phead_after = phead->next; new_node->next = phead_after;phead->next = new_node;phead = phead_after;    }
}struct Node* copyRandomList(struct Node* head) 
{//处理传空指针的情况if(head == NULL)return NULL;//一、创建节点，并尾插在每个原节点的后面Add_node(head);//二、处理新节点的random指针node* pcur = head;node* copy = pcur->next;while(pcur->next->next)//这里条件结束后不能处理最后一个节点{if(pcur->random != NULL)copy->random = pcur->random->next;pcur = copy->next;copy = pcur->next;}if(pcur->random != NULL)copy->random = pcur->random->next;//三、断开新链表与旧链表的联系pcur = head;node* new_head = pcur->next, * new_tail = pcur->next;while(pcur->next->next){pcur = pcur->next->next;new_tail->next = pcur->next;new_tail = new_tail->next;}return new_head;
}

二、链表的分类

        链表的结构非常多样，以下情况组合起来就有八种链表结构：

        每种情况具体如下：

        

        虽然有这么多的链表结构，但实际中最常用的还是两种结构：单链表与双向链表。

        单链表的全称是：单向不带头不循环链表；

        双向链表的全称是：双向带头循环链表。

        双向链表与单链表完全不是同一类。

三、双向链表

（一）概念与结构

        带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”。

        双向链表的节点结构：数据 + 指向后一个节点的指针 + 指向前一个节点的指针。

        双向链表比单链表多的东西：哨兵节点 + 指向前一个节点的指针 + 双向循环。

（二）双向链表的实现

双向链表的编写：

① 头文件：定义双向链表的节点结构体，声明要提供的操作（起到目录作用）；

② cpp文件：编写具体实现各种操作（起到内容作用）；

③ 测试文件：测试是否可以正常运行。

List.h

#pragma once#include<stdlib.h>
#include<iostream>
#include<stdbool.h>
#include<assert.h>
using namespace std;typedef int LTDataType;
typedef struct LTNode
{LTDataType data;struct LTNode* prev;struct LTNode* next;}LTNode;//一、节点的创建并初始化、打印链表、判断头节点、查找节点、销毁链表
//(一)节点的创建并初始化
LTNode* Buy_node(LTDataType num);
//(二)链表的初始化
LTNode* LTInit();
//(三)打印链表
void LTPrint(LTNode* phead);
//(四)判断是否只有头节点
bool LTEmpty(LTNode* phead);
//(五)查找节点
LTNode* LTFine(LTNode* phead, LTDataType num);
//(六)销毁链表(是指整个链表都销毁，包括哨兵尾，会影响头指针)
void LTDestroy(LTNode*& phead);//二、节点的插入
//(一)尾插
void LTPushBack(LTNode* phead, LTDataType num);
//(二)头插
void LTPushFront(LTNode* phead, LTDataType num);
//(三)指定位置插入节点
void LTInsert(LTNode* pos, LTDataType num);
//(四)指定位置之后插入节点
void LTInsertAfter(LTNode* pos, LTDataType num);//三、节点的删除
//(一)尾删
void LTPopBack(LTNode* phead);
//(二)头删
void LTPopFront(LTNode* phead);
//(三)指定位置删除节点
void LTErase(LTNode*& pos);
//(四)指定位置之后删除节点
void LTEraseAfter(LTNode* pos);

List.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"//一、节点的创建、初始化、打印链表、判断头节点、查找节点、销毁链表
//(一)节点的创建并初始化
LTNode* Buy_node(LTDataType num)
{//节点的创建LTNode* new_node = (LTNode*)malloc(sizeof(LTNode));if (new_node == nullptr){perror("Buy_node malloc fail");exit(1);}//节点的初始化new_node->data = num;new_node->next = new_node->prev = new_node;return new_node;
}
//(二)链表的初始化
LTNode* LTInit()
{LTNode* plist = Buy_node(-1);return plist;
}
//(三)打印链表
void LTPrint(LTNode* phead) 
{LTNode* pcur = phead->next;cout << "-> ";while (pcur != phead){cout << pcur->data << " -> ";pcur = pcur->next;}cout << endl;
}
//(四)判断是否只有头节点
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}
//(五)查找节点
LTNode* LTFine(LTNode* phead, LTDataType num)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == num)return pcur;pcur = pcur->next;}return nullptr;
}
//(六)销毁链表
void LTDestroy(LTNode*& phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next_noed = pcur->next;//next_noed->prev = phead;//phead->next = next_noed;free(pcur);pcur = next_noed;}free(phead);pcur = phead = nullptr;
}//二、节点的插入
//(一)尾插
void LTPushBack(LTNode* phead, LTDataType num)
{LTNode* new_node = Buy_node(num);new_node->next = phead;new_node->prev = phead->prev;phead->prev->next = new_node;phead->prev = new_node;}
//(二)头插
void LTPushFront(LTNode* phead, LTDataType num)
{LTNode* new_node = Buy_node(num);new_node->next = phead->next;new_node->prev = phead;phead->next->prev = new_node;phead->next = new_node;}
//(三)指定位置插入节点
void LTInsert(LTNode* pos, LTDataType num)
{assert(pos);LTNode* new_node = Buy_node(num);LTNode* pre_node = pos->prev;new_node->next = pos;new_node->prev = pre_node;pos->prev = new_node;pre_node->next = new_node;}
//(四)指定位置之后插入节点
void LTInsertAfter(LTNode* pos, LTDataType num)
{assert(pos);LTNode* new_node = Buy_node(num);LTNode* after_node = pos->next;new_node->next = after_node;new_node->prev = pos;after_node->prev = new_node;pos->next = new_node;
}//三、节点的删除
//(一)尾删
void LTPopBack(LTNode* phead)
{assert(phead);//空指针不可删除，需要判断assert(!LTEmpty(phead));//判断是不是只有头节点LTNode* del = phead->prev;LTNode* pre = del->prev;pre->next = phead;phead->prev = pre;free(del);del = nullptr;
}
//(二)头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->next;LTNode* del_after = del->next;del_after->prev = phead;phead->next = del_after;free(del);del = nullptr;
}
//(三)指定位置删除节点
void LTErase(LTNode*& pos)
{assert(pos);LTNode* pre_node = pos->prev;LTNode* after_node = pos->next;pre_node->next = after_node;after_node->prev = pre_node;free(pos);pos = nullptr;
}
//(四)指定位置之后删除节点
void LTEraseAfter(LTNode* pos)
{assert(pos);LTNode* del = pos->next;LTNode* after_node = del->next;after_node->prev = pos;pos->next = after_node;free(del);del = nullptr;}
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"void test()
{LTNode* plist = Buy_node(-1);//LTPrint(plist);for (int i = 1; i < 11; i++)LTPushBack(plist, i);//LTPushFront(plist, i);LTPrint(plist);/*for (int i = 0; i < 5; i++)LTPopFront(plist);LTPrint(plist);*///LTNode* re_pos =  LTFine(plist, 10);//LTInsertAfter(re_pos, 255);//LTEraseAfter(re_pos);LTDestroy(plist);//LTPrint(plist);
}int main()
{ test();return 0;
}

        总结：

                ① 第一个节点指的是第一个有效的节点，而哨兵位是无效的节点（头节点）；

                ② 插入时修改节点的顺序：先修改插入的新节点，再修改前一个指针（head->prev ）和head指针的指向；（先改新节点，然后从后向前改 ）

                ③ 在哨兵位之前插入，也是尾插；

四、顺序表与链表的分析

        以上内容仅供分享，若有错误，请多指正。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1535119.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

软件设计师容易考吗？

软件设计师容易考吗？

一、软考软件设计师难吗 软考软件设计师考试对于不同的人来说&#xff0c;难度可能有所差异。然而&#xff0c;总体来说&#xff0c;软考软件设计师考试是相对较难的考试&#xff0c;需要考生具备扎实的软件设计理论知识和实践经验。 从各地2024年上半年软考合格人数的公布情…
阅读更多...
Autosar模式管理实战系列-COMM模块状态机及重要函数讲解

Autosar模式管理实战系列-COMM模块状态机及重要函数讲解

1.Channel状态管理 上一节提到ComM进行通信模式管理提供有两大状态机，另外一个就是Channel状态管理。这里的Channel指的是一个通信总线，目前项目主要是采用CAN总线。ComM 模块对每一个Channel都定义了一个状态机，用于描述通道的各种状态、状态转移关系和状态转移动作。该状…
阅读更多...
Blender插件200个分享

Blender插件200个分享

Blender不仅开源免费&#xff0c;插件资源也相当丰富&#xff0c;今天我们一起来看看blender软件的插件&#xff0c;其中群友给我整理提供了200多个&#xff0c;可供各位大佬享用&#xff01; PS&#xff1a;回“渲染101农场云渲码6666”&#xff0c;领取&#xff0c;大家懂滴…
阅读更多...
roctracer 的应用示例

roctracer 的应用示例

1&#xff0c;不用 roctracer 的普通场景 mt.cpp /* Copyright (c) 2018-2022 Advanced Micro Devices, Inc.Permission is hereby granted, free of charge, to any person obtaining a copyof this software and associated documentation files (the "Software")…
阅读更多...
✨机器学习笔记（四）—— 逻辑回归、决策边界、过拟合、正则化

✨机器学习笔记（四）—— 逻辑回归、决策边界、过拟合、正则化

Course1-Week3: https://github.com/kaieye/2022-Machine-Learning-Specialization/tree/main/Supervised%20Machine%20Learning%20Regression%20and%20Classification/week3机器学习笔记&#xff08;四&#xff09; 1️⃣逻辑回归&#xff08;logistic regression&#xff09;…
阅读更多...
element-plus表单使用show-overflow-tooltip，避免占满屏幕，需要设置宽度

element-plus表单使用show-overflow-tooltip，避免占满屏幕，需要设置宽度

在表单中&#xff0c;<el-table-clumn>中添加show-overflow-tooltip&#xff0c;可以实现表格内容过多的问题。 属性官方解释&#xff1a;是否隐藏额外内容并在单元格悬停时使用 Tooltip 显示它们。 出现的问题&#xff1a; 使用了该属性之后&#xff0c;弹出的详细内…
阅读更多...
反射动态代理

反射动态代理

1. 反射 1.1 反射的概述&#xff1a; **专业的解释&#xff08;了解一下&#xff09;&#xff1a;**是在运行状态中&#xff0c;对于任意一个类&#xff0c;都能够知道这个类的所有属性和方法&#xff1b;对于任意一个对象&#xff0c;都能够调用它的任意属性和方法&#xff…
阅读更多...
【Linux实践】实验二：LINUX操作基础

【Linux实践】实验二：LINUX操作基础

【Linux实践】实验二&#xff1a;LINUX操作基础 实验目的实验内容实验步骤及结果1. 打开终端2. 关闭计算机命令3. 查看帮助文档4. 修改计算机主机名5. 显示月历和时间6. 统计行数、字符数、单词数 这章开始要涉及到命令了&#xff0c;其他关于命令的内容可以看我 2021年写的笔记…
阅读更多...
非金属失效与典型案例分析培训

非金属失效与典型案例分析培训

随着生产和科学技术的发展&#xff0c;人们不断对高分子材料提出各种各样的新要求。因为技术的全新要求和产品的高要求化&#xff0c;而客户对产品的高要求及工艺理解不一&#xff0c;于是高分子材料断裂、开裂、腐蚀、变色等之类失效频繁出现&#xff0c;常引起供应商与用户间…
阅读更多...
无人机几种常见的避障系统！！！

无人机几种常见的避障系统！！！

1. 视觉避障系统 工作原理&#xff1a; 视觉避障系统通过安装在无人机上的摄像头捕捉周围环境的图像&#xff0c;利用计算机视觉技术对图像进行处理和分析&#xff0c;提取出障碍物的信息。 通过对障碍物的识别和分类&#xff0c;无人机可以判断出障碍物的性质和危险程度&am…
阅读更多...
人工智能+数字孪生技术在智慧型项目中的应用研究(Word原件)

人工智能+数字孪生技术在智慧型项目中的应用研究(Word原件)

1　基于BIM的智慧社区运维管理信息系统构建 1.1　数据存储 1.2　数据交换 1.3　BIM模型的数据整合及轻量化 1.运维BIM模型 2.BIM模型的数据整合 3.BIM模型的轻量化处理 2　GIS与BIM融合数字孪生技术应用 2.1　BIM模型在实景三维GIS平台上分析 2.2　BIM与GIS数据交互 …
阅读更多...
汽车租赁系统1.0版本

汽车租赁系统1.0版本

汽车租赁系统1.0版本比较简陋&#xff0c;以后还会有2.0、3.0……就像《我爱发明》里面的一代机器二代机器&#xff0c;三代机器一样&#xff0c;是一个迭代更新的过程&#xff08;最近比较忙&#xff0c;可能会很久&#xff09;&#xff0c;这个1.0版本很简陋&#xff0c;也请…
阅读更多...
电阻、电容、电感的封装大小分别与什么参数有关？

电阻、电容、电感的封装大小分别与什么参数有关？

电阻封装大小与电阻值、额定功率有关&#xff1b; 电容封装大小与电容值、额定电压有关&#xff1b; 电感封装大小与电感量、额定电流有关。
阅读更多...
7. qml按键最优解

7. qml按键最优解

目录 qml自带按键状态按键长按按键延时按键防抖按键 qml自带按键 官网列出了他扩展的按键派生与AbstractButton Button CheckBox DelayButton ltemDelegate MenuBarltem Menultem RadioButton switch TabButton 一般开发的过程中根据业务的不同进行选择 AbstractButton 状态按…
阅读更多...
Linux云计算 |【第三阶段】PROJECT1-DAY3

Linux云计算 |【第三阶段】PROJECT1-DAY3

主要内容&#xff1a; Keepalived高可用、部署Ceph分布式存储 一、网站架构进阶项目案例 案例1&#xff1a;Keepalived高可用 延续 PROJECT1-DAY2 案例&#xff0c;部署两台代理服务器&#xff0c;实现如下效果&#xff1a; 1&#xff09;利用keepalived实现两台代理服务器的…
阅读更多...
测试通用面试题大全

测试通用面试题大全

24年软件测试的发展如何&#xff1f; 1、IT行业还会继续升温&#xff0c;高质量人才需求相对还是短缺。 2、要求变高之后&#xff0c;很难再下降了&#xff0c;学历和经验。 3、功能测试之外的东西&#xff0c;接口、性能和自动化要掌握一点。 4、长远来看&#xff0c;软件…
阅读更多...
Idea springboot项目热部署

Idea springboot项目热部署

使用 spring-boot-devtools spring-boot-devtools 是 Spring Boot 提供的开发工具模块&#xff0c;它可以自动检测到代码的变化并重启应用&#xff0c;实现热部署。 配置步骤&#xff1a; 添加依赖&#xff1a; 在项目的 pom.xml 中加入 spring-boot-devtools 依赖&#xff1…
阅读更多...
做海外问卷渠道查，你必备的几个答题工具（缺一不可，建议收藏）

做海外问卷渠道查，你必备的几个答题工具（缺一不可，建议收藏）

大家好&#xff0c;我是金言问卷。 近几年&#xff0c;随着我国经济的下行&#xff0c;越来越多的人开始寻求互联网上的创收机会。在这个背景下&#xff0c;海外问卷渠道查也成为一个备受关注的小众项目。 本文将为你揭秘&#xff0c;入局海外问卷渠道查必备的几个工具&#…
阅读更多...
电学基础概念详解及三相电公式汇总

电学基础概念详解及三相电公式汇总

​​​​​​​ 本文全面介绍了电路的基本组成、电学核心概念以及三相电的常用公式。首先&#xff0c;通过水力学中的现象类比&#xff0c;生动解释了电路中电池、开关、电阻和灯泡等元素的功能&#xff0c;帮助读者更好地理解电压、电流和电阻之间的关系。随后&#xff0c;详…
阅读更多...
Sparse4D v1

Sparse4D v1

Sparse4D: Multi-view 3D Object Detection with Sparse Spatial-Temporal Fusion Abstract 基于鸟瞰图 (BEV) 的方法最近在多视图 3D 检测任务方面取得了重大进展。与基于 BEV 的方法相比&#xff0c;基于稀疏的方法在性能上落后&#xff0c;但仍然有很多不可忽略的优点。为了…
阅读更多...
最新文章

Copyright @ 2022~2023