投稿
  1. 首页
  2. 随笔

单链表详解

微信表情雨 • 2022-12-17 • 随笔 • 阅读 15

单链表详解,第1张

单链表详解

目录

一、什么是链表

1、数据结构概要

2、功能

二、实现链表

1、定义一个具有结点特征的结构体

2、定义一个头指针

 3、实现尾插

尾插代码实现如下：

4、结点的创建：

 创建节点代码实现：

5、实现尾删

 尾删代码实现：

6、实现头插

头插代码实现：

 7、实现头删

头删代码实现：

8、实现任意结点位置的后的插入

任意插入代码实现：

9、实现任意结点位置后的删除

任意删除代码实现：

10、实现打印

打印代码实现：

11、实现查找某一数据的结点

查找代码实现：

12、实现某一位置结点数据的修改

修改数据代码实现：

三、全部代码附上

SList.h部分：

SList.c部分：

text.c部分：

运行结果附上：

一、什么是链表
1、数据结构概要

数据结构就是用某种结构去储存数据：

1、物理结构(数据在内存中的存储)

2、逻辑结构(由人为想象出来的)

顺序表就是逻辑和物理都连续的一种线性表。说明白一点顺序表就是玩数组。

链表就是逻辑连续，物理不一定连续的线性表。如下图，逻辑上是利用指针将其串联起来的，物理上却是杂乱的，最后以NULL空指针结束。

2、功能

大致了解什么是链表后，我们还需要知道链表的大概的功能有哪些？ 

1、首先清楚它是用于储存数据的一种结构

2、尾部插入数据，尾部删除数据，头部插入数据，头部删除数据，任意位置的插入，任意位置的删除，查找数据位置，修改数据的功能。

二、实现链表
1、定义一个具有结点特征的结构体

因为结构体内储存的数据类型不是确定的，为了避免以后维护起来太麻烦，所幸将类型重定义一下。

在链表中这样的一个结构体类型称为一个结点，我们需要这个结点指向下一个结点，所以需要定义一个结点类型的指针。

typedef int SListDateType;
//结点
typedef struct SListNode
{
	SListDateType date;
	struct SListNode* Next;
}SListNode;
2、定义一个头指针

这是最简单的单链表结构，相当于是一个空单链表

 

 3、实现尾插

实现尾插有两种情况：1、phead头指针为NULL。2、phead头指针为非空。

尾插代码实现如下： 
void SListPushBack(SListNode** pphead, SListDateType x)
{
	//创建结点
	SListNode* newnode = BuySListNode(x);
    //第一种情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
    //第二种情况
	else
	{
		SListNode* tail = *pphead;
		while (tail->Next != NULL)
		{
			tail = tail->Next;
		}

		tail->Next = newnode;
	}
}
4、结点的创建：

 创建节点代码实现： 
//创建一个结点
static SListNode* BuySListNode(SListDateType x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
	{
		printf("开辟空间失败n");
		exit(-1);
	}
	NewNode->date = x;
	NewNode->Next = NULL;

	return NewNode;
}
5、实现尾删

 实现尾删分三种情况：1、phead头指针为空指针。2、phead头指针不为空指针，只有一个结点。3、phead不为空指针、有多个结点。

 尾删代码实现： 
//尾删
void SListPopBack(SListNode** pphead)
{
	//如果是空链表
	if (*pphead == NULL)
	{
		return;
	}
	//如果只有一个结点
	else if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果有多个结点
	else
	{
		SListNode* prev = NULL;//前一个结点
		SListNode* tail = *pphead;//尾结点
		while (tail ->Next != NULL)
		{
			prev = tail;
			tail = tail->Next;
		}

		free(tail);
		tail = NULL;
		prev->Next = NULL;
	}
}
6、实现头插

实现头插分两种情况：1、phead == NULL。2、phead != NULL。

 由图解分析：两种情况用代码实现其实是一种逻辑。

头插代码实现： 
//头插
void SListPushFront(SListNode** pphead, SListDateType x)
{
	//创建结点
	SListNode* newnode = BuySListNode(x);
	newnode->Next = *pphead;
	*pphead = newnode;
}

 7、实现头删

实现头删有三种情况：1、phead == NULL。2、phead != NULL ,有一个结点。3、phead != NULL,有多个结点。

又图解分析，后面两种也可划分为一种代码实现逻辑：1、phead == NULL。2、phead != NULL,一个节点 + 多个结点的情况。

头删代码实现： 
//头删
void SListPopFront(SListNode** pphead)
{
	//1.phead == NULL
	//2.有一个结点 + 有多个结点
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* cur = *pphead;
		*pphead = (*pphead)->Next;
		free(cur);
		cur = NULL;
	}
}
8、实现任意结点位置的后的插入

因为单链表的缺陷（后一个结点无法找到前一个结点）所以只能实现结点后的插入，无法实现结点前的插入。

这种功能的实现也有三种情况：

如下图解分析：

 

 

图解分析：后只有一个结点 + 有多个结点）的代码逻辑相同 

任意插入代码实现： 
//任意插入
void SListInsertAfter(SListNode** pphead, SListDateType pos, SListDateType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->date != pos)
		{
			cur = cur->Next;
		}
		newnode->Next = cur->Next;//这里使用第二种避免找不到地址的方法
		cur->Next = newnode;
	}
}

 

9、实现任意结点位置后的删除

实现删除：3种情况：1、phead == NULL。 2、phead != NULL,一个结点。 3、phead != NULL,多个结点。

 

 

 

 由图解分析：

任意删除代码实现： 
//任意结点后删除
void SListEraseAfter(SListNode** pphead, SListDateType pos)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->date != pos)
		{
			cur->Next;
		}
		SListNode* next = cur->Next;
		SListNode* nextnext = next->Next;
		free(next);
		next = NULL;
		cur->Next = nextnext;
	}
}

10、实现打印

 

 

 由图解分析：三种情况下的开始。迭代，结束条件都是相同的，所以代码实现逻辑相同。

打印代码实现： 
//打印
void SListPrint(SListNode* phead)
{
	SListNode* Cur = phead;
	while (Cur != NULL)//遍历
	{
		printf("%d->", Cur->date);
		Cur = Cur->Next;
	}
	printf("NULLn");
}
11、实现查找某一数据的结点

查找代码实现： 
SListNode* SListFind(SListNode* phead, SListDateType x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->Next;
	}
	return NULL;
}

 

12、实现某一位置结点数据的修改

修改其实可以说和查找差不多，一模一样，只是在找到后，在对其的数据行修改即可。

修改数据代码实现： 
//任意结点数据的修改
void SListChange(SListNode* phead, SListDateType pos, SListDateType x)
{
	SListNode* cur = phead;
	while (cur->date != pos)
	{
		cur = cur->Next;
	}
	cur->date = x;
}
三、全部代码附上 SList.h部分： 
#pragma once

#include 
#include 
#include 

typedef int SListDateType;
//结点
typedef struct SListNode
{
	SListDateType date;
	struct SListNode* Next;
}SListNode;
//尾插
void SListPushBack(SListNode** pphead, SListDateType x);
//尾删
void SListPopBack(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SListDateType x);
//头删
void SListPopFront(SListNode** pphead);
//打印
void SListPrint(SListNode* phead);
//查找
SListNode* SListFind(SListNode* phead, SListDateType x);
//任意结点后的插入
void SListInsertAfter(SListNode** pphead, SListDateType pos, SListDateType x);
//任意结点后的删除
void SListEraseAfter(SListNode** pphead, SListDateType pos);
//任意位置的修改
void SListChange(SListNode* phead, SListDateType pos, SListDateType x);
SList.c部分： 
#define  _CRT_SECURE_NO_WARNINGS 1

#include "Slist.h"

//创建一个结点
static SListNode* BuySListNode(SListDateType x)
{
	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
	if (NewNode == NULL)
	{
		printf("开辟空间失败n");
		exit(-1);
	}
	NewNode->date = x;
	NewNode->Next = NULL;

	return NewNode;
}
//打印
void SListPrint(SListNode* phead)
{
	SListNode* Cur = phead;
	while (Cur != NULL)//遍历
	{
		printf("%d->", Cur->date);
		Cur = Cur->Next;
	}
	printf("NULLn");
}
//尾插
void SListPushBack(SListNode** pphead, SListDateType x)
{
	//创建结点
	SListNode* newnode = BuySListNode(x);
	//第一种情况，phead == NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//第二种情况，phead != NULL
	else
	{
		SListNode* tail = *pphead;
		while (tail->Next != NULL)
		{
			tail = tail->Next;
		}

		tail->Next = newnode;
	}
}

//尾删
void SListPopBack(SListNode** pphead)
{
	//如果是空链表
	if (*pphead == NULL)
	{
		return;
	}
	//如果只有一个结点
	else if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//如果有多个结点
	else
	{
		SListNode* prev = NULL;//前一个结点
		SListNode* tail = *pphead;//尾结点
		while (tail ->Next != NULL)
		{
			prev = tail;
			tail = tail->Next;
		}

		free(tail);
		tail = NULL;
		prev->Next = NULL;
	}
}

//头插
void SListPushFront(SListNode** pphead, SListDateType x)
{
	//创建结点
	SListNode* newnode = BuySListNode(x);
	newnode->Next = *pphead;
	*pphead = newnode;
}
//头删
void SListPopFront(SListNode** pphead)
{
	//1.phead == NULL
	//2.有一个结点 + 有多个结点
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* cur = *pphead;
		*pphead = (*pphead)->Next;
		free(cur);
		cur = NULL;
	}
}
//查找
SListNode* SListFind(SListNode* phead, SListDateType x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->Next;
	}
	return NULL;
}
//任意插入
void SListInsertAfter(SListNode** pphead, SListDateType pos, SListDateType x)
{
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->date != pos)
		{
			cur = cur->Next;
		}
		newnode->Next = cur->Next;
		cur->Next = newnode;
	}
}
//任意结点后删除
void SListEraseAfter(SListNode** pphead, SListDateType pos)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->Next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->date != pos)
		{
			cur->Next;
		}
		SListNode* next = cur->Next;
		SListNode* nextnext = next->Next;
		free(next);
		next = NULL;
		cur->Next = nextnext;
	}
}
//任意结点数据的修改
void SListChange(SListNode* phead, SListDateType pos, SListDateType x)
{
	SListNode* cur = phead;
	while (cur->date != pos)
	{
		cur = cur->Next;
	}
	cur->date = x;
}
text.c部分： 
#define  _CRT_SECURE_NO_WARNINGS 1

#include "Slist.h"

void TextSList(SListNode* phead)
{
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);
	SListPrint(phead);
	SListPushFront(&phead, 22);
	SListPrint(phead);
	SListPopFront(&phead);
	SListPrint(phead);
}
void TextSListFind(SListNode* phead)
{
	SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);
	SListPrint(phead);
	SListPushFront(&phead, 22);
	SListPrint(phead);
	SListPopFront(&phead);
	SListPrint(phead);
	SListNode* ret = SListFind(phead, 3);
	if (ret != NULL)
	{
		ret->date = 100;
	}

	SListPrint(phead);

	SListChange(phead, 1, 1000);
	SListPrint(phead);
	SListEraseAfter(&phead, 1000);
	SListPrint(phead);
	SListInsertAfter(&phead, 1000, 2);
	SListPrint(phead);
	CSList(&phead);
	SListPrint(phead);
}
int main()
{
	//头指针：最简单的单链表
	//SListNode* pList = NULL;
	SListNode* phead = NULL;

	//TextSList(phead);
	TextSListFind(phead);

	return 0;
}
运行结果附上：

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5714589.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
微信表情雨 微信表情雨 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存