双链表和循环链表的各种基本运算的算法（数据结构作业03）

双链表

        目的：双链表的存储结构和掌握双链表中各种基本运算算法的设计

        内容：编写一个程序dlinkst.cpp,实现双链表的各种基本运算和整体建表算法，双链表的元素类型Elem Type为int并在此基础上设计一个程序。

(1)初始化双链表h。

(2)依次采用尾插法插人a、b、c、d、e元素。

(3)输出双链表h。

(4)输出双链表h的长度。

(5)判断双链表h是否为空。

(6)输出双链表h的第3个元素。

(7)输出元素a的位置。

(8)在第4个元素的位置上插入f元素。

(9)输出双链表h。

(10)删除双链表h的第3个元素。

(11)输出双链表h。

(12)释放双链表h。

#include <stdio.h>
#include <stdlib.h>// 定义双链表节点结构
typedef struct DListNode {int data;struct DListNode *prev, *next;
} DListNode;// 定义双链表结构
typedef struct DLinkList {DListNode *head;
} DLinkList;// 初始化双链表
void InitList(DLinkList *L) {L->head = NULL;
}// 创建新节点
DListNode *CreateNode(int value) {DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));if (newNode == NULL) {printf("Memory allocation failed.\n");exit(-1);}newNode->data = value;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 插入尾部元素
void InsertTail(DLinkList *L, int value) {DListNode *newNode = CreateNode(value);//先创建这个结点if (L->head == NULL) {L->head = newNode;//头结点若为空，说明目前没元素，所以只需把新结点放在//头结点后面即可} else {DListNode *curr = L->head;while (curr->next != NULL) {curr = curr->next;}curr->next = newNode;newNode->prev = curr;//若头结点不为空，先创建一个指针从头结点开始一直遍历到尾结点//再将新结点放在尾结点后，新结点的prior设置为尾结点}
}// 输出双链表
void PrintList(DLinkList *L) {DListNode *curr = L->head;while (curr != NULL) {printf("%c ", curr->data);curr = curr->next;}printf("\n");//从头结点的后一个节点开始遍历链表
}// 获取双链表长度
int Length(DLinkList *L) {int count = 0;DListNode *curr = L->head;while (curr != NULL) {count++;curr = curr->next;}return count;//同样遍历链表即可
}// 判断双链表是否为空
int IsEmpty(DLinkList *L) {return L->head == NULL;//头结点后面没结点说明链表为空
}// 获取指定位置的元素
int GetElement(DLinkList *L, int pos) {if (pos < 0 || pos >= Length(L)) return -1;//位置不合法DListNode *curr = L->head;for (int i = 0; i < pos; ++i) {curr = curr->next;}//for循环找到对应位置return curr->data;
}// 查找元素的位置
int FindElement(DLinkList *L, int value) {DListNode *curr = L->head;int pos = 0;while (curr != NULL) {if (curr->data == value) return pos;curr = curr->next;pos++;}//同样是循环，不断匹配value，匹配成功就返回位置posreturn -1;
}// 在指定位置插入元素
void InsertAt(DLinkList *L, int pos, int value) {if (pos < 0 || pos > Length(L)) return;//位置不合法DListNode *newNode = CreateNode(value);//创建这个元素的结点if (pos == 0) {newNode->next = L->head;if (L->head != NULL) L->head->prev = newNode;L->head = newNode;//插入结点} else {DListNode *curr = L->head;for (int i = 0; i < pos - 1; ++i) {curr = curr->next;}newNode->next = curr->next;newNode->prev = curr;if (curr->next != NULL) curr->next->prev = newNode;//若插入的这个节点的位置不是尾结点curr->next = newNode;//位置是尾结点的情况}
}// 删除指定位置的元素
void DeleteAt(DLinkList *L, int pos) {if (pos < 0 || pos >= Length(L)) return;//位置不合法DListNode *curr = L->head;if (pos == 0) {L->head = L->head->next;if (L->head != NULL) L->head->prev = NULL;//若头结点后面有结点，就让头结点指向空} else {for (int i = 0; i < pos; ++i) {curr = curr->next;}curr->prev->next = curr->next;if (curr->next != NULL) curr->next->prev = curr->prev;//删除结点}free(curr);
}// 清空链表
void ClearList(DLinkList *L) {while (L->head != NULL) {DListNode *temp = L->head;L->head = L->head->next;free(temp);}
}int main() {DLinkList h;InitList(&h);// (2) 依次采用尾插法插入a、b、c、d、e元素。InsertTail(&h, 'a');InsertTail(&h, 'b');InsertTail(&h, 'c');InsertTail(&h, 'd');InsertTail(&h, 'e');// (3) 输出双链表h。printf("(3) 输出双链表h:");PrintList(&h);// (4) 输出双链表h的长度。printf("(4) 输出双链表h的长度: %d\n", Length(&h));// (5) 判断双链表h是否为空。printf("(5)判断双链表h是否为空: %s\n", IsEmpty(&h) ? "Yes" : "No");// (6) 输出双链表h的第3个元素。printf("(6) 输出双链表h的第3个元素: %c\n", GetElement(&h, 2));// (7) 输出元素a的位置。printf("(7) 输出元素a的位置: %d\n", FindElement(&h, 'a'));// (8) 在第4个元素的位置上插入f元素。InsertAt(&h, 3, 'f');printf("(8) 在第4个元素的位置上插入f元素:");PrintList(&h);// (9) 输出双链表h。printf("(9) 输出双链表h:");PrintList(&h);// (10) 删除双链表h的第3个元素。DeleteAt(&h, 2);printf("(10) 删除双链表h的第3个元素:");PrintList(&h);// (11) 输出双链表h。printf("(11) 输出双链表h:");PrintList(&h);// (12) 释放双链表h。ClearList(&h);return 0;
}

循环链表

         实验题：实现循环双链表的各种基本运算的算法目的：领会循环双链表的存储结构和掌握循环双链表中各种基本运算算法的设计。

        内容：编写一个程序cdlinklist..cpp,实现循环双链表的各种基本运算和整体建表算法(假设循环双链表的元素类型ElemType为int),完成以下功能。

(1)初始化循环双链表h。

(2)依次采用尾插法插入a、b、c、d、e元素。

(3)输出循环双链表h。

(4)输出循环双链表h的长度。

(5)判断循环双链表h是否为空。

(6)输出循环双链表h的第3个元素。

(7)输出元素a的位置。

(8)在第4个元素的位置上插入f元素。

(9)输出循环双链表h。

(10)删除循环双链表h的第3个元素。

(11)输出循环双链表h。

(12)释放循环双链表h。

 

#include <stdio.h>
#include <stdlib.h>// 定义循环双链表节点结构
typedef struct CDListNode {int data;struct CDListNode *prior, *next;
} CDListNode;// 定义循环双链表结构
typedef struct CDLinkList {CDListNode *head;//头结点
} CDLinkList;// 初始化循环双链表
void InitList(CDLinkList *L) {L -> head = NULL;//初始化头结点为空
}// 创建新节点
CDListNode *CreateNode(int value) {CDListNode *newNode = (CDListNode *)malloc(sizeof(CDListNode));newNode -> data = value;newNode -> prior = newNode -> next = NULL;//将新结点的prior和next初始化为空return newNode;
}// 插入尾部元素
void InsertTail(CDLinkList *L, int value) {CDListNode *newNode = CreateNode(value);if (L -> head == NULL) {L -> head = newNode;newNode -> prior = newNode -> next = newNode; // 形成循环，让尾结点的next指向头结点} else {CDListNode *tail = L -> head -> prior;//创建tail指针指向尾结点tail -> next = newNode;newNode -> prior = tail;//将新结点放在尾结点后面newNode -> next = L -> head;L -> head -> prior = newNode;//让新结点的next指向头结点，头结点的next指向新结点//形成循环}
}// 输出循环双链表
void PrintList(CDLinkList *L) {if (L -> head == NULL) {printf("循环链表为空\n");return;}//头结点为空代表循环链表为空CDListNode *curr = L -> head;do {printf("%c ", curr->data);curr = curr -> next;} while (curr != L->head);//do while循环遍历循环链表printf("\n");
}// 获取循环双链表长度
int Length(CDLinkList *L) {int count = 0;CDListNode *curr = L->head;if (curr == NULL) return 0;do {count++;curr = curr->next;} while (curr != L->head);//同样循环遍历，每次让count++，得到链表长度return count;
}// 判断循环双链表是否为空
int IsEmpty(CDLinkList *L) {return L->head == NULL;//若头结点为空则链表为空
}// 获取指定位置的元素
int GetElement(CDLinkList *L, int pos) {if (pos < 0 || pos >= Length(L)) return -1;//长度不合法直接返回CDListNode *curr = L -> head;int index = 0;do {if (index == pos) return curr -> data;//只要循环到指定位置就返回对应值，否则继续循环curr = curr -> next;index++;} while (curr != L->head);return -1;
}// 查找元素的位置
int FindElement(CDLinkList *L, int value) {CDListNode *curr = L -> head;int pos = 0;if (curr == NULL) return -1;//链表为空，无需查找，直接返回do {if (curr -> data == value) return pos;//循环不断匹配数值，相同则返回它的位置curr = curr -> next;pos++;} while (curr != L -> head);return -1;
}// 在指定位置插入元素
void InsertAt(CDLinkList *L, int pos, int value) {if (pos < 0 || pos > Length(L)) return;//位置不合法直接返回CDListNode *newNode = CreateNode(value);//创建要插入的那个结点if (pos == 0) {//pos为0表示要插入在头结点后面newNode -> next = L -> head;newNode -> prior = L -> head -> prior;//将新结点插入到头结点后L -> head -> prior -> next = newNode;L -> head -> prior = newNode;L -> head = newNode;//形成循环} else {CDListNode *curr = L -> head;int index = 0;do {if (index == pos - 1) break;curr = curr -> next;index++;} while (curr != L -> head);//找到要插入结点的位置newNode -> next = curr -> next;newNode -> prior = curr;curr -> next -> prior = newNode;curr -> next = newNode;//插入结点}
}// 删除指定位置的元素
void DeleteAt(CDLinkList *L, int pos) {if (pos < 0 || pos >= Length(L)) return;//位置不合法直接返回CDListNode *curr = L -> head;int index = 0;if (pos == 0) {L -> head -> prior -> next = L -> head -> next;L -> head -> next -> prior = L -> head -> prior;L -> head = L -> head ->next;free(curr);//删除第一个结点的情况} else {do {if (index == pos) break;curr = curr -> next;index++;} while (curr != L->head);//找到要删除的结点的位置curr -> prior -> next = curr -> next;curr -> next -> prior = curr -> prior;free(curr);//删除结点}
}// 清空链表
void ClearList(CDLinkList *L) {while (L -> head != NULL) {CDListNode *temp = L -> head;L -> head = L -> head -> next;free(temp);}L -> head = NULL;//释放头结点，并且将头结点的指针设置为空实现清空链表
}int main() {CDLinkList h;//初始化循环双链表InitList(&h);// (2) 依次采用尾插法插入a、b、c、d、e元素。InsertTail(&h, 'a');InsertTail(&h, 'b');InsertTail(&h, 'c');InsertTail(&h, 'd');InsertTail(&h, 'e');// (3) 输出循环双链表h。printf("(3) 输出循环双链表h:");PrintList(&h);// (4) 输出循环双链表h的长度。printf("(4) 输出循环双链表h的长度: %d\n", Length(&h));// (5) 判断循环双链表h是否为空。printf("(5) 判断循环双链表h是否为空: %s\n", IsEmpty(&h) ? "Yes" : "No");// (6) 输出循环双链表h的第3个元素。printf("(6) 输出循环双链表h的第3个元素: %c\n", GetElement(&h, 2));// (7) 输出元素a的位置。printf("(7) 输出元素a的位置: %d\n", FindElement(&h, 'a'));// (8) 在第4个元素的位置上插入f元素。InsertAt(&h, 3, 'f');// (9) 输出循环双链表h。printf("(9) 输出循环双链表h:");PrintList(&h);// (10) 删除循环双链表h的第3个元素。DeleteAt(&h, 2);// (11) 输出循环双链表h。printf("(11) 输出循环双链表h:");PrintList(&h);// (12) 释放循环双链表h。ClearList(&h);return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

电动车无钥匙一键启动‌系统应用

电动车无钥匙一键启动‌系统应用

电动车无钥匙一键启动‌是一种便捷的启动方式&#xff0c;它允许车主在不使用传统钥匙的情况下启动车辆。这种启动方式通常依赖于无线射频识别&#xff08;RFID&#xff09;技术&#xff0c;通过车主随身携带的智能卡里的芯片感应自动开关门锁。当车主走近车辆时&#xff0c;门…
阅读更多...
日志系统扩展一：日志落地数据库：MySQL、SQLite3

日志系统扩展一：日志落地数据库：MySQL、SQLite3

日志系统扩展一&#xff1a;日志落地数据库&#xff1a;MySQL、SQLite3 一、设计1.怎么落地2.落地的具体设计3.表的设计1.MySQL2.SQLite3 二、数据库访问Helper的实现1.需要事务&#xff0c;但是无需回滚&#xff0c;如何理解&#xff1f;1.需要事务2.无需回滚 2.SqliteHelper1…
阅读更多...
ICM20948 DMP代码详解（40）

ICM20948 DMP代码详解（40）

接前一篇文章&#xff1a;ICM20948 DMP代码详解&#xff08;39&#xff09; 上一回继续解析inv_icm20948_set_slave_compass_id函数&#xff0c;解析到第5段代码inv_icm20948_setup_compass_akm函数&#xff0c;本回解析接下来的代码。为了便于理解和回顾&#xff0c;再次贴出该…
阅读更多...
77、Python之函数式编程：一文搞懂functools模块的核心应用

77、Python之函数式编程：一文搞懂functools模块的核心应用

引言 Python作为一种支持多范式的编程语言&#xff0c;除了在“一切皆对象”的理念支持下的&#xff0c;函数对象也是一等公民、各种高阶函数的自然实现、lambda表达式快速编写纯函数之外。还有一个内置的模块functools&#xff0c;能够更好地支持我们在Python中应用函数式编程…
阅读更多...
企业职工薪资查询系统小程序的设计

企业职工薪资查询系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;员工管理&#xff0c;部门管理&#xff0c;工资信息管理&#xff0c;工资安排管理&#xff0c;考勤信息管理&#xff0c;交流论坛&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#…
阅读更多...
LTE协议栈学习

LTE协议栈学习

1、高通Modem架构 LTE网络架构 3、LTE协议栈 1、 NAS协议栈: EPS Mobility Management (EMM) 支持UE中的移动功能 EPS Session Management (ESM) 支持在UE和PDN网关之间建立和维护IP连接 高通平台NAS层结构 根据3GPP TS 23.122描述&#xff0c; 自动搜网顺序如下 HPLMN EH…
阅读更多...
数据结构之线性表——LeetCode：67. 二进制求和，27. 移除元素，26. 删除有序数组中的重复项

数据结构之线性表——LeetCode：67. 二进制求和，27. 移除元素，26. 删除有序数组中的重复项

67. 二进制求和 题目描述 67. 二进制求和 给你两个二进制字符串 a 和 b &#xff0c;以二进制字符串的形式返回它们的和。 运行代码&#xff08;javaC) class Solution {public String addBinary(String a, String b) {StringBuilder ansnew StringBuilder();int ca0;for(i…
阅读更多...
四川财谷通信息技术有限公司与抖音小店的深度合作

四川财谷通信息技术有限公司与抖音小店的深度合作

在数字经济蓬勃发展的今天&#xff0c;电商平台已成为推动社会经济增长的重要引擎。其中&#xff0c;抖音小店作为短视频与电商深度融合的产物&#xff0c;凭借其庞大的用户基础、精准的流量分发机制以及创新的购物体验&#xff0c;迅速崛起为电商领域的一股不可忽视的力量。而…
阅读更多...
CSS的表格属性

CSS的表格属性

border属性 规定CSS表格边框。 table,td{border: 1px solid green;/*1px表示设置边框的大小&#xff0c;solid表示边框为实线&#xff0c;green表示边框的颜*/} border-collpapse属性 设置表格的边框是否被折叠成一个单一的边框或隔开。 table{border-collapse: collapse;} wi…
阅读更多...
[spring]springboot日志

[spring]springboot日志

文章目录 一. 日志的用途二. 打印日志三. 日志框架门面模式(外观模式)SLF4J框架介绍 四. 日志格式日志级别配置日志级别日志持久化配置日志文件分割配置日志格式 五. 更简单的日志输出 一. 日志的用途 二. 打印日志 得到日志对象: 需要使用日志工厂LoggerFactory RestControl…
阅读更多...
【避雷指南】自学AI人工智能常踩的4个大雷区

【避雷指南】自学AI人工智能常踩的4个大雷区

1、数学基础 学习人工智能时&#xff0c;有一种常见的误解&#xff0c;认为一定要数学学的很好&#xff0c;才能进一步学人工智能。这种观念并不正确。虽然数学是AI的基石&#xff0c;为算法和模型提供了理论基础&#xff0c;但过分沉迷于数学理论可能会让学习过程变得枯燥无味…
阅读更多...
【第十二章：Sentosa_DSML社区版-机器学习之回归】

【第十二章：Sentosa_DSML社区版-机器学习之回归】

目录 12.1 线性回归 12.2 决策树回归 12.3 梯度提升决策树回归 12.4 保序回归 12.5 XGBoost回归 12.6 随机森林回归 12.7 广义线性回归 12.8 LightGBM回归 12.9 因子分解机回归 12.10 AdaBoost回归 12.11 KNN回归 12.12 高斯过程回归 12.13 多层感知机回归 【第十…
阅读更多...
UML类图绘制

UML类图绘制

目录 前言 一、如何在UML中表示一个类 二、类之间关系的表示 1.继承关系 2.关联关系 ①单向关联 ②双向关联关系 ③自关联关系 3.聚合关系 4.组合关系 5.实现关系 6.依赖关系 前言 在学习面向对象语言时&#xff0c;我们可以使用UML类图来描述将要编写的程序中类与…
阅读更多...
NASA：A-Train 云分级数据集(用于深度学习模型)

NASA：A-Train 云分级数据集(用于深度学习模型)

目录 简介 摘要 代码 引用 网址推荐 0代码在线构建地图应用 机器学习 A-Train 云分级数据集 简介 ATCS 是一个数据集&#xff0c;旨在训练深度学习模型&#xff0c;以便对多角度卫星图像中的云进行体积分割。 该数据集包括来自 PARASOL 任务上 POLDER 传感器的多角度偏…
阅读更多...
docker如何升级MySQL为最新版本

docker如何升级MySQL为最新版本

今天安全扫描发现MySQL存在漏洞&#xff0c;不用想别的升级到最新版。本篇文章有两个目的&#xff0c;1&#xff09;为自己做一个记录&#xff0c;下次升级的时候不用再浪费时间查资料&#xff1b;2&#xff09;给大家一点帮助&#xff1b; 因为我是docker部署&#xff0c;所以…
阅读更多...
在Windows系统上安装的 flatbuffers C++ 库

在Windows系统上安装的 flatbuffers C++ 库

步骤一 下载:https://github.com/google/flatbuffers git clone gitgithub.com:google/flatbuffers.git步骤二 打开安装目录,然后再打开该目录下的powershell, 新建build目录 cd build cmake ..步骤三 进入步骤二生成的build目录里面,点击FlatBuffers.sln,打开vs2019 补充…
阅读更多...
【巅峰算力，静谧之作】4卡4090GPU深度学习“静音”服务器

【巅峰算力，静谧之作】4卡4090GPU深度学习“静音”服务器

各位同仁&#xff0c;随着人工智能浪潮的汹涌澎湃&#xff0c;我们正步入一个前所未有的创新纪元。在这个充满挑战与机遇的时代&#xff0c;我愈发频繁地在工作场景中邂逅那些致力于深度学习探索的智者们。他们&#xff0c;对计算力的渴望如同对知识的追求一般&#xff0c;永无…
阅读更多...
阿里巴巴首页pc端1688店铺招牌店铺装修教程

阿里巴巴首页pc端1688店铺招牌店铺装修教程

1688运营1688批发首页1688装修模板1688店铺怎么装修模板自定义装修代码1688店铺装修模板旺铺装修阿里店铺首页怎么装修1688店铺装修教程视频全屏通栏代码1688店铺装修模板阿里巴巴店铺装修设计 阿里巴巴首页pc端1688店铺招牌店铺装修教程 工具&#xff1a;一秒美工
阅读更多...
海外仓与前置仓有什么不同，如何选择合适的WMS系统？

海外仓与前置仓有什么不同，如何选择合适的WMS系统？

在跨境电商和国际贸易的广阔舞台上&#xff0c;海外仓与前置仓作为两种重要的物流模式&#xff0c;各自以其独特的运营方式和目标&#xff0c;为卖家和消费者提供了高效、便捷的物流服务。 1.海外仓&#xff1a;海外仓是在国外设立的存储仓库&#xff0c;主要用于存放货物并服…
阅读更多...
【WRF工具】WRF Domain Wizard第二期：服务器中下载及安装

【WRF工具】WRF Domain Wizard第二期：服务器中下载及安装

【WRF工具】WRF Domain Wizard第二期&#xff1a;服务器下载及安装 准备WRF Domain Wizard下载及安装WRF Domain Wizard下载WRF Domain Wizard安装添加环境变量&#xff08;为当前用户永久添加环境变量&#xff09;Java环境安装报错-Exception in thread "main" java…
阅读更多...
最新文章

Copyright @ 2022~2023