C++11 数据结构3 线性表的循环链式存储,实现,测试
上一节课,我们学了线性表 单向存储结构(也就是单链表),这个是企业常用的技术,且是后面各种的基本,一定要牢牢掌握,如果没有掌握,下面的课程会云里雾里。
一 ,循环链表
1、什么是循环链表
— 概念上:
1、任何数据元素都有一个前驱和一个后继
2、所有的数据元素的关系构成一个逻辑的环
— 实现上:
1、循环链表是一种特殊的单链表
2、尾结点的指针域保存了首结点的地址
2、循环链表的逻辑构成
二 循环链表的插入示意图
头插法第一次插入
头插法非第一次插入
删除非第一个元素
删除第一个元素
三 代码实现
.h实现
#ifndef _003CIRCLELIST_H_
#define _003CIRCLELIST_H_typedef void CircleList; //要返回给上层的list 的首地址为 void *,为了阅读起名为CircleListtypedef struct _tag_CircleListNode //list 中的节点
{struct _tag_CircleListNode* next;
}CircleListNode;//创建循环链表
CircleList* CircleList_Create();//销毁循环链表
void CircleList_Destroy(CircleList* list);//清空循环列表
void CircleList_Clear(CircleList* list);//循环列表中目前存在的元素个数
int CircleList_Length(CircleList* list);//给循环列表中插入元素,node为要插入的元素的值,pos为位置
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);//从循环列表中的pos 位置获得具体的值
CircleListNode* CircleList_Get(CircleList* list, int pos);//从循环列表中删除pos位置的数据
CircleListNode* CircleList_Delete(CircleList* list, int pos);//从循环列表中删除 数据 为node 的点
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);CircleListNode* CircleList_Reset(CircleList* list);CircleListNode* CircleList_Current(CircleList* list);CircleListNode* CircleList_Next(CircleList* list);#endif
底层实现
#include "003CircleList.h"
#include "stdio.h"
#include "stdlib.h"
#include <string.h>typedef struct _tag_CircleList{CircleListNode header;CircleListNode* slider; //多了一个游标int length;
} TCircleList;CircleList* CircleList_Create(){TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList));if (ret == NULL) {printf("CircleList_Create func malloc error\n");return ret;}memset(ret,0,sizeof(TCircleList));ret->length = 0;ret->header.next = NULL;ret->slider = NULL;return ret;
}void CircleList_Destroy(CircleList* list) // O(1)
{free(list);
}void CircleList_Clear(CircleList* list){TCircleList* sList = (TCircleList*)list;if (sList != NULL){sList->length = 0;sList->header.next = NULL;sList->slider = NULL;}
}int CircleList_Length(CircleList* list){TCircleList* sList = (TCircleList*)list;int ret = -1;if (sList != NULL){ret = sList->length;}return ret;
}int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) // O(n)
{TCircleList* sList = (TCircleList*)list;int ret = (sList != NULL) && (pos >= 0) && (node != NULL);int i = 0;if (ret){CircleListNode* current = (CircleListNode*)sList;//current指向头部for (i = 0; (i < pos) && (current->next != NULL); i++){current = current->next;}//假设我们要插入的是pos =3,头结点不算,下来从0,1,2,3,4,5,6开始计算//循环完成后,current刚好是在 pos=2的位置,//要变成的是 2 node 3 ,也就是说node->next要是3node->next = current->next;//current的->next,现在也是2,指向新的节点nodecurrent->next = node;if (sList->length == 0){//如果是第一次插入将slider的指向nodesList->slider = node;}sList->length++;//如果是头插法,还需要做事情,让最后一个元素链接到这个新节点,if (current == (CircleListNode*)sList) {CircleListNode * last = CircleList_Get(list,sList->length-1);last->next = node;}//此处要理解,需结合图来看,后续会将 头插法,尾插法,中间插入法的三种图示画一下,方便理解}return ret;
}CircleListNode* CircleList_Get(CircleList* list, int pos) // O(n)
{TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;int i = 0;if ((sList != NULL) && (pos >= 0)){CircleListNode* current = (CircleListNode*)sList;for (i = 0; i < pos; i++){current = current->next;}ret = current->next;}return ret;
}CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n)
{TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;int i = 0;if ((sList != NULL) && (pos >= 0)){CircleListNode* current = (CircleListNode*)sList;CircleListNode* first = sList->header.next;CircleListNode* last = (CircleListNode*)CircleList_Get(sList, sList->length - 1);for (i = 0; i < pos; i++){current = current->next;}ret = current->next;current->next = ret->next;sList->length--;//如果删除的第一个结点。要额外处理if (first == ret){//让头结点的next要重新指向,指向的内容是保存在 被删除的节点的next中的。sList->header.next = ret->next;//让最后一个节点的next也要重新指向,指向的内容是保存在 被删除的节点的next中的。last->next = ret->next;}//如果删除的元素刚好是 游标指向的元素,则将游标往下移动if (sList->slider == ret){sList->slider = ret->next;}//如果list只有一个元素,删除后,就没有元素了,那么就需要将if (sList->length == 0){sList->header.next = NULL;sList->slider = NULL;}}return ret;
}CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) // O(n)
{TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;int i = 0;if (sList != NULL){CircleListNode* current = (CircleListNode*)sList;for (i = 0; i < sList->length; i++){if (current->next == node){ret = current->next;break;}current = current->next;}if (ret != NULL){CircleList_Delete(sList, i);}}return ret;
}CircleListNode* CircleList_Reset(CircleList* list) // O(1)
{TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;if (sList != NULL){sList->slider = sList->header.next;ret = sList->slider;}return ret;
}CircleListNode* CircleList_Current(CircleList* list) // O(1)
{TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;if (sList != NULL){ret = sList->slider;}return ret;
}CircleListNode* CircleList_Next(CircleList* list) // O(1)
{TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;if ((sList != NULL) && (sList->slider != NULL)){ret = sList->slider;sList->slider = ret->next;}return ret;
}
测试代码
#include "iostream"
#include <stdio.h>
#include <stdlib.h>extern "C" {
#include "003CircleList.h"
}using namespace std;struct Value
{CircleListNode header;int v;
};int main(int argc, char *argv[]){int i = 0;CircleList* list = CircleList_Create();struct Value v1;struct Value v2;struct Value v3;struct Value v4;struct Value v5;struct Value v6;struct Value v7;struct Value v8;v1.v = 1;v2.v = 2;v3.v = 3;v4.v = 4;v5.v = 5;v6.v = 6;v7.v = 7;v8.v = 8;CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));for (i = 0; i < CircleList_Length(list); i++){struct Value* pv = (struct Value*)CircleList_Get(list, i);printf("%d\n", pv->v);}//注意这里,这时候list除了头结点外,只有4个元素,1,2,3,4,对应0,1,2,3//代码中插入的pos =5,相当于在1和2中间插入一个5.CircleList_Insert(list, (CircleListNode*)&v5, 5);//因此如下的循环后,打印出来的是 1,5,2,3,4for (i = 0; i < CircleList_Length(list); i++){struct Value* pv = (struct Value*)CircleList_Get(list, i);printf("%d\n", pv->v);}CircleList_Delete(list, 0);//删除第一个元素,将1删除了//再次打印是 5 2 3 4 5 2 3 4for (i = 0; i < 2 * CircleList_Length(list); i++){struct Value* pv = (struct Value*)CircleList_Get(list, i);printf("%d\n", pv->v);}printf("\n");while (CircleList_Length(list) > 0){struct Value* pv = (struct Value*)CircleList_Delete(list, 0);printf("%d\n", pv->v);}printf("aaaaaa\n");CircleList_Insert(list, (CircleListNode*)&v1, 0);CircleList_Insert(list, (CircleListNode*)&v2, 0);CircleList_Insert(list, (CircleListNode*)&v3, 0);CircleList_Insert(list, (CircleListNode*)&v4, 0);CircleList_Insert(list, (CircleListNode*)&v5, 0);CircleList_Insert(list, (CircleListNode*)&v6, 0);CircleList_Insert(list, (CircleListNode*)&v7, 0);CircleList_Insert(list, (CircleListNode*)&v8, 0);//注意,这里是用的头插法,因此是8,7,6,5,4,3,2,1,但是第一个插入的是1,因此游标指向1,又因为是循环的,因此下一个是8,结果是1,8,7,6,5,4,3,2for (i = 0; i < CircleList_Length(list); i++){struct Value* pv = (struct Value*)CircleList_Next(list);printf("%d\n", pv->v);}printf("bbbbbbbbbb\n");//游标reset 是指向的第一个元素CircleList_Reset(list);//1,2,3 将3剔除队列的游戏,游标reset后,指向的是8,因此123,将3剔除队列的有些结果为 6,3,8,4,7,1,5,2while (CircleList_Length(list) > 0){struct Value* pv = NULL;for (i = 1; i < 3; i++){CircleList_Next(list);}printf("ccc\n");//游标reset之后,指向数字8,往后移动了2次,就是指向6pv = (struct Value*)CircleList_Current(list);printf("%d\n", pv->v);CircleList_DeleteNode(list, (CircleListNode*)pv);}CircleList_Destroy(list);return 0;}
相关文章:
C++11 数据结构3 线性表的循环链式存储,实现,测试
上一节课,我们学了线性表 单向存储结构(也就是单链表),这个是企业常用的技术,且是后面各种的基本,一定要牢牢掌握,如果没有掌握,下面的课程会云里雾里。 一 ,循环链表 1…...
初识DOM
目录 前言: 1.初识DOM: 1.1DOM树: 1.2节点(Node): 1.2.1元素节点: 1.2.2属性节点: 1.2.3文本节点: 1.3Document对象: 2.操作网页元素: 2.1找出元素: 2.1.1document.getElementById(id)࿱…...
计算机视觉实验五——图像分割
计算机视觉实验五——图像分割 一、实验目标二、实验内容1.了解图割操作,实现用户交互式分割,通过在一幅图像上为前景和背景提供一些标记或利用边界框选择一个包含前景的区域,实现分割①图片准备②代码③运行结果④代码说明 2.采用聚类法实现…...
移动Web学习06-移动端适配Less预处理器项目案例
项目目标:实现在不同宽度设备中等比缩放的网页效果 Less代码 import ./base; import ./normalize;// 变量: 存储37.5 rootSize: 37.5rem; *{margin: 0;padding: 0; } body {background-color: #F0F0F0; }// 主体内容 .main {// padding-bottom: (50 / 37.5rem);pa…...
LangChain-25 ReAct 让大模型自己思考和决策下一步 AutoGPT实现途径、AGI重要里程碑
背景介绍 大模型ReAct(Reasoning and Acting)是一种新兴的技术框架,旨在通过逻辑推理和行动序列的构建,使大型语言模型(LLM)能够达成特定的目标。这一框架的核心思想是赋予机器模型类似人类的推理和行动能…...
24/04/15总结
多线程: 线程 线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位 并发:在同一时刻,有多个指令在单个cpu上交替执行 并行:在同一时刻,有多个指令在多个cpu上同时执行 多线程的实现方式 1.继承…...
vue3、vue2中nextTick源码解析
nexttick是啥 nextTick是Vue提供的一个全局API,由于Vue的异步更新策略导致我们对数据的修改不会更新,如果此时想要获取更新后的Dom,就需要使用这个方法. vue的异步更新策略意思是如果数据变化,vue不会立刻更新dom,而是开启一个队列,把组件更…...
【氮化镓】GaN HEMTs结温和热阻测试方法
文章《Temperature rise detection in GaN high-electron-mobility transistors via gate-drain Schottky junction forward-conduction voltages》,由Xiujuan Huang, Chunsheng Guo, Qian Wen, Shiwei Feng, 和 Yamin Zhang撰写,发表在《Microelectroni…...
c++11 标准模板(STL)本地化库 - 平面类别(std::codecvt) - 在字符编码间转换,包括 UTF-8、UTF-16、UTF-32 (四)
本地化库 本地环境设施包含字符分类和字符串校对、数值、货币及日期/时间格式化和分析,以及消息取得的国际化支持。本地环境设置控制流 I/O 、正则表达式库和 C 标准库的其他组件的行为。 平面类别 在字符编码间转换,包括 UTF-8、UTF-16、UTF-32 std::…...
【状态压缩 容斥原理 组合数学】100267. 单面值组合的第 K 小金额
本文涉及知识点 状态压缩 容斥原理 组合数学 二分查找算法合集 LeetCode100267. 单面值组合的第 K 小金额 给你一个整数数组 coins 表示不同面额的硬币,另给你一个整数 k 。 你有无限量的每种面额的硬币。但是,你 不能 组合使用不同面额的硬币。 返回…...
.net框架和c#程序设计第三次测试
目录 一、测试要求 二、实现效果 三、实现代码 一、测试要求 二、实现效果 数据库中的内容: 使用数据库中的账号登录: 若不是数据库中的内容: 三、实现代码 login.aspx文件: <% Page Language"C#" AutoEventW…...
架构师系列-搜索引擎ElasticSearch(五)- 索引设计
索引创建后,要非常谨慎,创建不好后面会出现各种问题。 索引设计的重要性 索引创建后,索引分片只能通过_split和_shrink 接口对其进行成倍的增加和缩减。 ES的数据是通过_routing分配到各个分片上的,所以本质上不推荐区改变索引的…...
kafka ----修改log4j、jmx、jvm参数等
1、修改log4j 日志路径 在kafka-run-class.sh文件中修改如下配置,将 LOG_DIR变量指定为自己想要存储的路径 # Log directory to use if [ "x$LOG_DIR" "x" ]; thenLOG_DIR"$base_dir/logs" fi2、修改jmx参数 在kafka-run-class.s…...
Python 全栈 Web 应用模板:成熟架构,急速开发 | 开源日报 No.223
tiangolo/full-stack-fastapi-template Stars: 15.6k License: MIT full-stack-fastapi-template 是一个现代化的全栈 Web 应用模板。 使用 FastAPI 构建 Python 后端 API。使用 SQLModel 进行 Python SQL 数据库交互(ORM)。Pydantic 用于数据验证和设…...
STM32之DHT11温湿度传感器
目录 一 DHT11温湿度传感器简介 1.1 传感器特点 1.2 传感器特性 1.3 传感器引脚说明 二 测量原理及方法 2.1 典型应用电路 2.2 单线制串行简介 2.2.1 串行接口 (单线双向) 2.2.2 数据示例 2.3 通信时序 三 单片机简介 3.1 STM32F103C8T6最小系统板 四 接线说明 …...
paddle ocr
paddle安装教程,git clone xxxgit https://blog.csdn.net/Castlehe/article/details/117356343 只有paddle 1.x 的教程:https://github.com/PaddlePaddle/PaddleOCR/blob/static/doc/doc_en/quickstart_en.md 报错是因为安装的是paddle 2.x而教程只给了…...
Xcode 15.0 新 #Preview 预览让 SwiftUI 界面调试更加悠然自得
概览 从 Xcode 15 开始,苹果推出了新的 #Preview 宏预览机制,它无论从语法还是灵活性上都远远超过之前的预览方式。#Preview 不但可以实时预览 SwiftUI 视图,而且对 UIKit 的界面预览也是信手拈来。 想学习新 #Preview 预览的一些超实用调试…...
【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境
【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境 安装完VS2019后,打开终端x64 Native Tools Command Prompt for Vs 2019,直接运行conda会出现‘conda’ 不是内部或外部命令,也不是可运行的程序 原因分析&am…...
网络篇09 | 运输层 udp
网络篇09 | 运输层 udp 01 简介UDP 是面向报文的 02 报文协议 01 简介 UDP 只在 IP 的数据报服务之上增加了一些功能:复用和分用、差错检测 UDP 的主要特点:无连接。发送数据之前不需要建立连接。 使用尽最大努力交付。即不保证可靠交付。 面向报文。…...
vim相关指令
vim的各种模式及其转换关系图 vim 默认处于命令模式!!! 模式之间转换的指令 除【命令模式】之外,其它模式要切换到【命令模式】,只需要无脑 ESC 即可!!! [ 命令模式 ] 切换至 [ 插…...
STM32常见调试工具介绍
STM32的常见调试工具主要包括ST-LINK、USB转TTL、USB转485以及USB转CAN。这些工具在嵌入式系统开发、调试以及通信中发挥着重要的作用。 1.ST-LINK: ST-LINK是STMicroelectronics公司专为其STM32系列微控制器开发的调试和编程工具。既能仿真也能将编译好的程序下载…...
简历上写熟悉Linux下常用命令?直接寄
大家写简历技术栈时,都觉得越多越好,其中一条,熟悉Linux下常用命令?其实开发中Linux不是必备考点,除了运维,真正用的多的仅仅cd ls mkdir等,但当面试官问到上面命令时,是不是就傻眼了…...
【设计模式】4、prototype 原型模式
四、prototype 原型模式 https://refactoringguru.cn/design-patterns/prototype 如果希望 复制对象, 可使用 “prototype 模式” 如果 “待复制的对象” 是 interface 而不是 class, 或者如果 class 有 private 变量时. 无法知道 "待复制的对象"的细节, 则需要其…...
ES6 关于Class类的继承 extends(2024-04-10)
1、简介 类Class 可以通过extends关键字实现继承,让子类继承父类的属性和方法。extends 的写法比 ES5 的原型链继承,要清晰和方便很多。 class Foo {constructor(x, y) {this.x x;this.y y;console.log(父类构造函数)}toString() {return ( this.x …...
边缘计算【智能+安全检测】系列教程--使用OpenCV+GStreamer实现真正的硬解码,完全消除马赛克
通过现有博客的GST_URL = "rtspsrc location=rtsp://admin:abcd1234@192.168.1.64:554/h264/ch01/main/av_stream latency=150 ! rtph264depay ! avdec_h264 ! videorate ! videoconvert ! appsink sync=false" GStreamer的解码方式解码,大多情况应该存在上图马赛克…...
Anaconda在Ubuntu下的安装与简单使用
一、参考资料 ubuntu16.04下安装&配置anacondatensorflow新手教程 二、安装Anaconda 下载 Miniconda镜像1 or Miniconda镜像2 # 下载 wget Miniconda3-py39_4.10.3-Linux-x86_64.sh# 安装 bash Miniconda3-py39_4.10.3-Linux-x86_64.sh一路yes 安装过程中的选项 Do you …...
网络编程【InetAddress , TCP 、UDP 、HTTP 案例】
day38上 网络编程 InetAddress 理解:表示主机类 一个域名 对应 多个IP地址 public static void main(String[] args) throws UnknownHostException {//获取本机的IP地址 // InetAddress localHost InetAddress.getLocalHost(); // System.out.println(localHos…...
软考中级工程师网络技术第二节网络体系结构
OSPF将路由器连接的物理网络划分为以下4种类型,以太网属于(25),X.25分组交换网属于(非广播多址网络NBMA)。 A 点对点网络 B 广播多址网络 C 点到多点网络 D 非广播多址网络 试题答案 正确答案: …...
Mac 软件清单
~自留备用~ Macbook用了几年之后, 512G的内置硬盘有些紧张了, 这几天总是提示空间不足, 就重装了下系统, 重装之后竟然不记得有些软件的名字和下载链接, 特此记录 Office 办公套件 直接从微软官网下载Office 安装包https://officecdnmac.microsoft.com/pr/C1297A47-86C4-4C1F…...
【Leetcode每日一题】 分治 - 颜色分类(难度⭐⭐)(57)
1. 题目解析 题目链接:75. 颜色分类 这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。 2.算法原理 算法思路解析 本算法采用三指针法,将数组划分为三个区域,分别用于存放值为0、1和2的元素。通过…...
站酷网官网/新闻发稿
多半的时间,都花在了格式转换上……或者在修转换bug上面。 const char* char* char[] stringQString类型常用: QString::fromStdString(string str); QString::Number(int str); QString::toString(QString str); 实际遇到的稀奇古怪的需要 1.string转…...
zencart 一个产品网站下单/长沙网站se0推广优化公司
269页程序清单10.19 flc.c程序有错误。 如图中所示,方法1处应加上const限定,否则有些编译器会出现从不兼容指针传递参数的警告,方法2没有方法1安全,方法2是去除原型和定义中的const限定。 下面展示第1种修改方法: 像…...
wordpress后台编辑主题时提示:抱歉_该文件无法被编辑/百度指数的功能
好吧主页的又改版了这下终于容易区分大陆与国际版的区别了。2014年12月12日起改版。 主页再次沦落为找不到东西的后果,其实很少进入这个主页,一般也直接使用http://manage.windowsazure.cn/ 直接进入Azure的门户(国际版是https://manage.wind…...
武进网站建设哪家好/小程序引流推广平台
题目: html: body中有2个div 遍历,给每个div添加点击事件,输出值。 js: var声明: 效果: 点击每个div后都打印2。 用户点击前,for循环就已经执行完了,是2,oncl…...
pc端网站建设相关查阅资料/今天国内新闻10条
首先,我们先普及一下编程语言的基础知识。其实无论用任何编程语言来开发程序,都是为了让计算机干活,比如编写一篇文章,下载一首MP3等,而计算机干活的CPU只认识机器的指令,所以,尽管不同的编程语…...
对网站主要功能界面进行赏析/网站推广关键词工具
(1)计算器的定义为:接受用户输入指令不数据,经由中央处理器的数学与逻辑单元运算处理后,以产生或储存成有用的信息;(2)计算机的五大单元包括:输入单元、 输出单元、CPU内…...