手搓带头双向循环链表（C语言）

2024-04-28 20:20
文章标签 语言 链表 双向 循环 带头

本文主要是介绍手搓带头双向循环链表（C语言），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

List.h

List.c

ListTest.c

测试示例

带头双向循环链表优劣分析

List.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}ListNode;//创建节点
ListNode* BuyListNode(LTDataType x);
//初始化
ListNode* ListInit();
//打印链表
void ListPrint(ListNode* phead);
//尾插
void ListPushBack(ListNode* phead, LTDataType x);
//尾删
void ListPopBack(ListNode* phead);
//销毁
void ListDistroy(ListNode* phead);
//头插
void ListPushFront(ListNode* phead, LTDataType x);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, LTDataType x);
//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置的值
void ListErase(ListNode* pos);

List.c

#include "List.h"//创建节点
ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));//申请空间失败if (node == NULL){perror("BuyListNode");exit(-1);}node->data = x;node->prev = NULL;node->next = NULL;return node;
}//初始化
ListNode* ListInit()
{ListNode* phead = BuyListNode(-1);phead->prev = phead;phead->next = phead;return phead;
}//打印链表
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->prev != phead);ListNode* tailPrev = phead->prev->prev;free(phead->prev);tailPrev->next = phead;phead->prev = tailPrev;
}//销毁
void ListDistroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;ListNode* tmp = cur;while (cur != phead){cur = cur->next;free(tmp);tmp = cur;}phead->prev = phead;phead->next = phead;
}//头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);newnode->next = first;first->prev = newnode;newnode->prev = phead;phead->next = newnode;
}//头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* first = phead->next;ListNode* second = first->next;free(first);second->prev = phead;phead->next = second;
}//查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

头插尾插复用：

//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//头插
void ListPushFront(ListNode* phead, LTDataType x)
{ListInsert(phead->next, x);
}//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{ListInsert(phead, x);
}

 头删尾删复用：

//删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//头删
void ListPopFront(ListNode* phead)
{assert(phead->next != phead);ListErase(phead->next);
}//尾删
void ListPopBack(ListNode* phead)
{assert(phead->prev != phead);ListErase(phead->prev);}

ListTest.c

#include "List.h"void test1()
{ListNode* phead = NULL;//初始化phead = ListInit();ListPrint(phead);//测试尾插ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPushBack(phead, 5);ListPrint(phead);//测试尾删ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);/*ListPopBack(phead);ListPrint(phead);*/ListDistroy(phead);
}void test2()
{ListNode* phead = NULL;//初始化phead = ListInit();ListPrint(phead);//测试头插ListPushFront(phead, 1);ListPushFront(phead, 2);ListPushFront(phead, 3);ListPushFront(phead, 4);ListPushFront(phead, 5);ListPrint(phead);//测试头删ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);/*ListPopFront(phead);ListPrint(phead);*/ListDistroy(phead);
}
void test3()
{ListNode* phead = NULL;//初始化phead = ListInit();ListPrint(phead);//测试在pos位置之前插入ListInsert(phead, 1);ListInsert(phead, 2);ListInsert(phead, 3);ListInsert(phead, 4);ListInsert(phead, 5);ListPrint(phead);ListInsert(phead->next, 6);ListInsert(phead->next, 7);ListInsert(phead->next, 8);ListInsert(phead->next, 9);ListInsert(phead->next, 10);ListPrint(phead);//测试删除pos位置的值ListNode* pos = ListFind(phead, 1);ListErase(pos);ListPrint(phead);pos = ListFind(phead, 5);ListErase(pos);ListPrint(phead);pos = ListFind(phead, 10);ListErase(pos);ListPrint(phead);ListDistroy(phead);
}
int main()
{//测试尾插尾删//test1();//测试头插头删//test2();//测试在pos位置插入删除test3();return 0;
}

测试示例

尾插尾删：

头插头删：

在pos位置插入删除:

带头双向循环链表优劣分析

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持：O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

这篇关于手搓带头双向循环链表（C语言）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/944174。

相关文章

好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

项目主页：https://tangyuan96.github.io/minigpt_3d_project_page/ 代码：https://github.com/TangYuan96/MiniGPT-3D 论文：https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA，被ACM MM2024接收，只拥有47.8M的可训练参数，在一张RTX
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2