C语言手把手带你掌握带头双向循环链表
作者:平凡的人1 发布时间:2023-01-14 16:52:59
标签:C语言,带头,双向,循环,链表
前言
关于链表这一块,写了多篇博客,学习了顺序表、单链表、及其一些练习题
顺序表:传送门:顺序表
单链表:传送门:单链表1 链表2
链表OJ:传送门:链表OJ
今天,我又来水一水博客, 介绍关于双链表。
带头双向循环链表的结构
实际上,单链表也存在一个比较大的缺陷:
1.不能从后往前遍历
2.无法找到前驱
除了单链表之外,我们自然还有双向链表,我们要说的就是带头双向循环链表,简单理解为:带头结点的,有两个方向的。循环的。结构图如下:
结构虽然比较复杂,但是极大方便我们找结点,比如可以直接找到尾结点,然后再进入相关的操作。实际代码的操作将会比单链表简单,极为方便,这里不做过多说明,直接上手代码
代码操作
我们直奔主题,进入代码实现的操作,之前的操作如果理解了,那我相信这个对于你来说肯定是不难的。下面直接给出源码:
List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
//带头双向循环--最优链表结构,在任意位置插入删除数据都是O(1)
typedef struct listNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}ListNode;
//初始化
ListNode*ListInit();
//销毁
void ListDestory(ListNode* phead);
//打印
void ListPrint(ListNode* phead);
//尾插
void ListPushBack(ListNode* phead, LTDataType x);
//头插
void ListPushFront(ListNode* phead, LTDataType x);
//头删
void ListPopFront(ListNode* phead);
//尾删
void ListPopBack(ListNode* phead);
ListNode* ListFind(ListNode* phead, LTDataType x);
//在pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置的值
void ListErase(ListNode* pos);
List.c
#include "List.h"
//开辟一个新结点
ListNode* BuyListNode(LTDataType x)
{
ListNode* newnode =(ListNode*)malloc(sizeof(ListNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//初始化
ListNode* ListInit()
{
ListNode*phead = BuyListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//销毁
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
//打印
void ListPrint(ListNode* phead)
{
ListNode* cur = phead->next;
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 ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* first = phead->next;
ListNode* newnode = BuyListNode(x);
newnode->next = first;
first->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
//头删
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
//尾删
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
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位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
//删除pos位置的值
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
Test.c
#include "List.h"
void TestList1()
{
ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
ListPushFront(plist, 0);
ListPushFront(plist, -1);
ListPrint(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPrint(plist);
ListPopBack(plist);
ListPrint(plist);
}
void TestList2()
{
ListNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
ListNode* pos = ListFind(plist, 3);
if (pos)
{
pos->data *= 10;
printf("找到了,并且*10\n");
}
else
{
printf("没找到\n");
}
ListPrint(plist);
ListInsert(pos, 300);
ListPrint(plist);
ListErase(pos);
ListPrint(plist);
}
int main()
{
TestList2();
return 0;
}
来源:https://blog.csdn.net/weixin_60478154/article/details/124092194
0
投稿
猜你喜欢
- 先来看看效果图如何使用示例代码PromptViewHelper pvHelper = new PromptViewHelper(mActiv
- 一、概念从本质上来说,它就是一个匿名函数,可以用来直接实现接口中的方法,从而简化代码。但是Lambda有一个限制,不能实现接口中的所有方法,
- 构造函数public class FileDemo { public static void
- 安装方式:1):通过ppa(源) 方式安装.2):通过官网安装包安装.JDK官网下载地址一:使用ppa(源)方式安装:1):添加ppa源su
- 开放端口安全组没开放端口是原罪!!!导致好多BUG费时费力。Hbase悄悄 * 的用了好多端口,比如被我抓到的42239,直接搜索报错药不对症
- 一:什么是Bitmap像素级的操作相信大家都知道一张jpg或png放大后会是一个个小格子,称为一个像素(px),而且一个小格子是一种颜色,也
- 【面试高频】- ThreadLocal的使用场景以及使用方式是怎么样的1 两大使用场景-ThreadLocal的用途典型场景1:每个线程需要
- System.Collections.ArrayList类是一个特殊的数组。通过添加和删除元素,就可以动态改变数组的长度。一.优点1. 支持
- 本文实例讲述了安卓Android6.0权限动态获取操作。分享给大家供大家参考,具体如下:众所周知 , 安卓6.0现在运用的越来越广泛 , 因
- 1、迭代器迭代器(iterator)解决的是集合访问的问题,提供一种方法顺序访问一个集合对象中的各个元素,而不暴露对象内部标识。迭代器还有一
- 装饰器模式概述装饰器模式(Decorator Pattern)也称为包装模式(Wrapper Pattern),属于结构型模式。它是指在不改
- 很多主流框架都使用了反射技术.像ssh框架都采用两种技术 xml做配置文件+反射技术.与反射有关的类包.java.lang.reflect.
- Android Spinner 组件Spinner: 下拉组件使用事项:布局在XML 中实现,具体的数据在JAVA 代码中实现;所用知识点:
- 一 :问题背景问题:当查询接口较复杂时候,数据的获取都需要[远程调用],必然需要花费更多的时间。 假如查询文章详情页面,需要如下标注的时间才
- 说明:基于atguigu学习笔记。在了解spring boot自动配置原理前,再来了解下两个注解@Import注解和@Conditional
- 从服务器下载文件中文名乱码解决方案,具体文字说明不多了,直接贴代码了,具体代码如下:try { &n
- 本文实例讲述了Android编程之ListView和EditText发布帖子隐藏软键盘功能。分享给大家供大家参考,具体如下:在Android
- 前言日常开发中,特别是音视频开发,需要在界面上渲染视频,比如制作一个播放器、或者视频编辑工具、以及视频会议客户端。通常拿到的是像素格式数据,
- springboot微服务内置了tomcat,在工程目录下执行:mvn clean package,可以将项目打成jar,通过java -j
- 摘要:想必大家做开发的时候都会用到下拉刷新的控件,现在各种第三方的下拉刷新控件不胜枚举。当然最NB的还是XListView。其他也有针对Gr