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

本文小编为大家详细介绍“C语言数据结构之单链表怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言数据结构之单链表怎么实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

一.为什么使用链表

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

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

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

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

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

二.链表的概念

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

三.链表的实现

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语言数据结构之单链表怎么实现”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。