数据结构与算法学习笔记四---双向链表的表示和实现(C语言)

news/2024/10/24 11:16:02/

1.前言

        这篇文章主要介绍双向链表的表示和实现。

2.双向链表

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

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

5.返回链表中第一个与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;
}

6.表长

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

7.前驱节点

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

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

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

9.删除

       和单链表算法相同。

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

10.后继节点

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; // 将后继节点的数据赋值给nextElementreturn 1; // 找到后继节点，返回1}p = p->next; // 移动到下一个节点}return 0; // 没有找到指定元素
}

11.遍历节点

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

12.完整代码

#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; // 将后继节点的数据赋值给nextElementreturn 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 listfor (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.ppmy.cn/news/1461072.html

相关文章

Redis如何避免数据丢失？——RDB

Redis如何避免数据丢失？——RDB

目录 1. RDB机制的配置 2. fork()函数和写时复制(Copy On Write&#xff09; 什么是Copy On Write 系统fork中使用Copy On Write机制 3. RDB文件结构 RDB文件内容和内容顺序 InfoAuxFields是rdb信息数据 数据库数据 数据 数据存储格式 字符串编码 操作码 4. RDB的2…
阅读更多...
vue 中的 Vuex

vue 中的 Vuex

Vuex Vuex是什么&#xff1f; 概念&#xff1a;专门在vue中实现集中式状态&#xff08;数据&#xff09;管理的一个Vue插件&#xff0c;对Vue应用中多个组件的共享状态进行集中式的管理(读/写&#xff09;&#xff0c;也是一种组件间通信的方式&#xff0c;且适用于任意组件间…
阅读更多...
Spring boot环境的常见问题

Spring boot环境的常见问题

文章目录 一、启动类无法运行二、包相关问题2.1 默认配置的包无法下载2.2 第三方库的包无法下载2.3 包找不到 三、出现了一个无效的源发行版17四、类文件具有错误的版本 61.0&#xff0c;应为52.0五、控制台乱码 一、启动类无法运行 原因&#xff1a;IDEA 没有把当前项目识别成…
阅读更多...
基于 Spring Boot 博客系统开发（七）

基于 Spring Boot 博客系统开发（七）

基于 Spring Boot 博客系统开发&#xff08;七&#xff09; 本系统是简易的个人博客系统开发&#xff0c;为了更加熟练地掌握 SprIng Boot 框架及相关技术的使用。&#x1f33f;&#x1f33f;&#x1f33f; 基于 Spring Boot 博客系统开发&#xff08;六&#xff09;&#x1f…
阅读更多...
【云原生】Kubeadm搭建K8S

【云原生】Kubeadm搭建K8S

一、部署Kubernetes 实验环境 服务器主机名IP地址主要组件k8s集群master01 etcd01master01192.168.10.100kube-apiserver kube-controller-manager kube-schedular etcdk8s集群node01 etcd02node01192.168.10.101kubelet kube-proxy docker flannelk8s集群node02 etcd03nod…
阅读更多...
容器组件：角标组件，纵向拖动组件（HarmonyOS学习第四课【4.2】）

容器组件：角标组件，纵向拖动组件（HarmonyOS学习第四课【4.2】）

Badge&#xff08;角标组件&#xff09; 可以附加在单个组件上用于信息标记的容器组件。 说明 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 支持单个子组件。 说明 子组件类型&#xff1a;系统组件…
阅读更多...
物理层——计算机网络学习笔记二

物理层——计算机网络学习笔记二

目录 物理层的基本概念 数据通信的基础知识 物理层下面的传输媒体 信道复用技术 图片大部分来源于谢希仁《计算机网络》教材配套的ppt。 这一样都是介绍一下概念性的东西&#xff0c;了解一下就行&#xff0c;就重要性而言不如后面的内容。 物理层的作用&#xff1a;考虑如何才…
阅读更多...
国产化开源鸿蒙系统智能终端RK3568主板在电子班牌项目的应用

国产化开源鸿蒙系统智能终端RK3568主板在电子班牌项目的应用

国产化开源鸿蒙系统智能终端主板AIoT-3568A、人脸识别算法的的电子班牌方案可支持校园信息发布、人脸识别考勤、考场管理、查询互动等多项功能&#xff0c;助力学校在硬件上实现信息化、网络化、数字化&#xff0c;构建“学校、教师、学生”三个维度的智慧教育空间。 方案优势 …
阅读更多...
最新文章

Copyright @ 2022~2023