暴力数据结构之单链表专题

  • 开发
  • 27

1. 单链表的初始化

首先定义节点的结构，然后动态内存申请一部分空间，每一个节点都有一个值以及指向下一个节点的指针，称作值域和指针域。 

//定义节点的结构
//数据 + 指向下一个节点的指针

typedef int SLTDataType;

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

初始化需要为链表节点动态申请一块空间，然后对值域和指针域初始化。

//初始化函数
SLTNode* SLTBuyNode(SLTDataType x) 
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

2. 单链表的相关函数

2.1 头插和头删

首先断言头结点不能为空，然后直接从表头插入节点。

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	//将链表依次后移,从头插入
	newnode->next = *pphead;
	*pphead = newnode;
}

断言判断头结点及其地址都不为空，然后将原头结点的下一个节点保存起来，释放原来的头结点，则原头结点的下一个节点成为新的头结点。

//头删函数
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
2.2 尾插和尾删

断言头结点不能为空，同样插入，但是要判断原链表是否为空链表，是空链表则直接插入，反之遍历链表找到尾节点再插入。

//尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead 就是指向第一个节点的指针
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的是尾节点
		ptail->next = newnode;
	}
}

断言判断头结点及其地址均不为空，同样的原链表如果只有一个节点则直接释放，反之找到尾节点后释放尾节点。

//尾删函数
void SLTPopBack(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);
	//考虑链表只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(pphead);
		pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
2.3 在指定位置的前后插入数据

断言待插入节点位置、头结点及其地址均不为空，如果pos为头结点就直接头插，反之遍历链表找到pos的上一个节点，然后在二者中间插入。

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead && *pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为头节点
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

断言待插入节点位置、头结点及其地址均不为空，找到pos的上一个节点，然后在二者中间插入。 

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
2.4 删除当前节点或后面节点

 断言待插入节点位置、头结点及其地址均不为空，如果pos为头结点直接头删，反之遍历链表找     到pos节点后保存相邻节点，释放pos节点，将相邻节点连接起来形成新链表。

//删除pos当前指向的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//pos是头结点/不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

断言待插入节点位置及其下一个节点均不为空，保存pos下一个节点即待删除节点，释放pos节点，将相邻节点连接起来形成新链表。

//删除pos之后的节点
void SLTErase(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos = del->next;
	free(del);
	del = NULL;
}
2.5 销毁和查找 

遍历链表找符合的节点，然后直接返回该节点。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//pcur == NULL;
	return NULL;
}

由于前面有动态内存申请，所以要进行释放free掉，就有了销毁函数。 

//销毁链表
void SLTDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

3. 代码展示（可自行复制调试）

3.1 test.c
#include"SList.h"

void SListTest01()
{
	//链表是由一个一个的节点组成
	//创建几个节点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将四个节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	//调用链表的打印
	SLTNode* plist = node1;
	SLTPrint(plist);
}

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//SLTPushBack(NULL, 5);
	//
	//测试头插
	//SLTPushFront(&plist, 6);
	//SLTPrint(plist);
	//SLTPushFront(&plist, 7);
	//SLTPrint(plist);
	//SLTPushFront(&plist, 8);
	//SLTPrint(plist);

	//测试尾删
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

}

int main()
{
	//SListTest01();
	SListTest02();
	return 0;
}
3.2 SList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


//定义节点的结构
//数据 + 指向下一个节点的指针

typedef int SLTDataType;

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

//打印函数
void SLTPrint(SLTNode* phead);

//初始化函数
SLTNode* SLTBuyNode(SLTDataType x);

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//头删函数
void SLTPopFront(SLTNode** pphead);

//尾删函数
void SLTPopBack(SLTNode** pphead);


//删除pos之后的节点
void SLTErase(SLTNode* pos);


//销毁链表
void SLTDesTroy(SLTNode** pphead);
3.3 SList.c 
#include"SList.h"


//打印函数
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("->%d", pcur->data);
		pcur = pcur->next;
	}
	printf("->NULL\n");
}


//初始化函数
SLTNode* SLTBuyNode(SLTDataType x) 
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//newnode *pphead
	//将链表依次后移,从头插入
	newnode->next = *pphead;
	*pphead = newnode;
}


//尾插函数
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead 就是指向第一个节点的指针
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的是尾节点
		ptail->next = newnode;
	}
}



//尾删函数
void SLTPopBack(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);
	//考虑链表只有一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(pphead);
		pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}


//头删函数
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}



//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//pcur == NULL;
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead && *pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//判断是否为头节点
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}



//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


//删除pos当前指向的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//pos是头结点/不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


//删除pos之后的节点
void SLTErase(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos = del->next;
	free(del);
	del = NULL;
}

//销毁链表
void SLTDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

阅读全部

相关推荐

  1. 暴力数据结构之单链表专题

    2024-04-24 08:58:04       28 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-24 08:58:04       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-24 08:58:04       100 阅读

  9. 在Django里面运行非项目文件

    2024-04-24 08:58:04       82 阅读

  19. Python语言-面向对象

    2024-04-24 08:58:04       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-24 08:58:04       85 阅读

热门阅读

  1. PostCss 概述

    2024-04-24 08:58:04       35 阅读

  2. 如何在 Ubuntu 16.04 上配置 NTP 以在 NTP Pool 项目中使用

    2024-04-24 08:58:04       33 阅读

  3. 文件分享新风尚，二维码生成器全功能解析

    2024-04-24 08:58:04       41 阅读

  6. 新手入门人工智能：从零开始学习AI的正确途径

    2024-04-24 08:58:04       36 阅读

  9. 1. 2XX (Success 成功状态码)

    2024-04-24 08:58:04       33 阅读

  11. 服务器端的图片一般存储在哪？

    2024-04-24 08:58:04       49 阅读

  13. 实现 vue&react 混合开发项目步骤-微前端

    2024-04-24 08:58:04       40 阅读

  15. 240. 搜索二维矩阵 II

    2024-04-24 08:58:04       34 阅读

  16. 【matlab】【数值分析】针对特殊矩阵的追赶法的matlab实现

    2024-04-24 08:58:04       34 阅读

  18. 每天一个数据分析题（二百八十五）

    2024-04-24 08:58:04       34 阅读

  20. 每天一个数据分析题（二百八十七）

    2024-04-24 08:58:04       43 阅读

  28. 前端科举面经-HTML篇

    2024-04-24 08:58:04       43 阅读