努力学c的楼下小王

努力学c的楼下小王

关注
发信
关注(28)粉丝(399)

线性表之-单向链表(无头)

目录

什么是单向链表

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

顺序表：

链表：

链表表示(单项)和实现

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单链表(无头)的实现

线性表之-单向链表(无头)-LMLPHP

 线性表之-单向链表(无头)-LMLPHP

所用文件

定义三个文件：

  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;
}

单向链表讲解完毕啦！创作不易，如果喜欢请留下个赞吧，感激不尽😊线性表之-单向链表(无头)-LMLPHP

09-06 05:05
Powered by LMLPHP ©2024 努力学c的楼下小王 0.007372