C语言单链表的图文示例讲解

目录
  • 一、单链表的结构
  • 二、单链表的函数接口
    • 1. 申请结点及打印单链表
    • 2. 尾插尾删
    • 3. 头插头删
    • 4. 中间插入和删除
      • 1. 在 pos 指向的结点之后插入结点
      • 2. 在 pos 指向的结点之前插入结点
      • 3. 删除 pos 指向的结点的后一个结点
      • 4. 删除 pos 指向的结点
    • 6. 查找
    • 7. 销毁单链表

在上一篇所讲述的 动态顺序表 中存在一些缺陷

1、当空间不够时需要扩容,扩容是有一定的消耗的

如果每次空间扩大一点,可能会造成空间的浪费,而空间扩小了,又会造成频繁的扩容2、在顺序表中进行头部和中部的插入时需要移动数据,效率低下

对于顺序表的这些缺陷,有如下解决方案

1、需要时申请一块空间,不需要时将其释放

2、插入删除不需要移动数据

而链表就符合这两点,本篇介绍 无头单向非循环链表(单链表)

一、单链表的结构

空链表: 此时没有存储数据,只有一个指针指向 NULL

以上便是单链表的结构:

  • 每一块空间可以按需申请释放
  • 插入和删除不需要移动数据,修改每块空间的指针指向即可

在习惯上将申请的一块一块的空间称为结点,指向第一个结点的指针称为头指针

//数据的类型:这里以 int 来举例
typedef int SLTDataType;
//结点的类型
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

二、单链表的函数接口

1. 申请结点及打印单链表

在插入时需要申请结点,为了避免麻烦重复的操作,这里将申请结点封装为一个函数

申请结点函数如下:

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode == NULL)
	{
		//开辟空间失败,打印错误信息
		perror("malloc");
		//结束程序
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

为了验证插入、删除等得到的结果是否正确,提供打印单链表的函数,这里数据类型以 int 为例,当读者采用的类型不同时,自行更改函数即可

打印单链表函数如下:

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

2. 尾插尾删

尾插:在链表的最后一个结点之后插入结点

尾插函数如下:

//在链表为空时,需要改变头指针,这里采用传二级指针的方式
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//申请结点
	SLTNode* newnode = BuySLTNode(x);
	//链表为空时
	if(*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到最后一个结点
		SLTNode* ptail = *pphead;
		while(ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

尾删:删除链表最后一个结点

尾删函数如下:

//链表只有一个结点时,需要改变头指针,这里采用传二级指针的方式
void SLTPopBack(SLTNode** pphead)
{
	//链表为空时,无法删除
	assert(*pphead);
	//链表只有一个结点时
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找到倒数第二个结点
		SLTNode* ptail = *pphead;
		while(ptail->next->next)
		{
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}
}

3. 头插头删

头插: 在第一个结点之前插入新结点

头插函数如下:

//需要改变头指针,这里采用传二级指针的方式
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	//申请结点
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头删:删除链表的第一个结点

头删函数如下:

//需要改变头指针,这里采用传二级指针的方式
void SLTPopFront(SLTNode** pphead)
{
	//链表为空时,无法删除
	assert(*pphead);
	//保存第二个结点
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

4. 中间插入和删除

中间插入:通过后面介绍的查找函数 SLTFind 获得指向结点的指针 pos,在 pos 指向的 结点之前 或 之后 插入结点

1. 在 pos 指向的结点之后插入结点

在 pos 之后插入结点函数如下:

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//pos 不能为空
	assert(pos);
	//申请结点
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2. 在 pos 指向的结点之前插入结点

在 pos 之前插入结点函数如下:

//pos 指向头结点时,需要改变头指针,这里采用传二级指针的方式
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//pos 不能为空
	assert(pos);
	//头插
	if(*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		//找到 pos 的前一个结点
		SLTNode* prev = *pphead;
		while(prev->next != pos)
		{
			prev = prev->next;
		}
		//申请结点
		SLTNode* newnode = BuySLTNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

中间删除:通过后面介绍的查找函数 SLTFind 获得指向结点的指针 pos,删除 pos 指向的结点 或 后一个结点

3. 删除 pos 指向的结点的后一个结点

删除 pos 之后的结点函数如下:

void SLTEraseAfter(SLTNode* pos)
{
	//pos 不能为空
	assert(pos);
	//指向最后一个结点时,不做处理
	if(pos->next == NULL)
	{
		return;
	}
	else
	{
		//保存后一个结点
		SLTNode* next = pos->next;
		pos->next = next->next;
		free(next);
	}
}

4. 删除 pos 指向的结点

删除 pos 指向的结点函数如下:

//pos 指向头结点时,需要改变头指针,这里采用传二级指针的方式
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	//pos 不能为空
	assert(pos);
	//头删
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到 pos 的前一个结点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

6. 查找

查找:如果数据存在,返回该数据结点的指针,不存在返回 NULL

查找函数如下:

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

7. 销毁单链表

在单链表中,存储数据的结点是由自己开辟的,当不使用单链表时,应将其销毁

销毁单链表函数如下:

需要将头指针置空,这里采用传二级指针的方式
void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		//保存下一个结点
		SLTNode* nextnode = cur->next;
		free(cur);
		cur = nextnode;
	}
	//将头指针置空
	*pphead = NULL;
}

到此这篇关于C语言单链表的图文示例讲解的文章就介绍到这了,更多相关C语言单链表 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言数据结构之单链表存储详解

    目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码 如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一

  • C语言中单链表的基本操作(创建、销毁、增删查改等)

    目录 链表分类 单链表的介绍 单链表的基本操作 创建 打印 尾插 头插 尾删 头删 查找 任意位置插入 任意位置删除 销毁 完整代码 总结 链表分类 链表主要有下面三种分类方法: 单向或者双向 带头或者不带头 循环或者非循环综合来看链表有八种类型,本文主要针对的是不带头节点的非循环单链表. 单链表的介绍 typedef struct SListNode { DataType data;//数据域 struct SListNode *next;//结构体指针,指向下一个节点 }SListNode;

  • C语言单链表遍历与求和示例解读

    目录 单链表的遍历 单链表的求和 单链表的遍历 描述: 牛牛从键盘输入一个长度为 n 的数组,问你能否用这个数组组成一个链表,并顺序输出链表每个节点的值. 输入描述: 第一行输入一个正整数 n ,表示数组的长度 第二行输入n个数据 输出描述: 制作一个链表然后输出这个链表的值 输入: 4 5 4 2 1 输出: 5 4 2 1 #include<stdio.h> #include<stdlib.h> typedef int DataType; typedef struct link

  • C语言数据结构之单链表的查找和建立

    目录 单链表的查找 按位查找 按值查找 单链表的建立 尾插法 头插法建立单链表 单链表的查找 其实在单链表的插入和删除中,我们已经使用过单链表的查找方法,因为插入和删除的前提都是先找到对应的结点,所以这里就不再多解释 按位查找 GetElem(L, i):按位查找操作.获取表 L 中第 i 个位置的元素的值 //按位查找 LNode * GetElem(LinkList L, int i) { if (i < 0) return false; LNode *p; //指针p指向当前扫描到的结点

  • C语言数据结构之单链表操作详解

    目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点 注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/

  • C语言实现单链表的基本操作分享

    目录 导语 单链表 单链表的特点 定义 初始化操作 头插法 尾插法 删除第i个元素 在第i个位置插入 导语 无论是顺序存储结构还是链式存储结构,在内存中进行存放元素的时候,不仅需要存放该元素的相关信息,还需要存放该元素和其他元素之间的关系,而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系,不需要额外的信息去表达元素和元素之间的关系,而对于链式存储这种非顺序存储的结构,需要额外附加指针去表示这种关系. 单链表 每个结点除了存放数据元素外,还要存储指向下一个节点的指针

  • C语言中单链表(不带头结点)基本操作的实现详解

    目录 一.单链表的概念 二.单链表的基本操作 1.创建单个结点 2.创建具有n个结点的链表 3.打印单链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个结点 9.在某个结点后面插入 10.在某个结点前面插入 11.删除某个位置后面的结点 12.删除某个结点 13.销毁单链表 三.测试代码 通过对顺序表的学习,我们可以发现顺序表有以下几点缺陷: 1.空间不够时需要扩容,扩容尤其是用realloc进行异地扩容时,是有一定代价的,其次还可能存在一定空间浪费. 2.头部或者中间插入删除,需要挪动

  • C语言单链表的图文示例讲解

    目录 一.单链表的结构 二.单链表的函数接口 1. 申请结点及打印单链表 2. 尾插尾删 3. 头插头删 4. 中间插入和删除 1. 在 pos 指向的结点之后插入结点 2. 在 pos 指向的结点之前插入结点 3. 删除 pos 指向的结点的后一个结点 4. 删除 pos 指向的结点 6. 查找 7. 销毁单链表 在上一篇所讲述的 动态顺序表 中存在一些缺陷 1.当空间不够时需要扩容,扩容是有一定的消耗的 如果每次空间扩大一点,可能会造成空间的浪费,而空间扩小了,又会造成频繁的扩容2.在顺序表

  • c语言单链表尾添加的深入讲解

    前言 犹豫了几天,看了很多大牛写的关于c语言链表,感触很多,终于下定决心,把自己对于链表的理解随之附上,可用与否,自行裁夺.由于作者水平有限也是第一次写,不足之处,竭诚希望得到各位大神的批评指正.制作不易,不喜勿喷,谢谢!!! 在正文开始之前,我先对数组和链表进行简单的对比分析. 链表也是一种很常见的数据结构,不同于数组的是它是动态进行存储分配的一种结构.数组存放数据时,必须要事先知道元素的个数.举个例子,比如一个班有40个人,另一个班有100个人,如果要用同一个数组先后来存放这两个班的学生数据

  • C语言单链表实现方法详解

    本文实例讲述了C语言单链表实现方法.分享给大家供大家参考,具体如下: slist.h #ifndef __SLIST_H__ #define __SLIST_H__ #include<cstdio> #include<malloc.h> #include<assert.h> typedef int ElemType; typedef struct Node { //定义单链表中的结点信息 ElemType data; //结点的数据域 struct Node *next

  • C语言单链表实现多项式相加

    本文实例为大家分享了C语言单链表实现多项式相加的具体代码,供大家参考,具体内容如下 //多项式的相加和相乘 #include<stdio.h> #include<stdlib.h> #pragma warning(disable:4996)//兼容scanf typedef struct node { int coef; int expon; struct node* link; }Polynode,*Polynomial; Polynomial InsertPolyLinklis

  • Go语言单链表实现方法

    本文实例讲述了Go语言单链表实现方法.分享给大家供大家参考.具体如下: 1. singlechain.go代码如下: 复制代码 代码如下: ////////// //单链表 -- 线性表 package singlechain //定义节点 type Node struct {     Data int     Next *Node } /* * 返回第一个节点 * h 头结点  */ func GetFirst(h *Node) *Node {     if h.Next == nil {  

  • C语言单链表的实现

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素. 链表结构: SList.h #pragma once typedef int DataType; typedef struct SListNode { DataType data; struct SListNode* next; }SListNode; // 如果要修改链表就必须加引用 SListNode* _BuyNode(DataType x); //建立节点 void PrintSlist(SListNode

  • 详解go语言单链表及其常用方法的实现

    目的 在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构. 1.链表的特点和初始化 1.1.链表的特点 用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的) 1.2.结点 结点(node) 数据域 => 存储元素信息 指针域 => 存储结点的直接后继,也称作指针或链 首元结点 是指链表中存储的第一个数据元素的结点 头结点 是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须) 头指

  • C语言单链表实现学生管理系统

    本文实例为大家分享了C语言单链表实现学生管理系统的具体代码,供大家参考,具体内容如下 代码: #include<stdio.h> #include<stdlib.h> #include <string.h> #include <malloc.h> struct Student { int num;//学号 char name[20];//名字 char sex[2]; int age; struct Student *next; }; void insert

  • R语言的下载安装图文教程讲解

    什么是R语言 R语言是一个开源的数据分析环境,起初是由数位统计学家建立起来,以更好的进行统计计算和绘图,这篇wiki中包含了一些基本情况的介绍.由于R可以通过安装扩展包(Packages)而得到增强,所以其功能已经远远不限于统计分析,如果感兴趣的话可以到官方网站了解关于其功能的更多信息. 至于R语言名称的由来则是根据两位主要作者的首字母(Robert Gentleman and Ross Ihaka),但过于简短的关键词也造成在搜索引擎中很不容易找到相关的资料.不过这个专门的搜索网站可以帮到你.

随机推荐