【数据结构】 双链表的基本操作 （C语言版）

目录

一、双链表

1、双链表的定义：

2、双链表表的优缺点： 

二、双链表的基本操作算法（C语言）

 1、宏定义

 2、创建结构体

3、双链表的初始化 

4、双链表表插入

5、双链表的查找

6、双链表的取值

7、求双链表长度

8、双链表的删除

9、双链表的清空

10、双链表的销毁

11、输出链表元素

三、双链表的全部代码（C语言）

四、运行结果

一、双链表

1、双链表的定义：

双链表也叫双向链表，是一种链表数据结构。它的每个数据结点包含两个指针，一个指向前一个结点，另一个指向后一个结点。这意味着从双向链表的任何节点都可以方便地访问其前驱或后继节点。通常，我们构造双向循环链表，它的特点是尾节点的指针域指向头结点，整个链表形成一个环。

 

2、双链表表的优缺点： 

双链表的优点：

  1. 可以方便地访问前驱和后继节点，既可以向前也可以向后遍历链表。
  2. 在某些情况下，双链表比单链表更节省空间，因为它不需要额外的指针来存储前驱和后继节点的信息。

双链表的缺点：

  1. 插入和删除节点相对复杂，需要更多的时间来调整指针。
  2. 双链表需要更多的存储空间，因为每个节点都需要额外的指针来存储前驱和后继节点的信息。

二、双链表的基本操作算法（C语言）

 1、宏定义
#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;
 2、创建结构体
typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
} DuLNode, *DuLinkList;
3、双链表的初始化 
//双链表初始化
Status DInitList(DuLinkList &head) {
    head = new DuLNode;
    head->prior = NULL;
    head->next = NULL;
    return OK;
}
4、双链表表插入
//插入
Status DListInsert(DuLinkList &head, int i, ElemType e) {
    DuLinkList p = head;
    int j = 0;
    while (p && (j < i - 1)) {
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1) {
        return ERROR;
    }

    DuLNode *s = new DuLNode;
    s->data = e;
    s->next = p->next;
    if(p->next != NULL){
      p->next->prior = s;	
    }
    p->next = s;
    s->prior = p;

    return OK;
}
5、双链表的查找

//查找
int DLocateLinkListElem(DuLinkList head, ElemType e) {
    DuLinkList p = head->next;
    int j = 1;
    while (p && (p->data != e)) {
        p = p->next;
        j++;
    }
    if (p == NULL) { 
        return 0;
    }
    return j;
}
6、双链表的取值
//取值
Status DGetLinkList(DuLinkList head, int i, ElemType &e) {
    DuLinkList p = head->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (p == NULL) {
        return ERROR;
    }
    e = p->data;

    return OK;
}
7、求双链表长度
//求双链表长度
Status DGetLinkListLength(DuLinkList head) {
    DuLinkList p = head->next;
    int length = 0;
    while (p!=NULL) {            //单链表不为空表时
        length++;
        p = p->next;
    }
    return length;
}
8、双链表的删除
//删除
Status DListDelete(DuLinkList &head, int i, ElemType &e) {
    DuLinkList p = head;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }

    if (!p) {
        return ERROR;
    }
    DuLinkList q = p->next;
    e = q->data;
	p->next = q->next;
    if(q->next != NULL){
    	q->next->prior=p;
    }
    delete q;
    return OK;
}
9、双链表的清空
//清空
Status DClearLinkList(DuLinkList &head) {
    DuLinkList p = head->next;
    DuLinkList q;
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
    return OK;
}
10、双链表的销毁
//销毁
Status DestoryDLinkList(DuLinkList &head) {
    DuLinkList p;
    while (head) {
        p = head;
        head = head->next;
        delete p;
    }
    return OK;
}
11、输出链表元素
//输出链表元素
void DprintLinkList(DuLinkList head) {
    DuLinkList p = head->next;
    while (p) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

三、双链表的全部代码（C语言）

#include <stdio.h>

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
} DuLNode, *DuLinkList;

//双链表初始化
Status DInitList(DuLinkList &head) {
    head = new DuLNode;
    head->prior = NULL;
    head->next = NULL;
    return OK;
}

//功能菜单
int choice() {
    printf("==================================\n");
    printf("         双链表操作功能菜单        \n");
    printf("1、插入元素  2、查询表长  3、按位查找\n");
    printf("4、按值查找  5、删除元素  6、销毁链表\n");
    printf("7、清空链表  8、批量插入  9、链表元素\n");
    printf("==================================\n");
    return 0;
}

//插入
Status DListInsert(DuLinkList &head, int i, ElemType e) {
    DuLinkList p = head;
    int j = 0;
    while (p && (j < i - 1)) {
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1) {
        return ERROR;
    }

    DuLNode *s = new DuLNode;
    s->data = e;
    s->next = p->next;
    if(p->next != NULL){
      p->next->prior = s;	
    }
    p->next = s;
    s->prior = p;

    return OK;
}

//查找
int DLocateLinkListElem(DuLinkList head, ElemType e) {
    DuLinkList p = head->next;
    int j = 1;
    while (p && (p->data != e)) {
        p = p->next;
        j++;
    }
    if (p == NULL) { 
        return 0;
    }
    return j;
}

//取值
Status DGetLinkList(DuLinkList head, int i, ElemType &e) {
    DuLinkList p = head->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (p == NULL) {
        return ERROR;
    }
    e = p->data;

    return OK;
}

//求双链表长度
Status DGetLinkListLength(DuLinkList head) {
    DuLinkList p = head->next;
    int length = 0;
    while (p!=NULL) {            //单链表不为空表时
        length++;
        p = p->next;
    }
    return length;
}


//删除
Status DListDelete(DuLinkList &head, int i, ElemType &e) {
    DuLinkList p = head;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }

    if (!p) {
        return ERROR;
    }
    DuLinkList q = p->next;
    e = q->data;
	p->next = q->next;
    if(q->next != NULL){
    	q->next->prior=p;
    }
    delete q;
    return OK;
}


//清空
Status DClearLinkList(DuLinkList &head) {
    DuLinkList p = head->next;
    DuLinkList q;
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
    return OK;
}

//销毁
Status DestoryDLinkList(DuLinkList &head) {
    DuLinkList p;
    while (head) {
        p = head;
        head = head->next;
        delete p;
    }
    return OK;
}

//输出链表元素
void DprintLinkList(DuLinkList head) {
    DuLinkList p = head->next;
    while (p) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {

    DuLinkList Dlist;

    printf("双链表正在初始化....\n");
    int InitStatus = DInitList(Dlist);
    if (InitStatus == OK) {
        printf("双链表初始化成功！\n");
    } else {
        printf("双链表初始化失败！\n");
    }

    choice();

    while (1) {
        int flag;
        printf("请输入所需的功能编号：\n");
        scanf("%d", &flag);

        switch (flag) {//通过开关进行功能选择
            case 1: {//插入元素
                //ListInsert_Dul(Dlist,1,'a');
                int insertIndex;
                ElemType inserElem;
                printf("请输入插入元素位置及插入元素(请在英文状态下输入例如:1,a): \n");
                scanf("%d,%c", &insertIndex, &inserElem);
                Status InsertS = DListInsert(Dlist, insertIndex, inserElem);
                if (InsertS == OK) {
                    printf("向双链表%d个位置,插入元素为%c成功！\n\n", insertIndex, inserElem);
                } else {
                    printf("向双链表插入元素失败！\n\n");
                }
            }
                break;
            case 2: {//求单链表的长度
                int length = DGetLinkListLength(Dlist);
                printf("循环双链表的长度为:%d。 \n\n", length);
            }
                break;
            case 3: {//取值
                Status GetIndex;
                printf("请输入需要查询的元素的位置：\n");
                scanf("%d", &GetIndex);
                ElemType GetElem;
                int GetStatus = DGetLinkList(Dlist, GetIndex, GetElem);
                if (GetStatus == OK) {
                    printf("从单链表中获取第%d位置元素成功，所获取到的元素为：%c。\n\n", GetIndex, GetElem);
                } else {
                    printf("从单链表中获取第%d位置元素失败！\n\n", GetIndex);
                }
            }
                break;
            case 4: {//查找
                ElemType LocateElem;
                printf("请输入想要查找元素：\n");
                getchar();    //用于接收回车
                scanf("%c", &LocateElem);
                Status LocateIndex = DLocateLinkListElem(Dlist, LocateElem);
                if (LocateIndex > 0) {
                    printf("从双链表中查找元素%c成功，它在循环链表中的位置为第%d个！\n\n", LocateElem, LocateIndex);
                } else {
                    printf("从双链表中查找元素%c失败！\n\n", LocateElem);
                }
            }
                break;
            case 5: {//删除
                //ListDelete_DuL(list,1);
                Status DeleteIndex;
                printf("请输入想要删除元素的位置：\n");
                scanf("%d", &DeleteIndex);
                ElemType DeleteElem;
                ElemType DeleteStatus = DListDelete(Dlist, DeleteIndex, DeleteElem);
                if (DeleteStatus == OK) {
                    printf("删除双链表第%d个位置的元素成功，删除的元素为：%c。\n\n", DeleteIndex, DeleteElem);
                } else {
                    printf("删除双链表第%d个位置的元素失败！\n\n", DeleteIndex);
                }
            }
                break;
            case 6: {//销毁
                Status DestoryStatus = DestoryDLinkList(Dlist);
                if (DestoryStatus == OK) {
                    printf("双环链表销毁成功！\n\n");
                } else {
                    printf("双链表销毁失败！\n\n");
                }
            }
                break;
            case 7: {//清空
                Status ClearStatus = DClearLinkList(Dlist);
                if (ClearStatus == OK) {
                    printf("双链表清空成功！\n\n");
                } else {
                    printf("双链表清空失败！\n\n");
                }
            }
                break;
            case 8: {//批量插入
                int on;
                printf("请输入想要插入的元素个数：\n");
                scanf("%d", &on);
                ElemType array[on];
                for (int i = 1; i <= on; i++) {
                    getchar();
                    printf("向双链表第%d个位置插入元素为:", (i));
                    scanf("%c", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status InsertStatus = DListInsert(Dlist, i, array[i]);
                    if (InsertStatus == OK) {
                        printf("向双链表第%d个位置插入元素%c成功！\n", i, array[i]);
                    } else {
                        printf("向双链表第%d个位置插入元素%c失败！\n", i, array[i]);
                    }
                }
            }
                break;
            case 9: {//输出链表元素
                DprintLinkList(Dlist);
            }
                break;
               
            default: {
                printf("输入错误，无此功能，请检查输入:\n\n");
            }
        }
    }

    return 1;

}

四、运行结果

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2023年12月 Scratch 图形化（一级）真题解析#中国电子学会#全国青少年软件编程等级考试

2023年12月 Scratch 图形化（一级）真题解析#中国电子学会#全国青少年软件编程等级考试

Scratch图形化等级考试（1~4级）全部真题・点这里 一、单选题（共25题，每题2分，共50分） 第1题 观察下列每个圆形中的四个数，找出规律，在括号里填上适当的数？（ ） A：9 B：17 C：21 D：5 答案：C 左上角的数=下面两个数的和+右上角的数
阅读更多...
142.环形链表 II 、141. 环形链表（附带源码）

142.环形链表 II 、141. 环形链表（附带源码）

目录 一、142问题的分析与解决&#xff1a; 二、怎么做&#xff1f; 三、142代码 四、141代码 一、142问题的分析与解决&#xff1a; 核心&#xff1a;定义快慢指针&#xff1a;slow、fast 思路是当快指针fast进环时&#xff0c;慢指针slow一定没有进环 这个时候就是就变…
阅读更多...
flink基本概念

flink基本概念

1. Flink关键组件: 这里首先要说明一下“客户端”。其实客户端并不是处理系统的一部分&#xff0c;它只负责作业的提交。具体来说&#xff0c;就是调用程序的 main 方法&#xff0c;将代码转换成“数据流图”&#xff08;Dataflow Graph&#xff09;&#xff0c;并最终生成作业…
阅读更多...
Leetcode刷题笔记题解（C++）：LCR 174. 寻找二叉搜索树中的目标节点

Leetcode刷题笔记题解（C++）：LCR 174. 寻找二叉搜索树中的目标节点

思路&#xff1a;二叉搜索树的中序遍历是有序的从大到小的&#xff0c;故得出中序遍历的结果&#xff0c;即要第cnt大的数为倒数第cnt的数 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeN…
阅读更多...
新闻每天都在更新，那网页上的新闻页面是怎么使用Dreamweaver制作的？

新闻每天都在更新，那网页上的新闻页面是怎么使用Dreamweaver制作的？

新闻每天都在更新&#xff0c;那网页上的新闻页面是怎么使用Dreamweaver制作的&#xff1f; 新闻有很多种&#xff0c;但大多数结构都差不多&#xff0c;我们就先做一个简单的新闻页面&#xff0c;如图1中画圈圈的新闻内容。 图1 案例实现 新闻页面一般由四个部分构成&#…
阅读更多...
【spring】代码生成器

【spring】代码生成器

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;spring ⛺️稳中求进&#xff0c;晒太阳 代码生成器&#xff08;本质IO流&#xff09; 在mybatis的逆向工程生成model和mapper接口和xml文件后&#xff0c;还需要反复的写Service的接口和…
阅读更多...
何为PyTorch？

何为PyTorch？

PyTorch的名字来源于它的功能和设计哲学。"Py"代表Python&#xff0c;因为PyTorch是一个基于Python的深度学习库&#xff0c;它充分利用了Python语言的灵活性和易用性&#xff0c;为开发者提供了简洁而强大的接口。“Torch”则代表其前身—— Torch&#xff0c;这是一…
阅读更多...
7.前端--CSS-复合选择器

7.前端--CSS-复合选择器

1.什么是复合选择器 复合选择器是由两个或多个基础选择器&#xff0c;通过不同的方式组合而成的&#xff0c;可以更准确、更高效的选择目标元素&#xff08;标签&#xff09; 常用的复合选择器包括&#xff1a;后代选择器、子选择器、并集选择器、伪类选择器等等 2.后代选择器 …
阅读更多...
Opencv轮廓检测运用与理解

Opencv轮廓检测运用与理解

目录 引入 基本理解 加深理解 ①比如我们可以获取我们的第一个轮廓,只展示第一个轮廓 ②我们还可以用一个矩形把我们的轮廓给框出来 ③计算轮廓的周长和面积 引入 顾名思义,就是把我们图片的轮廓全部都描边出来 也就是我们在日常生活中面部识别的时候会有一个框,那玩意就…
阅读更多...
wayland（wl_shell） + egl + opengles 最简实例

wayland（wl_shell） + egl + opengles 最简实例

文章目录 前言一、ubuntu 上相关环境准备1. ubuntu 上安装 weston2. 确定ubuntu 上安装的opengles 版本3. 确定安装的 weston 是否支持 wl_shell 接口二、窗口管理器接口 wl_shell 介绍二、代码实例1.egl_wayland_demo.c2. 编译和运行2.1 编译2.2 运行总结参考资料前言 本文主…
阅读更多...
如何才能拥有比特币 - 01 ？

如何才能拥有比特币 - 01 ？

如何才能拥有BTC 在拥有 BTC 之前我们要先搞明白 BTC到底保存在哪里&#xff1f;我的钱是存在银行卡里的&#xff0c;那我的BTC是存在哪里的呢&#xff1f; BTC到底在哪里&#xff1f; 一句话概括&#xff0c;BTC是存储在BTC地址中&#xff0c;而且地址是公开的&#xff0c;…
阅读更多...
webpack-dev-server原理解析及其中跨域解决方法

webpack-dev-server原理解析及其中跨域解决方法

webpack proxy ,就是 webpack 提供的解决跨域的方案。其基本行为是接受客户端发送的请求后转发给其他的服务器&#xff0c;目的是为了解决在开发模式下的跨域问题。 原理 webpack中的proxy 工作原理是利用了 http-proxy-middleware 这个http 代理中间件&#xff0c;实现将请求…
阅读更多...
Canny边缘检测 双阈值检测理解

Canny边缘检测 双阈值检测理解

问题引入 我们用一个实际例子来引入问题 import cv2 import numpy as npimgcv2.imread("test.png",cv2.IMREAD_GRAYSCALE) # 修改图像大小 show cv2.resize(img,(500,500))v1cv2.Canny(show,120,250) v2cv2.Canny(show,50,100)# 连接图像 res np.hstack((v1,v2)…
阅读更多...
【C语言】动态内存函数介绍

【C语言】动态内存函数介绍

目录 1.malloc和free 2.calloc 3.realloc 1.malloc和free C语言提供了一个动态内存开辟的函数malloc&#xff1a; void* malloc(size_t size); 这个函数向内存申请一块连续可用的空间&#xff0c;并返回指向这块空间的指针。 ✔如果开辟成功&#xff0c;则返回一个指向开…
阅读更多...
3.RHCSA脚本配置及通过node2改密码

3.RHCSA脚本配置及通过node2改密码

运行脚本发现node2不成功 脚本破解 选第二个 Ctrl x 换行 破解成功后做node2的改密码题 回到redhat, 发现检测程序检测密码题成功,得了8分.
阅读更多...
【Java】Maven的安装与配置

【Java】Maven的安装与配置

初识Maven Maven是专门用于管理和构建Java项目的工具&#xff0c;它的主要功能有&#xff1a; 提供了一套标准化的项目结构 提供了一套标准化的构建流程&#xff08;编译&#xff0c;测试&#xff0c;打包&#xff0c;发布……&#xff09; 提供了一套依赖管理机制 标准化的…
阅读更多...
Hadoop基本概论

Hadoop基本概论

目录 一、大数据概论 1.大数据的概念 2.大数据的特点 3.大数据应用场景 二、Hadoop概述 1.Hadoop定义 2.Hadoop发展历史 3.Hadoop发行版本 4.Hadoop优势 5.Hadoop1.x/2.x/3.x 6.HDFS架构 7.Yarn架构 8.MapReduce架构 9.大数据技术生态体系 一、大数据概论 1.大数…
阅读更多...
74.MySQL 分页原理与优化（下）

74.MySQL 分页原理与优化（下）

文章目录 前言一、一次分页查询的演进二、分页数据在不同页反复出现的坑 前言 上一篇文章介绍了分页原理与优化&#xff1a;73.MySQL 分页原理与优化&#xff08;上&#xff09; 但分页还有一个“坑”需要注意&#xff0c;本文细细道来&#xff0c;可能很多朋友都踩过这个坑还…
阅读更多...
【大数据】流处理基础概念（一）：Dataflow 编程基础、并行流处理

【大数据】流处理基础概念（一）：Dataflow 编程基础、并行流处理

流处理基础概念&#xff08;一&#xff09;&#xff1a;Dataflow 编程基础、并行流处理 1.Dataflow 编程基础1.1 Dataflow 图1.2 数据并行和任务并行1.3 数据交换策略 2.并行流处理2.1 延迟与吞吐2.1.1 延迟2.1.2 吞吐2.1.3 延迟与吞吐 2.2 数据流上的操作2.2.1 数据接入和数据…
阅读更多...
圆的参数方程是如何推导的？

圆的参数方程是如何推导的？

圆的参数方程是如何推导的？ 1. 圆的三种参数表示2. 三角函数万能公式3. 回到圆的参数方程1. 圆的三种参数表示 已知圆的第一种参数方程为： x 2 + y 2 = r x^2+y^2=r x2+y2=r   圆的图像如下： 通过上图，不难理解，圆的参数方程还可以用三角函数表示，也就是第二种参数表…
阅读更多...
最新文章

Copyright @ 2022~2023