数据结构与算法学习笔记二---线性表的实现二(C语言)

目录

前言

1.双向链表的定义

2.双向链表的表示和实现

1.双向链表的定义

2.初始化

3.插入

4.销毁

5.双向链表是否为空

6.表长

7.获取双向链表中的元素

8.删除

9.遍历节点

10.完整代码

前言

        记录下双向链表的表示和实现。

1.双向链表的定义

        单链表中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为 0(1)，而查找直接前驱的执行时间为 0(n)。为克服单链表这种单向性的缺点，可利用双向链表(Double Linked List )。
        双向链表是一种链表数据结构，每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。

2.双向链表的表示和实现

1.双向链表的定义

// 定义
typedef struct DNode {
    int data;
    struct DNode *prev; //前驱节点
    struct DNode *next; //后继节点
} DNode, *DoubleLinkList;

2.初始化

// 初始化
void initDoubleLinkList(DoubleLinkList *list) {
    *list = NULL;
}

3.插入

// 插入
void insertAtEnd(DoubleLinkList *list, int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = NULL;

    if (*list == NULL) {
        newNode->prev = NULL;
        *list = newNode;
    } else {
        DNode *current = *list;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
        newNode->prev = current;
    }
}

4.清空

void clearDoubleLinkList(DoubleLinkList & doubleLinkList){
    DoubleLinkList p = doubleLinkList;
    p->next = nullptr;
    p->prior = nullptr;
}

4.返回链表中第一个与element相同的数据元素的下标

        释放链表指针，调用free函数。

int locationDoubleLinkListElement(DoubleLinkList doubleLink,int element,int * position){
    DoubleLinkList p = doubleLink;
    int j = 1;
    while (p != NULL) {
        if (p->data == element) {
            * position = j;
            return 1;
        }
        p = p->next;
        j++;
    }
    return 0;
}

5.表长

int doubleLinkListLength(DoubleLinkList doubleLinkList){
    DNode * p = doubleLinkList->next;
    int length = 1;
    while (p != NULL) {
        p = p->next;
        length ++;
    }
    return length;
}

6.前驱节点

int priorDoubleElement(DoubleLinkList doubleLink,int element,int * priorElement){
    DoubleLinkList p = doubleLink;
    int j = 1;
    while (p != NULL) {
        if (p->data == element) {
            if (p->prev == NULL) {
                return 0;
            }
            * priorElement = p->prev->data;
            return 1;
        }
        p = p->next;
        j++;
    }
    return 0;
}

7.获取双向链表中的元素

int getDoubleLinkElement(DoubleLinkList doubleLink,int position,int *element){
    DoubleLinkList current = doubleLink;
    int j = 1;
    while (current != NULL && j< position) {
        current = current->next;
        j++;
    }
    if (!current || j > position) {//第i个元素不存在
        return 0;
    }
    * element = current->data;
    
    return 1;
}

8.删除

       和单链表算法相同。

bool deleteDoubleLinkList(DoubleLinkList &doubleLinkList, int position){
    if (position < 1 || position > doubleLinkListLength(doubleLinkList)) {//删除位置非法
        return false;
    }
    
    DoubleLinkList p = doubleLinkList;
    int j = 0;
    while (p->next != nullptr && j < position - 1) {// 找到要删除结点的前一个结点
        p = p->next;
        ++j;
    }
    
    if (j < position - 1 || p->next == nullptr) {
        return false; // 删除位置超出范围
    }
    
    DoubleLinkList q = p->next; // 要删除的结点
    p->next = q->next; // 前一个结点指向后一个结点
    free(q); // 释放删除结点的内存
    return true;
}

9.后继节点

int nextDoubleElement(DoubleLinkList doubleLink, int element, int *nextElement){
    DoubleLinkList p = doubleLink->next; // 从第一个数据节点开始遍历
    while (p != NULL) {
        if (p->data == element) {
            if (p->next == NULL) {
                return 0; // 没有后继节点
            }
            *nextElement = p->next->data; // 将后继节点的数据赋值给nextElement
            return 1; // 找到后继节点，返回1
        }
        p = p->next; // 移动到下一个节点
    }
    return 0; // 没有找到指定元素
}

10.遍历节点

void traverseDoubleLinkList(DoubleLinkList & doubleLinkList){
    DoubleLinkList p = doubleLinkList->next;
    while (p != nullptr) {
        cout<<p->data<<"\t";
        p = p->next;
    }
    cout<<endl;
}

11.完整代码

       

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

// 定义
typedef struct DNode {
    int data;
    struct DNode *prev; //前驱节点
    struct DNode *next; //后继节点
} DNode, *DoubleLinkList;

// 初始化
void initDoubleLinkList(DoubleLinkList *list) {
    *list = NULL;
}
// 双向链表是否为空
int doubleLinkListEmpty(DoubleLinkList doubleLinkList){
    return doubleLinkList == NULL;
}
// 获取第position位置的数据元素
int getDoubleLinkElement(DoubleLinkList doubleLink,int position,int *element){
    DoubleLinkList current = doubleLink;
    int j = 1;
    while (current != NULL && j< position) {
        current = current->next;
        j++;
    }
    if (!current || j > position) {//第i个元素不存在
        return 0;
    }
    * element = current->data;
    
    return 1;
}
// 返回链表中第一个与element相同的数据元素的下标
int locationDoubleLinkListElement(DoubleLinkList doubleLink,int element,int * position){
    DoubleLinkList p = doubleLink;
    int j = 1;
    while (p != NULL) {
        if (p->data == element) {
            * position = j;
            return 1;
        }
        p = p->next;
        j++;
    }
    return 0;
}
// 前驱节点
int priorDoubleElement(DoubleLinkList doubleLink,int element,int * priorElement){
    DoubleLinkList p = doubleLink;
    int j = 1;
    while (p != NULL) {
        if (p->data == element) {
            if (p->prev == NULL) {
                return 0;
            }
            * priorElement = p->prev->data;
            return 1;
        }
        p = p->next;
        j++;
    }
    return 0;
}
// 后继节点
int nextDoubleElement(DoubleLinkList doubleLink, int element, int *nextElement){
    DoubleLinkList p = doubleLink->next; // 从第一个数据节点开始遍历
    while (p != NULL) {
        if (p->data == element) {
            if (p->next == NULL) {
                return 0; // 没有后继节点
            }
            *nextElement = p->next->data; // 将后继节点的数据赋值给nextElement
            return 1; // 找到后继节点，返回1
        }
        p = p->next; // 移动到下一个节点
    }
    return 0; // 没有找到指定元素
}
// 删除双向链表中的指定位置的节点
int deleteDoubleLinkList(DoubleLinkList *doubleLink, int index) {
    if (*doubleLink == NULL || index < 1) {
        // 链表为空或者索引无效，无法删除
        return 0;
    }

    DoubleLinkList current = *doubleLink;

    // 如果要删除的是第一个节点
    if (index == 1) {
        *doubleLink = current->next; // 更新头指针
        if (*doubleLink != NULL) {
            (*doubleLink)->prev = NULL; // 更新新的第一个节点的前驱指针
        }
        free(current); // 释放删除的节点内存
        return 1; // 返回删除成功
    }

    int position = 1;

    // 查找要删除的节点
    while (current != NULL && position < index) {
        current = current->next;
        position++;
    }

    // 如果current为空，说明索引超出范围
    if (current == NULL) {
        return 0; // 删除失败
    }

    // 处理前驱节点的next指针
    if (current->prev != NULL) {
        current->prev->next = current->next;
    }

    // 处理后继节点的prev指针
    if (current->next != NULL) {
        current->next->prev = current->prev;
    }

    // 释放要删除的节点的内存
    free(current);

    return 1; // 返回删除成功
}



// 插入
void insertAtEnd(DoubleLinkList *list, int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = NULL;

    if (*list == NULL) {
        newNode->prev = NULL;
        *list = newNode;
    } else {
        DNode *current = *list;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
        newNode->prev = current;
    }
}

// 使用数组生成测试数据
void createDoubleLinkList(DoubleLinkList *linkList, int values[], int size) {
    initDoubleLinkList(linkList); // Initialize the doubly linked list
    for (int i = 0; i < size; i++) {
        insertAtEnd(linkList, values[i]); // Insert each element into the list
    }
}
int doubleLinkListLength(DoubleLinkList doubleLinkList){
    DNode * p = doubleLinkList->next;
    int length = 1;
    while (p != NULL) {
        p = p->next;
        length ++;
    }
    return length;
}
// 打印
void printList(DoubleLinkList list) {
    printf("**********\t链表数据元素\t**********\n");
    while (list != NULL) {
        printf("%d ", list->data);
        list = list->next;
    }
    printf("\n");
}
void traverseDoubleLinkList(DoubleLinkList doubleLinkList){
    while (doubleLinkList != NULL) {
        printf("%d ", doubleLinkList->data);
        doubleLinkList = doubleLinkList->next;
    }
    printf("\n");
}
void debugDoubleLinkInformation(char * string){
    printf("\n********** [测试%s] **********\n",string);
}
int main(int argc, const char *argv[]) {
    DoubleLinkList list;
    int element;
    printf("初始化双向节点\t✅\n");
    initDoubleLinkList(&list);
    if (doubleLinkListEmpty(list)) {
        printf("空链表\t✅\n");
    }
    // 使用数据初始化数据
    int testData[] = {10, 20, 30, 40, 50};
    int dataSize = sizeof(testData) / sizeof(testData[0]);
    // 创建双向链表测试数据
    createDoubleLinkList(&list, testData, dataSize);
    // 打印双向链表中的元素
    printList(list);
    debugDoubleLinkInformation("双向链表表长");
    if (!doubleLinkListEmpty(list)) {
        printf("链表不为空,表长:%d\t✅\n",doubleLinkListLength(list));
    }
    
    debugDoubleLinkInformation("双向链表中的数据元素");
    if (!getDoubleLinkElement(list, 0, &element)) {
        printf("非法位置\t✅\n");
    }
    if (getDoubleLinkElement(list, 1, &element)) {
        printf("第1个位置的数据元素下标为:%d\t✅\n",element);
    }
    if (getDoubleLinkElement(list, 2, &element)) {
        printf("第2个位置的数据元素下标为:%d\t✅\n",element);
    }
    if (getDoubleLinkElement(list, 5, &element)) {
        printf("第5个位置的数据元素下标为:%d\t✅\n",element);
    }
    if (!getDoubleLinkElement(list, 6, &element)) {
        printf("非法位置\t✅\n");
    }
    
    debugDoubleLinkInformation("双向链表中的下标");
    int position;
    if (locationDoubleLinkListElement(list, 10, &position)) {
        printf("数据元素10的下标为:%d\t✅\n",position);
    }
    if (locationDoubleLinkListElement(list, 20, &position)) {
        printf("数据元素20的下标为:%d\t✅\n",position);
    }
    if (locationDoubleLinkListElement(list, 50, &position)) {
        printf("数据元素50的下标为:%d\t✅\n",position);
    }
    if (!locationDoubleLinkListElement(list, 60, &position)) {
        printf("数据元素50的下标不存在\t✅\n");
    }
    
    debugDoubleLinkInformation("双向链表中的前驱节点");
    int priorElement;
    if (!priorDoubleElement(list, 10, &priorElement)) {
        printf("数据元素10的前驱节点不存在\t✅\n");
    }
    if (priorDoubleElement(list, 20, &priorElement)) {
        printf("数据元素20的前驱节点为:%d\t✅\n",priorElement);
    }
    if (priorDoubleElement(list, 30, &priorElement)) {
        printf("数据元素30的前驱节点为:%d\t✅\n",priorElement);
    }
    if (priorDoubleElement(list, 40, &priorElement)) {
        printf("数据元素40的前驱节点为:%d\t✅\n",priorElement);
    }
    if (priorDoubleElement(list, 50, &priorElement)) {
        printf("数据元素40的前驱节点为:%d\t✅\n",priorElement);
    }
    if (!priorDoubleElement(list, 100, &priorElement)) {
        printf("数据元素100的前驱节点不存在\t✅\n");
    }

    debugDoubleLinkInformation("双向链表中的后继节点");
    int nextElement;
    if (nextDoubleElement(list, 10, &nextElement)) {
        printf("数据元素10的后继节点为:%d\t✅\n",nextElement);
    }
    if (nextDoubleElement(list, 20, &nextElement)) {
        printf("数据元素20的后继节点为:%d\t✅\n",nextElement);
    }
    if (nextDoubleElement(list, 30, &nextElement)) {
        printf("数据元素30的后继节点为:%d\t✅\n",nextElement);
    }
    if (nextDoubleElement(list, 40, &nextElement)) {
        printf("数据元素40的后继节点为:%d\t✅\n",nextElement);
    }
    if (!nextDoubleElement(list, 50, &nextElement)) {
        printf("数据元素50的后继节点不存在\t✅\n");
    }
    if (!nextDoubleElement(list, 100, &nextElement)) {
        printf("数据元素100的后继节点不存在\t✅\n");
    }
    debugDoubleLinkInformation("双向链表删除功能");
    printf("删除之前的链表\n");
    traverseDoubleLinkList(list);
    if (deleteDoubleLinkList(&list, 5)) {
        printf("删除之后的链表\n");
        traverseDoubleLinkList(list);
    }else{
        printf("删除失败\n");
    }


    return 0;
}

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

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

相关文章

实习算法准备之BFSDFS

实习算法准备之BFSDFS

这里写目录标题 1 理论1.1 BFS框架 2 例题2.1 二叉树的最小高度2.2 打开转盘锁2.3 滑动谜题 1 理论 BFS和DFS是两个遍历算法&#xff0c;其中DFS之前已经接触过&#xff0c;就是回溯&#xff0c;忘记的话请回顾回溯篇的例题&#xff08;全排列&#xff0c;N皇后&#xff09; B…
阅读更多...
C++解方程组的库

C++解方程组的库

解决多元多次方程组的问题&#xff0c;你可以考虑以下几个C库&#xff1a; Eigen: Eigen库是一个高性能的C模板库&#xff0c;用于线性代数运算。它提供了强大的矩阵运算功能&#xff0c;可以用来解多元一次方程组。对于多次方程组&#xff0c;你可能需要结合Eigen和一些数值优…
阅读更多...
Rust网络请求神器reqwest介绍和使用，5分钟速学

Rust网络请求神器reqwest介绍和使用，5分钟速学

在 Rust 生态中&#xff0c;reqwest 可以说是最流行的 HTTP 客户端库了。它提供了一个高层级的、人性化的 API&#xff0c;让我们可以非常轻松地发送各种 HTTP 请求和处理响应。无论是 quickstart、自定义请求头、cookie 管理&#xff0c;还是文件上传&#xff0c;reqwest 都能…
阅读更多...
了解Cookie登录：原理、实践与安全指南

了解Cookie登录：原理、实践与安全指南

什么是Cookie登录&#xff1f; Cookie是什么 当你首次登录网站时&#xff0c;你会输入用户名和密码。在后台&#xff0c;网站的服务器验证这些凭据是否正确。一旦确认你的身份无误&#xff0c;服务器就会创建一个Cookie&#xff0c;并将其发送到你的浏览器。这了解Cookie登录…
阅读更多...
38-数组 _ 一维数组

38-数组 _ 一维数组

38-1 数组的创建 数组是一组相同类型元素的集合。 数组的创建方式&#xff1a; type_t arr_name [const_n]; //type_t 是指数组的元素类型 //const_n是一个常量表达式&#xff0c;用来指定数组的大小 举例&#xff1a; int arr[10]; char ch[5]; double data[20]; 问&…
阅读更多...
HarmonyOS 实战开发-MindSpore Lite引擎进行模型推理

HarmonyOS 实战开发-MindSpore Lite引擎进行模型推理

场景介绍 MindSpore Lite 是一款 AI 引擎&#xff0c;它提供了面向不同硬件设备 AI 模型推理的功能&#xff0c;目前已经在图像分类、目标识别、人脸识别、文字识别等应用中广泛使用。 本文介绍使用 MindSpore Lite 推理引擎进行模型推理的通用开发流程。 基本概念 在进行开…
阅读更多...
vscode连接远程Linux服务器时，没有权限新建文件夹或者文件

vscode连接远程Linux服务器时，没有权限新建文件夹或者文件

参考链接&#xff1a; VS code 保存或新建文件没有权限的问题 vscode连接远程Linux服务器时&#xff0c;没有权限新建文件夹或者文件&#xff1a; 用一条命令解决&#xff1a; sudo chown -R myuser /path/to/foldermyuser是当前用户名&#xff0c; /path/to/folder是 需要操…
阅读更多...
编程学习路线

编程学习路线

Java最强学习路线 快来官网定制一套属于自己的学习路线吧 官方网址&#xff1a; Learn to become a modern Java developerCommunity driven, articles, resources, guides, interview questions, quizzes for java development. Learn to become a modern Java developer by…
阅读更多...
运维笔记：基于阿里云跨地域服务器通信（上）

运维笔记：基于阿里云跨地域服务器通信（上）

运维笔记 阿里云&#xff1a;跨地域服务器通信&#xff08;上&#xff09; - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this a…
阅读更多...
【嵌入式AI开发】轻量级卷积神经网络MobileNet项目实战——文末完整源码工程文件

【嵌入式AI开发】轻量级卷积神经网络MobileNet项目实战——文末完整源码工程文件

前言：本文介绍轻量级卷积神经网络MobileNet网络实战，包含MobileNetV1、MobileNetV2、ResNet50三个预训练模型可供选择。 实现：1.预训练MobileNet图像分类，2.调用摄像头实时MobileNet图像分类，3.MobileNet视频图像分类。 MobileNet网络理论详解：【嵌入式AI开发】轻量级卷…
阅读更多...
git提交常用

git提交常用

git config --global user.name "你的名字或昵称" git config --global user.email "你的邮箱" 第一次上传到码云 1.找到要提交到码云的文件夹 右击打开Git Bash Here 2.用命令行创建本地仓库 git init 3.将待全部文件放入缓冲区 git add . 4.提交缓…
阅读更多...
优化贪吃蛇在前进过程中，前进和后退的问题

优化贪吃蛇在前进过程中，前进和后退的问题

1. 左边为head,右边为tail 定义相反数在abs&#xff08;&#xff09;绝对值函数中实现 2. 在转向函数turn()中&#xff0c;如果绝对值不相等的时候才赋予方向的值 3.贪吃蛇吃食物的思路 3.1 初始化食物initFood(), 蛇碰到食物函数hasFood&#xff08;&#xff09;,在移…
阅读更多...
如何用Python实现智能客服问答系统

如何用Python实现智能客服问答系统

随着人工智能技术的不断发展&#xff0c;机器人客服与聊天系统成为了热门话题。Python作为一种简单易学、功能强大的编程语言&#xff0c;在机器人客服与聊天系统的开发中具有广泛应用。 本文将介绍如何使用Python实现机器人客服与聊天系统&#xff0c;包括实现方式、代码示例和…
阅读更多...
Mysql-主从复制理解

Mysql-主从复制理解

环境&#xff1a;mysql&#xff0c;主从复制&#xff0c;必须有2个mysql实例&#xff0c;也就是说可以在一台电脑上安装2个msyql&#xff0c;或者2台服务器&#xff0c;一个主服务器&#xff0c;一个从服务器 在实际的生产中&#xff0c;为了解决Mysql的单点故障已经提高MySQL的…
阅读更多...
【Unity动画系统】动画基本原理与Avater骨骼复用

【Unity动画系统】动画基本原理与Avater骨骼复用

动画基本原理 动画片段文件是一个描述物体变化状态的文本文件 在Unity中创建的资源文件大多都是YAML语言编写的文本文件 Curves表示一种变化状态&#xff0c;为空的话则没有记录任何内容 位置变化后的旋转变化状态&#xff1a; 动画文件里的Path名字要相同才能播放相同的动画 …
阅读更多...
外贸财务挑战面面观：应对难题之道大揭秘！

外贸财务挑战面面观：应对难题之道大揭秘！

出海也开始卷起来了。越来越多的中国企业投身海外市场&#xff0c;寻求更广阔的发展空间。然而&#xff0c;出海之路并非坦途&#xff0c;企业既需把握全球商机&#xff0c;又需应对数字化转型、本土化运营、文化差异性等多重挑战。企业出海&#xff0c;该如何应对这些风浪&…
阅读更多...
GPU服务器和普通服务器有何区别？

GPU服务器和普通服务器有何区别？

众所周知&#xff0c;服务器是网络中的重要设备&#xff0c;要接受少至几十人、多至成千上万人的访问&#xff0c;因此对服务器具有大数据量的快速吞吐、超强的稳定性、长时间运行等严格要求。 GPU服务器和普通服务器的主要区别在于硬件配置和适用场景&#xff0c;特别是处理器…
阅读更多...
C 函数递归

C 函数递归

目录 什么是递归 递归的限制条件 递归的例子 1、用递归求n的阶乘 递归扩展学习 1、青蛙跳台阶 思路 代码实现 2、汉诺塔问题​ 思路 代码实现 总结 什么是递归 递归&#xff1a;“递推” “回归” 在C语言中&#xff0c;函数递归就是&#xff1a;函数自己调用自…
阅读更多...
FANUC机器人SOCKET连接指令编写

FANUC机器人SOCKET连接指令编写

一、创建一个.KL文件编写连接指令 创建一个KL文本来编写FANUC机器人socket连接指令 二、KAREL指令代码 fanuc机器人karel编辑器编辑的karel代码如下&#xff1a; PROGRAM SM_CON %COMMENT SOCKET连接 %STACKSIZE 4000 --堆栈大小 %INCLUDE klevccdfVAR status,data_type,in…
阅读更多...
武汉星起航：成功挂牌新起点，董事长张振邦引领行业再攀高峰

武汉星起航：成功挂牌新起点，董事长张振邦引领行业再攀高峰

2023年10月30日&#xff0c;对于武汉星起航电子商务有限公司而言&#xff0c;是一个具有里程碑意义的日子。这一天&#xff0c;公司在上海股权托管交易中心成功挂牌展示&#xff0c;正式登陆资本市场&#xff0c;开启了公司发展的新篇章。这一创举不仅彰显了公司在跨境电商领域…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站