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

2024-04-24 02:44
文章标签 单链 数据结构 专题 暴力

本文主要是介绍暴力数据结构之单链表专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于暴力数据结构之单链表专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/930563。

相关文章

Python数据结构之单向链表和双向链表

Python数据结构之单向链表和双向链表

链表的定义： 链表是通过一个个节点（Node）组成的，每个节点都包含了称为数据域(data)和指针域(next)的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。 链表的操作 is_empty() 链表是否为空length() 链表长度即节点个数travel() 遍历链表add(item) 链表头部添加节点append(item) 链表尾
阅读更多...
数据结构与算法---线性表

数据结构与算法---线性表

线性表 1.顺序表 需求分析 /*创建顺序表具体功能：初始化顺序表销毁顺序表获取顺序表元素个数输出顺序表中的内容自动扩容增 --- 插入数据（包含了尾部添加功能）删 --- 删除数据（包含了尾部删除功能）改 --- 修改数据查 --- 查找数据尾部追加尾部删除*/ C语言实现 #include<stdio.h>#include<stdlib.h>#include<stdbool.h
阅读更多...
[数据结构]——非比较排序—计数排序

[数据结构]——非比较排序—计数排序

该篇文章 所涉及代码收录仓库：登录 - Gitee.com 目录 1.非比较排序——计数排序 2.最终实现 1.解析 2.以int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };为例，手撕分析 3.代码实现 4.计数排序具有以下主要特性： 1.非比较排序——计数排序 思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 2.最终
阅读更多...
数据结构===散列表

数据结构===散列表

文章目录 概要散列思想散列函数散列冲突开放寻址法装载因子 链表法 代码Java小结 概要 散列表是一种很有趣的数据结构。 散列表是一个很有用的数据结构。它是数组演练而来的，又是一个基于数组的扩展的数据结构。接下来看看。 散列思想 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。 散列表是由k
阅读更多...
数据结构与算法之经典排序算法

数据结构与算法之经典排序算法

一、简单排序 在我们的程序中，排序是非常常见的一种需求，提供一些数据元素，把这些数据元素按照一定的规则进行排序。比如查询一些订单按照订单的日期进行排序，再比如查询一些商品，按照商品的价格进行排序等等。所以，接下来我们要学习一些常见的排序算法。 1.1冒泡排序（Bubble Sort） 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 排序原理： 比较相邻的元素
阅读更多...
C语言/数据结构——每日一题（分割链表）

C语言/数据结构——每日一题（分割链表）

一.前言 今天在LeetCode觉得很不错，想和大家们一起分享这道链表题——分割链表：https://leetcode.cn/problems/partition-list-lcci废话不多说，让我们直接进入正题吧。 二.正文 1.1题目描述 1.2题目分析 大致思路：我们可以通过建立两个链表，一个小链表，一个大链表。 当原链表在遍历的过程中，如果该数据小于x，我们就把该节点尾插到
阅读更多...
算法数据结构--单调栈

算法数据结构--单调栈

文章目录 介绍单调递增栈单调递减栈图示应用场景 步骤模板Deque用法例题[739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)[496. 下一个更大元素 I](https://leetcode.cn/problems/next-greater-element-i/) 总结 介绍 单调栈是一种特殊的栈数据结构，
阅读更多...
【ZZULIOJ】1095: 时间间隔（函数专题）（Java）

【ZZULIOJ】1095: 时间间隔（函数专题）（Java）

目录 题目描述 输入 输出 样例输入 Copy 样例输出 Copy 提示 code 题目描述 从键盘输入两个时间点(24小时制），输出两个时间点之间的时间间隔，时间间隔用“小时:分钟:秒”表示。要求程序定义如下两个函数，并在main()中调用这两个函数实现相应的功能,其中main函数系统已经实现，你只需要完成下面这两个函数的定义。  //把时分秒转换成秒并返回, 三个参
阅读更多...
[数据结构]———归并排序

[数据结构]———归并排序

具体代码：在gitee仓库：登录 - Gitee.com 目录 ​编辑 1.基本思想：   2. 代码解析 1.分析  2.逻辑图 3.运行结果  1.基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先
阅读更多...
数据结构之红黑树——BST的变种2

数据结构之红黑树——BST的变种2

转自：http://hxraid.iteye.com/blog/611816 感谢原文作者的分享 红黑树的性质与定义 红黑树(red-black tree) 是一棵满足下述性质的二叉查找树： 1. 每一个结点要么是红色，要么是黑色。 2. 根结点是黑色的。 3. 所有叶子结点都是黑色的（实际上都是Null指针，下图用NIL表示）。叶子结点不包含任何关键字信
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2