温馨提示×

温馨提示×

您好，登录后才能下订单哦！

密码登录×
登录注册×
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
登 录 注册有礼
云服务器 香港服务器 高防服务器
最新更新 网站标签 地图导航
产品

C语言中单链表如何实现

发布时间：2022-11-15 09:23:11 来源：亿速云 阅读：102 作者：iii 栏目：开发技术

这篇文章主要介绍“C语言中单链表如何实现”，在日常操作中，相信很多人在C语言中单链表如何实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C语言中单链表如何实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

    通过对顺序表的学习，我们可以发现顺序表有以下几点缺陷：

    1.空间不够时需要扩容，扩容尤其是用realloc进行异地扩容时，是有一定代价的，其次还可能存在一定空间浪费。

    2.头部或者中间插入删除，需要挪动数据，效率低下。

    那我们可以对其所具有的缺陷进行优化：可以按需申请空间同时插入删除时不挪动数据。而单链表就符合这些优化所具有特点。但是我们要注意的是单链表具有这些优点并不代表链表就可以完全替代顺序表。

    一、单链表的概念

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

    C语言中单链表如何实现

    从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续，物理结构中指针域存储的是下一个结点的地址；而且链式结构的结点一般都是从堆上申请出来的；从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。链表存储数据的区域可分为数据域和指针域：

    C语言中单链表如何实现

    用代码表示链表中的数据域和指针域如下：

    typedef int STLDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}STLNode;

    思考：为什么在申请的时候需要申请堆上的空间？因为堆上申请的空间存储数据的时候不会因为函数销毁而销毁，堆上的空间需要的时候就申请，不需要的时候就释放；函数栈帧上开辟的空间存储的数据会因为函数栈帧的销毁而释放，后面在进行尾插和头插时候新的结点不能链接到表上。

    二、单链表的基本操作

    1.创建单个结点

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

    2.创建具有n个结点的链表

    SLTNode* CreateSList(int n)
{
    int i = 0;
    SLTNode* ptail = NULL,*phead = NULL;
    for (i = 0; i < n; i++)
    {
        SLTNode* newnode = BuySLTNode(i);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
    }
    return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//    int i = 0;
//    SLTNode* ptail = NULL;
//    for (i = 0; i < n; i++)
//    {
//        SLTNode* newnode = BuySLTNode(i);
//        if (*pphead == NULL)
//        {
//            ptail = *pphead = newnode;
//        }
//        else
//        {
//            ptail->next= newnode;
//            ptail = newnode;
//        }
//    }
//}

    上述代码中提供了两种实现方式，没有注释的是返回头指针的，注释内容是没有返回值，形参使用的是二级指针改变头指针指向的地址。

    3.打印单链表

    void SLTPrint(SLTNode* phead)
{
    SLTNode* tail = phead;
    while (tail)
    {
        printf("%d ", tail->val);
        tail = tail->next;
    }
    printf("\n");
}

    4.尾插

    void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
    SLTNode* tail = *pphead;
    SLTNode* newnode = BuySLTNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

    尾插时，要注意当单链表的头结点为空的时候，要先将新结点作为头结点。因为当头结点为空时，需要改变头指针，所以传过来的为二级指针（也可以使用一级指针，不过此时要有返回值），要想改变SLTNode*的值，就要传递它的地址即SLTNode**类型。

    5.尾删

    void SLTPopBack(SLTNode** pphead)//尾删
{
    assert(*pphead);
    if ((*pphead)->next==NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        SLTNode* prev = NULL;
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

    尾删时也要注意区分是否为头结点；同时注意删除后，要将其置空prev->next = NULL。

    6.头插

    void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

    7.头删

    void SLTPopFront(SLTNode** pphead)//头删
{
    assert(*pphead);
    SLTNode* nextnode = (*pphead)->next;
    free(*pphead);
    *pphead = nextnode;
}

    头插和头删是单链表的优势，尾插和尾删是顺序表的优势。同时在尾删时注意将*pphead加上括号用来区分优先级，否则会报错。

    8.查找某个结点

    SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
    SLTNode* tail = phead;
    while (tail)
    {
        if (tail->val == x)
        {
            return tail;
        }
        tail = tail->next;
    }
    return NULL;
}

    注意循环条件，当循环条件写为while(tail->next)时，会有空指针的风险，同时还会漏掉最后一个结点。

    9.在某个结点后面插入

    void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = pos->next;
    pos->next = newnode;
    newnode->next = tail;
}

    10.在某个结点前面插入

    void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    if (pos == *pphead)
    {
        /*newnode->next = *pphead;
        *pphead = newnode;*/
        SLTPushBack(pphead, x);
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next != pos)
        {
            tail = tail->next;
        }
        tail->next = newnode;
        newnode->next = pos;
    }
}

    11.删除某个位置后面的结点

    void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLTNode* tail = pos->next;
        pos->next = tail->next;
        free(tail);
    }
}

    12.删除某个结点

    void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
    assert(pos);
    SLTNode* tail = *pphead;
    if (pos == *pphead)
    {
        SLTNode* nextNode = (*pphead)->next;
        free(*pphead);
        *pphead = nextNode;
    }
    else
    {
        while (tail->next != pos)
        {
            tail = tail->next;
        }
        tail->next = pos->next;
        free(pos);
    }
}

    13.销毁单链表

    void SLTDestroy(SLTNode** pphead)//销毁
{
    assert(*pphead);
    SLTNode* tail = *pphead;
    
    while (tail)
    {
        SLTNode* next = tail->next;
        free(tail);
        tail = next;
    }
    *pphead = NULL;
}

    注意最后要将头结点置空。

    三、测试代码

    #define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SList {
	struct Slist* next;
	SLTDataType val;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuySLTNode malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
SLTNode* CreateSList(int n)
{
	int i = 0;
	SLTNode* ptail = NULL, * phead = NULL;
	for (i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//	int i = 0;
//	SLTNode* ptail = NULL;
//	for (i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (*pphead == NULL)
//		{
//			ptail = *pphead = newnode;
//		}
//		else
//		{
//			ptail->next= newnode;
//			ptail = newnode;
//		}
//	}
//}
void SLTPrint(SLTNode* phead)
{
	SLTNode* tail = phead;
	while (tail)
	{
		printf("%d ", tail->val);
		tail = tail->next;
	}
	printf("\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* tail = *pphead;
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);
	SLTNode* nextnode = (*pphead)->next;
	free(*pphead);
	*pphead = nextnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
	SLTNode* tail = phead;
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
	pos->next = newnode;
	newnode->next = tail;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	if (pos == *pphead)
	{
		/*newnode->next = *pphead;
		*pphead = newnode;*/
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = pos;
	}
}
void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* tail = pos->next;
		pos->next = tail->next;
		free(tail);
	}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
	assert(pos);
	SLTNode* tail = *pphead;
	if (pos == *pphead)
	{
		SLTNode* nextNode = (*pphead)->next;
		free(*pphead);
		*pphead = nextNode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}
void SLTDestroy(SLTNode** pphead)//销毁
{
	assert(*pphead);
	SLTNode* tail = *pphead;

	while (tail)
	{
		SLTNode* next = tail->next;
		free(tail);
		tail = next;
	}
	*pphead = NULL;
}
void TestSL()
{
	SLTNode* plist = CreateSList(2);
	/*SLTNode* plist = NULL;
	CreateSList(&plist,10);//没有返回值
	SLTPrint(plist);*/
	SLTPushBack(&plist, 600);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPushFront(&plist, 300);
	SLTPushFront(&plist, 400);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 600);
	if (pos)
	{
		SLInsertAfter(pos, 700);
		SLTInsert(&plist, pos, 500);
		SLTEraseAfter(pos);
		//SLTErase(&plist, pos);

	}
	SLTPrint(plist);
	SLTDestroy(&plist);
	SLTPrint(plist);
}
int main()
{
	TestSL();
	return 0;
}

    到此，关于“C语言中单链表如何实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！

    向AI问一下细节
    推荐阅读：
    1. C语言实现单链表（LinkedList）
    2. [c语言]单链表的实现

    免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

    c语言

    猜你喜欢

    最新资讯
    相关推荐

    相关标签

    c语言的一些基础程序 c语言学习 c语言原创文章 c语言学习总结 c语言结构体 c语言中 c语言初学者 c语言操作 c语言指针 c语言基础 c语言库函数 c语言编程 c语言项目 c语言c程序c/c++ C语言标识符 ai android access == auto
    AI
    助
    手
    产品服务
    地区划分
    专题活动
    帮助支持
    关于我们
    售后咨询
    7*24小时在线电话：400-100-2938
    7*24小时在线 QQ：800811969
    关注亿速云

    亿速云公众号

    手机网站二维码

    Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有

    广州亿速云计算有限公司粤ICP备17096448号-1 粤公网安备 44010402001142号增值电信业务经营许可证编号：B1-20181529