单链表的实现（C语言）_c语言 单链表实现 csdn

目录

前言（顺序表的问题及思考）

一、链表

1.1. 概念与结构

 1.2 链表的分类

        1.2.1. 单向或者双向

        1.2.2.带头或者不带头 

        1.2.3.循环或者非循环

 1.3 链表的实现

 二、链表的具体实现

1.单链表的空间分配

2. 打印链表

3. 尾插

4. 头插

5. 尾删

 6. 头删

 7. 查找

 8. 在pos位置插入

9. 在pos位置删除

10. 销毁

总结

动态内存分配（malloc）详解-CSDN博客https://blog.csdn.net/TheWhiteFox/article/details/108502906

前言（顺序表的问题及思考）

问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下面给出了链表的结构来看看。

一、链表

1.1. 概念与结构

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

 

 1.2 链表的分类

        实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

        1.2.1. 单向或者双向

        1.2.2.带头或者不带头 

         

        1.2.3.循环或者非循环

         虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

 1.3 链表的实现

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data; // val
	struct SListNode* next; // 存储下一个节点的地址
}SListNode, SLN;
 
void SListPrint(SListNode* phead);
void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPushFront(SListNode** pphead, SLTDataType x);
void SListPopBack(SListNode** pphead);
void SListPopFront(SListNode** pphead);
SListNode* SListFind(SListNode* phead, SLTDataType x);
 
// 在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
// 删除pos 位置
void SListErase(SListNode** pphead, SListNode* pos);
 
// 在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 删除pos位置后面的值
void SListEraseAfter(SListNode* pos);
 
void SListDestroy(SListNode** pphead);

 二、链表的具体实现

 注意以下几点：

1）.每个节点都有一个data并且存放着下一个节点的地址；

2）.单链表的每一次都要用malloc开辟一个新的空间，由于堆区每次malloc开辟的空间不一定是连续的，所以链表在物理上看上去连续，但是其实不连续，它只是在逻辑上是连续的。

3）.链表有一个头指针变量，它可以说是第0个节点，称为整个单链表的头结点，其存放的是一个地址，一般不存放任何数据，只是存放第一个节点的地址，以找到该链表。

4）.只有链表不为空的时候，才需要对单链表进行空间分配，需要一个节点，就开辟一个节点进行连接。

5）.记住最后一个节点所存放的地址被要求为空，作为链表的结束，代表后续没有节点。

1.单链表的空间分配

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("BuySListNode error\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
    return newnode;
}

2. 打印链表

void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur->next != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3. 尾插

        注意：传址，头指针的改变

//空链表的创建
//SListNode* SList = NULL;
//SListPushBack(SList,i)
//void SListPushBack(SListNode* phead,SLDataType x)尾插
//SList是一个指向SListNode的指针，phead也是一个指向SListNode的指针，属于传值传参
//这样只是一份临时拷贝，形参的改变不会影响实参
//c语言指针有一个这样的原则：若想改变int变量，就需要传int*变量
//&SList，SList的地址可以这么理解，SList存放的是SListNode的地址，解引用才能得到&SList
//所以相当于传&SList可以改变SList
//所以若这里传址的话即SListPushBack(&SList,i)
//pphead是指向SListNode*类型的指针，即指向指针（该指针指向SListNode类型）的指针
//即存放指向SListNode类型的指针的地址
//&SList是指针的地址，而该指针存放的是SListNode的地址
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//空指针的解引用是耍流氓
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)//pphead接收的&SList,*pphead就是SList本身
	{
		//这就是说该链表无节点，可以直接插入
		*pphead = newnode;//现在让SList指向newnode即可插入成功
	}
	else
	{//找尾，尾插即可
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

4. 头插

void SListPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;//如果是空链表的时候，*pphead == NULL,先让newnode->next=NULL也是合理的
	*pphead = newnode;
}

5. 尾删

        分情况讨论

                1）单节点2）多节点3）空脸变

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		//空链表
		return;
	}
	else
	{
		//单节点的时候，改变了头结点
		if ((*pphead)->next == NULL)
		{
			free(*pphead);//释放第一个节点
			*pphead = NULL;
		}
		else
		{
			//多节点找尾尾删
 
			/*经典错误,
			单链表是以尾结点指向空作为结束，free(tail)后，会让上一个结点指向野指针
			while (tail->next != NULL)
			{
				tail = tail->next;
			}
			free(tail);
			tail = NULL;*/
			SListNode* tail = *pphead;
			SListNode* prev = NULL;
			while (tail->next != NULL)
			{
				prev = tail;//记录前一个指针
				tail = tail->next;
			}
			free(tail);
			tail = NULL;
			prev->next = NULL;//单链表的结束
		}
	}
}

 6. 头删

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		return;
	}
	if ((*pphead)->next == NULL)//一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

 7. 查找

        注意：别忘记尾结点也要查找得到才行

SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur != NULL)//只有这样才能检查最后一个节点
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//找不到返回NULL
}

 8. 在pos位置插入

        思考：pos位置后插入更简单！

// 在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//1.空链表
	if (*pphead == NULL)
	{
		return;//空链表都没有pos位置，无意义
	}
	//2.单节点
	else if ((*pphead)->next == NULL)
	{
		SListPushFront(pphead, x);//pphead是SList的地址
	}
	//3.多节点
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	//SListNode* next = pos->next;
	//SListNode* newnode = BuySListNode(x);
 
	//pos->next = newnode;
	//newnode->next = next;
 
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

9. 在pos位置删除

// 删除pos 位置
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead) == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
 
	SListNode* next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

10. 销毁

        同样注意尾结点也需要销毁。

void SListDestroy(SListNode** pphead)
{
	assert(*pphead);
	SListNode* cur = *pphead;
	SListNode* next = NULL;
	while (cur)//这样才能free掉尾结点
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

---

总结

        多动手画图！