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

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("NULL\n");
}

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 <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
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("NULL\n");
}
//尾插
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;
}

运行结果附上：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/474544