Day03_数据结构（手写）

01.数据结构画图

02.

//11.按值查找返回位置                      
int search_value(node_p H,int value)       
{                                          if(H==NULL){                           printf("入参为空.\n");             return -1;                         }                                      if(empty_double(H)){                   return -2;                         }                                      int i;                                 node_p p=H->next;                      for(i=0;p!=NULL;i++,p=p->next)         {                                      if(p->data==value){                return i;                      }                                  }                                      }                                          


//12.按位置修改元素                                 
void update_pos(node_p H,int pos,int new_value)     
{                                                   if(H==NULL){                                    printf("入参为空.\n");                      return;                                     }                                               if(empty_double(H)){                            printf("双项链表为空,没有值可以修改.\n");   return;                                     }                                               if(pos<0){                                      return;                                     }                                               int i;                                          node_p p;                                       for(i=0,p=H->next;i<pos;i++,p=p->next){         p->data=new_value;                          }                                               }

02.自己实现双向循环链表的代码
a.创建
b.创建结点
c.头插
d.尾插
e.按位置插入
f.头删、尾删、按位置删除
g.按位置查找返回值

]main.c

#include "dloop.h"
int main()
{node_p H=(node_p)create_dloop();//1.头插printf("请输出头插的第一个数字双向链表:\n");insert_head(H,4);show(H);printf("请输出头插的第二个数字双向链表:\n");insert_head(H,3);show(H);printf("请输出头插的第三个数字双向链表:\n");insert_head(H,2);show(H);printf("请输出头插的第四个数字双向链表:\n");insert_head(H,1);show(H);//2.尾插printf("请输出尾插的第一个数字双向链表:\n");insert_tail(H,5);show(H);printf("请输出尾插的第二个数字双向链表:\n");insert_tail(H,6);show(H);//3.按位置插入printf("请输出按位置插入双向链表:\n");insert_pos(H,3,77);show(H);//4.头删printf("请输出头删双向链表:\n");dele_head(H);show(H);//5.尾删printf("请输出头删双向链表:\n");dele_tail(H);show(H);//6.按位置删除printf("请输出按位置删除双向链表:\n");delete_pos(H,3);show(H);//7.按位置查找返回值int ret=search_value(H,2);printf("请输出按位查找的返回值%d:\n",ret);show(H);printf("销毁前:\n");printf("%p\n",H);free_loop(&H);printf("销毁后:\n");printf("%p\n",H);}

dloop.c

#include "dloop.h"
//1.创建双链表的空结点
node_p create_dloop()
{node_p H=(node_p)malloc(sizeof(node));if(H==NULL){printf("申请内存失败.\n");return NULL;}H->pri=H;H->next=H;H->len=0;return H;
}
//2.申请结点
node_p create_node(int value)
{node_p new=(node_p)malloc(sizeof(node));new->next=NULL;new->data=value;
}
//3.判空
int empty_dloop(node_p H)
{if(H==NULL){printf("入参为空.\n");return -1;}return H->next==H?1:0;
}
//4.头插
void insert_head(node_p H,int value)
{if(H==NULL){printf("入参为空.\n");return;}node_p new=create_node(value);new->next=H->next;new->pri=H;if(H->next!=NULL){H->next->pri=new;}H->next=new;H->len++;
}
//5.尾插
void insert_tail(node_p H,int value)
{if(H==NULL){printf("入参为空.\n");return;}int i;node_p new=create_node(value);node_p p=H;//1.找到了最后一个结点的位置while(p->next!=H){p=p->next;}new->pri=p;new->next=H;p->next=new;H->pri=new;H->len++;
}
//6.按位置插入
void insert_pos(node_p H,int pos,int value)
{if(H==NULL){printf("入参为空.\n");return;}if(pos<0){printf("插入位置的数据不合理.\n");return;}int i;node_p p;for(i=1,p=H->next;i<pos-1;i++,p=p->next){if(p==H){printf("位置不合理.\n");return;}}if(p==H){printf("位置不合理.\n");return;}node_p new=(node_p)create_node(value);new->next=p->next;new->pri=p;if(p->next!=H){p->next->pri=new;}p->next=new;H->len++;	
}
//7.输出
void show(node_p H)
{if(H==NULL){printf("入参为空.\n");return;}if(empty_dloop(H)){printf("双向循环链表为空,无输出.\n");return;}node_p p=H->next;while(p!=H){printf("%d->",p->data);p=p->next;}printf("NULL\n");
}
//8.头删
void dele_head(node_p H)
{if(H==NULL){printf("入参为空.\n");return;}if(empty_dloop(H)){printf("循环双链表为空,无数据可删除.\n");return;}node_p dele=H->next;//判断是否就一个数据if(dele->next!=H){dele->next->pri=H;}H->next=dele->next;free(dele);H->len--;
}
//9.尾删
void dele_tail(node_p H)
{if(H==NULL){printf("入参为空.\n");return;}node_p p=H;while(p->next!=H){p=p->next;}p->pri->next=H;H->pri=p->pri;free(p);H->len--;
}
//10.按位置删除
void delete_pos(node_p H,int pos)
{if(H==NULL){printf("入参为空.\n");return;}if(empty_dloop(H)){printf("双向链表为空.\n");return;}node_p p;int i;for(i=1,p=H->next;i<pos;i++,p=p->next){if(p==H){printf("位置不合理.\n");return;}}if(p==H){printf("位置不合理.\n");return;}//1.pos+1结点的前驱指向pos-1结点if(p->next!=H){p->next->pri=p->pri;}//2.pos-1结点的后继指向pos+1结点p->pri->next=p->next;free(p);H->len--;
}//11.按位置查找返回值
int search_value(node_p H,int pos)
{if(H==NULL){printf("入参为空.\n");return -1;}if(empty_dloop(H)){printf("双向循环链表为空.\n");return -2;}int i;node_p p;for(i=1,p=H->next;i<pos;i++,p=p->next){if(p==H){printf("位置不合理.\n");return -3;}}if(p==H){printf("位置不合理.\n");return -3;}return p->data;
}
//12.释放链表
void free_loop(node_p *H)
{if(H==NULL||*H==NULL){printf("入参为空.\n");return;}while((*H)->next!=(*H)){dele_head(*H);}free(*H);*H==NULL;
}

dlloop.h

#ifndef __DLOOP_H__
#define __DLOOP_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node
{union{int len;int data;};struct node *pri;struct node *next;
}node,*node_p;node_p create_dloop();
node_p create_node(int value);
int empty_dloop(node_p H);
void insert_head(node_p H,int value);
void insert_tail(node_p H,int value);
void insert_pos(node_p H,int pos,int value);
void show(node_p H);
void dele_head(node_p H);
void dele_tail(node_p H);
void delete_pos(node_p H,int pos);
int search_value(node_p H,int pos);
void free_loop(node_p *H);#endif

03.整理链表和顺序表的优缺点

链表和顺序表是两种常见的数据存储结构，它们各自有不同的优缺点，下面为你详细介绍：

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组来实现。

优点
  1. 随机访问效率高：通过数组下标可以直接访问任意位置的元素，时间复杂度为 $O(1)$。例如，在一个长度为 $n$ 的数组 arr 中，访问 arr[i] 能快速定位到对应元素。
  2. 缓存局部性好：由于顺序表的元素在内存中是连续存储的，计算机在访问元素时，会把相邻的数据也加载到缓存中，后续访问相邻元素时能更快获取，提高了访问效率。
  3. 空间利用率高：顺序表不需要额外的指针来维护元素之间的关系，只存储数据本身，因此空间利用率相对较高。
缺点
  1. 插入和删除操作效率低：在顺序表中间或开头插入、删除元素时，需要移动大量后续元素，平均时间复杂度为 $O(n)$。例如，在数组中间插入一个元素，需要将插入位置之后的所有元素依次向后移动一位。
  2. 空间扩展不便：当顺序表需要扩容时，通常需要重新分配一块更大的内存空间，并将原有的数据复制过去，操作比较耗时。而且如果一次性分配过大的空间，可能会造成内存浪费；分配过小，又需要频繁扩容。
  3. 内存分配要求高：顺序表要求内存空间必须连续，当需要存储大量数据时，可能难以找到足够大的连续内存空间。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。常见的链表有单链表、双向链表和循环链表。

优点
  1. 插入和删除操作效率高：在链表中插入或删除元素，只需要修改相邻节点的指针，不需要移动大量元素，时间复杂度为 $O(1)$（前提是已经找到插入或删除的位置）。例如，在单链表中插入一个新节点，只需修改前一个节点的指针和新节点的指针。
  2. 空间动态分配：链表的节点是在需要时动态分配内存的，不需要预先分配大量连续的内存空间，避免了内存浪费和分配失败的问题。
  3. 内存利用率高：链表不需要连续的内存空间，只要有足够的零散内存，就可以创建链表节点，适合存储大量数据。
缺点
  1. 随机访问效率低：链表只能从表头开始依次遍历查找元素，访问第 $i$ 个元素的平均时间复杂度为 $O(n)$，无法像顺序表那样直接通过下标访问。
  2. 额外空间开销大：链表的每个节点除了存储数据本身，还需要额外的指针来指向下一个节点（双向链表还需要指向前驱节点），增加了空间开销。
  3. 缓存局部性差：由于链表的节点在内存中是分散存储的，访问元素时可能无法充分利用缓存，导致访问效率降低。

综上所述，顺序表适合随机访问频繁、数据量固定的场景；链表适合插入和删除操作频繁、数据量动态变化的场景。

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

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【Java学习笔记】Collections工具类

【Java学习笔记】Collections工具类

Collections 工具类 基本介绍 &#xff08;1&#xff09;Collections 中提供了一系列静态方法对集合元素进行排序&#xff0c;查询和修改等操作 &#xff08;2&#xff09;操作对象&#xff1a;集合 常用方法一览表 方法描述reverse(List<?> list)反转 List 中元素…
阅读更多...
spring-webmvc @ResponseBody 典型用法

spring-webmvc @ResponseBody 典型用法

典型用法 基本用法&#xff1a;返回 JSON 数据 GetMapping("/users/{id}") ResponseBody public User getUser(PathVariable Long id) {return userService.findById(id); }Spring 自动使用 Jackson&#xff08;或其他 HttpMessageConverter&#xff09;将 User 对…
阅读更多...
AI-调查研究-08-跑步分析研究 潜在伤害与预防 不同年龄段与性别的情况

AI-调查研究-08-跑步分析研究 潜在伤害与预防 不同年龄段与性别的情况

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月16日更新到&#xff1a; AI炼丹日志-29 - 字节…
阅读更多...
AI任务相关解决方案9-深度学习在工业质检中的应用:基于DeepLabv3+模型的NEU-seg数据集语义分割研究

AI任务相关解决方案9-深度学习在工业质检中的应用:基于DeepLabv3+模型的NEU-seg数据集语义分割研究

大家好我是微学AI，今天给大家介绍一下AI任务相关解决方案9-深度学习在工业质检中的应用:基于DeepLabv3+模型的NEU-seg数据集语义分割研究。DeepLabv3+模型在NEU-seg数据集上实现了高达87.65%的平均交并比(mIoU)，为金属表面缺陷的高精度检测提供了有力工具。本文将详细探讨Dee…
阅读更多...
mysql JSON_EXTRACT JSON_UNQUOTE 函数

mysql JSON_EXTRACT JSON_UNQUOTE 函数

在处理mysql 有存储的json字段&#xff0c;需要提取时候发现JSON_EXTRACT函数&#xff0c;发现此函数提取后会带有引号&#xff0c;组合使用JSON_UNQUOTE 可去掉引号&#xff01; JSON_EXTRACT 函数概述 JSON_EXTRACT是MySQL中用于从JSON文档中提取数据的函数&#xff0c;语法…
阅读更多...
Prompt：更好的提示与迭代

Prompt：更好的提示与迭代

欢迎来到啾啾的博客&#x1f431;。 记录学习点滴。分享工作思考和实用技巧&#xff0c;偶尔也分享一些杂谈&#x1f4ac;。 有很多很多不足的地方&#xff0c;欢迎评论交流&#xff0c;感谢您的阅读和评论&#x1f604;。 目录 1 引言1.1 引用资料 2 更好的提示2.1 情景学习IC…
阅读更多...
SQL85 统计每个产品的销售情况

SQL85 统计每个产品的销售情况

SQL85 统计每个产品的销售情况 好复杂&#xff0c;俺不中了。。 问题描述 本查询旨在分析2023年各产品的销售情况&#xff0c;包括&#xff1a; 每个产品的总销售额、单价、总销量和月均销售额每个产品销量最高的月份及其销量每个产品购买量最高的客户年龄段 解题思路 1. 基…
阅读更多...
Django MAC Pycharm 命令行建立项目，注册app运行失败，找不到views导入包

Django MAC Pycharm 命令行建立项目，注册app运行失败，找不到views导入包

相对复杂的情况 你没有直接在Pycharm中建立一个Django项目&#xff0c;而是直接建立某个项目或者打开某个项目&#xff0c;使用命令后安装Django后&#xff0c;使用命令后建立了Django项目&#xff0c;尽管你的目录尽可能干净&#xff0c;只有Django项目&#xff0c;但是这仍然…
阅读更多...
窄带和宽带谁略谁优

窄带和宽带谁略谁优

窄带&#xff08;Narrowband&#xff09;与宽带&#xff08;Broadband&#xff09;深度对比 ——涵盖 优缺点、适用场景、调制方式 1. 窄带&#xff08;Narrowband&#xff09; 1.1 核心特点 带宽&#xff1a;≤25 kHz&#xff08;典型值&#xff0c;如NB-IoT仅占用180kHz&a…
阅读更多...
李佳琦直播间618收官：6成销量为国货，多品类增超25%

李佳琦直播间618收官：6成销量为国货，多品类增超25%

618大促迎来收官&#xff0c;作为电商消费的关键风向标&#xff0c;李佳琦直播间生动呈现了当下消费市场的多元趋势。 据「TMT星球」了解&#xff0c;在长达近40天的大促里&#xff0c;李佳琦直播间不仅延续过往的高人气与强带货力&#xff0c;更在高质价比产品、高质量服务保…
阅读更多...
c++ noexcept关键字

c++ noexcept关键字

noexcept 是 C11 中引入的一个关键字&#xff0c;用来标记函数声明&#xff0c;表示该函数不会抛出异常。它可以用于函数、函数指针、Lambda 表达式等。使用 noexcept 可以帮助编译器进行优化&#xff0c;提高代码的执行效率&#xff0c;并且让程序在处理异常时更加明确。 1. …
阅读更多...
腾讯混元3D制作简单模型教程-2

腾讯混元3D制作简单模型教程-2

以下是腾讯混元3D制作简单模型的详细教程&#xff0c;整合最新版本特性&#xff08;截至2025年6月&#xff09;&#xff0c;操作门槛低且无需专业基础&#xff1a; &#x1f5a5; 一、在线生成&#xff08;最快30秒完成&#xff09; ‌访问平台‌ 打开 腾讯混元3D创作引擎官网…
阅读更多...
阿里云申请ssl证书，同时需要绑定域名，下载nginx压缩包，nginx添加证书路径即可

阿里云申请ssl证书，同时需要绑定域名，下载nginx压缩包，nginx添加证书路径即可

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、ssl是什么&#xff1f;二、登录阿里云三、图片教程四、添加域名前缀&#xff08;www&#xff09;如&#xff1a;www.baidu.com总结 一、ssl是什么&#xff1f; …
阅读更多...
额度互动促进金融健康，蚂蚁消金创新智能实时交互式风控系统

额度互动促进金融健康，蚂蚁消金创新智能实时交互式风控系统

“蚂蚁消金希望利用交互式智能风控技术&#xff0c;挖掘年轻人努力成长的证明”。6月19日&#xff0c;在上海举行的2025中国国际金融展上&#xff0c;蚂蚁消金首席风险官林嘉南分享了&#xff0c;如何将大模型技术应用在交互式智能风控领域&#xff0c;从而促进额度的互动性&am…
阅读更多...
SAP-ABAP：LOOP ... ASSIGNING高效处理内表数据详解

SAP-ABAP：LOOP ... ASSIGNING高效处理内表数据详解

在ABAP中&#xff0c;LOOP ... ASSIGNING 是高效处理内表数据的关键技术&#xff0c;它通过字段符号(field symbol) 直接访问内表内存地址&#xff0c;避免数据副本创建。以下是详细用法指南&#xff1a; 一、基础语法结构 FIELD-SYMBOLS: <fs_line> TYPE any. " …
阅读更多...
Tomcat本地部署Maven Java Web项目

Tomcat本地部署Maven Java Web项目

接下来是在widows部署maven javaweb 首先要配置tomcat&#xff0c;我这里是联合项目&#xff0c;需要配置多个tomcat 选择每个对应的war包 这里的项目名和端口号要改&#xff0c;否则多个项目启动会因为端口号占用无法启动 Tomcat运行项目 打包 在右边的Maven视图里面找到…
阅读更多...
golang--具名返回值、匿名返回值与 defer 语句之间的关系，以及 panic 对它们的影响

golang--具名返回值、匿名返回值与 defer 语句之间的关系，以及 panic 对它们的影响

好的&#xff0c;我们来详细探讨 Go 语言中具名返回值、匿名返回值与 defer 语句之间的关系&#xff0c;以及 panic 对它们的影响。这是 Go 错误处理和资源管理中的核心机制。 核心概念 具名返回值 (Named Return Values): 在函数签名中声明返回变量名。例如&#xff1a;fun…
阅读更多...
FFmpeg 超级详细安装与配置教程（Windows 系统）

FFmpeg 超级详细安装与配置教程（Windows 系统）

1. 前言 FFmpeg 是一个用于处理视频、音频等多媒体文件的开源工具包。它支持几乎所有的多媒体格式转换、剪辑和编辑&#xff0c;是开发者和多媒体工作者必备的工具。本文详细讲解如何在 Windows 系统上安装 FFmpeg 并进行基本配置。 2. 下载 FFmpeg 安装包 打开 Download FFmp…
阅读更多...
Pytorch中gather()函数详解和实战示例

Pytorch中gather()函数详解和实战示例

在 PyTorch 中&#xff0c;torch.gather() 是一个非常实用的张量操作函数&#xff0c;主要用于根据索引从输入张量中选择特定位置的值。它常用于注意力机制、序列处理等场景。 函数定义 torch.gather(input, dim, index) → Tensorinput&#xff1a;待提取数据的张量。dim&…
阅读更多...
uniapp 微信小程序在线引入字体图标

uniapp 微信小程序在线引入字体图标

在线引入字体图标&#xff0c;出现体验版&#xff0c;真机调试字体图标不出来&#xff0c;模拟器上是好的 由于字体图标和小程序域名不在同一个&#xff0c;所以出现了跨域问题&#xff0c;将字体图标文件放到小程序同一个域名下就好了
阅读更多...
最新文章

Copyright @ 2022~2023