首页 > 其他分享 >数据结构~~链表

数据结构~~链表

时间:2024-09-30 22:55:18浏览次数:11  
标签:pphead SLTNode cur next 链表 phead 数据结构

目录

一、链表的概念

二、单链表

1.单链表的结构

2.单链表的接口实现 

2.1、动态申请节点

2.2、单链表打印 

2.3、摧毁单链表 

2.4、单链表尾插 

2.5、单链表的头插 

2.6、单链表的尾删 

2.7、单链表的头删 

2.8、单链表在pos位置之前插入x

2.9、单链表删除pos位置的值

2.10、单链表查找

三、双链表

1.双链表的结构

2.双链表的接口实现 

2.1、动态申请节点

2.2、双链表打印 

2.3、摧毁双链表 

2.4、双链表的尾插

2.5、双链表的头插 

2.6、双链表的尾删 

2.7、双链表的头删 

2.8、双链表在pos位置之前插入x

2.9、双链表删除pos位置的值

2.10、双链表查找

2.11、判断双链表是否为空 

四、关于链表的练习

1.环形链表

2.环形链表plus

3.随机链表的复制

五、完整代码

单链表

双链表

六、总结


一、链表的概念

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

1.从图上看出链式结构在逻辑上是连续的,但是在物理上不一定连续

2.现在中的结点一般都是从堆申请出来的

3. 从堆申请的空间,两次申请的空间可能连续,也可能不连续

链表的分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:

1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。

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

二、单链表

单链表就是无头+单向+非循环链表

1.单链表的结构

typedef int SLTDataType;
typedef struct SListNode      //定义一个链表节点
{
	SLTDataType data;         //结点的数据
	struct SListNode* next;   //指向下一个节点
}SLTNode;

2.单链表的接口实现 

2.1、动态申请节点
SLTNode* SLBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
2.2、单链表打印 
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
2.3、摧毁单链表 
void SLDesty(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
2.4、单链表尾插 

分两种情况:1.若链表为空链表,直接将该节点作为头节点;

                      2.若链表不为空,遍历链表到尾结点,在尾插。

void SLPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLBuyNode(x);
	if (*pphead==NULL)
	{
		*pphead = newnode;
		return;
	}
	else 
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = NULL;
	}
	
}
2.5、单链表的头插 
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLBuyNode(x);
	newnode->data = x;
	newnode->next = NULL;

	newnode->next = *pphead;
	*pphead = newnode;
}

2.6、单链表的尾删 
void SLPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//法1
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
		//法2:
		/*SLTNode* tail=*pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}
}

2.7、单链表的头删 
void SLPopFront(SLTNode** pphead)
{
	assert(*pphead);
	/*if ((*pphead)->next == NULL)  //法1
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* del = *pphead;
		*pphead = del->next;
		free(del);
		del = NULL;
	}*/
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
}

2.8、单链表在pos位置之前插入x
void SLInsert(SLTNode** pphead,SLTNode*pos,SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = SLBuyNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.9、单链表删除pos位置的值
void SLEarst(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

2.10、单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

三、双链表

双链表就是带头+双向+循环链表

1.双链表的结构

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next; //上一个结点
	struct ListNode* prev; //下一个结点
	LTDataType data;
}LTNode;

2.链表的接口实现 

2.1、动态申请节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("err malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
2.2、双链表打印 
void LTPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	printf("head<<->>");
	while (cur != phead)
	{
		printf("%d<<->>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
2.3、摧毁双链表 
void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
2.4、双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

2.5、双链表的头插 
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}

2.6、双链表的尾删 
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

2.7、双链表的头删 
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;  
	LTNode* second = del->next;
	free(del);
	second->prev = phead;
	phead->next = second;

}

2.8、双链表在pos位置之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	pos->prev = newnode;
	newnode->next = pos;
	prev->next = newnode;
	newnode->prev = prev;

}

2.9、双链表删除pos位置的值
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);

}

2.10、双链表查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
2.11、判断双链表是否为空 
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

四、关于链表的练习

1.环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

思路:使用两个指针,一个快指针(每次移动两步)和一个慢指针(每次移动一步)。如果链表中有环,那么快指针最终会追上慢指针。

 在使用快慢指针判断链表是否有环时,如果链表中存在环,那么快指针最终会追上慢指针。

这是因为快指针每次移动两步,而慢指针每次移动一步。当快指针进入环后,它会在环内不断循环,而慢指针则会逐渐靠近环。由于快指针的速度是慢指针的两倍,所以它们之间的距离会逐渐缩小,最终快指针会追上慢指针。

需要注意的是,这种方法的前提是链表中存在环。如果链表是线性的,那么快指针最终会到达链表的尾部,而慢指针则会到达链表的末尾,它们不会相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
          return true;
    }
    return false;
}

 为什么一定会相遇,有没有可能会错过,永远追不上?

假设slow进环时,fast跟slow距离是N,fast追击slow的过程为

1.N是偶数,第一轮就追上了

2.N是奇数,第一轮追击会错过,距离变成C-1(C是环的长度)

    2.1、如果C-1是偶数,下一轮就追上了

    2.2、如果C-1是奇数,那么就永远追不上

3.N是奇数时,C也是奇数

   N是偶数时,C也是偶数

结论:一定会追上

N是偶数第一轮就追上了

N是奇数第一轮追不上,C-1是偶数第二轮就追上了

2.环形链表plus

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路:先使用快慢指针判断链表是否有环。如果有环,再找到环的入口。具体做法是,当快慢指针相遇时,将慢指针重新指向头节点,然后让快慢指针以相同的速度移动,它们再次相遇的节点就是环的入口.

 要确定链表中环的入口节点,可以按照以下步骤进行:

1. 使用快慢指针(一个指针每次移动一步,另一个指针每次移动两步)在链表中移动。

2. 当快慢指针相遇时,说明存在环。

3. 此时,将慢指针重新指向链表头部。

4. 然后让慢指针和快指针同时以每次移动一步的速度继续移动,它们再次相遇的节点就是环的入口节点。

这是因为当快慢指针相遇时,慢指针在环中走的距离是快指针的一半,此时将慢指针移回头部,再同步移动,它们再次相遇的位置就是环的入口。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode* meet=slow;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}
3.随机链表的复制

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

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

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

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

 思路:

1.首先创建一个新的链表,逐个节点进行复制。
2. 在复制节点时,同时处理随机指针的复制,通过遍历原链表找到对应的随机节点在新链表中的位置

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        struct Node* next=cur->next;
        cur->next=copy;
        copy->next=next;
        cur=next;
    }
    cur=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;
    struct Node*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;
}

五、完整代码

SList · JiaWei/TU数据结构 - 码云 - 开源中国 (gitee.com)https://gitee.com/jjawei/tu-data-structure/tree/master/SListList · JiaWei/TU数据结构 - 码云 - 开源中国 (gitee.com)https://gitee.com/jjawei/tu-data-structure/tree/master/List

单链表

SList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead); //打印
void SLPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾插
SLTNode* SLBuyNode(SLTDataType x);//malloc 扩容

void SLPopFront(SLTNode** pphead);  //头删
void SLPopBack(SLTNode** pphead);   //尾删

SLTNode* STFind(SLTNode* phead, SLTDataType x);//找

void SLInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);//pos 之前 插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);//pos 之后插入
void SLEarst(SLTNode** pphead, SLTNode* pos);//pos 之前 删除
void SLEarstAfter(SLTNode* pos);//pos 之后删除

void SLDesty(SLTNode** pphead);//摧毁链表

SList.c

#include"SList.h"

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
SLTNode* SLBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc err");
		return;//(SLTNode*)1;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLBuyNode(x);
	newnode->data = x;
	newnode->next = NULL;

	newnode->next = *pphead;
	*pphead = newnode;
}
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLBuyNode(x);
	if (*pphead==NULL)
	{
		*pphead = newnode;
		return;
	}
	else 
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = NULL;
	}
	
}
void SLPopFront(SLTNode** pphead)
{
	assert(*pphead);
	/*if ((*pphead)->next == NULL)  //法1
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* del = *pphead;
		*pphead = del->next;
		free(del);
		del = NULL;
	}*/
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
}

void SLPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//法1
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
		//法2:
		/*SLTNode* tail=*pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}
}
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SLInsert(SLTNode** pphead,SLTNode*pos,SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = SLBuyNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLEarst(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
void SLEarstAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;

}
void SLDesty(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
双链表

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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

LTNode* LTInit();
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);

void LTPrint(LTNode* phead);

void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
LTNode* BuyLTNode(LTDataType x);
LTNode* LTFind(LTNode*phead,LTDataType x);

void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);

void LTDestroy(LTNode* phead);

List.c

#include"List.h"
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("err malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
void LTPrint(LTNode* phead)
{
	LTNode* cur = phead->next;
	printf("head<<->>");
	while (cur != phead)
	{
		printf("%d<<->>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyLTNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* first = phead->next;  
	LTNode* second = first->next;
	free(first);
	second->prev = phead;
	phead->next = second;

}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
	pos->prev = newnode;
	newnode->next = pos;
	prev->next = newnode;
	newnode->prev = prev;

}
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);

}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

六、总结

关于单链表为什么要传二级指针:

在数据结构中,链表之所以要使用二级指针,是因为链表中的每个节点都是一个包含数据和指向下一个节点的指针的结构体,而每个节点的地址都是动态分配的。如果传入的是一级指针,函数内部只能访问到该节点的数据部分,而无法修改该节点的指针部分,也无法修改链表的结构。因此,需要传递二级指针,函数内部通过修改该指针所指向的内存中的值,即头节点的指针,来改变链表的结构。

在单链表中需要传递二级指针的原因主要有以下几点:

1. 修改链表头指针:当需要在函数中对单链表的头指针进行修改时,如果只传递一级指针,那么在函数内部对指针的修改不会影响到函数外部的原始链表头指针。使用二级指针可以在函数内部直接修改原始链表的头指针。

2.而双链表通常不需要传递二级指针,可能是因为双链表的结构相对更复杂,操作方式和逻辑与单链表有所不同,在某些情况下可以通过其他方式来实现对链表的修改和操作。

需要注意的是,这只是一般情况,具体的实现和需求可能会因具体的编程场景和设计而有所差异。

顺序表和链表的差别:

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

标签:pphead,SLTNode,cur,next,链表,phead,数据结构
From: https://blog.csdn.net/2301_78029441/article/details/142665044

相关文章

  • redis的数据结构,内存处理,缓存问题
    redisObjectredis任意数据的key和value都会被封装为一个RedisObject,也叫redis对象:这就redis的头信息,占有16个字节redis中有两个热门数据结构1.SkipList,跳表,首先是链表,和普通链表有以下差异:元素按照升序排列存储节点可能包含多个指针,指针跨度不同那么跳表的特点有以下:......
  • 信息学奥赛复赛复习07-CSP-J2020-03表达式前置知识点-结构体、链表、链式前向星
    PDF文档公众号回复关键字:2024093012020CSP-J题目1优秀的拆分[题目描述]链式前向星模板题,读入n个点,m条边,以及flag,若flag==1则图有向,否则无向。对每个点输出它的每一条边[输入格式]第一行三个数n,m,flag,题意如上所示第2~1+m行,每行三个数,x,y,z,代表从x到y有一条长为z的......
  • 【hot100-java】【合并两个有序链表】
    记忆中,两个指针合并即可。 建立哨兵节点dum/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(intval){this.val=val;}*ListNode(intval,ListNodenext......
  • 【数据结构】链表(2)
     【LinkedList的模拟实现】这是java中的一个集合类,可以当成链表来使用,作为链表时,它视为包含三个域,是一个双向链表【构建LinkedList框架】publicclassMyLinkedList{staticclassListNode{publicintval;publicListNodeprev;//前驱......
  • Scala数据结构简单介绍
    数据结构的定义: 1.数组(Array)    (1)定义:        定长数组:newArray[T](数组长度)        变长数组:ArrayBuffer[T]()    (2)示例:        定长数组:valarr1=newArray[Int](3)        变长数组(需提前导包):valarr2=Arr......
  • 203_移除链表元素
    203_移除链表元素【问题描述】给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例一:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例二:输入:head=[],val=1输出:[]示例三:输入:head=[7,7,7......
  • 数据结构:基本概念及术语
    一、基本概念        在数据结构中,有这样一些基本概念:数据、数据元素、数据项、数据对象,对于它们的具体含义我就不赘述了,在这就简要说明一下它们之间的关系:    首先,我们可以把数据看成一个大集合,那数据元素就相当于这个集合中的一个个元素,然后一些性质相同的......
  • 97th 2024/8/26 树形数据结构小结
    精锐线段树\(\big/\)平衡树综合题目五步取首1、每个节点需要维护的信息有?可从题目要求的目标或经推导后得到的要求的目标得到如对于括号序列这一题,将"("转化为-1,")"转化为1后,要求的答案就变成了最大前缀和和最小后缀和然后就变成了平衡树板题(区间赋值,反转,翻转)2、需要的标记......
  • c语言实现:链表创建、插入、删除、翻转
    #include<stdio.h>#include<stdlib.h>//链表创建typedefstructNode{intdata;structNode*next;}Node;//创建一个节点Node*createNode(intdata){Node*newNode=(Node*)malloc(sizeof(Node));newNode->data=data;newNode......
  • 【Redis基础篇】超详细♥Redis安装教程、5种常用数据结构和常见命令、Jedis和SpringDa
    文章目录一、Redis与客户端安装教程1、NoSQL介绍(1)结构化与非结构化(2)关联和非关联(3)查询方式(4)事务(5)总结2、Redis介绍3、安装Redis(1)依赖库(2)上传安装包并解压(3)Redis三种启动方式①默认启动②指定配置启动③开机自启4、Redis客户端(1)Redis命令行客户端(2)图形化桌面客户端(3......