文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >专栏 >数据结构与算法（链表）

数据结构与算法（链表）

作者头像
风中的云彩
发布于 2024-11-07 13:52:06
发布于 2024-11-07 13:52:06
14700
代码可运行
举报
文章被收录于专栏：C/C++的自学之路C/C++的自学之路
运行总次数：0
代码可运行
关联问题
换一批

我可以接受失败，但绝对不能接受未奋斗过的自己。

前言

这是我学习数据结构的第三份笔记，有关链表的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有关顺序表，没看过的同学可以去看看： 有关顺序表的笔记

链表

链表的概念

1. 链表是⼀种物理存储结构上非连续、非顺序的存储结构。 2. 链表是线性表的一种，所以它一定在逻辑结构上是线性的。 3. 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 4. 链表实际上由一个个节点和头指针组成。

链表的分类

1. 链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构。 2. 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表。

  1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
  2. 带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

结点的概念

1. 结点的组成主要有两个部分：当前结点要保存的数据和下⼀个结点的地址（指向下一个节点的指针）。 2. 链表中每个结点都是独立申请的，即需要插入数据时才去申请⼀块结点的空间。 3. 我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。 4. 两个节点之间的地址不一定是连续的。

头指针

1. 我们在创建一个链表时，其实是创建了一个指向这个链表的头指针。 2. 我们使用指向不同链表的头指针来区分不同链表。 3. 由于我们用头指针来表示链表，所以我们在修改链表时候，传入的是头指针的地址。 4. 如果是单链表，那么头指针指向第一个节点；如果是双链表，那么头指针指向头节点。

头节点

1. 头节点在数据结构中，特别是在链表中，有着特殊的作用。它的主要目的是简化链表操作的边界条件处理。 2. 因为头节点的存在，所以不需要单独处理空链表或者在第一个元素上插入、删除的情况。 3. 头节点和第一个节点是两个概念。

单链表（不带头单向不循环链表）

定义单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
typedef int LTDataType
typedef struct SListNode
{
	LTDataType data; //节点数据
	struct SListNode* next; //指针变量指向下一个节点
}SListNode;
//SListNode==Single List Node 单链表节点
创建新的节点
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
SListNode* AddSListNode(SLTDataType x)
{
	SListNode* node=(SListNode*)malloc(sizeof(SListNode));
    //链表在物理结构上可以是非线性的，所以只需要直接开辟新的节点就行，所以用malloc。
    //这里开辟一个节点空间，所以用SListNode* node。
    //而线性表是开辟一个动态数组空间，所以是int* node。
	node->data = x;
	node->next = NULL;
	return node;//返回一个指向新节点的指针
}
打印单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void PrintSListNode(SListNode* phead)//不需要对原来的链表进行修改，所以只要传值。
{
    assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
    //打印链表的话，至少要求链表里面有节点
	SListNode* purc = phead;
	while (purc != NULL)//去遍历链表
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
	printf("NULL\n");
}
尾插单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void BackPushSListNode(SListNode** pphead, SLTDataType x)
//一条链表需要用最前面的头指针来表示，又由于需要对于链表进行修改，所以传入头指针的地址。
{
    //插入的时候不需要一定要求链表里面有节点，所以不用assert()断言。
    //但是需要分有节点和无节点进行讨论
	SListNode* newnode = AddSListNode(x);
	SListNode* purc = *pphead;//一般不能用头节点直接去遍历。需要新命名一个节点专门去遍历
	if (*pphead == NULL)//如果链表里面没有节点
	{
		*pphead = newnode;
	}
	else//如果链表里面有节点
	{
		while (purc->next != NULL)
		{
			purc = purc->next;
		}
		purc->next = newnode;
	}
}
头插单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void FrontPushSListNode(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = AddSListNode(x);
    if (*pphead == NULL)//如果链表里面没有节点
	{
		*pphead = newnode;
	}
	else//如果链表里面有节点
    {
	    newnode->next = *pphead;//把新节点的指针指向原来链表中的第一个节点
	    *pphead = newnode;//把头指针指向新节点
    }
}
单链表指定位置前插入节点
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void InsertSListNode(SListNode** pphead, SListNode* pos, SLTDataType x)
//在指定位置pos之前插入新节点
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
    assert(pos);
	SListNode* newnode=AddSListNode(x);
	SListNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}
单链表指定位置后插入节点
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void SListNodeInsert(SListNode* pos, SLTDataType x)
//在指定位置之后插入新节点
{
    assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
	assert(pos);
	SListNode* newnode = AddSListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
尾删单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void BackPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	SListNode* ptail = *pphead;
	SListNode* prev = NULL;
	if (ptail->next == NULL)//链表中只有一个节点时
	{
		free(ptail);
		ptail = NULL;
	}
	else//链表中不只有一个节点时
	{
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
        //此时，ptail保存的是最后一个节点的地址
        //此时，prev保存的是倒数第二个节点的地址
		prev->next = NULL;//确保倒数第二个节点的指针指向空
		free(ptail);//释放最后一个节点的地址
		ptail = NULL;//把ptail指向NULL，防止形成野指针
	}
}
头删单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void FrontPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	if ((*pphead)->next == NULL)//链表中只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}
指定删除单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void DeleteSListNode(SListNode** pphead, SListNode* pos)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	assert(pos);
	SListNode* prev = *pphead;
    if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
    else
    {
	    while (prev->next != pos)
	    {
		    prev = prev->next;
	    }
	    prev->next = pos->next;
	    free(pos);
	    pos = NULL;
    }
}
搜索单链表节点
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
SListNode* SearchSListNode(SListNode* phead, SLTDataType x)
{
	assert(phead);//搜索链表时候，需要确保链表里面至少有一个节点
	SListNode* purc = phead;
	while (purc)
	{
		if (purc->data == x)
		{
			printf("找到了。\n");
			return purc;
		}
		else
		{
			purc = purc->next;
		}
	}
	printf("没找到。\n");
}
销毁单链表
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void DestroySListNode(SListNode** pphead)
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	SListNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur!=NULL)
		{
			SListNode* next = pcur->next;
			free(pcur);
			pcur = next;
		}
	}
	*pphead = NULL;
}

单链表实现代码

<test.h>文件

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SLTNode* next;
}SListNode;
void PrintSListNode(SListNode* phead);
void BackPushSListNode(SListNode** pphead, SLTDataType x);
SListNode* AddSListNode(SLTDataType x);
void FrontPushSListNode(SListNode** pphead, SLTDataType x);
void BackPopSListNode(SListNode** pphead);
void FrontPopSListNode(SListNode** pphead);
SListNode* SearchSListNode(SListNode* phead, SLTDataType x);
void InsertSListNode(SListNode** pphead, SListNode* pos, SLTDataType x);
void STLNodeSListNode(SListNode** pphead, SListNode* pos, SLTDataType x);
void DeleteSListNode(SListNode** pphead, SListNode* pos);
void DestroySListNode(SListNode** pphead);

<test.c>文件

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#include "test.h"
void PrintSListNode(SListNode* phead)//不需要对原来的链表进行修改，所以只要传值。
{
    assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
    //打印链表的话，至少要求链表里面有节点
	SListNode* purc = phead;
	while (purc != NULL)//去遍历链表
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
	printf("NULL\n");
}

SListNode* AddSListNode(SLTDataType x)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	//链表在物理结构上可以是非线性的，所以只需要直接开辟新的节点就行，所以用malloc。
	//这里开辟一个节点空间，所以用SListNode* node。
	//而线性表是开辟一个动态数组空间，所以是int* node。
	node->data = x;
	node->next = NULL;
	return node;//返回一个指向新节点的指针
}

void BackPushSListNode(SListNode** pphead, SLTDataType x)
//一条链表需要用最前面的头指针来表示，又由于需要对于链表进行修改，所以传入头指针的地址。
{
    //插入的时候不需要一定要求链表里面有节点，所以不用assert()断言。
    //但是需要分有节点和无节点进行讨论
	SListNode* newnode = AddSListNode(x);
	SListNode* purc = *pphead;//一般不能用头节点直接去遍历。需要新命名一个节点专门去遍历
	if (*pphead == NULL)//如果链表里面没有节点
	{
		*pphead = newnode;
	}
	else//如果链表里面有节点
	{
		while (purc->next != NULL)
		{
			purc = purc->next;
		}
		purc->next = newnode;
	}
}

void FrontPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	if ((*pphead)->next == NULL)//链表中只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}

void BackPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	SListNode* ptail = *pphead;
	SListNode* prev = NULL;
	if (ptail->next == NULL)//链表中只有一个节点时
	{
		free(ptail);
		ptail = NULL;
	}
	else//链表中不只有一个节点时
	{
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
        //此时，ptail保存的是最后一个节点的地址
        //此时，prev保存的是倒数第二个节点的地址
		prev->next = NULL;//确保倒数第二个节点的指针指向空
		free(ptail);//释放最后一个节点的地址
		ptail = NULL;//把ptail指向NULL，防止形成野指针
	}
}

void FrontPopSListNode(SListNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)//链表中只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}

SListNode* SearchSListNode(SListNode* phead, SLTDataType x)
{
	assert(phead);//搜索链表时候，需要确保链表里面至少有一个节点
	SListNode* purc = phead;
	while (purc)
	{
		if (purc->data == x)
		{
			printf("找到了。\n");
			return purc;
		}
		else
		{
			purc = purc->next;
		}
	}
	printf("没找到。\n");
}

void InsertSListNode(SListNode** pphead, SListNode* pos, SLTDataType x)
//在指定位置pos之前插入新节点
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
    assert(pos);
	SListNode* newnode=AddSListNode(x);
	SListNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

void SListNodeInsert(SListNode* pos, SLTDataType x)
//在指定位置之后插入新节点
{
    assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
	assert(pos);
	SListNode* newnode = AddSListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void DeleteSListNode(SListNode** pphead, SListNode* pos)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	assert(pos);
	SListNode* prev = *pphead;
    if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
    else
    {
	    while (prev->next != pos)
	    {
		    prev = prev->next;
	    }
	    prev->next = pos->next;
	    free(pos);
	    pos = NULL;
    }
}

void DestroySListNode(SListNode** pphead)
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	SListNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur!=NULL)
		{
			SListNode* next = pcur->next;
			free(pcur);
			pcur = next;
		}
	}
	*pphead = NULL;
}

int main()
{
	SListNode* plist = NULL;
	BackPushSListNode(&plist, 2);
	BackPushSListNode(&plist, 3);
	BackPushSListNode(&plist, 4);
	FrontPushSListNode(&plist, 1);
	//Back_Pop_STLNode(&plist);
	//Front_Pop_STLNode(&plist);
	SListNode* pos1 = SearchSListNode(plist, 3);
	InsertSListNode(&plist, pos1, 9);
	SListNodeInsert(pos1, 8);
	DeleteSListNode(&plist, pos1);
	//Destroy_STLNode(&plist);
	PrintSListNode(plist);
	return 0;
}

1. 单链表在已知一个节点的情况下，如果需要找到上一个节点，则需要从头开始遍历；如果需要找到下一个节点，则根据指针可以直接找到。

双向链表 （带头双向循环链表）

定义双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

创建新的节点

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
ListNode* CreateListNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

插入头节点

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void InitListNode(ListNode** pphead)
//由于要改变phead指针的指向，所以要传入phead的地址，即使用ListNode** pphead。
{
	*pphead = CreateListNode(-1);//头指针指向头节点（不存储有效数据的节点）
}

打印双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void PrintListNode(ListNode* phead)
{
    assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
}

尾插双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void BcakPushListNode(ListNode* phead, DataType x)
//由于phead已经指向头节点，所以不再需要改变phead指向，所以使用ListNode* phead。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	ListNode* prev = phead;
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;//尾节点的表示：phead->prev
	phead->prev = newnode;
}

头插双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void FrontPushListNode(ListNode* phead, DataType x)
//头插指的是，往头节点后面插入一个节点（第一个节点之前）。
//如果往头节点前面插入一个节点，那么本质上是尾插。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

判断双向链表是否为空

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
bool IsEmpty(ListNode* phead)
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	return (phead->next != phead);//除去头节点外，必须有第一个节点才算非空双向链表。
}

尾删双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void BcakPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _prev = phead->prev->prev;
	ListNode* _pop = phead->prev;
	_prev->next = phead;
	phead->prev = _prev;
	free(_pop);
	_pop = NULL;
}

头删双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void FrontPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _second = phead->next->next;
	ListNode* _first = phead->next;
	phead->next = _second;
	_second->prev = phead;
	free(_first);
	_first = NULL;
}

双向链表任意位置查找节点

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
ListNode* FindListNode(ListNode* phead, DataType x)
{
	assert(IsEmpty(phead));//查找链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		if (purc->data == x)
		{
			return purc;
		}
		purc = purc->next;
	}
	return NULL;
}

指定位置之后插入节点

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void ListNodeInsert(ListNode* pos, DataType x)
{
    assert(IsEmpty(phead));//指定位置插入节点的话，至少要求链表里面那个位置上有节点
	assert(pos);//确保是一个节点地址
	ListNode* newnode = CreateListNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

指定位置删除节点

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void ListNodePop(ListNode* pos)
{
	assert(pos);//确保是一个节点地址
	assert(IsEmpty(pos));//指定位置删除节点的话，至少要求链表里面那个位置上有节点
	ListNode* _prev = pos->prev;
	ListNode* _next = pos->next;
	_prev->next = _next;
	_next->prev = _prev;
	free(pos);
	pos=NULL;
}

销毁双向链表

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void DestroyListNode(ListNode** pphead)
{
	assert(IsEmpty(*pphead));
    //要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* purc = (*pphead)->next;
	while (purc != *pphead)
	{
		ListNode* next = purc->next;
		free(purc);
		purc = next;
	}
	free(purc);
	purc = NULL;
	*pphead = NULL;
}

双链表实现代码

<list.h>文件

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

//创建新的节点
ListNode* CreateListNode(DataType x);

//初始化节点
void InitListNode(ListNode** pphead);

//尾插
void BcakPushListNode(ListNode* phead, DataType x);

//头插
void FrontPushListNode(ListNode* phead, DataType x);

//打印链表
void PrintListNode(ListNode* phead);

//判断链表是否为空
bool IsEmpty(ListNode* phead);

//尾删
void BcakPopListNode(ListNode* phead);

//头删
void FrontPopListNode(ListNode* phead);

//查找节点
ListNode* FindListNode(ListNode* phead, DataType x);

//任意位置插入节点
void ListNodeInsert(ListNode* pos, DataType x);

//任意位置删除节点
void ListNodePop(ListNode* pos);

//销毁链表
void DestroyListNode(ListNode** pphead);

<test.c>文件

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#include "list.h"

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

void InitListNode(ListNode** pphead)//由于要改变phead指针的指向，所以要传入phead的地址，即使用ListNode** pphead。
{
	*pphead = CreateListNode(-1);//头指针指向头节点（不存储有效数据的节点）
}

void BcakPushListNode(ListNode* phead, DataType x)
//由于phead已经指向头节点，所以不再需要改变phead指向，所以使用ListNode* phead。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	ListNode* prev = phead;
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;//尾节点的表示：phead->prev
	phead->prev = newnode;
}

void FrontPushListNode(ListNode* phead, DataType x)
//头插指的是，往头节点后面插入一个节点（第一个节点之前）。
//如果往头节点前面插入一个节点，那么本质上是尾插。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

void PrintListNode(ListNode* phead)
{
    assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
}

bool IsEmpty(ListNode* phead)
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	return (phead->next != phead);//除去头节点外，必须有第一个节点才算非空双向链表。
}

void BcakPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _prev = phead->prev->prev;
	ListNode* _pop = phead->prev;
	_prev->next = phead;
	phead->prev = _prev;
	free(_pop);
	_pop = NULL;
}

void FrontPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _second = phead->next->next;
	ListNode* _first = phead->next;
	phead->next = _second;
	_second->prev = phead;
	free(_first);
	_first = NULL;
}

ListNode* FindListNode(ListNode* phead, DataType x)
{
	assert(IsEmpty(phead));//查找链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		if (purc->data == x)
		{
			return purc;
		}
		purc = purc->next;
	}
	return NULL;
}

void ListNodeInsert(ListNode* pos, DataType x)
{
    assert(IsEmpty(phead));//指定位置插入节点的话，至少要求链表里面那个位置上有节点
	assert(pos);//确保是一个节点地址
	ListNode* newnode = CreateListNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

void ListNodePop(ListNode* pos)
{
	assert(IsEmpty(phead));//指定位置删除节点的话，至少要求链表里面那个位置上有节点
	assert(pos);//确保是一个节点地址
	ListNode* _prev = pos->prev;
	ListNode* _next = pos->next;
	_prev->next = _next;
	_next->prev = _prev;
	free(pos);
	pos=NULL;
}

void DestroyListNode(ListNode** pphead)
{
	assert(IsEmpty(*pphead));
    //要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* purc = (*pphead)->next;
	while (purc != *pphead)
	{
		ListNode* next = purc->next;
		free(purc);
		purc = next;
	}
	free(purc);
	purc = NULL;
	*pphead = NULL;
}

顺序表与单链表的区别

1. 如果要求频繁的查找，不需要进行大面积插入删除，则用顺序表 。 2. 如果不要求频繁的查找，而需要进行大面积插入删除，则用链表 。

致谢

感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-11-04，如有侵权请联系 cloudcommunity@tencent.com 删除
数据结构与算法
指针
null
链表
数据

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据结构与算法
指针
null
链表
数据
评论
登录后参与评论
暂无评论
登录 后参与评论
推荐阅读
Scrapy框架之批量下载360妹纸图
python存储httpjavascript爬虫
0.导语1.项目初始化2.定义存储结构3.Spider核心代码4.pipeline下载及存储5.json知识
公众号guangcity
2019/09/20
6000
Scrapy框架之批量下载360妹纸图
Scrapy框架的使用之Item Pipeline的用法
scrapy存储
Item Pipeline是项目管道，本节我们详细了解它的用法。 首先我们看看Item Pipeline在Scrapy中的架构，如下图所示。 图中的最左侧即为Item Pipeline，它的调用发生
崔庆才
2018/06/25
7.4K1
data pipeline是做什么_pycharm创建爬虫项目
python
爬取爱套图网图片：https://github.com/EExplode/scrapy_aitaotu
全栈程序员站长
2022/10/05
4850
Scrapy框架的使用之Scrapy对接Selenium
scrapyseleniumjavaajax
Scrapy抓取页面的方式和requests库类似，都是直接模拟HTTP请求，而Scrapy也不能抓取JavaScript动态渲染的页面。在前文中抓取JavaScript渲染的页面有两种方式。一种是分析Ajax请求，找到其对应的接口抓取，Scrapy同样可以用此种方式抓取。另一种是直接用Selenium或Splash模拟浏览器进行抓取，我们不需要关心页面后台发生的请求，也不需要分析渲染过程，只需要关心页面最终结果即可，可见即可爬。那么，如果Scrapy可以对接Selenium，那Scrapy就可以处理任何
崔庆才
2018/06/25
2.7K0
Scrapy 框架实战：构建高效的快看漫画分布式爬虫
pythonscrapy
Scrapy是一个为了爬取网站数据，提取结构性数据而编写的应用框架，它提供了强大的数据提取能力、灵活的扩展机制以及高效的异步处理性能。其核心架构包括：
小白学大数据
2025/08/28
700
Scrapy 对接 Selenium
爬虫
Scrapy抓取页面的方式和Requests库类似，都是直接模拟HTTP请求，因此如果遇到JavaScript渲染的页面Scrapy同样是无法抓取的，而在前文中我们抓取JavaScript渲染的页面有
崔庆才
2017/08/08
6.6K0
Scrapy 对接 Selenium
利用 Scrapy 爬取知乎用户信息
其他
　　思路：通过获取知乎某个大V的关注列表和被关注列表，查看该大V和其关注用户和被关注用户的详细信息，然后通过层层递归调用，实现获取关注用户和被关注用户的关注列表和被关注列表，最终实现获取大量用户信息。 一、新建一个scrapy项目　　 scrapy startproject zhihuuser 　　移动到新建目录下： cd zhihuuser 　　新建spider项目： scrapy genspider zhihu zhihu.com 二、这里以爬取知乎大V轮子哥的用户信息来实现爬取知乎大量用户信息。 a)
希希里之海
2018/05/16
6980
Scrapy框架之爬取城市天气预报
python存储jsonmongodb数据库
1.项目初始化2.提取数据 2.1 原理分析 2.2 数据抽取 2.3 自定义spider3.存储数据 3.1 修改settings.py 3.2 数据存储4.结果展示5.作者的话
公众号guangcity
2019/09/20
1.8K1
Scrapy框架之爬取城市天气预报
Python(十六)
scrapycssxslt & xpathhttp
接下来的几篇，我们将介绍一下最流行的爬虫框架 Scrapy。本篇，我们会介绍一下 Scrapy 的基本使用。
1ess
2021/11/01
3720
Python(十六)
手把手教你用Scrapy爬取知乎大V粉丝列表
mongodb数据库sql云数据库 MongoDB爬虫
导读：通过获取知乎某个大V的关注列表和被关注列表，查看该大V以及其关注用户和被关注用户的详细信息，然后通过层层递归调用，实现获取关注用户和被关注用户的关注列表和被关注列表，最终实现获取大量用户信息。
IT阅读排行榜
2021/05/06
9770
一个scrapy框架的爬虫(爬取京东图书)
scrapy爬虫
我们的这个爬虫设计来爬取京东图书(jd.com)。 scrapy框架相信大家比较了解了。里面有很多复杂的机制，超出本文的范围。 1、爬虫spider tips： 1、xpath的语法比较坑，但是你可以在chrome上装一个xpath helper，轻松帮你搞定xpath正则表达式 2、动态内容，比如价格等是不能爬取到的 3、如本代码中，评论爬取部分代码涉及xpath对象的链式调用，可以参考 # -*- coding: utf-8 -*- # import scrapy # 可以用这句代替下面三句，但不推荐
用户1225216
2018/03/05
1.4K0
17.splash_case06_ScrapySplashTest-master
settings
taobao.py # -*- coding: utf-8 -*- from scrapy import Spider, Request from urllib.parse import quote from scrapysplashtest.items import ProductItem from scrapy_splash import SplashRequest script = """ function main(splash, args) splash.images_enabled = f
hankleo
2020/09/17
4280
Python爬虫案例：Scrapy+XPath解析当当网网页结构
pythonscrapyxpath
在当今大数据时代，网络爬虫已成为获取互联网信息的重要工具。作为Python生态中最强大的爬虫框架之一，Scrapy凭借其高性能、易扩展的特性受到开发者广泛青睐。本文将详细介绍如何利用Scrapy框架结合XPath技术解析当当网的商品页面结构，实现一个完整的电商数据爬取案例。
小白学大数据
2025/07/24
1220
分布式爬虫搭建系列 之三---scrapy框架初用
python爬虫scrapyide
其次，通过我们的神器PyCharm打开我们的项目--crawlquote（也可以将PyCharm打开我们使用虚拟环境创建的项目）
wfaceboss
2019/04/08
6370
分布式爬虫搭建系列 之三---scrapy框架初用
Python爬虫框架：scrapy爬取知乎数据
mongodb数据库sql云数据库 MongoDB爬虫
基础环境沿用之前的环境，只是增加了MongoDB（非关系型数据库）和PyMongo（Python 的 MongoDB 连接库），默认我认为大家都已经安装好并启动 了MongoDB 服务。
python学习教程
2019/10/22
1.6K0
Python爬虫框架：scrapy爬取知乎数据
Scrapy框架的使用之Scrapy入门
scrapymongodb数据库
接下来介绍一个简单的项目，完成一遍Scrapy抓取流程。通过这个过程，我们可以对Scrapy的基本用法和原理有大体了解。 一、准备工作 本节要完成的任务如下。 创建一个Scrapy项目。 创建一个Spider来抓取站点和处理数据。 通过命令行将抓取的内容导出。 将抓取的内容保存的到MongoDB数据库。 二、准备工作 我们需要安装好Scrapy框架、MongoDB和PyMongo库。 三、创建项目 创建一个Scrapy项目，项目文件可以直接用scrapy命令生成，命令如下所示： scrapy st
崔庆才
2018/06/25
1.5K0
scrapy 进阶使用
爬虫linux数据库mongodb
乐百川
2018/01/09
2.1K0
scrapy 进阶使用
实操 | 从0到1教你用Python来爬取整站天气网
pythonscrapyphp爬虫selenium
Scrapy是Python开发的一个快速、高层次的屏幕抓取和web抓取框架，用于抓取web站点并从页面中提取结构化的数据。
润森
2019/09/17
8000
实操 | 从0到1教你用Python来爬取整站天气网
Scrapy项目实战：爬取某社区用户详情
cookiespipelinesettings
get_cookies.py from selenium import webdriver from pymongo import MongoClient from scrapy.crawler import overridden_settings # from segmentfault import settings import time import settings class GetCookies(object): def __init__(self): # 初始化组件
hankleo
2020/09/17
6230
起点小说爬取--scrapy/redis/scrapyd
scrapy云数据库 Redis®
之前写了一篇网络字体反爬之pyspider爬取起点中文小说 可能有人看了感觉讲的太模糊了，基本上就是一笔带过，一点也不详细。这里要说明一下，上一篇主要是因为有字体反爬，所以我才写了那篇文章，所以主要就是提一个字体反爬的概念让大家知道，其中并没有涉及到其他比较难的知识点，所以就是大概介绍一下。
星星在线
2018/08/21
1.9K0
起点小说爬取--scrapy/redis/scrapyd
推荐阅读
编辑精选文章
万字详解高可用架构设计Go 开发者必备：Protocol Buffers 入门指南10分钟带你彻底搞懂分布式链路跟踪多租户的 4 种常用方案亿级月活的社交 APP，陌陌如何做到 3 分钟定位故障？60页PPT全解：DeepSeek系列论文技术要点整理
相关讨论
CAE 如何学呢？微信学英语？学习小程序可以先学HTML、CSS、JavaScript,那么想学云开发应该学什么？
相关课程
JavaAI绘画-StableDiffusion图像生成C/Python
Scrapy框架之批量下载360妹纸图
6000
Scrapy框架的使用之Item Pipeline的用法
7.4K1
data pipeline是做什么_pycharm创建爬虫项目
4850
Scrapy框架的使用之Scrapy对接Selenium
2.7K0
Scrapy 框架实战：构建高效的快看漫画分布式爬虫
700
Scrapy 对接 Selenium
6.6K0
利用 Scrapy 爬取知乎用户信息
6980
Scrapy框架之爬取城市天气预报
1.8K1
Python(十六)
3720
手把手教你用Scrapy爬取知乎大V粉丝列表
9770
一个scrapy框架的爬虫(爬取京东图书)
1.4K0
17.splash_case06_ScrapySplashTest-master
4280
Python爬虫案例：Scrapy+XPath解析当当网网页结构
1220
分布式爬虫搭建系列 之三---scrapy框架初用
6370
Python爬虫框架：scrapy爬取知乎数据
1.6K0
Scrapy框架的使用之Scrapy入门
1.5K0
scrapy 进阶使用
2.1K0
实操 | 从0到1教你用Python来爬取整站天气网
8000
Scrapy项目实战：爬取某社区用户详情
6230
起点小说爬取--scrapy/redis/scrapyd
1.9K0
相关推荐
Scrapy框架之批量下载360妹纸图
更多 >
Windows技术交流
LV.7
TJNUAAAAA
文章
1.1K
获赞
3.8K
专栏
1
目录
  • 前言
  • 链表
    • 链表的概念
    • 链表的分类
    • 结点的概念
    • 头指针
    • 头节点
  • 单链表（不带头单向不循环链表）
    • 定义单链表
    • 创建新的节点
    • 打印单链表
    • 尾插单链表
    • 头插单链表
    • 单链表指定位置前插入节点
    • 单链表指定位置后插入节点
    • 尾删单链表
    • 头删单链表
    • 指定删除单链表
    • 搜索单链表节点
    • 销毁单链表
  • 单链表实现代码
    • <test.h>文件
    • <test.c>文件
  • 双向链表 （带头双向循环链表）
    • 定义双向链表
    • 创建新的节点
    • 插入头节点
    • 打印双向链表
    • 尾插双向链表
    • 头插双向链表
    • 判断双向链表是否为空
    • 尾删双向链表
    • 头删双向链表
    • 双向链表任意位置查找节点
    • 指定位置之后插入节点
    • 指定位置删除节点
    • 销毁双向链表
  • 双链表实现代码
    • <list.h>文件
    • <test.c>文件
  • 顺序表与单链表的区别
  • 致谢
加入讨论
的问答专区 >
月小水长0
相关课程
一站式学习中心 >
Java
2211人在学
java
AI绘画-StableDiffusion图像生成
1718人在学
腾讯混元生图
高性能应用服务
C/Python
1121人在学
c 语言
python
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论
2