首页 > 其他分享 >C语言简单的数据结构：单链表

C语言简单的数据结构：单链表

时间：2024-04-11 11:30:36浏览次数：17  
标签：pphead 单链 SLTNode NULL pos C语言 next 数据结构 plist

目录：


我们在使用顺序表的时候我们发现了一些问题：
1.涉及到中间插入和头插时会进行数据的移动，导致效率较低
2.增容的空间会进行数据的拷贝
3.每次申请的空间不一定被使用，导致空间浪费
以上都说明顺序表不是很完美的，那有什么解决方法呢？
没错那就是：链表

1. 单链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。
所以链表也是线性表的一种（物理结构上不一定时线性的，逻辑结构是连续的）

在这里插入图片描述
这就是链表的结构，它是由存储的数据和指向下一个节点的指针组成的
那么链表的定义就可以写出来了：
在这里插入图片描述

2. 单链表的实现

2.1单链表的定义、创建和打印

2.11单链表的定义

首先是文件的创建和之前的一样：SList.h头文件，SList.c、test.c源文件
然后就是定义结构体了，这里用到的方法和顺序表的方法一样
在这里插入图片描述

2.12单链表的创建

接下来我们进行节点的创建，这里创建了四个节点
在这里插入图片描述

那我们如何让他们互相找到呢，这就是前面说的：放指向下一个节点的指针
在这里插入图片描述

这样就构成了一个链表

2.13单链表的打印

打印函数的函数的声明：
在这里插入图片描述

在这里插入图片描述

这里多创建一个指针防止对原来指针进行改变
在这里插入图片描述
我们在这里创建了一个pcur来接受传进来的传进来的地址接收，然后当pcur指向的不为NULL指针时，将数值打印出来，然后让pcur 指向下一个节点的地址，这就是链表的遍历

测试：
在这里插入图片描述

2.2单链表的头插和尾插

在这里插入图片描述

函数的声明（但这里有问题下文会改正）
既然要加数据就要先把数据放入节点中：
在这里插入图片描述
简单的空间开辟，将数值放入即可

2.21尾插

在这里插入图片描述
将我们最后的节点指向NULL改成限一个节点的地址，然后让下一个节点指向NULL即可
在这里插入图片描述

但是这个代码中有问题：
原链表如果是空链表，那么while语句就对NULL指针解引用，就会出现问题
解决方法：直接将新开辟的节点给phead即可
在这里插入图片描述
但还是有问题
在这里插入图片描述
这里并没有改变，我们进行调试：
在这里插入图片描述
发现形参变了而实参没有变化，就要传地址，而不是传值
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这样就改完了
测试：
在这里插入图片描述

在这里插入图片描述
这样就正确了，在优化一下：
在这里插入图片描述

2.22头插

在这里插入图片描述
和尾插一样但是申请的节点要指向之前的链表头，然后成为链表头
在这里插入图片描述
这里如果phead是NULL也可以，直接会替换NULL
测试：
在这里插入图片描述

2.3单链表的头删和尾删

在这里插入图片描述
函数声明

2.31尾删

在这里插入图片描述
将指针到5位置的数据删除掉，好要将第四个节点指向NULL
在这里插入图片描述
用快慢指针进行更改即可
但这个代码还有问题：
在这里插入图片描述
这种情况就不用找尾部节点
在这里插入图片描述
测试：
在这里插入图片描述
此时在进行尾删就会报错
在这里插入图片描述

2.31头删

在这里插入图片描述
创建新指针接收，让后进行释放后再将保存的指针重新赋值即可
测试：
在这里插入图片描述

2.4单链表的查找

声明：
在这里插入图片描述

在这里插入图片描述

链表进行遍历，找不到就返回NULL，一个循环加判断就可以了
测试：
在这里插入图片描述

2.5单链表指定位置的插入和删除

2.51指定位置前插入数据

在这里插入图片描述
在这里插入图片描述

这里因为有pos就一定有数值所以pphead不能为NULL
在这里插入图片描述
这是pos在中间时可以使用，进行遍历然后让prev,newnode,pos相连接就可以了
在这里插入图片描述

代码在头部就行不通，因为在前面无法找到pos，在最后面时可以行的
在这里插入图片描述

这里加个判断进行头插的调用即可
测试：
在这里插入图片描述

2.52指定位置后插入数据

在这里插入图片描述
为什么没有头节点？
因为之后插入直接在pos进行操作即可不用对pos前的数据
在这里插入图片描述
这里连接的方法有两种：
1.是先蓝（尾部连接）再红（头部连接）
2.先红（头部连接）后蓝（尾部连接）
这里分析一下：
在这里插入图片描述

这里第二种pos的指针next已经先改变了，无法再给newnode
在这里插入图片描述
关系明了了，代码不难的
测试：
在这里插入图片描述

2.53删除pos节点

在这里插入图片描述
在这里插入图片描述
这里又涉及到找pos前的数据了，所以有pphead
在这里插入图片描述
这里先找pos将其的指向下个地址给prev，然后释放pos
但这里又有pos在首位的时候会查不到，和之前的解决方法一样
在这里插入图片描述

测试：
在这里插入图片描述

2.54删除pos之后节点

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
这里如果pos后没有节点就不可以删除，要用assert对pos->next进行断言
测试：
在这里插入图片描述
在这里插入图片描述

2.6单链表的销毁

在这里插入图片描述

在这里插入图片描述
要一个一个的释放掉，就要用指针保存下一个节点的地址
在这里插入图片描述
测试：
在这里插入图片描述

本文代码：

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
//定义节点的结构
typedef struct SListNode
{
	SLTDataType data;
	struct SLintNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);//打印链表

SLTNode* SLTBuyNode(SLTDataType x);//新节点存放数据
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//指定位置前插入数据
void SLTInstertAfter(SLTNode* pos, SLTDataType x); //指定位置后插入数据

void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点
void SLTEraseAfter(SLTNode* pos);//删除pos之后节点

void SListDesTroy(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

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

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//新节点的创建
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		//找尾（patil的下一个节点为NULL）
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表和地址都不为NULL
	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)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	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 SLTInstertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(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;
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#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);
	SListDesTroy(&plist);
}

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//SLTPushFront(&plist, 5);
	//SLTPushFront(&plist, 7);
	//SLTPushFront(&plist, 8);
	//SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest03()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* find = SLTFind(plist, 1);
	SLTInstertAfter(find, 11);
	SLTPrint(plist);
	SLTNode* find1 = SLTFind(plist, 4);
	SLTInstertAfter(find1, 11);
	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest04()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SListDesTroy(&plist);
	SLTPrint(plist);
}

int main()
{
	/*SListTest01();*/
	/*SListTest03();*/
	SListTest04();
	return 0;
}

以上就是本文的全部内容了，希望对大家有所帮助，大家加油！！！

标签：pphead,单链,SLTNode,NULL,pos,C语言,next,数据结构,plist
From： https://blog.csdn.net/2302_82004664/article/details/137558585

相关文章

  • （Java）数据结构——排序（第一节）堆排序+PTA L2-012 关于堆的判断
    前言本博客是博主用于复习数据结构以及算法的博客，如果疏忽出现错误，还望各位指正。堆排序（HeapSort）概念堆排序是一种基于堆数据结构的排序算法，其核心思想是将待排序的序列构建成一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，再将剩余元素重新调整为最大堆（或最小堆），重复......
  • C语言顺序表代码实现
    声明：著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除，删除k个元素、有序表插入、元素逆置、2个有序表合并等。#include<stdio.h>#include<stdlib.h>//顺序表的定义：#defineListSiz......
  • C语言单链表代码实现
    声明：著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除，求表长、有序表插入、元素逆置、2个有序表合并等。#include<stdio.h>#include<stdlib.h>//单链表的定义：typedefintDataType......
  • 数据结构：单链表
    一.链表的概念及结构概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。但是在逻辑结构上是顺序的。链表的结构其实就像的火车：车厢是独立存在的，且每节车厢都有车门。想象⼀下这样的场景，假设每节车厢的车门都是锁......
  • C语言笔记二的补充（实例应用）——猜数游戏的简单实现
    猜数字游戏要求：电脑自动生成1~100的随机数玩家猜数字，猜数字的过程中，根据猜测数据的大小给出反馈，直至才对，游戏结束。基础知识搭建：随机数的生成使用rand函数intrand(void);rand函数会返回一个伪随机数，这个随机数的范围是在0~RAND_MAX之间，这个RAND_MAX的大小是依赖编......
  • C语言笔记二——分支和循环（上）
    分支和循环1.if语句1.1if语句的语法形式如下：if(表达式)语句表达式成立（为真）语句执行；表达式不成立（为假）语句不执行。在C语言中，0为假，非0为真。//instance#include<stdio.h>intmain(){  intnum=0;  scanf("%d",&num);  if(num%2==1){   ......
  • C语言: 字符串函数(下)
    片头在上一篇中,我们介绍了字符串函数。在这一篇章中，我们将继续学习字符串函数，准备好了吗？开始咯！1.strncpy函数1.1strncpy函数的用法strncpy是C语言中的一个字符串处理函数，它用于将一个字符串的一部分内容复制到另一个字符串中。其函数原型为:char*strncpy(char*dest......
  • 初识--数据结构
    什么是数据结构？我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了，学习C语言不就够了吗？为什么还要学习数据结构呢？这是因为：数据结构能够解决C语言解决不了的问题，比如：图形，树状图...要了解数据结构，就必须要知道：数据，数据项，数据元素，数据对象，......
  • C语言分支和循环详解
    在程序中基础的三种结构为顺序结构,选择结构(分支结构),循环结构,几乎所有日常可见的事均可分为这三种结构或者这三种结构的组合.今天,我们就来详细了解一下关于C语言分支和循环语句.在正式介绍之前呢,先给大家提及一下C语言的控制语句:C语言共有9种控制语句,可以分为3类:......
  • 常用数据结构
    程序=数据结构+算法，数据结构是程序的骨架，而算法则是程序的灵魂常用的数据结构数组（Array）：是一种线性数据结构，由相同类型的元素组成，可以通过索引访问元素。链表（LinkedList）：是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。栈（Stack）：是一种后进先出（LIFO）的数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99