单链表---结构体实现

定义

链表称为线性表的链式存储,顺序表逻辑上相邻的数据,存储位置也相邻。链表逻辑上相邻的数据,存储位置是随机分布在内存的各个位置上的。

对于每一个结点,定义的结构体是:

typedef struct _LinkNode 
{int date;				//数据域,存储数据,这里是int类型的数据struct _LinkNode* next; // 指针域,指向了后继元素(下一个结点)的地址
}LinkNode , LinkList;       //两个别名的作用是一模一样的,只是为了区分头结点和结点

 链表的初始化

我们用一个结构体指针L来指向链表,最开始是带一个头结点的空链表,头结点的数据域一般赋值为-1,也可以存储着链表的长度。头结点的指针域指针第一个元素结点,最开始是没有元素结点的空链表(有头结点),如图:

代码实现

bool initLinkList(LinkList*& L) //参数是对结构体指针的引用
{L = new LinkList; //也可以写成 L = new LinkNode ;if (!L){return false; // 申请内存失败,返回了一个空指针}L->next = NULL;return true;
}

链表的插入

头插法

将新结点插到头结点的后面,有两种形式,一是链表为空,二是链表中已有元素结点,如图

你可以分情况,不过也可以不用,例如:

bool insertLinkList(LinkList*& L, LinkNode *node) //node指向要添加的结点
{if (!L || !node) return false;node->next = L->next; //包含两种情况L->next = node;return true;
}

尾插法

尾插,顾名思义就是在最后一个结点插入之后,也分两种情况,一是链表为空,二是链表中已有元素结点,第一种情况的图和头插法的第一种情况的图一样,就是插入方式不同,以下是第二种情况的图:

我们只需要找到 next 指向 NULL 的这个结点就好了

bool LinkListinsert(LinkList*& L, LinkNode *node)
{if (!L || !node) return false;LinkNode* p = NULL;p = L;while (p->next != NULL) //如果是空链表,p == L,所以是包含两种情况{p = p->next;}node->next = p->next;p->next = node;return true;
}

指定位置插入

在第 i 个结点前插入,那么我们就必须有个临时指针指向第 i-1 个结点

bool InsertLink(LinkList*& L, int i, int e) // 这里也可以用之前的LinkNode *node参数,不过可能i不合法
{if (!L) return false;LinkNode* p = L , *s = NULL ;int j = 0;while (p && j < i - 1) // 指向第 i-1 个结点{	p = p->next;j++;}//如果在第0个位置之前插入(i<1) || 如果在最后一个结点+2的位置之前插入(i>n+1,n为链表长度)---都是非法的if (i < 1 || !p) return false;s = new LinkNode;s->date = e;s->next = p->next;p->next = s;return true;
}

遍历链表(打印链表)

bool PrintLinkList(LinkList *& L)
{if(!L) return false; LinkNode* p = L->next; //首先指向第一个结点,如果为空链表就会指向 NULLwhile (p != NULL) // 直到指向最后一个结点的 next 指针(NULL){printf("%d ", p->date);p = p->next;}cout << endl;return true;
}

遍历链表,也可以用来求链表的长度,代码与这个类似。

链表的获取

获取链表第 i 个结点的数据域。

bool GetElemLink(LinkList*& L, int i, int &e) //e返回获取的数据域
{LinkNode* p = L;int j = 0;while ( p!=NULL && j < i){p = p->next;j++;}if (p==NULL || i < 1) //i是非法的:i > n(n为链表长度,例如:获取第n+1个结点的数据域)或者是 i < 1(例如:获取了第0个结点的数据域){return false;}e = p->date;return true;
}

链表的查找

查找我们输入的元素在链表中出现的第一个位置。

bool FindElem(LinkList* L, int e,int &index) // index返回位置
{if (!L || !L->next) return false; //空链表LinkNode* p = L->next; // 现在指向第一个结点int j = 1;  while (p != NULL && p->date != e) {p = p->next;j++;}if (p == NULL)return false;else{index = j;return true;}
}

链表的删除

删除第 i 个结点,i 可能不合法,注意不合法的原因。

bool DeleteLinkNode(LinkList*& L, int i)
{LinkNode* p = NULL , *q = NULL;p = L;int j = 0;while ( p->next!=NULL && j < i - 1){p = p->next;j++;}// 指向第 i-1 个结点if (i < 1 || p->next == NULL) //i非法,删除第0个结点(i<1) 或者是 删除第n+1个结点(i>n,n为链表的长度)return false;else{q = p->next;p->next = q->next ;delete q;return true;}}

链表的销毁(清空)

销毁就是要归还所申请的内存,删除某个结点时,一定要保存下一个结点的地址。简要解释:先保存第一个结点的地址,随后删除头结点(也申请了空间),再保存第二个结点的地址,删除第一个结点,再保存第三个结点……以此类推,可以将全部结点删除。

void DestoryLink(LinkList*& L)
{LinkNode* p = NULL, * q = NULL;p = L;while (p != NULL){	q = p->next;//cout << "删除元素" << p->date << endl;delete p;p = q;}}

总代码

以下是全部代码,链表的函数有不同的实现方法。也许我的代码和别人有些差异,所以可以看看 main 函数中是怎样的。

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>using namespace std;typedef struct _LinkNode
{int date;				//数据域struct _LinkNode* next; // 指针域}LinkNode , LinkList;//初始化链表
bool initLinkList(LinkList*& L)
{L = new LinkList;if (!L){return false;}L->next = NULL;return true;
}//前插法
bool insertLinkList(LinkList*& L, LinkNode *node)
{if (!L || !node) return false;node->next = L->next;L->next = node;return true;
}//尾插法
bool LinkListinsert(LinkList*& L, LinkNode *node)
{if (!L || !node) return false;LinkNode* p = NULL;p = L;while (p->next != NULL){p = p->next;}node->next = p->next;p->next = node;return true;
}//在第i个结点前插入---指定位置插入
bool InsertLink(LinkList*& L, int i, int e)
{if (!L) return false;LinkNode* p = L , *s = NULL ;int j = 0;while (p && j < i - 1){	p = p->next;j++;}//如果在第0个位置之前插入(i<1) || 如果在最后一个结点+2的位置之前插入(i>n+1,n为链表长度)---都是非法的if (i < 1 || !p) return false;s = new LinkNode;s->date = e;s->next = p->next;p->next = s;return true;
}//打印链表
void PrintLinkList(LinkList *& L)
{LinkNode* p = L->next;while (p != NULL){printf("%d ", p->date);p = p->next;}cout << endl;
}//获取第i个结点的数据元素
bool GetElemLink(LinkList*& L, int i, int &e)
{LinkNode* p = L;int j = 0;while ( p!=NULL && j < i){p = p->next;j++;}if (p==NULL || i < 1){return false;}e = p->date;return true;
}//在链表中查找元素,并且用index返回位置
bool FindElem(LinkList* L, int e,int &index)
{if (!L || !L->next) return false;LinkNode* p = L->next;int j = 1;while (p && p->date != e){p = p->next;j++;}if (p == NULL)return false;else{index = j;return true;}
}//删除第i个结点
bool DeleteLinkNode(LinkList*& L, int i)
{LinkNode* p = NULL , *q = NULL;p = L;int j = 0;while ( p->next!=NULL && j < i - 1){p = p->next;j++;}if (i < 1 || p->next == NULL) //删除第0个结点(i<1) 或者是 删除第n+1个结点(i>n,n为链表的长度)return false;else{q = p->next;p->next = q->next ;delete q;return true;}}//清空(销毁)链表
void DestoryLink(LinkList*& L)
{LinkNode* p = NULL, * q = NULL;p = L;while (p != NULL){	q = p->next;//cout << "删除元素" << p->date << endl;delete p;p = q;}}
int main(void)
{LinkList* L = NULL; //指向表头(头结点)的指针LinkNode* e = NULL; //指向结点的指针initLinkList(L);int elem = 0;		//结点的数据元素int i;				//第几个结点int n = 0;			//输入的个数int flag = -1;while (flag != 0){cout << "1.前插链表" << endl<< "2.尾插链表" << endl<< "3.指定位置前插入" << endl<< "4.打印链表" << endl<< "5.获取第i个结点的数据" << endl<< "6.查找元素" << endl<<"7.删除元素"<<endl<< "0.退出(销毁链表)" << endl;cout << "请选择:";cin >> flag;switch (flag){case 1:cout << "请输入前插法插入链表的个数";cin >> n;cout << "请依次输入" << n << "个数:";while (n--){e = new LinkNode;cin >> e->date;insertLinkList(L, e);}break;case 2:cout << "请输入尾插入链表的个数";cin >> n;cout << "请依次输入" << n << "个数:";while (n--){e = new LinkNode;cin >> e->date;LinkListinsert(L, e);}break;case 3:cout << "请输入插入的位置和元素:";cin >> i >> elem;InsertLink(L, i, elem);break;case 4:PrintLinkList(L);break;case 5:cout << "请输入要获取的结点i:";cin >> i;if (GetElemLink(L, i, elem)){cout << "第" << i << "个结点的值为" << elem << endl;}else{cout << "获取元素失败" << endl;}break;case 6:cout << "请输入要查找的元素:";cin >> elem;if (FindElem(L, elem, i)){cout << "找到了,此元素的位置是" << i << endl;}else{cout << "表中无此值" << endl;}break;case 7:cout << "请输入要删除的结点i:";cin >> i;if (DeleteLinkNode(L, i)){cout << "删除成功" << endl;}else{cout << "删除失败" << endl;}break;case 0:DestoryLink(L);break;default:cout << "输入非法! " << endl;break;}}return 0;
}

这里也可以将代码复制,自己调试测试一下,删除某些代码,看看会有什么影响,更能理解。

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

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

相关文章

C# Winform编程(3)对话框

C# Winform编程&#xff08;3&#xff09;对话框 Show(string text);Show(string text, string caption);Show(string text, string caption, MessageBoxButtons buttons);Show(string text, string caption, MessageBoxButtons buttons, MessageBoxIcon icon); using System;…

大模型的背景与现状问题

一、大模型的发展背景 谈起大模型&#xff0c;第一时间想到的是什么&#xff1f;是主流的ChatGPT&#xff1f;或者GPT4&#xff1f;还是DALL-E3&#xff1f;亦或者Midjourney&#xff1f;以及Stablediffusion&#xff1f;还是层出不穷的其他各类AI Agent应用工具&#xff1f;大…

ST-SSL:基于自监督学习的交通流预测模型

文章信息 文章题为“Spatio-Temporal Self-Supervised Learning for Traffic Flow Prediction”&#xff0c;是一篇发表于The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)的一篇论文。该论文主要针对交通流预测任务&#xff0c;结合自监督学习&#…

香港学界呼吁RWA“在港先发”,构建基于港元稳定币的Web3生态!

2023年以来&#xff0c;市场对于RWA&#xff08;Real World Assets&#xff09;即真实世界资产“代币化”的讨论愈发频繁&#xff0c;一些观点认为 RWA将在下一轮加密资产牛市中成为焦点&#xff0c;部分Web3创业者和传统金融企业也快速将业务方向瞄准相关赛道&#xff0c;而被…

架构-设计原则

1、面向对象的SOLID 1.1 概述 SOLID是5个设计原则开头字母的缩写&#xff0c;其本身就有“稳定的”的意思&#xff0c;寓意是“遵从SOLID原则可以建立稳定、灵活、健壮的系统”。5个原则分别如下&#xff1a; Single Responsibility Principle&#xff08;SRP&#xff09;&am…

grafana api创建dashboard 记录

文章目录 json model导入申请api key创建dashboard删除dashboard json model导入 直接在ui通过json model 导入&#xff0c;开发自己用还好&#xff0c;但对非开发人员不太友好&#xff0c;故考虑通过api后台自动创建 api doc : https://grafana.com/docs/grafana/v9.3/devel…

R实现动态条件相关模型与GARCH模型结合研究中美股市动态相关性(DCC-GARCH模型)

大家好&#xff0c;我是带我去滑雪&#xff01; 中美两国是全球最大的经济体&#xff0c;其经济活动对全球产业链和贸易体系都具有巨大影响。中美之间的经济互动包括大规模的贸易、投资和金融往来。这些互动不仅仅反映在经济数据上&#xff0c;还体现在股市上。中美股市的联动关…

吃瓜教程-模型的评估与选择

在训练集上的误差称为训练误差&#xff08;training error&#xff09;或经验误差&#xff08;empirical error&#xff09;。在测试集上的误差称为测试误差&#xff08;test error&#xff09;。学习器在所有新样本上的误差称为泛化误差&#xff08;generalization error&…

drawio简介以及下载安装

drawio简介以及下载安装 drawio是一款非常强大的开源在线的流程图编辑器&#xff0c;支持绘制各种形式的图表&#xff0c;提供了 Web端与客户端支持&#xff0c;同时也支持多种资源类型的导出。 访问网址&#xff1a;draw.io或者直接使用app.diagrams.net直接打开可以使用在线版…

PyTorch 深度学习之处理多维特征的输入Multiple Dimension Input(六)

1.Multiple Dimension Logistic Regression Model 1.1 Mini-Batch (N samples) 8D->1D 8D->2D 8D->6D 1.2 Neural Network 学习能力太好也不行&#xff08;学习到的是数据集中的噪声&#xff09;&#xff0c;最好的是要泛化能力&#xff0c;超参数尝试 Example, Arti…

软件工程与计算总结(九)软件体系结构基础

目录 ​编辑 一.体系结构的发展 二.理解体系结构 1.定义 2.区分体系结构的抽象与实现 3.部件 4.连接件 5.配置 三.体系结构风格初步 1.主程序/子程序 2.面向对象式 3.分层 4.MVC 一.体系结构的发展 小规模编程的重点在于模块内部的程序结构非常依赖于程序设计语言…

仪酷LabVIEW OD实战(3)——Object Detection+onnx工具包快速实现yolo目标检测

‍‍&#x1f3e1;博客主页&#xff1a; virobotics(仪酷智能)&#xff1a;LabVIEW深度学习、人工智能博主 &#x1f384;所属专栏&#xff1a;『LabVIEW深度学习工具包』『仪酷LabVIEW目标检测工具包实战』 &#x1f4d1;上期文章&#xff1a;『仪酷LabVIEW OD实战(2)——Obje…

E047-论坛漏洞分析及利用-针对Wordpress论坛进行信息收集与漏洞扫描的探索

任务实施: E047-论坛漏洞分析及利用-针对Wordpress论坛进行信息收集与漏洞扫描的探索 任务环境说明&#xff1a; 服务器场景&#xff1a;p9_kali-6&#xff08;用户名&#xff1a;root&#xff1b;密码&#xff1a;toor&#xff09; 服务器场景操作系统&#xff1a;Kali Li…

MPNN 模型:GNN 传递规则的实现

首先&#xff0c;假如我们定义一个极简的传递规则 A是邻接矩阵&#xff0c;X是特征矩阵&#xff0c; 其物理意义就是 通过矩阵乘法操作&#xff0c;批量把图中的相邻节点汇聚到当前节点。 但是由于A的对角线都是 0.因此自身的节点特征会被过滤掉。 图神经网络的核心是 吸周围…

mysql中的几种排名函数

mysql中的排名函数 mysql里面的排名函数&#xff0c;涉及有以下几个&#xff1a; rank()、dense_rank()、row_number() 1、rank() 函数 RANK() OVER (PARTITION BY <expression>[{,<expression>...}]ORDER BY <expression> [ASC|DESC], [{,<expression…

MySQL有时候命中索引有时候又不命中

索引失效的情况 -----可能 索引主要看where 、group by 、order by 1.组合索引不遵循最佳左前缀法制。最佳左前缀法制&#xff1a;如果索引了多列&#xff0c;要遵循最左前缀法则&#xff0c;指的是查询从索引的最左前列开始并且不跳过索引中的列。如组合索引为A B C 只有ABC,A…

C# RestoreFormer 图像修复

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.Drawing; using System.Drawing.Imaging; using System.Windows.Forms;namespace 图像修复 {pu…

【SpringCloud-10】SCA-nacos

前言&#xff1a; 前面介绍的springcloud&#xff0c;可以看做第一代&#xff0c;称为&#xff1a;SCN&#xff08;spring cloud Netflix&#xff09;; 接下来介绍的是第二代&#xff1a;SCA&#xff08;spring cloud alibaba&#xff09;&#xff1b; SCA主要有以下组件&#…

Java|学习|异常

1.异常 1.1 异常 1.1.1 概述 异常&#xff1a;就是程序出现了不正常的情况。 Error&#xff1a;严重问题&#xff0c;不需要处理。 Exception&#xff1a;称为异常类&#xff0c;它表示程序本身可以处理的问题。 RuntimeException&#xff1a;在编译器不检查&#xff0c;出…

关于Skywalking Agent customize-enhance-trace对应用复杂参数类型取值

对于Skywalking Agent customize-enhance-trace 大家应该不陌生了&#xff0c;主要支持以非入侵的方式按用户自定义的Span跟踪对应的应用方法&#xff0c;并获取数据。 参考https://skywalking.apache.org/docs/skywalking-java/v9.0.0/en/setup/service-agent/java-agent/cust…