C语言实现带头双向循环链表的接口

本文实例为大家分享了C语言实现带头双向循环链表的接口,供大家参考,具体内容如下

各函数功能如下

申请空间

ListNode* BuyListNode(LTDataType x)
{
 ListNode* node = (ListNode*)malloc(sizeof(ListNode));
 node->next = NULL;
 node->prev = NULL;
 node->data = x;
 return node;
}

初始化

ListNode* ListInit()
{
 ListNode* phead = BuyListNode(0);
 phead->next = phead;
 phead->prev = phead;

 return phead;
}

指定位置插入

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;
}

头插

void ListPushFront(ListNode* phead, LTDataType x)
{
 //assert(phead);
 //ListNode* first = phead->next;
 //ListNode* newnode = BuyListNode(x);
 phead newnode first
 //phead->next = newnode;
 //newnode->prev = phead;
 //newnode->next = first;
 //first->prev = newnode;

 ListInsert(phead->next, x);//实现了指定位置插入后,可以套用
}

尾插

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;

 ListInsert(phead, x);
}

指定位置删除

void ListErase(ListNode* pos)
{
 assert(pos);

 ListNode* prev = pos->prev;
 ListNode* next = pos->next;

 prev->next = next;
 next->prev = prev;

 free(pos);
}

头删

void ListPopFront(ListNode* phead)
{
 //assert(phead);
 //assert(phead->next != phead);

 //ListNode* first = phead->next;
 //ListNode* second = first->next;

 //free(first);

 //phead->next = second;
 //second->prev = phead;

 ListErase(phead->next);
}

尾删

void ListPopBack(ListNode* phead)
{
 //assert(phead);
 //assert(phead->next != phead);

 //ListNode* tail = phead->prev;
 //ListNode* tailPrev = tail->prev;
 //free(tail);

 //tailPrev->next = phead;
 //phead->prev = tailPrev;

 ListErase(phead->prev);

}

查找

ListNode* ListFind(ListNode* phead, LTDataType x)
{
 assert(phead);

 ListNode* cur = phead->next;
 while (cur)
 {
  if (cur->data == x)
  {
   return cur;
  }
  cur = cur->next;
 }

 return NULL;
}

判空

int ListEmpty(ListNode* phead)
{
 assert(phead);
 return phead->next == phead ? 1 : 0;
}

元素个数

int ListSize(ListNode* phead)
{
 assert(phead);

 int size = 0;
 ListNode* cur = phead->next;
 while (cur != phead)
 {
  size++;
  cur = cur->next;
 }
 return size;
}

链表销毁

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;
}

List.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef int LTDataType;
typedef struct ListNode
{
 struct ListNode* next;
 struct ListNode* prev;
 LTDataType data;
}ListNode;

//打印
void ListPrint(ListNode* phead);

//申请空间
ListNode* BuyListNode(LTDataType x);

//初始化
ListNode* ListInit();

//尾插
void ListPushBack(ListNode* phead, LTDataType x);

//头插
void ListPushFront(ListNode* phead, LTDataType x);

//尾删
void ListPopBack(ListNode* phead);

//头删
void ListPopFront(ListNode* phead);

//查找
ListNode* ListFind(ListNode* phead, LTDataType x);

//插入
void ListInsert(ListNode* pos, LTDataType x);

//删除
void ListErase(ListNode* pos);

//空返回1,非空返回0
int ListEmpty(ListNode* phead);

//元素个数
int ListSize(ListNode* phead);

//链表销毁
void ListDestory(ListNode* phead);

List.c

#include "List.h"

ListNode* BuyListNode(LTDataType x)
{
 ListNode* node = (ListNode*)malloc(sizeof(ListNode));
 node->next = NULL;
 node->prev = NULL;
 node->data = x;
 return node;
}

ListNode* ListInit()
{
 ListNode* phead = BuyListNode(0);
 phead->next = phead;
 phead->prev = phead;

 return phead;
}

//打印
void ListPrint(ListNode* phead)
{
 ListNode* cur = phead->next;
 while (cur != phead)
 {
  printf("%d ", cur->data);
  cur = cur->next;
 }
 puts("\n------------------------------------------------\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;

 ListInsert(phead, x);
}

//头插
void ListPushFront(ListNode* phead, LTDataType x)
{
 //assert(phead);
 //ListNode* first = phead->next;
 //ListNode* newnode = BuyListNode(x);
 phead newnode first
 //phead->next = newnode;
 //newnode->prev = phead;
 //newnode->next = first;
 //first->prev = newnode;

 ListInsert(phead->next, x);
}

//尾删
void ListPopBack(ListNode* phead)
{
 //assert(phead);
 //assert(phead->next != phead);

 //ListNode* tail = phead->prev;
 //ListNode* tailPrev = tail->prev;
 //free(tail);

 //tailPrev->next = phead;
 //phead->prev = tailPrev;

 ListErase(phead->prev);

}

//头删
void ListPopFront(ListNode* phead)
{
 //assert(phead);
 //assert(phead->next != phead);

 //ListNode* first = phead->next;
 //ListNode* second = first->next;

 //free(first);

 //phead->next = second;
 //second->prev = phead;

 ListErase(phead->next);
}

//查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
 assert(phead);

 ListNode* cur = phead->next;
 while (cur)
 {
  if (cur->data == x)
  {
   return cur;
  }
  cur = cur->next;
 }

 return NULL;
}

//插入
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;
}

//删除
void ListErase(ListNode* pos)
{
 assert(pos);

 ListNode* prev = pos->prev;
 ListNode* next = pos->next;

 prev->next = next;
 next->prev = prev;

 free(pos);
}

//空返回1,非空返回0
int ListEmpty(ListNode* phead)
{
 assert(phead);
 return phead->next == phead ? 1 : 0;
}

int ListSize(ListNode* phead)
{
 assert(phead);

 int size = 0;
 ListNode* cur = phead->next;
 while (cur != phead)
 {
  size++;
  cur = cur->next;
 }
 return size;
}

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;
}

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);
 ListPushFront(plist, -2);
 ListPrint(plist);

 ListPopFront(plist);
 ListPopFront(plist);
 ListPopFront(plist);
 ListPrint(plist);

 ListDestory(plist);
 plist = NULL;
}

int main()
{
 TestList1();
 return 0;
}

总结

链表优点:

1.按需申请内存,需要存一个数据,就申请一块内存。不存在空间浪费。
2.任意位置O(1)时间内插入删除数据

链表缺点:

1.不支持下标的随机访问
2.缓存命中率相对低。

顺序表优点

1.按下标去进行随机访问
2.cpu高速缓存命中率比较高

顺序表缺点

1.空间不够需要增容。(一定程序的性能消耗),可能存在一定的空间浪费
2.头部或者中间插入删除数据,需要挪动数据,效率比较低->O(N)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C语言数据结构之判断循环链表空与满

    C语言数据结构之判断循环链表空与满 前言: 何时队列为空?何时为满? 由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等.因此,我们无法通过front=rear来判断队列"空"还是"满". 注:先进入的为'头',后进入的为'尾'. 解决此问题的方法至少有三种: 其一是另设一个布尔变量以匹别队列的空和满: 其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始

  • C语言实现循环链表

    本文实例为大家分享了C语言实现循环链表的具体代码,供大家参考,具体内容如下 注意事项: 1.循环链表设置尾指针.由于在链表的操作过程中,尾指针会不断变化,所以在一些函数的形参中都设置指向头指针的指针.以及链表的结束判断条件变成q是否等于尾指针. 2.注意传递的实参需要取地址 3.循环链表的优势在于双链表合并,以及实现尾插法简单(首先新建结点指向头结点,然后把尾指针的next域指向该新建结点) 4.在创建链表时,使用尾插法,而不是用头插法(因为头插法很难去更新尾指针,使得最后尾指针还需额外更新一次

  • C语言单循环链表的表示与实现实例详解

    1.概述: 对于一个循环链表来说,其首节点和末节点被连接在一起.这种方式在单向和双向链表中皆可实现.要转换一个循环链表,可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点.再来看另一种方法,循环链表可以被视为"无头无尾".这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下. 指向整个列表的指针可以被称作访问指针. 用单向链表构建的循环链表 循环链表中第一个节点之前就是最后一个节点,反之亦然.循环链表的无边界使得在这

  • C语言中双向链表和双向循环链表详解

    双向链表和双向循环链表 和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作 新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =

  • C语言数据结构之循环链表的简单实例

     C语言数据结构之循环链表的简单实例 实例代码: # include <stdio.h> # include <stdlib.h> typedef struct node //定义链表中结点的结构 { int code; struct node *next; }NODE,*LinkList; /*错误信息输出函数*/ void Error(char *message) { fprintf(stderr,"Error:%s/n",message); exit(1)

  • C语言基于循环链表解决约瑟夫环问题的方法示例

    本文实例讲述了C语言基于循环链表解决约瑟夫环问题的方法.分享给大家供大家参考,具体如下: 概述: 约瑟夫环问题,是一个经典的循环链表问题,题意是:已知 n 个人(以编号1,2,3,-,n分别表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列:他的下一个人又从 1 还是顺时针开始报数,数到 m 的那个人又出列:依次重复下去,要求找到最后出列的那个人. 例如有 5 个人,要求从编号为 3 的人开始,数到 2 的那个人出列: 出列顺序依次为: 编号为 3 的人开始数 1

  • C语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • C语言实现带头双向循环链表的接口

    本文实例为大家分享了C语言实现带头双向循环链表的接口,供大家参考,具体内容如下 各函数功能如下 申请空间 ListNode* BuyListNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = x; return node; } 初始化 ListNode* ListInit() { ListN

  • C语言实现带头双向循环链表

    目录 前言 1. 创建结构体 2.malloc新节点 3.创建哨兵位节点 4.尾插 5.打印 6.尾删 7.头插 8.在指定位置pos的前面进行插入 9. 删除指定位置pos节点 10.销毁链表 前言 在实际生活中最常用的就是这两种链表.无头单向非循环链表.和带头双向循环链表.无头单向非循环链表:结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.另外这种结构在笔试面试中出现很多.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数

  • C语言中带头双向循环链表基本操作的实现详解

    目录 一.概念与结构 二.基本操作的实现 1.创建结点 2.初始化链表 3.打印链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个数并返回其指针 9.在某个位置之前插入 10.删除某个位置 11.判断链表是否为空 12.计算链表中有效值的个数 13.销毁链表 三.测试代码 一.概念与结构 无头单向非循环链表结构简单,一般不会单独用来存数据.实际中更多的是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.而带头双向循环链表的结构较为复杂,一般用在单独存储数据.实际中使用的链表数据结构,都

  • C语言 超详细介绍与实现线性表中的带头双向循环链表

    目录 一.本章重点 二.带头双向循环链表介绍 2.1什么是带头双向循环链表? 2.2最常用的两种链表结构 三.带头双向循环链表常用接口实现  3.1结构体创建 3.2带头双向循环链表的初始化  3.3创建新节点 3.4尾插 3.5打印链表 3.6头插 3.7尾删 3.8头删 3.9查找data(返回data的节点地址) 3.10在pos位置之前插入节点 3.11删除pos位置的节点 四.实现接口总结 五.在线oj训练与详解 一.本章重点 带头双向循环链表介绍 带头双向循环链表常用接口实现 实现接

  • C++带头双向循环链表超详细解析

    目录 什么是带头双向循环链表 带头双向循环链表常用接口实现 上期我们讲完了无头单向非循环链表,这期我们接着来讲链表中结构最复杂的带头双向循环链表! 本期主要内容: 什么是带头双向循环链表? 带头双向循环链表常用接口实现! 顺序表和链表的区别和联系! 什么是带头双向循环链表 什么是带头?双向?循环?(带头双向循环链表) 带头:代表链表存在一个哨兵位节点,也就是头节点,这个节点不存放任何的有效数据! 双向:每个节点都有两个指针,分别指向它的前一个节点和后一个节点! 循环:最后一个节点next不再指向

  • C语言编程数据结构带头双向循环链表全面详解

    目录 前言 一.什么是带头循环双向链表 二.链表初始化 三.链表接口函数 1.尾插 2.头插 3.头删 4.尾删 5.任意位置插入数据 6.任意位置删除数据 四.打印链表 总结 前言 上一篇数据结构专栏:C语言数据结构单链表接口函数全面讲解教程 我们介绍了单链表的各个接口函数,大家可能会发现单链表存在一些缺陷:比如它一个节点要存储数据+下一个节点地址,占用的空间要远多于顺序表:并且由于单链表是无法从后往前找的,如果你想进行尾删这样的操作,你必须从第一个节点往后找,你的时间复杂度一定是O(n).

  • C语言带头双向循环链表的示例代码

    目录 前言 结构分析 链表的基本操作实现 创建节点 初始化链表 链表销毁 打印链表 链表尾插 链表尾删 链表头插 链表头删 链表查找 链表pos位置前面去插入 删除pos位置 链表判空 代码复用 总代码及头文件 前言 对于链表来说,不只有单链表这一个品种: 链表有很多种形态 按方向分:单向.双向 按带不带头:带头.不带头 按循环:循环.不循环 1.单向或则双向: 2.带头或者不带头: 3.循环或者不循环: 组合排列一下的话,链表一共有8种形态!!! 今天我们就来学习一下结构最复杂的带头双向循环链

  • C语言详解如何实现带头双向循环链表

    目录 创建链表存储结构 创建结点 链表的初始化 双向链表的打印 双向链表尾插 双向链表尾删 双向链表头插 双向链表头删 双向链表查找 双向链表pos前插入结点 双向链表删除pos位置的结点 双向链表的销毁 顺序表和链表的区别 2022042311415360.{C}{C}png" /> 创建链表存储结构 我们需要创建一个结构体来存储一个链表结点的相关信息. typedef int ListDataType;//将ListDataType先定义为int类型,根据需要可以改为不同的类型 //创

  • C语言手把手带你掌握带头双向循环链表

    目录 前言 带头双向循环链表的结构 代码操作 前言 关于链表这一块,写了多篇博客,学习了顺序表.单链表.及其一些练习题 顺序表:传送门:顺序表 单链表:传送门:单链表1   链表2 链表OJ:传送门:链表OJ 今天,我又来水一水博客, 介绍关于双链表. 带头双向循环链表的结构 实际上,单链表也存在一个比较大的缺陷: 1.不能从后往前遍历 2.无法找到前驱 除了单链表之外,我们自然还有双向链表,我们要说的就是带头双向循环链表,简单理解为:带头结点的,有两个方向的.循环的.结构图如下: 结构虽然比较

  • C++零基础精通数据结构之带头双向循环链表

    目录 与单链表的区别 代码的实现 接口 节点的构造 初始化链表 开辟节点 销毁链表 打印链表 尾插链表 尾删链表 头插链表 头删链表 查找链表 链表pos位置的删除 总结 与单链表的区别 单向/双向 单向:只有一个next指针,只指向下一位元素 双向:有两个指针,指向上一位和下一位元素,寻找前一节点和后一节点很便利 带头/不带头 带头:在本来的头结点之前还有一个哨兵卫节点作为头节点,它的址域指针指向头节点,值域不做使用 不带头:没有哨兵卫头节点,在尾删尾插等问题中要考虑头结点的情况(局限) 循环

随机推荐