乐山网站建设

专注高端品牌网站建设行业优质供应商！认准小谭建站！
028-86922220135-1821-9792
  • 首页
  • 网站建设
    网站设计包含服务 网站制作流程 有效沟通方式 售后服务
  • 微信开发
  • 案例展示
    乐山小谭建站公司作品案例展示
  • 新闻资讯
  • 解决方案
  • 小谭建站
  • 联系我们

    • 一篇文章带你学完链表基础（C语言）-创新互联

    链表，也称线性表的链式存储结构，其元素在内存空间上不是连续的，通过指针链接来决定元素的次序。
    链表

    创新互联是一家成都网站制作、成都网站设计，提供网页设计，网站设计，网站制作，建网站，按需网站开发，网站开发公司，从2013年开始是互联行业建设者，服务者。以提升客户品牌价值为核心业务，全程参与项目的网站策划设计制作，前端开发，后台程序制作以及后期项目运营并提出专业建议和思路。目录
    • 一、链表的分类
      • 1.单向或者双向
      • 2.带头或者不带头
      • 3.循环或者非循环
    • 二、单链表的实现
      • 动态申请一个节点
      • 单链表打印
      • 单链表尾插
      • 单链表尾删
      • 单链表头插
      • 单链表头删
      • 单链表查找
      • 单链表pos之后插入x
      • 单链表pos之前插入x
      • 单链表删除pos之后的节点
      • 单链表删除pos节点
      • 单链表销毁
    • 例题——删除链表中等于给定值 val 的所有节点
      • 方法一：原链表修改
      • 方法二：创建新链表
      • 方法三：创建带头链表
    • 例题——反转链表
      • 方法一：迭代法
      • 方法二：递归法
    • 三、双向带头循环链表的实现
      • 动态申请一个节点
      • 初始化
      • 打印
      • 尾插
      • 尾删
      • 头插
      • 头删
      • 查找
      • 插入
      • 删除
      • 判断链表是否为空
      • 返回链表长度
      • 销毁
    • 四、总结

    一、链表的分类

    链表的结构多种多样，以下的情况组合起来就有8种链表结构。

    1.单向或者双向

    单向
    双向

    2.带头或者不带头

    不带头
    带头

    3.循环或者非循环

    非循环
    循环
    虽然有这么多种结构，但是我们最常用的只有两种：
    1.无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。
    非循环
    2.带头双向循环链表：结构最复杂，但实现起来比较简单。
    在这里插入图片描述

    二、单链表的实现
    typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;
	struct SListNode* next;
}SLTNode;
//动态申请一个节点
SLTNode* BuySListNode(SLTDataType x);
//单链表打印
void SLTPrint(SLTNode* phead);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表头插
void SLTPushFount(SLTNode** pphead, SLTDataType x);
//单链表头删
void SLTPopFount(SLTNode** pphead);
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//单链表pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//单链表pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//单链表删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//单链表删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表销毁
void SLTDestroy(SLTNode** pphead);
    动态申请一个节点
    SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{perror("malloc file:");
		exit(-1);//退出程序
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
    单链表打印
    void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;
	while (cur != NULL)
	{printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
    单链表尾插
    void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{*pphead = newnode;
	}
	else
	{SLTNode* tail = *pphead;
		while (tail->next)
		{	tail = tail->next;
		}
		tail->next = newnode;
	}
}

    这里使用二级指针是因为当链表为空时，需要改变一级指针phead为newnode，想要改变一级指针的值要用二级。

    单链表尾删
    void SLTPopBack(SLTNode** pphead)
{assert(*pphead);
	if ((*pphead)->next == NULL)
	{free(*pphead);
		*pphead = NULL;
	}
	else
	{SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{	prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
    单链表头插
    void SLTPushFount(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
    单链表头删
    void SLTPopFount(SLTNode** pphead)
{assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
    单链表查找
    SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;
	while (cur)
	{if (cur->data == x)
		{	return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
    单链表pos之后插入x
    void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
    单链表pos之前插入x
    void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);
	if (*pphead == pos)
	{SLTPushFount(pphead, x);
	}
	else
	{SLTNode* prev = *pphead;
		while (prev->next != pos)
		{	prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

    ------为什么在pos之后插入x相比在之前插入要简单呢？
    因为想要在pos之前插入，必须要找到pos的前一个节点，只能通过遍历链表来找到它。后面的删除指定结点也是相同的道理。

    单链表删除pos之后的节点
    void SLTEraseAfter(SLTNode* pos)
{assert(pos);
	if (pos->next == NULL)
	{return;
	}
	else
	{SLTNode* nextNode = pos->next;
		pos->next = pos->next->next;
		free(nextNode);
	}
}
    单链表删除pos节点
    void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);
	if (*pphead == pos)
	{SLTPopFount(pphead);
	}
	else
	{SLTNode* prev = *pphead;
		while (prev->next != pos)
		{	prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
    单链表销毁
    void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;
	while (cur)
	{SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

    通过以上代码可以看出，相比顺序表，链表的头插和头删要简便许多，而尾插和尾删要繁琐一些，这是因为链表不能随机存取，想要找到最后一个结点必须从头开始遍历。
    学会了单链表的实现，那么有不少单链表的题就可以有思路了，许多题看似复杂，但实际上就是单链表的插入、删除。

    例题——删除链表中等于给定值 val 的所有节点

    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
    val = 5：
    图例

    方法一：原链表修改
    struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *p = head;
	
    while (cur)
    {if(cur == head) //当cur为头时
        {if (cur->val == val)
            {cur = cur->next;
                head = cur;
                p = cur;
            }
            else 
            {cur = cur->next;
            }
        }
        else if (cur->next == NULL) //当cur为尾时
        {if (cur->val == val)
            {cur = cur->next;
                p->next = NULL;
            }
            else 
            {cur = cur->next;
            }
        }
        else //当cur在中间
        {if (cur->val == val)
            {cur = cur->next;
                p->next = p->next->next;
            }
            else 
            {p = cur;
                cur = cur->next;
            }
        }
    }
    return head;
}

    这是我做这道题时想出的第一个方法，这个方法非常繁琐，要考虑三种情况，就是当cur在头、尾、中间。这个方法很容易想到但难以用代码去实现，在写代码的过程中经常容易乱。
    其实这个方法可以优化一下，把“if (cur->val = val)”这个判断拿到外层。代码如下：

    struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head, *prev = head;
    while (cur)
    {if (cur->val == val)
        {if (cur == head) //当cur为头时
            {cur = cur->next;
                free(head);
                head = cur;
                prev = cur;
            }
            else //当cur不为头
            {prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

    这下看起来是不是简单多了？
    回到优化前的代码：在每一个判断cur位置的条件语句中，都包含了对cur->val的判断，于是我想到不妨把里面的这个条件语句拿出来，这样外层就只需要if-else就好了，少了一层判断。再看内部，我也只分了两个条件，一个是cur为头，另一个就是不为头，当cur在中间和尾时的操作其实时相同的，所以把它们合并在一起。并且加上了free函数，把要删除的结点free掉，防止内存泄漏。
    其实很多人第一次写都会写出像优化前那样的代码，这很正常，因为初次接触思路可能没有那么清晰，多练练就好了。

    方法二：创建新链表

    与其像方法一那样在原链表上进行操作，我们不妨创建一个新的链表，然后把符合条件的值尾插到新链表中。

    struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
    struct ListNode* newhead = NULL; //新链表的头
    struct ListNode* tail = NULL; //新链表的尾
    while (cur)
    {if (cur->val != val)
        {if (tail == NULL) //判断新链表是否为空
            {newhead = tail = cur;
            }
            else
            {tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if (tail) //把新链表的尾结点的next置NULL
    {tail->next = NULL;
    }
    return newhead;
}

    这种方法想起来不难，实现起来也不难，写完之后就会发现这不就是单链表的尾插吗，只不过就是加了一个筛选条件而已。

    方法三：创建带头链表

    第三种方法是创建一个带头链表。
    我们知道，单链表的尾插相比头插要复杂一些，于是我想到采用带头链表。
    采用带头链表可以省去判断新链表是否为空，因为它一定带有头节点不为空，使代码更简洁。
    注意：本题要求返回的链表不能带有头节点，所以在最后应该返回头节点的next。

    struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur = head;
    struct ListNode* guard, *tail;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); //动态开辟一个头结点
    guard->next = NULL;

    while (cur)
    {if (cur->val != val)
        {tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
        else 
        {struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    tail->next = NULL;
    struct ListNode* newhead = guard->next;
    free(guard); 
    return newhead;
}

    这种方法不用考虑多种情况，是我最喜欢的方法。

    例题——反转链表

    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    图例

    方法一：迭代法

    这题其实很容易，我们只需要创建一个新链表，然后依次把原链表中的元素头插到新链表中即可。代码如下:

    struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head; 
    struct ListNode* rhead = NULL;
    while (cur)
    {struct ListNode* next = cur->next;
        cur->next = rhead;
        rhead = cur;
        cur = next;
    }
    return rhead;
}
    方法二：递归法

    这道题也可以采用递归的方法，不过有些难以理解。

    struct ListNode* reverseList(struct ListNode* head)
{if (head == NULL || head->next == NULL)
    {return head;
    }
    struct ListNode* newhead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
}

    图解

    三、双向带头循环链表的实现

    双向带头循环链表虽然结构最复杂，但是实现起来可一点也不复杂，相信你通过前面对单链表的学习，一定能自己写出双向链表。

    typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
//动态申请一个结点
LTNode* BuyListNode(LTDataType x);
//初始化
LTNode* LTInit();
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//插入
void LTInsert(LTNode* phead, LTDataType x);
//删除
void LTErase(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//返回链表长度
size_t LTSize(LTNode* phead);
//销毁
void LTDestroy(LTNode* phead);
    动态申请一个节点
    LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{perror("malloc fail");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}
    初始化
    LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
    打印
    void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;
	while (cur != phead)
	{printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
    尾插
    void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LTInsert(phead, x);
}
    尾删
    void LTPopBack(LTNode* phead)
{assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	//LTErase(phead->prev);
}
    头插
    void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);
	LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
	//LTInsert(phead->next, x);
}
    头删
    void LTPopFront(LTNode* phead)
{assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);
	phead->next = second;
	second->prev = phead;
	//LTErase(phead->next);
}
    查找
    LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{if (cur->data == x)
		{	return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
    插入
    void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
    删除
    void LTErase(LTNode* pos)
{assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

    在实现插入、删除后，我们其实可以将其复用到尾插尾删头插头删中。

    判断链表是否为空
    bool LTEmpty(LTNode* phead)
{assert(phead);
	return phead->next == phead;
}
    返回链表长度
    size_t LTSize(LTNode* phead)
{assert(phead);
	LTNode* cur = phead->next;
	size_t size = 0;
	while (cur != phead)
	{++size;
		cur = cur->next;
	}
	return size;
}
    销毁
    void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;
	while (cur != phead)
	{LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
    四、总结

    本文主要讲述了单链表和双向带头循环链表的实现，其中单链表尤为重要，在笔试和面试中经常会考到，建议各位读完本文多去刷一些有关单链表的题，它还有许多奥秘等待大家去探索。

    你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


    新闻标题：一篇文章带你学完链表基础（C语言）-创新互联
    分享地址：http://lszwz.com/article/icgig.html

    其他资讯

    售后响应及时

    7×24小时客服热线

    数据备份

    更安全、更高效、更稳定

    价格公道精准

    项目经理精准报价不弄虚作假

    合作无风险

    重合同讲信誉，无效全额退款

    联系我们

    TEL

    135-1821-9792

    028-86922220

    地址：乐山市太升南路288号锦天国际

    快捷导航

    Shortcut

    二维码

    QR CODE

    • 微信公众号

    • 手机端网站

    乐山小谭建站工作室是一家专注从事于高品质视觉体验及互联网设计开发，乐山网站建设，乐山网站设计，乐山网页设计，乐山网站制作，品牌网站建设，营销网站建设，集团网站建设，企业网站建设，外贸网站建设，响应式网站建设，小程序开发，微信开发，企业形象设计，企业宣传视频等服务，小谭建站位于乐山市龙岗区大运软件小镇，小谭建站拥有经验丰富的高级网站建设工程师和一流的网页高端设计人员，具备各种规模与类型网站建设的雄厚实力，在网站建设领域树立了自己独特的设计风格。
    友情链接 交换友情链接
    双流能亿建站   企业网站制作   眉山网站建设   四川国泰民安消防   成都做手机网站   无边发光字   VI设计   艾名斯智能   八点广告   简阳电信服务器托管   

    Copyright © 2022 青羊区小谭信息技术咨询服务工作室 乐山建站工作室 All Rights Reserved   蜀ICP备2021004003号-25

    Copyright © 2022 青羊区小谭信息技术咨询服务工作室 乐山建站工作室 

    蜀ICP备2021004003号-25