C语言数据结构之单链表的实现

目录
  • 一.为什么使用链表
  • 二.链表的概念
  • 三.链表的实现
    • 3.1 创建链表前须知
    • 3.2 定义结构体
    • 3.3 申请一个节点
    • 3.4 链表的头插
    • 3.5 链表的尾插
    • 3.6 链表的尾删
    • 3.7 链表的头删
    • 3.8 寻找某节点
    • 3.9 在指定节点前插入节点
    • 3.10 删除指定节点前的节点
    • 3.11 链表的销毁

一.为什么使用链表

在学习链表以前,我们存储数据用的方式就是数组。使用数组的好处就是便于查找数据,但缺点也很明显。

使用前需声明数组的长度,一旦声明长度就不能更改

插入和删除操作需要移动大量的数组元素,效率慢

只能存储一种类型的数据.

为了解决上述的问题,我们就可以使用链表来存储数据。

二.链表的概念

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

三.链表的实现

3.1 创建链表前须知

结点:链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据;二为下一个结点的地址,

头结点:在单链表的第一个结点之前附设一个结点,这个节点不存储数据,称之为头结点

3.2 定义结构体

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

typedef int SLDateType; //链表中存储的数据类型,可换成其他

typedef struct SListNode
{
	SLDateType date;
	struct SListNode* next; //指向下一个节点的指针
}SListNode;

3.3 申请一个节点

SListNode* BuyListNode(SLDateType x)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    if (NULL == newNode)
    {
        printf("malloc error\n"); //内存开辟失败
        exit(-1);
    }
    else
    {
        newNode->date = x; // 给新节点赋值
        newNode->next = NULL;
    }
    return newNode;
}

3.4 链表的头插

void SListPushFront(SListNode** pphead/*要改动头指针,所以要传递二级指针*/, SLDateType x)
{
    SListNode* newNode = BuyListNode(x); //申请节点
    newNode->next = *pphead;
    *pphead = newNode;
}

3.5 链表的尾插

void SListPushBack(SListNode** pphead, SLDateType x)
{
    SListNode* newNode = BuyListNode(x);
    if (*pphead == NULL) //若头指针为空,则链表为空链表,直接将新节点接到头指针后
    {
        *pphead = newNode;
    }
    else
    {
        SListNode* tail = *pphead;
        while (tail->next != NULL) //找链表的尾部
        {
            tail = tail->next;
        }
        tail->next = newNode;//将新节点接到尾部
    }
}

3.6 链表的尾删

void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	if (*pphead == NULL)//链表为空,则不进行任何操作
	{
		return;
	}
	else if ((*pphead)->next == NULL) //链表只有一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//其余情况
	{
		SListNode* tail = *pphead; //链表的尾部节点
		SListNode* pre = NULL;//链表尾的前一个节点
		while (tail->next != NULL)//找尾
		{
			pre = tail;
			tail = tail->next;
		}
		pre->next = tail->next; //将尾节点的指针域赋值给前一个节点的指针域
		free(tail);
	}
}

3.7 链表的头删

void SListPopFront(SListNode** pphead)
{
    assert(pphead);
    if (*pphead == NULL) //链表为空什么也不做
    {
        return;
    }
    else
    {
        SListNode* head = *pphead;//记录原本的第一个节点
        *pphead = head->next; //让头指针指向第二个节点
        free(head);//释放第一个节点
    }
}

3.8 寻找某节点

SListNode* SListFind(SListNode* phead, SLDateType x)
{
    SListNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->date == x) //找到则返回该节点
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL; //未找到则返回空
}

3.9 在指定节点前插入节点

void SListInsert(SListNode** pphead, SListNode* pos/*要插入的位置*/, SLDateType x)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* cur = *pphead; //当前所指向的位置
		SListNode* pre = NULL; //前一个节点
		while (cur != pos)
		{
			pre = cur;
			cur = cur->next;
		}
		SListNode* newNode = BuyListNode(x);
		pre->next = newNode;
		newNode->next = cur;
	}
}

3.10 删除指定节点前的节点

void SListErase(SListNode** pphead, SListNode* pos/*要插入的位置*/)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* cur = *pphead;
		SListNode* pre = *pphead;
		while (cur != pos)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = cur->next;
		free(cur);
	}
}

3.11 链表的销毁

void SListDestory(SListNode** pphead)
{
    if (*pphead == NULL)
    {
        return;
    }
    else
    {
        while (*pphead != NULL)
        {
            SListNode* cur = *pphead;
            *pphead = cur->next;
            free(cur);
        }
    }
}

到此这篇关于C语言数据结构之单链表的实现的文章就介绍到这了,更多相关C语言 单链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言数据结构实例讲解单链表的实现

    目录 1.单链表 2.单链表的实现 头文件 函数的实现 (1)打印链表 (2)动态申请结点 (3)尾插 (4)头插 (5)尾删 (6)头删 (7)查找 (8)在pos之前插入 (9)删除pos (10)在pos之后插入 (11)在pos后删除 (12)最后用完记得销毁 3.各功能的测试 这里我们来简单实现单链表的增删查找. 1.单链表 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 . (链表和我们生活中最接近的就是火车了.) 2.单链

  • C语言实题讲解快速掌握单链表上

    目录 1.移除链表元素 2.反转链表 3.链表的中间节点 4.链表中倒数第k个节点 5.合并两个有序链表 6.链表分割 1.移除链表元素 链接直达: 移除链表元素 题目: 思路: 此题要综合考虑多种情况,常规情况就如同示例1,有多个节点,并且val不连续,但是非常规呢?当val连续呢?当头部就是val呢?所以要分类讨论 常规情况: 需要定义两个指针prev和cur,cur指向第一个数据,prev指向cur的前一个.依次遍历cur指向的数据是否为val,若是,则把prev的下一个节点指向cur的下

  • C语言 超详细模拟实现单链表的基本操作建议收藏

    目录 1 链表的概念及结构 2 链表的分类 3 链表的实现无头+单向+非循环链表增删查改实现 3.1 链表的定义 3.2 链表数据的打印 3.3 链表的尾插 3.4 链表空间的动态申请 3.5 链表的头插 3.6 链表的尾删 3.7 链表的头删 3.8 链表任意位置的前插入 3.9 链表任意位置的后插入 3.10 链表的任意位置的删除 3.11 链表的任意位置的前删除 3.12 链表的任意位置的后删除 3.13 链表的销毁 3.14 链表的总结 1 链表的概念及结构 概念:链表是一种物理存储结构

  • ​​​​​​​C语言实现单链表基本操作方法

    目录 存储结构 基本功能 头插法创建单链表 尾插法创建单链表 获取指定位置的元素 在指定位置插入元素 删除指定位置的元素 获取单链表的长度 合并两个非递减的单链表 晴链表 遍历打印单链表 附上完整代码 存储结构 typedef int dataType://爱护据类型 typedef struct Node { DataType data; // 结点数据 struct Node *next; // 指向下一个结点的指针 } Node, *LinkList; 基本功能 头插法创建单链表void

  • C语言实题讲解快速掌握单链表下

    目录 1.移除链表元素 2.反转链表 3.链表的中间节点 4.链表中倒数第k个节点 5.合并两个有序链表 6.链表分割 1.移除链表元素 链接直达: 移除链表元素 题目: 思路: 此题要综合考虑多种情况,常规情况就如同示例1,有多个节点,并且val不连续,但是非常规呢?当val连续呢?当头部就是val呢?所以要分类讨论 常规情况: 需要定义两个指针prev和cur,cur指向第一个数据,prev指向cur的前一个.依次遍历cur指向的数据是否为val,若是,则把prev的下一个节点指向cur的下

  • C语言数据结构与算法之单链表

    目录 基本概念 读取数据元素 获取第i个结点的数据元素 插入数据元素  初始化链表 打印链表 顺序表查空 顺序表的删除  删除第i个结点及其数据元素 情况1:当删除的是第一个元素 情况2:除第一个结点外 完整代码 删除单链表整表 单链表VS顺序表 基本概念 链表的每一个结点中只包含一个指针域 优点 : 储存空间利用高效 举例来说: typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Studen

  • 数据结构 C语言实现循环单链表的实例

    数据结构 C语言实现循环单链表的实例 实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环

  • C语言数据结构之单链表的实现

    目录 一.为什么使用链表 二.链表的概念 三.链表的实现 3.1 创建链表前须知 3.2 定义结构体 3.3 申请一个节点 3.4 链表的头插 3.5 链表的尾插 3.6 链表的尾删 3.7 链表的头删 3.8 寻找某节点 3.9 在指定节点前插入节点 3.10 删除指定节点前的节点 3.11 链表的销毁 一.为什么使用链表 在学习链表以前,我们存储数据用的方式就是数组.使用数组的好处就是便于查找数据,但缺点也很明显. 使用前需声明数组的长度,一旦声明长度就不能更改 插入和删除操作需要移动大量的

  • C语言数据结构之单链表与双链表的增删改查操作实现

    目录 前言 单链表的增删改查 定义结构体以及初始化 增加结点 删除结点 查找修改结点 移除结点 最终效果 双链表的基本操作 初始化建表 遍历双链表 指定位置插入结点 指定位置删除结点 查找结点位置 最终效果 结语 前言 上篇博客分享了创建链表传入二级指针的细节,那么今天就分享几个c语言课程实践设计吧.这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了,那么再应对复杂的链表类的题也就能慢慢钻研了.学习是一个积累的过程,想要游刃有余就得勤学苦练! 单链表的增删改查 (1)项目需求 构造带有头结点的

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

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

  • 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;/

  • Go语言数据结构之单链表的实例详解

    目录 任意类型的数据域 实例01 快慢指针 实例02 反转链表 实例03 实例04 交换节点 实例05 任意类型的数据域 之前的链表定义数据域都是整型int,如果需要不同类型的数据就要用到 interface{}. 空接口 interface{} 对于描述起不到任何的作用(因为它不包含任何的method),但interface{}在需要存储任意类型的数值的时候相当有用,因为它可以存储任意类型的数值. 一个函数把interface{}作为参数,那么它可以接受任意类型的值作为参数:如果一个函数返回i

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

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

  • python算法与数据结构之单链表的实现代码

    =一.链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是

  • Go 语言数据结构之双链表学习教程

    目录 双链表 创建节点 双链表遍历 扩展功能 链表长度 插入 删除 反转双链表 总结 双链表 双链表 (Doubly Linked List),每个节点持有一个指向列表前一个元素的指针,以及指向下一个元素的指针. 双向链表的节点中包含 3 个字段: 数据域 Value 一个 Next 指针指向双链表中的下一个节点 一个 Prev 指针,指向双链表中的前一个节点 结构体如下: type Node struct { Prev *Node Value int Next *Node } 实际应用: 音乐

  • C#数据结构之单链表(LinkList)实例详解

    本文实例讲述了C#数据结构之单链表(LinkList)实现方法.分享给大家供大家参考,具体如下: 这里我们来看下"单链表(LinkList)".在上一篇<C#数据结构之顺序表(SeqList)实例详解>的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大. 而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data

随机推荐