数据结构：线性表之-单向链表(无头)_单项链表是什么专业

目录

什么是单向链表

顺序表和链表的区别和联系

顺序表：

链表：

链表表示(单项)和实现

1.1 链表的概念及结构

1.2单链表(无头)的实现

所用文件

将有以下功能：

链表定义

创建新链表元素

尾插

头插

尾删

头删

查找-给一个节点的指针

改

pos位置之前插入

删除pos位置的值

成品展示

SList.h

SList.c

test.c

---

什么是单向链表

单向链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的指针。每个节点只能访问它后面的节点，而不能访问前面的节点。

单向链表的特点：

• 每个节点包含数据和指向下一个节点的指针。
• 最后一个节点的指针指向空值（NULL），表示链表的结束。
• 可以动态地添加或删除节点，链表的长度可以根据需要进行扩展或缩小。
• 可以根据指针迅速插入或删除节点，而不需要移动其他节点。

单向链表相对于数组来说，具有一些优点和缺点：

• 优点：插入和删除元素的时间复杂度为O(1)，不需要像数组一样进行元素的移动；链表长度可以动态调整，没有固定大小的限制。
• 缺点：要访问特定位置的元素需要从头开始遍历，时间复杂度为O(n)；相比于数组，在使用额外的指针存储下一个节点的信息，会占用更多的内存空间。

由于单向链表的特点，它常常被用于需要频繁插入和删除元素的场景，或者在事先无法确定数据大小和数量的情况下使用。

顺序表和链表的区别和联系

顺序表：

优点：
空间连续、支持随机访问
缺点：

1. 中间或前面部分的插入删除时间复杂度O(N)
2. 2.增容的代价比较大。

链表：

缺点：
以节点为单位存储，不支持随机访问
优点：

1. 任意位置插入删除时间复杂度为O(1)
2. 没有增容消耗，按需申请节点空间，不用了直接释放。

链表表示(单项)和实现

1.1 链表的概念及结构

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

1.2单链表(无头)的实现

 

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
   构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
   是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
   来很多优势，实现反而简单了，后面我们代码实现了就知道了。

所用文件

定义三个文件：

1. 头文件 SList.h
2. 函数的实现SList.c
3. 代码的测试test.c

将有以下功能：

//打印链表
void SListPrint(SLTNode* phead);
 
//创建新链表元素（动态申请一个节点）
SLTNode* BuySListNode(SLTDataType x);
 
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
 
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
 
//尾删
void SListPopBack(SLTNode** pphead);
 
//头删
void SListPopFront(SLTNode** pphead);
 
//查找->可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);
 
//改
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);
 
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
 
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

链表定义

定义链表基本结构

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

创建新链表元素

创建新元素用于插入原链表

SLTNode* BuySListNode(SLTDataType x)
{
	//开辟空间
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
 
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//开辟空间
	SLTNode* newnode = BuySListNode(x);
 
	if (*pphead == NULL)
	{
		//防止开始时节点为空
		*pphead = newnode;
	}
	else
	{
		//找尾节点
		SLTNode* tail = *pphead;//找到链表首元素
		while (tail->next != NULL)
		{
			//检索到未节点
			tail = tail->next;
		}
		//插入
		tail->next = newnode;
	}
}

头插

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
 
	newnode->next = *pphead;
	*pphead = newnode;//地址传给pphead  
	//*pphead=&plist
	
	/*
		头插无需检查是否为空
	*/
}

尾删

void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next==NULL)
	{
		//1，只有一个节点
 
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//2，有多个节点
		
		//将前一个链元素中存放的地址换为NULL，防止野指针
		/* 写法一 */
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next!=NULL)
		{
			tailPrev = tail;//tail的地址
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
 
		/* //写法二
		* //tail寻找的是倒数第二个元素
		while (tail->next->next!=NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
		*/
	}
}

头删

void SListPopFront(SLTNode** pphead)
{ 
	//防止被删空
	assert(*pphead);
	
	//找到首位链表元素
	SLTNode* next = (*pphead)->next;//存储首元素存放下一个元素的地址
	free(*pphead);//释放首元素
	*pphead = next;//将第二位元素改为首元素
}

查找-给一个节点的指针

//无需更改元素，故传一级指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data==x)
			return cur;
		cur = cur->next;
	}
	//未找到指定元素，返回NULL
	return NULL;
}

改

改元素是建立再查找基础之上进行更改

void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{
	printf("修改成功:\n");
	//先找到相应元素，再进行更改
	SLTNode* ret = SListFind(phead, y);
	ret->data = x;
}

pos位置之前插入

任意位置之前插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
 
	//头插
	if (pos == *pphead)
		SListPushFront(pphead, x);
	else
	{ 
		//任意位置之前插入
		SLTNode* prev = *pphead;
		while (prev->next!=pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
		}
		//找到位置
		SLTNode* newnode = BuySListNode(x);//创建新链表元素，并赋值
		prev->next = newnode;//给前一个元素赋上下一元素地址
		newnode->next = pos;//给插入元素存放下一个元素的地址
	}
}

删除pos位置的值

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
 
	if (*pphead == pos)
		SListPopFront(pphead);//头删
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
			//移到pos前一位，next存放的是pos的地址
		}
		//将prev存放的地址改为pos后一个元素的地址
		prev->next = pos->next;
		//释放pos
		free(pos);
		pos = NULL;
	}
}

成品展示

SList.h

#pragma once
 
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
 
typedef int SLTDataType;
 
typedef struct SListNode
{
	int data;
	struct SListNode* next;
}SLTNode;
 
//打印链表
void SListPrint(SLTNode* phead);
 
//创建新链表元素（动态申请一个节点）
SLTNode* BuySListNode(SLTDataType x);
 
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
 
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
 
//尾删
void SListPopBack(SLTNode** pphead);
 
//头删
void SListPopFront(SLTNode** pphead);
 
//查找->可在查找的基础上进行修改SListAlter
SLTNode* SListFind(SLTNode* phead,SLTDataType x);
 
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);
 
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
 
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

SList.c

#include "SList.h"
 
//打印
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur!=NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;//存放下一个元素的地址
	}
	printf("NULL\n");
}
 
//创建新链表元素
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newnode);
 
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}
 
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
 
	SLTNode* newnode = BuySListNode(x);//data
 
	if (*pphead == NULL)
	{
		//防止开始时节点为空
		*pphead = newnode;
	}
	else
	{
		//找尾节点
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			//存放新节点地址
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
 
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
 
	SLTNode* newnode = BuySListNode(x);
 
	newnode->next = *pphead;
	*pphead = newnode;//地址传给pphead  
	//*pphead=&plist
	
	/*
		头插无需检查是否为空
	*/
}
 
//尾删
void SListPopBack(SLTNode** pphead)
{
	assert(*pphead);
	
	if ((*pphead)->next==NULL)
	{
		//1，只有一个节点
 
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//2，有多个节点
 
		//将前一个链元素中存放的地址换为NULL，防止野指针
		/* 写法一 */
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next!=NULL)
		{
			tailPrev = tail;//tail的地址
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
 
		/* //写法二
		* //tail寻找的是倒数第二个元素
		while (tail->next->next!=NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
		*/
	}
}
 
//头删
void SListPopFront(SLTNode** pphead)
{ 
	//防止被删空
	assert(*pphead);
 
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
 
//查找-给一个节点的指针
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data==x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
 
//改
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{
	assert(phead);
	printf("修改成功:\n");
	SLTNode* ret = SListFind(phead, y);
	ret->data = x;
}
//pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
 
	//头插
	if (pos == *pphead)
		SListPushFront(pphead, x);
	else
	{ 
		SLTNode* prev = *pphead;
		while (prev->next!=pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
		}
		//找到位置
		SLTNode* newnode = BuySListNode(x);//创建新链表元素，并赋值
		prev->next = newnode;//给前一个元素赋上下一元素地址
		newnode->next = pos;//给插入元素存放下一个元素的地址
	}
}
 
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
 
	if (*pphead == pos)
		SListPopFront(pphead);//头删
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)//找到pos的位置
		{
			prev = prev->next;//prev存放pos的地址
			//移到pos前一位，next存放的是pos的地址
		}
		//将prev存放的地址改为pos后一个元素的地址
		prev->next = pos->next;
		//释放pos
		free(pos);
		pos = NULL;
	}
}

test.c

test.c仅仅是用于测试代码，本文以弄懂单向链表为主，故不进行菜单制作
但改测试中也包含了对部分链表结构即原理进行了讲解，请耐心看完

#include "SList.h"
void TestSList1()
{	
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n1);
 
	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n2);
 
	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n3);
 
	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	assert(n4);
	
	n1->data=1;
	n2->data=2;
	n3->data=3;
	n4->data=4;
 
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	
	SListPrint(n1);
}
 
void TestSList2()
{
	SLTNode* plist = NULL;
	//传的是plist指针的地址
	
	//如果直接传plist，将导致SLTNode* phead中
	//phead为临时拷贝，不影响实参
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	
	SListPrint(plist);//不改变无需传二级指针
 
	SListPushFront(&plist,0);
	SListPrint(plist);
 
	SListPopFront(&plist);
	SListPrint(plist);
	
	SListPopBack(&plist);
	/*SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);
	SListPopBack(&plist);
	SListPrint(plist);*/
	/*SListPopBack(&plist);
	SListPrint(plist);*/
}
	
void TestSList3()
{
	SLTNode* plist = NULL;
	//传的是plist指针的地址
 
	//如果直接传plist，将导致SLTNode* phead中
	//phead为临时拷贝，不影响实参
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
 
	SListPrint(plist);//不改变无需传二级指针
 
 
	//查找
	SLTNode* ret = SListFind(plist, 3);
	if (ret)
	{
		//返回值不为空则为找到
		printf("找到了\n");
	}
	SListPrint(plist);
	修改
	//SListAlter(plist, 20, 2);
	//SListPrint(plist);
 
	//插入
	SLTNode* pos = SListFind(plist, 3);//先要找到再进行更改
	if (pos)
	{
		SListInsert(&plist, pos, 40);
	}
	SListPrint(plist);
 
	//删除
	pos = SListFind(plist, 2);//先要找到再进行删除
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}
 
int main()
{
	TestSList3();
	 
	return 0;
}

单向链表讲解完毕啦！创作不易，如果喜欢请留下个赞吧，感激不尽