数据结构----链表

一丶概念

          链表又称单链表、链式存储结构,用于存储逻辑关系为“一对一”的数据。
          和顺序表不同同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。

二丶特点

         特点:内存不连续,通过指针进行连接
         解决: 长度固定的问题,插入删除麻烦的问题
         逻辑结构:线性结构
         存储结构:链式存储
         操作:增删改查
struct node
{int data;   //数据域:存储数据struct node *next;    //指针域:存储下一个节点的地址
};

三丶单向链表

1.分类

        有头链表:存在一个头节点,头节点数据域无效,指针域有效。
        无头链表:每一个节点的数据域和指针域都有效。

2.有头单向链表

        存在一个头节点,数据域无效,指针域有效

#include <stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域struct node *next;//指针域
} node_t, *node_p;
int main(int argc, char const *argv[])
{node_t A={1,NULL};//输入数据node_t B={2,NULL};node_t C={3,NULL};node_t D={4,NULL};A.next=&B;B.next=&C;C.next=&D;node_p p;//头指针指向头节点node_t S = {'\0',&A};p=H.next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");return 0;
}

3.无头单向链表

所有节点的指针域和数据域都有效

#include <stdio.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;     //数据域用来存数据struct node *next; //指针域用来存下一个节点的地址
} node_t, *node_p;// node_t A; //等同于 struct node A;
// node_p p; //等同于 struct node *p;int main(int argc, char const *argv[])
{//1.定义4个节点node_t A = {'a', NULL};node_t B = {'b', NULL};node_t C = {'c', NULL};node_t D = {'d', NULL};//2.连接四个节点A.next = &B; //连接A和BB.next = &C;C.next = &D;//3.定义一个头指针指向第一个节点node_p p = &A;//4. 通过指针遍历无头单向链表while (p != NULL){printf("%c ", p->data); //打印节点中的数据域 a b c dp = p->next;            //让p指向下一个节点}printf("\n");return 0;
}

链表尾插法练习

写一个有头单向链表,用于保存输入的学生成绩,实现一输入学生成绩就创建一个新的节点,将成绩保存起来。再将该节点链接到链表的尾,直到输入-1结束。

要求:每个链表的节点由动态内存分配得到 , 也就是用malloc。

过程:

1.  malloc申请空间link_node_t大小作为头节点

2.  将新节点放到链表尾部

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域存放数据struct node *next;//指针域记录下一个结点地址
} node_t, *node_p;
void ShowLinklist(node_p p)//打印数据
{while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}
int main(int argc, char const *argv[])
{int score = 0;// 创建一个头节点node_p p_head = (node_p)malloc(sizeof(node_t));if (NULL == p_head)//容错判断{printf("malloc err");return -1;}//让头指针的指针域置空p_head->next = NULL;//创建一个尾节点node_p p_tail = (node_p)malloc(sizeof(node_t));if (NULL == p_head){printf("p_tail malloc err");return -1;}p_tail = p_head;//让尾节点指向头节点while (1){//循环输入成绩scanf("%d", &score);//输入-1时停止结束循环if (score == -1)break;//新建一个节点p_newnode_p p_new = (node_p)malloc(sizeof(node_t));if (NULL == p_new)//容错判断{printf("p_new malloc err");return -1;}p_new->data = score; //将数据存入新的节点p_new->next = NULL;//让新的节点的指针域置空p_tail->next = p_new;//让尾节点连接到新的节点p_tail=p_new;//更新尾节点}node_p p = p_head->next;ShowLinklist(p);return 0;
}

4.有头单向链表的函数操作

插入的思想

1. 先遍历找到要插入节点的前一个节点,假设这个节点为A;A的下一个节点为B;将C插入A与B之间;
2.先让C的指针域指向B;
3.再让A的指针域指向C;

(注意:顺序不可以调换)

int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new)                             // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data;    // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new;       // 前一个节点的指针域等于新节点的地址return 0;
}

删除的思想

      1.先遍历找到要删除节点的前一个节点,假设为A;

      2、找一个临时指针指向要删除的节点;
      3、  将A的指针域指向删除节点的下一个节点;
      4、  释放被删除节点

int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next;                                 node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next;  // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1);            // 将被删除指针释放,指针置空p1 = NULL;
}


转置的思想:

(1) 将头节点与当前链表断开,断开前保存下头节点的下一个节点,保证后面链表能找得到,定义一个q保存头节点的下一个节点,断开后前面相当于一个空的链表,后面是一个无头的单向链表
(2) 遍历无头链表的所有节点,将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)

void ReverseLinkList(node_p p)
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前,保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点(相当于无头单向链表的头指针)//1.断头,断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点,防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表,指向此时的第一个节点q=temp;}

完整的单链表操作

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;          // 数据域存放数据struct node *next; // 指针域记录下一个结点地址
} node_t, *node_p;
node_p CreateEpLinkist() // 创建一个空的有头单向链表
{node_p p = (node_p)malloc(sizeof(node_t)); // 开辟节点空间大小if (NULL == p){printf("CreatEpLinklist err");return NULL;}p->next = NULL; // 初始化头结点return p;
}
int StrlenLinklist(node_p p)//计算单链表长度
{int len = 0;while (p->next != NULL){p = p->next;len++;}return len;
}
int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new)                             // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data;    // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new;       // 前一个节点的指针域等于新节点的地址return 0;
}
int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next;                                 node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next;  // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1);            // 将被删除指针释放,指针置空p1 = NULL;
}
void ModifyLinklist(node_p p, int post, int data) // 修改函数
{for (int i = 0; i <= post; i++) // 让指针指向要修改的节点位置p = p->next;p->data = data; // 指针域等于新的数据
}
void SearchLinklist(node_p p, int data)//查找数据
{int i = 0;p = p->next;while (p != NULL){if (p->data == data){printf("%d\n", i);//打印第一个相同数据的下标break;}p = p->next;i++;}
}
void ClearLinklist(node_p p)//清空链表
{while(StrlenLinklist(p)!=0){DeleteLinklist(p,0);//删除第一个节点}
}
void ShowLinklist(node_p p)// 打印数据
{while (p->next)// 当指针p的指针域为空时停止循环{p = p->next;printf("%d ", p->data);}printf("\n");
}
void ReverseLinkList(node_p p)//链表转置
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前,保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点(相当于无头单向链表的头指针)//1.断头,断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点,防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表,指向此时的第一个节点q=temp;}}
int IsEpLinklist(node_p p)
{return p->next == NULL;
}
int main(int argc, char const *argv[])
{node_p p = CreateEpLinkist(); // 创建一个空的有头单向链表InsertLinklist(p, 0, 1);// 进行插入数据InsertLinklist(p, 1, 2);InsertLinklist(p, 2, 3);InsertLinklist(p, 3, 4);InsertLinklist(p, 4, 5);InsertLinklist(p, 5, 6);ShowLinklist(p);// 打印数据DeleteLinklist(p, 0);// 删除数据ShowLinklist(p);// 打印数据ModifyLinklist(p, 0, 0); // 修改数据ShowLinklist(p);// 打印数据SearchLinklist(p, 2);ReverseLinkList(p);ShowLinklist(p);// 打印数据ClearLinklist(p);if(IsEpLinklist(p))printf("IsEpLinkList\n");free(p);p =NULL;return 0;return 0;
}

5.单向循环链表

四丶总结:

顺序表和单向链表比较:
             (1).顺序表在内存当中连续存储的(数组),但是链表在内存当中是不连续存储的,通过指针将数据链接在一起
            (2).顺序表的长度是固定的,但是链表长度不固定
            (3).顺序表查找方便,但是插入和删除麻烦,链表,插入和删除方便,查找麻烦

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

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

相关文章

DolphinScheduler集群部署问题(趟坑)总结

目录 官方文档 官方项目地址 问题解决 官方文档 DolphinScheduler | 文档中心 (apache.org) 官方项目地址 部署及使用过程中的问题可以参见项目Issue:Issues apache/dolphinscheduler GitHub GitHub - apache/dolphinscheduler at 3.2.2-release 问题解决 1、JVM在运…

Simple RPC - 05 从零开始设计一个客户端(下)_ 依赖倒置和SPI

文章目录 Pre概述依赖倒置原则与解耦设计与实现1. 定义接口来隔离调用方与实现类2. 实现类DynamicStubFactory3. 调用方与实现类的解耦 依赖注入与SPI的解耦依赖注入SPI&#xff08;Service Provider Interface&#xff09; 总结 Pre Simple RPC - 01 框架原理及总体架构初探 …

网络编程:OSI协议,TCP/IP协议,IP地址,UDP编程

目录 国际网络通信协议标准&#xff1a; 1.OSI协议&#xff1a; 2.TCP/IP协议模型&#xff1a; 应用层 &#xff1a; 传输层&#xff1a; 网络层&#xff1a; IPV4协议 IP地址 IP地址的划分&#xff1a; 公有地址 私有地址 MA…

dotnet常用命令详解

命令预览 基础命令 new&#xff1a;创建项目 restore&#xff1a;恢复依赖 build&#xff1a;编译项目 publish&#xff1a;生成项目需要的文件准备发布项目 run&#xff1a;运行项目 test&#xff1a;测试项目 vstest&#xff1a;从指定的程序集中运行测试 pack&#…

升级阿里云linux服务器上的php版本

查看已安装的php软件包 [rootiZbp13pl2v34qj0thwq9aiZ ~]# rpm -qa|grep php php74-php-common-7.4.26-1.el7.remi.x86_64 oniguruma5php-6.9.7.1-1.el7.remi.x86_64 php74-php-gd-7.4.26-1.el7.remi.x86_64 php74-php-opcache-7.4.26-1.el7.remi.x86_64 php74-php-json-7.4.2…

记录|Git工具——下载GitHub项目

目录 前言一、Step 1. 下载Git二、Step2. 用Git Bash 下载到本地更新时间 前言 参考文章&#xff1a; 1、如何使用Git将Github项目拉到本地 2、git 安装、创建仓库、上传项目、克隆下载、常用命令 – 一篇文章总结&#xff08;适用github / gitee&#xff09; 3、Git的使用【入…

政策驱动,科技引领,漫途信息化监测方案守护农村饮水安全!

近日&#xff0c;山西省人民政府正式发布《山西省农村供水高质量发展规划》&#xff0c;明确到2030年&#xff0c;全面实现农村24小时供水&#xff0c;县域农村饮水安全标准化建设达标率力争达到80%&#xff0c;基本实现农村供水城市化、城乡供水均等化。 现阶段部分地区受…

ArcGIS简单介绍

ArcGIS体系结构 &#xff08;1&#xff09;GIS Server 宿主各种GIS资源&#xff0c;将他们封装为服务提供给客户端应用。GIS Server分为两部分&#xff1a;Server Object Manager&#xff08;SOM&#xff09;和Server Object Containers&#xff08;SOCs&#xff09;。一个SO…

Java语言程序设计——篇十三(4)

&#x1f33f;&#x1f33f;&#x1f33f;跟随博主脚步&#xff0c;从这里开始→博主主页&#x1f33f;&#x1f33f;&#x1f33f; 欢迎大家&#xff1a;这里是我的学习笔记、总结知识的地方&#xff0c;喜欢的话请三连&#xff0c;有问题可以私信&#x1f333;&#x1f333;&…

仪表板展示|DataEase看中国:2024巴黎奥运会中国体育代表团战绩报告

背景介绍 北京时间2024年8月12日凌晨&#xff0c;巴黎奥运会闭幕。在本届奥运会中&#xff0c;我们不仅见证了许多新世界纪录的诞生&#xff0c;更看到了中国体育的强大实力与无限潜力。中国运动健儿们卓越的表现和顽强的拼搏精神&#xff0c;不但让国人为之自豪&#xff0c;也…

Windows 11 Build 27686 上手体验:2TB FAT32、更好的沙盒等功能

Windows 11 Build 27686 现已在 Insider Program 的 Canary 频道发布&#xff0c;其中包含一些有趣的内容。该版本确认了微软更改 FAT32 大小限制的计划&#xff0c;并将其大小限制从 32GB 提高到 2TB。与此同时&#xff0c;沙盒也得到了改进。让我们来详细了解一下此次更新。 …

【卡码网Python基础课 16.出现频率最高的字母】

目录 题目描述与分析描述2.分析 一、哈希表二、代码编写 题目描述与分析 描述 题目描述&#xff1a; 给定一个只包含小写字母的字符串&#xff0c;统计字符串中每个字母出现的频率&#xff0c;并找出出现频率最高的字母&#xff0c;如果最高频率的字母有多个&#xff0c;输出…

Nginx--虚拟机配置

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 1、什么是虚拟主机 虚拟主机是一种特殊的软硬件技术&#xff0c;它可以将网络上的每一台计算机分成多个虚拟主机&#xff0c;每个虚拟主机可以独立对…

字符串函数!!!(续)(C语言)

一. strtok函数的使用 继续上次的学习&#xff0c;今天我们来认识一个新的函数strtok&#xff0c;它的原型是char* strtok(char* str,const char* sep)&#xff0c;sep参数指向了一个字符串&#xff0c;定义了用作分隔符的字符合集&#xff0c;第一个参数指定⼀个字符串&#…

基于C# winform部署图像动漫化AnimeGANv2部署onnx模型

【界面截图】 【效果演示】 【部分实现代码】 using System; using System.Diagnostics; using System.Windows.Forms; using OpenCvSharp;namespace FIRC {public partial class Form1 : Form{Mat src null;public Form1(){InitializeComponent();}private void button1_Cli…

消息系统-WebSocket消息推送

消息系统-WebSocket消息推送 接口层使用消息通知 1.数据库设计: 1.消息通知表 2.消息记录表 3.用户表和角色表及用户角色记录表 2.设计: 未使用消息中间件 ,利用接口层调用消息通知接口工具类 3.前端:消息通知页面 1.消息通知列表 2.消息通知标签 3.消息通知未读抽屉列表 一.…

Ubuntu离线安装库并解决依赖关系

&#xff08;1&#xff09;起因 安装插件出现库未找到的错误 configure: error: curses library is required but not found.&#xff08;2&#xff09;解决方法 手动到Ubuntu的库发布网页下载 http://packages.ubuntu.com/ 选择系统对应架构的版本下载&#xff0c;然后上传…

django(REST_FRAMEWORK)+swagger+Apifox 集成

1.reset_framework 1.1安装rest_framework 1.2使用rest_framework 在django框架中setting文件中注册rest_framework INSTALLED_APPS [rest_framework, ]2.reset_frameworkswagger 2.1.安装drf_yasg 2.2.在django框架中setting文件中注册drf_yasg INSTALLED_APPS [drf_…

滴滴开源新项目Unify:聚焦Flutter与原生通信难题,助力跨端应用落地

引言 在移动开发领域&#xff0c;移动跨端技术因其提效收益&#xff0c;逐渐成为业界趋势之一。Flutter 作为近年来热门的跨端技术&#xff0c;以高性能、自渲染、泛跨端著称&#xff0c;得到广泛应用。在滴滴国际化业务中&#xff0c;我们大量应用 Flutter。目前已在滴滴国际化…

【大模型部署及其应用 】RAG检索技术和生成模型的应用程序架构:RAG 使用 Meta AI 的 Llama 3

目录 RAG检索技术和生成模型的应用程序架构1. **基本概念**2. **工作原理**3. **RAG的优势**4. **常见应用场景**5. **RAG的挑战**6. **技术实现**参考RAG 使用 Meta AI 的 Llama 3亲自尝试运行主笔记本与文档应用聊天关键架构组件1. 自定义知识库2. 分块3. 嵌入模型4. 矢量数据…