扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言双向链表的原理与使用操作
  • 243

0
分享到

C语言双向链表的原理与使用操作

2024-04-02 19:04:59 243人浏览 安东尼
摘要

目录一.引入二.双向链表的定义三.双向链表与单链表对比3.1图示对比3.2代码对比四.双向链表的操作4.1双向链表的创建4.2双向链表的插入4.3双向链表的删除4.4双向链表的销毁五

一.引入

我们在单链表中，有了next指针，这个指针是用来指向下一个节点的，如果我们需要查找下一个结点的时间复杂度为o(1),如果我们需要查找上一个节点的时候，那么时间复杂度就变为o(n)了，需要从头进行遍历一遍；这时我们就会想：如果可以向前查找就方便了许多，因此我们引入了双向链表。

二.双向链表的定义

双向链表：是在单链表的每个节点中，再设置一个指向前驱结点的指针域。

顾名思义就是链表由单向的变成了双向的，每一个节点由原来的一个指针变为两个指针，一个用来指向直接后继，另一个用来指向直接前驱。

三.双向链表与单链表对比

通过对比可以更好认识二者的联系与区别。

3.1图示对比

单链表：

双向链表：

3.2代码对比

单链表代码如下：

typedef struct node{ //定义单链表结点类型
	int data; //数据域，可以是别的各种数据类型
	struct Node *next; //指针域
}LNode, *LinkList;

双向链表代码如下：

typedef struct DulNode{
	int data;			// 	数据域
	struct DulNode *prior;		//  向前的指针
	struct DulNode *next;		//  向后的指针
}DulNode,*DuLinkList;

四.双向链表的操作

双向链表是单链表中扩展出来的结构，所以有很多的操作是和单链表相同的，如求长度，查找元素，获取一个元素，这里我们对双向链表进行创建，插入，删除，销毁的一系列操作。

4.1双向链表的创建

双向链表在初始化时，要给首尾两个节点分配内存空间。成功分配后，需要将首节点的prior指针和尾节点的next指针都指向NULL，这是十分关键的一步，因为这是之后用来判断空表的条件。并且当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

pElem CreatList(){
	pElem head = (pElem)malloc( sizeof(eElem) );
	assert( head != NULL );		//进行断言
	head->next = head->prior = NULL；//初始化链表指针置空
	return head;
}

4.2双向链表的插入

双向链表的插入其实并不复杂，只是在原有单链表的基础上多了连接一个向前的指针而已。但是需要注意的是操作的顺序很重要，不可以写反了。

以下面这个为例，假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间

核心代码就只有以下四行：

s->prior=p; //把p赋值给s的前驱
s->next=p->next;// 把p->next赋值给s的后继
p->next->prior=s;// 把s赋值给p->next的前驱
p->next=s;   //把s赋值给p的后继

切记顺序不可以记错 在写代码的时候可以将操作步骤画出来，理清实施步骤的顺序。

4.3双向链表的删除

如果将插入操作的原理理解后，那么删除就很好理解了。

删除只需要两个步骤：

核心代码只有三行：

p->prior->next=p->next; //把p->next赋值给p->prior的后继
p->next->prior=p->prior;//把p->prior赋值给p->next的前驱
free(p); //释放结点

4.4双向链表的销毁

销毁一个双向链表的操作同单链表的相似。指针不断向后运动，每运动一个结点，释放上一个结点。

代码如下：

void DestroyList( pElem head ){
	pElem tmp;
	while( head->next != NULL ){
		tmp = head;		//  指针不断后移
		head = head->next;
		free(tmp);
	}
	free(head);
}

五.总结

双向链表相比于单链表来说，是更复杂一些的，毕竟多了一个prior指针，对于插入和删除需要特别注意这两种操作的核心思想以及操作顺序。另外双向链表，带来了方便，可以有效提高算法的时间性能。

六.全部代码

这里引用一位大佬写的代码，将头插法和尾插法创建表都写了，写的很细节，很清楚大家可以参考一下。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
    elemtype data;
    struct node * next;
    struct node * prior;
}node;
typedef struct node* dlinklist;
status visit(elemtype c){
    printf("%d ",c);
}

status initdlinklist(dlinklist * head,dlinklist * tail){
    (*head)=(dlinklist)malloc(sizeof(node));
    (*tail)=(dlinklist)malloc(sizeof(node));
    if(!(*head)||!(*tail))
        return ERROR;
     
    (*head)->prior=NULL;
    (*tail)->next=NULL;
    
    (*head)->next=(*tail);
    (*tail)->prior=(*head);
}

status emptylinklist(dlinklist head,dlinklist tail){
    if(head->next==tail)
       return TRUE;
    else
       return FALSE;
} 
 
status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pmove=tail,pinsert;
    pinsert=(dlinklist)malloc(sizeof(node));
    if(!pinsert)
         return ERROR;
    pinsert->data=data;
    pinsert->next=NULL;
    pinsert->prior=NULL;
    tail->prior->next=pinsert;
    pinsert->prior=tail->prior;
    pinsert->next=tail;
    tail->prior=pinsert;
} 
 
status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pmove=head,qmove=tail,pinsert;
    pinsert=(dlinklist)malloc(sizeof(node));
    if(!pinsert)
        return ERROR;
    else{
        pinsert->data=data;
        pinsert->prior=pmove;
        pinsert->next=pmove->next;
        pmove->next->prior=pinsert;
        pmove->next=pinsert;
    }
}
 
status traverselist(dlinklist head,dlinklist tail){
    
    dlinklist pmove=head->next;
    while(pmove!=tail){
        visit(pmove->data);
        pmove=pmove->next;
    }
    printf("\n");
}

status locateelem(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pmove=head->next;
    int pos=1;
    while(pmove&&pmove->data!=data){
        pmove=pmove->next;
        pos++;
    }
    return pos;
}

status listlength(dlinklist head,dlinklist tail){
    dlinklist pmove=head->next;
    int length=0;
    while(pmove!=tail){
        pmove=pmove->next;
        length++;
    }
    return length;
}

status inverse(dlinklist head,dlinklist tail){
    dlinklist pmove=tail->prior;
    while(pmove!=head){
        visit(pmove->data);
        pmove=pmove->prior;
    }
    printf("\n");
}

status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
    int i=1;
    dlinklist pmove=head->next;
    while(pmove&&i<pos){
        pmove=pmove->next;
        i++;
    }
    if(!pmove||i>pos){
        printf("输入数据非法\n");
        return ERROR;
    }
    else{
        *data=pmove->data;
        pmove->next->prior=pmove->prior;
        pmove->prior->next=pmove->next;
        free(pmove);
    }
}

status inserttail(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pinsert;
    pinsert=(dlinklist)malloc(sizeof(node));
    pinsert->data=data;
    pinsert->next=NULL;
    pinsert->prior=NULL;
    tail->prior->next=pinsert;
    pinsert->prior=tail->prior;
    pinsert->next=tail;
    tail->prior=pinsert;
    return OK;
} 
int main(void){
    dlinklist head,tail;
    int i=0;
    elemtype data=0;
    initdlinklist(&head,&tail);
    if(emptylinklist(head,tail))
        printf("链表为空\n");
    else
        printf("链表不为空\n");
    printf("头插法创建链表\n"); 
    for(i=0;i<10;i++){
        createdlinklisthead(head,tail,i);
    }
    traverselist(head,tail);
    for(i=0;i<10;i++){
        printf("表中值为%d的元素的位置为",i); 
        printf("%d位\n",locateelem(head,tail,i));
    }
    printf("表长为%d\n",listlength(head,tail));
    printf("逆序打印链表");
    inverse(head,tail);
    for(i=0;i<10;i++){
        deleteelem(head,tail,1,&data);
        printf("被删除的元素为%d\n",data);
    }
    traverselist(head,tail);
    if(emptylinklist(head,tail))
        printf("链表为空\n");
    else
        printf("链表不为空\n");
        printf("尾插法创建链表\n");
    for(i=0;i<10;i++){
        //inserttail(head,tail,i);
        createdlinklisttail(head,tail,i);
    }
    traverselist(head,tail);
    printf("逆序打印链表");
    inverse(head,tail);
}

到此这篇关于C语言双向链表的原理与使用操作的文章就介绍到这了,更多相关C语言双向链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C语言双向链表的原理与使用操作

本文链接: https://lsjlt.com/news/149436.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C语言双向链表的原理与使用操作
    目录一.引入二.双向链表的定义三.双向链表与单链表对比3.1图示对比3.2代码对比四.双向链表的操作4.1双向链表的创建4.2双向链表的插入4.3双向链表的删除4.4双向链表的销毁五...
    99+
    2024-04-02
  • C语言循环链表的原理与使用操作
    目录一.引入二.循环链表的定义三.单链表与循环链表对比3.1图示对比3.2代码对比四.循环链表的操作4.1循环链表的初始化4.2循环链表的建立4.2.1头插法建立循环链表4.2.2尾...
    99+
    2024-04-02
  • C语言中双链表的基本操作
    目录带头结点的双向循环链表基本操作创建销毁打印尾插法尾删头插头删查找元素位置任意位置插入任意位置删除完整代码及测试总结带头结点的双向循环链表 链表结构如下： 每个节点都有一个数据域和...
    99+
    2023-02-05
    C语言双链表 双链表的基本操作 C语言双链表操作
  • C语言如何实现双向链表和双向循环链表
    本文小编为大家详细介绍“C语言如何实现双向链表和双向循环链表”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言如何实现双向链表和双向循环链表”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。双向链表和双向循环链表...
    99+
    2023-06-16
  • C语言类的双向链表详解
    目录前言双向链表的定义双向链表的创建节点的创建双向链表节点查找双向链表的插入双向链表的节点删除双向链表的删除总结前言 链表（linked list)是一种这样的数据结构，其中的各对象...
    99+
    2024-04-02
  • Java双向链表的操作
    目录前言一、认识双向链表二、双向链表的增删改查1.插入头插尾插在index位置插入2.修改3.查询4.删除删除index位置的节点头删尾删删除第一个值为val的节点删除所有值为val...
    99+
    2024-04-02
  • C语言如何实现双向链表
    本篇内容介绍了“C语言如何实现双向链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！双向链表的基本操作    ...
    99+
    2023-06-16
  • C语言数据结构之单链表与双链表的增删改查操作实现
    目录前言单链表的增删改查定义结构体以及初始化增加结点删除结点查找修改结点移除结点最终效果双链表的基本操作初始化建表遍历双链表指定位置插入结点指定位置删除结点查找结点位置最终效果结语前...
    99+
    2024-04-02
  • C语言实现带头双向循环链表
    目录前言1. 创建结构体2.malloc新节点3.创建哨兵位节点4.尾插5.打印6.尾删7.头插8.在指定位置pos的前面进行插入9. 删除指定位置pos节点10.销毁链表前言 在...
    99+
    2024-04-02
  • C语言超详细i讲解双向链表
    目录一、双向链表的概念二、双向链表的实现三、链表与顺序表的差别四、链表oj总结一、双向链表的概念 1、概念：概念：双向链表是每个结点除后继指针外还有⼀个前驱指针。双向链表也有带头结点...
    99+
    2024-04-02
  • C语言实现带头双向环形链表
    双向循环链表 上一次我们讲了单向无头非循环链表的实现，单向无头非循环链表的特点是：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。而带头双向循环链表则恰恰与无...
    99+
    2024-04-02
  • c语言如何创建双向循环链表
    要创建一个双向循环链表，你可以按照以下步骤进行：1. 首先，定义一个节点结构体，包含一个数据域和两个指针域，分别指向前一个节点和后一...
    99+
    2023-08-25
    c语言
  • C语言链表的操作有哪些
    这篇“C语言链表的操作有哪些”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C语言链表的操作有哪些”文章吧。前言编译工具：vs...
    99+
    2023-06-30
  • 详解C语言中双向循环链表的实现
    目录实现细节辅助理解图具体实现代码1、对链表进行初始化2、任意位置前的插入3、任意位置的删除4、头插和尾删完整代码头文件具体函数测试实现细节 1、带一个哨兵位（哨兵节点，初始节点，不...
    99+
    2024-04-02
  • C语言算法学习之双向链表详解
    目录一、练习题目二、算法思路1、设计浏览器历史记录2、扁平化多级双向链表3、展平多级双向链表4、二叉搜索树与双向链表一、练习题目 题目链接难度1472. 设计浏览器历史记录★★★☆☆...
    99+
    2024-04-02
  • c语言回调函数双向链表指的是什么
    C语言回调函数双向链表指的是一种数据结构，它是由多个节点组成的链式结构。每个节点包含了数据域和两个指针，分别指向前一个节点和后一个节...
    99+
    2023-10-18
    c语言
  • C语言实现带头双向循环链表的接口
    本文实例为大家分享了C语言实现带头双向循环链表的接口，供大家参考，具体内容如下 各函数功能如下 申请空间 ListNode* BuyListNode(LTDataType x) ...
    99+
    2024-04-02
  • C语言带头双向循环链表的示例代码
    目录前言结构分析链表的基本操作实现创建节点初始化链表链表销毁打印链表链表尾插链表尾删链表头插链表头删链表查找链表pos位置前面去插入删除pos位置链表判空代码复用总代码及头文件前言 ...
    99+
    2022-11-13
    C语言带头双向循环链表 C语言 双向循环链表 C语言 循环链表
  • C语言怎么实现带头双向环形链表
    本篇内容主要讲解“C语言怎么实现带头双向环形链表”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C语言怎么实现带头双向环形链表”吧!双向循环链表上一次我们讲了单向无头非循环链表的实现，单向无头非循...
    99+
    2023-06-21
  • C语言如何实现带头双向循环链表
    这篇文章主要介绍了C语言如何实现带头双向循环链表，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。前言在实际生活中最常用的就是这两种链表。无头单向非循环链表。和带头双向循环链表。...
    99+
    2023-06-29
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作