手搓带头双向循环链表(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)只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/317772.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【已解决】Python Selenium chromedriver Pycharm闪退的问题

概要 根据不同的业务场景需求&#xff0c;有时我们难免会使用程序来打开浏览器进行访问。本文在pycharm中使用selenium打开chromedriver出现闪退问题&#xff0c;根据不断尝试&#xff0c;最终找到的问题根本是版本问题。 代码如下 # (1) 导入selenium from selenium import …

新势力4月交付量比拼:理想超问界夺冠,小米首月交付超七千辆 | 最新快讯

理想汽车超越问界夺下 4 月新势力交付量冠军。 5 月 1 日&#xff0c;各大造车新势力纷纷亮出最新成绩。新入局者小米汽车也准时发布了交付数据&#xff0c;在交付首月&#xff0c;同时又是非完整交付月&#xff0c;小米就交出了超七千辆的好成绩&#xff0c;在造车新势力中尚属…

基于Spring Boot的校园闲置物品交易网站设计与实现

基于Spring Boot的校园闲置物品交易网站设计与实现 开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/idea 系统部分展示 系统功能界面图&#xff0c;在系统首页可以查看…

数字旅游引领未来智慧之旅:科技应用深度重塑旅游生态,智慧服务全面升级打造极致高品质旅游体验

随着信息技术的飞速发展&#xff0c;数字旅游作为旅游业与科技融合的新兴业态&#xff0c;正以其独特的魅力和优势&#xff0c;引领着旅游业迈向智慧之旅的新时代。数字旅游不仅通过科技应用重塑了旅游生态&#xff0c;更通过智慧服务为游客带来了高品质的旅游体验。本文将深入…

HOT100与剑指Offer

文章目录 前言一、300. 最长递增子序列&#xff08;HOT100&#xff09;二、62. 不同路径&#xff08;HOT100&#xff09; 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招&#xff0c;计划刷完hot100和剑指Offer的刷题计划&#xff0c;加油&#xff01; 根据要求&#xff…

AngularJS 的生命周期和基础语法

AngularJS 的生命周期和基础语法 文章目录 AngularJS 的生命周期和基础语法1. 使用步骤2. 生命周期钩子函数3. 点击事件4. if 语句1. if 形式2. if else 形式 5. for 语句6. switch 语句7. 双向数据绑定 1. 使用步骤 // 1. 要使用哪个钩子函数&#xff0c;就先引入 import { O…

kaggle(4) Regression with an Abalone Dataset 鲍鱼数据集的回归

kaggle&#xff08;4&#xff09; Regression with an Abalone Dataset 鲍鱼数据集的回归 import pandas as pd import numpy as npimport xgboost import lightgbm import optuna import catboostfrom sklearn.model_selection import train_test_split from sklearn.metrics …

STM32利用硬件I2C读取MPU6050陀螺仪数据

有了前面的基本配置&#xff0c;这节读取MPU6050的数据还算是简单&#xff0c;主要就是初始化时给MPU6050一些配置&#xff0c;取消睡眠模式&#xff0c;MPU6050开机是默认睡眠模式的&#xff0c;读写无效&#xff0c;所以上来就要先更改配置&#xff1a; MPU6050寄存器初始化…

LLM优化:开源星火13B显卡及内存占用优化

1. 背景 本qiang~这两天接了一个任务&#xff0c;部署几个开源的模型&#xff0c;并且将本地经过全量微调的模型与开源模型做一个效果对比。 部署的开源模型包括&#xff1a;星火13B&#xff0c;Baichuan2-13B, ChatGLM6B等 其他两个模型基于transformers架构封装&#xff0…

java-stream流案例

需求 代码 Vote类 // 1. 定义一个投票类 public class Vote {private String name;private ArrayList<String> voteList;public Vote(String name, ArrayList<String> voteList) {this.name name;this.voteList voteList;}public String getName() {return nam…

微信小程序:5.数据绑定

在Data中定义数据早wxml中进行数据使用 在data中定义数据 在页面对应的js对象中找到data&#xff0c;然后把数据进行定义即可 Page({data: {motto: Hello World,userInfo: {avatarUrl: defaultAvatarUrl,nickName: ,},hasUserInfo: false,canIUseGetUserProfile: wx.canIUse…

Ollamallama

Olllama 直接下载ollama程序&#xff0c;安装后可在cmd里直接运行大模型&#xff1b; llama 3 meta 开源的最新llama大模型&#xff1b; 下载运行 1 ollama ollama run llama3 2 github 下载仓库&#xff0c;需要linux环境&#xff0c;windows可使用wsl&#xff1b; 接…

linux 光驱(光盘)安装

文章目录 选择光盘自带 YUM 库创建 repo创建文件夹挂载光驱开机自启动挂载安装软件YUM 安装RPM 安装源码包安装 选择光盘 vmware 选择光盘 自带 YUM 库 ls /etc/yum.repos.d创建 repo vim /etc/yum.repo.d/demo.repo // 编写 repo 相关配置 [demo] namedemo baseurlfile://…

Java进阶-File、递归、IO流

目录 前言 File类概述 File类创建对象 绝对路径和相对路径 File类常用API 判断文件类型、获取文件信息 创建文件、删除文件功能 遍历文件夹 方法递归 递归的形式和特点 递归的算法流程、核心要素 常见案例 经典问题-猴子吃桃问题 非规律化递归案例-文件搜索 非规…

【网络原理】UDP协议 | UDP报文格式 | 校验和 | UDP的特点 | 应用层的自定义格式

文章目录 一、UDP协议1.UDP的传输流程发送方接收方 2.UDP协议报文格式&#xff1a;长度受限校验和如何校验&#xff1a;CRC算法&#xff1a;循环冗余算法md5算法&#xff1a; 2.UDP的特点 二、开发中常见的自定义格式1.xml&#xff08;古老&#xff09;2.json&#xff08;最流行…

java案例-读取xml文件

需求 导入依赖 <dependencies><!-- dom4j --><dependency><groupId>dom4j</groupId><artifactId>dom4j</artifactId><version>1.6.1</version></dependency> </dependencies>代码 SAXReader saxReade…

Ansible自动化

Ansible自动化 自动化的需求&#xff1a; 1. 在什么样的场景下需要自动化&#xff1f; 批量化的工作&#xff1a; 装软件包、配置服务、升级、下发文件… 2. 为什么在自动化工具中选择ansible&#xff1f; 对比shell脚本&#xff1a; 相对于用shell的脚本来实现自动化&#x…

跨平台桌面客户端开发框架

跨平台桌面客户端开发框架允许开发者创建能够在多个操作系统上运行的桌面应用程序。以下是一些流行的跨平台桌面客户端开发框架。这些框架各有优势&#xff0c;选择哪个框架取决于项目需求、团队的技术栈以及对特定特性的偏好。 1.Electron &#xff1a; 使用JavaScript, HTML…

uniapp视频播放器(h5+app)

关于uniapp视频播放器遇到的一些问题&#xff0c;mark下。 中途遇到了很多问题&#xff0c;如果有相同的伙伴遇到了类似的&#xff0c;欢迎交流 官方的video播放器在app上不友好&#xff0c;有以下功能不支持。 loadedmetadata、controlstoggle不支持导致只能手写控制层。 不…

python学习之词云图片生成

代码实现 import jieba import wordcloudf open("D:/Pythonstudy/data/平凡的世界.txt", "r", encoding"utf-8") t f.read() print(t) f.close() ls jieba.lcut(t) txt " ".join(ls)w wordcloud.WordCloud(font_path"D:/cc…