首页 > 其他分享 >链表-双向链表的基本设计(C语言代码实现)

链表-双向链表的基本设计(C语言代码实现)

时间:2024-08-27 09:22:56浏览次数:11  
标签:pre 结点 next 链表 双向 C语言 data

1. 双向链表的简介&概念

单链表在很多时候已经可以胜任很多优秀的操作了,但是,单链表任然存在不足,所谓‘单链表’,是指结点中只有一个指向其后继的指针,具有单向性,有时需要搜索大量数据的时候,就必须要多次进行从头开始的遍历,这样的搜索不是很便利。

图:单链表示意图

对此在单链表的基础上,产生了双向链表的概念,即: 在单链表的基础上,对于每一个结点设计一个前驱结点,前驱结点与前一个结点相互连接,构成一个链表。

双向链表可以简称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

图:双向链表示意图

一个完整的双向链表应该是头结点的pre指针指为空,尾结点的next指针指向空,其余结点前后相链。

2. 双向链表的结点设计

对于每一个结点而言,有:

其中,DATA表示数据,其可以是简单的类型(如int,double等等),也可以是复杂的结构体(struct类型);

pre代表的是前驱指针,它永远指向当前结点的前一个结点,注意,如果当前结点是头结点,则pre指针为空;

next代表的是后继指针,它永远指向当前结点的下一个结点,注意,如果当前结点是尾结点,则next指针为空

其代码设计可以为:

typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line,*a;
//分别表示该结点的前驱(pre),后继(next),以及当前数据(data)

3. 双链表的创建

对于创建双向链表,我们需要先创建头结点再逐步的进行添加,请注意,双向链表的头结点是有数据元素的,也就是头结点的data域中是存有数据的,这与一般的单链表是不同的。

对于逐步添加数据,我们采取的做法是,开辟一段新的内存空间作为新的结点,为这个结点进行的data进行赋值,然后将已成链表的上一个结点的next指针指向自身,自身的pre指针指向上一个结点。

其代码可以设计为:

//创建双链表
line* initLine(line * head){
    int number,pos=1,input_data;
    //三个变量分别代表结点数量,当前位置,输入的数据
    printf("请输入创建结点的大小\\n");
    scanf("%d",&number);
    if(number<1){return NULL;} //输入非法直接结束

    //头结点创建///
    head=(line*)malloc(sizeof(line));
    head->pre=NULL;
    head->next=NULL;
    printf("输入第%d个数据\\n",pos++);
    scanf("%d",&input_data);
    head->data=input_data;
  
    line * list=head;
    while (pos<=number) {
        line * body=(line*)malloc(sizeof(line));
        body->pre=NULL;
        body->next=NULL;
        printf("输入第%d个数据\\n",pos++);
        scanf("%d",&input_data);
        body->data=input_data;
        
        list->next=body;
        body->pre=list;
        list=list->next;
    }
    return head;
}

初步看起来双向链表似乎比单链表的两种创建方法要复杂,其实将过程逐步拆解为 创建头结点----创建一个新的结点----将头结点和新结点相互链接----再度创建新结点……这样的过程去思考,再反过头多看几遍代码会有助于理解。

标签:pre,结点,next,链表,双向,C语言,data
From: https://blog.csdn.net/qq_45398836/article/details/141531262

相关文章

  • 手把手带你用C语言实现控制台小游戏扫雷(附源码)
    文章目录一、扫雷游戏整体设计思路1.扫雷游戏功能说明2.游戏的分析和设计3.文件结构设计:二、主函数大致模型三、创建棋盘四、初始化棋盘五、打印棋盘六、布置雷七、排查雷八、源码九、如何把游戏分享给小伙伴十、扫雷进阶的一些思路一、扫雷游戏整体设计思路1.扫雷......
  • C语言程序设计-实现三(N)子棋游戏
    画自己喜欢的画,别停笔小艺术家。实现三子棋:test.c //测试游戏的逻辑#include"game.h"//自己的头文件voidmenu(){ printf("*****************************\n"); printf("******1.play0.exit******\n"); printf("*****************************\n&quo......
  • javascript怎么实现链表?
    在JavaScript中实现链表通常涉及定义一个链表节点类(通常称为ListNode)和一个链表类(例如LinkedList),然后在这个链表类中实现各种操作链表的方法,如添加节点、删除节点、遍历链表等。以下是使用JavaScript实现单向链表的一个基本示例:链表节点类(ListNode)首先,我们定义一个链表节点......
  • 【故障识别与诊断】基于EEMD-MPE-KPCA-BILSTM(集合经验模态分解-多尺度排列嫡-核主元
      ......
  • 【C语言】详解函数
    文章目录前言一、函数的概念二、自定义函数1.函数的语法形式2.形参和实参3.return语句三、库函数1.标准库和头文件2.库函数的使用四、函数的声明和定义五、传值调用和传址调用六、嵌套调用和链式访问1.嵌套调用2.链式访问前言一、函数的概念二~三、自定义函......
  • 新手专科准大一学习c语言的第10天之strcpy、memset、自定义函数的学习与应用
    strcpystrcpy是C语言标准库中的一个字符串操作函数,用于将源字符串复制到目标字符串中。#include<stdio.h>#include<string.h>intmain(){chararr1[50];//确保目标数组足够大,能够容纳源字符串chararr2[]="helloworld";//源字符串......
  • [我的C语言学习笔记(08)]C语言输入输出以及缓冲区概念
    查阅stdio.h标准库(https://cplusplus.com/reference/cstdio/),可以发现不少输入输出函数。这些是格式输入输出:这些是字符(包括字符串,也即字符数组)输入输出:这篇会介绍几个常用函数的用法,同时介绍缓冲区的概念。文章目录stream的概念输出printf函数putchar函数pu......
  • 【C语言】宏定义详解---老公出轨版 (づ◡﹏◡)づ
    目录C语言宏定义详解1.宏定义关键词总览2.`#define`3.`#undef`4.`#ifdef`5.`#ifndef`6.`#if`7.`#else`8.`#elif`9.`#endif`10.`#include`11.`#error`12.`#pragma`12.1`#pragmaonce`12.2`#pragmapack`12.3`#pragmawarning`12.4`#pragmaGCC`13.`#li......
  • 【链栈的实现】--------本质为不带头结点的 头插法建立起来的单链表
    1.链栈的基本属性与特征:链栈是运算受限的单链表,只能在链表头部进行操作2.链栈的相关基础操作汇总初始化操作:操作结果:构造一个空栈S。InitStack(LinkStack*s)判定S是否为空栈:初始条件:栈S已存在操作结果:若栈S为空栈,则返回TRUE,否则FALSE.StackEmpty(LinkStack......
  • C语言--类型转换
    数据的类型不同,在进行混合运算时会涉及到类型转换问题,转换的方法有哪些?一、自动转换:遵循一定的规则,由编译系统自动完成.(一)自动转换的原则:1、占用内存字节数少(取值范围小)的类型,向占用内存字节数多(取值范围大)的类型转换,目的是为了保证精度不降低.2、转换方向:3、当......