线性表：关于链表（主要以单链表为例）的相关理解和应用

多清澈这天空 晴雨相拥 同心逐梦！

坚守我信心  一路出众！！

首先，按照惯例，欢迎大家边听歌边观看本博客

▶ 紫荆花盛开 (163.com)（建议复制链接，浏览器打开，csdn打开太慢了）

2022香港回归祖国25周年主题歌曲，好听！！！

一.单链表

首先 大家肯定知道链表的表达方式，如下

typedef struct LNode
{
    ElemType data;
    struct LNode *next;

}LinkNode;

定义一个LNode，node节点，结点，L是link，表示链接，所以叫做LNode链接结点构成链表

第一个存放元素的信息，链表的特点就是多存了一个节点（指针域）指向后继节点。

0.1稍微浅浅的给大家补充一下结构体的知识点：

1.一个正常的结构体代码编写

struct
{
int num;
char name[20];
char sex;
float score;
}boy1,boy2;

你可以直接在boy2后面打个{ }初始化，在使用boy的时候我们可以具体到一个成员如boy1.num 即为boy1结构体的num成员

然后接下来其实更加常见的定义是这样子的

struct stu
{
int num;
char name[20];
char sex;
float score;
}*boy1,boy2; //boy1是结构体指针,boy2是结构体

这时候我们对指向结构体的指针标表示的成员方式有所不同，可表示为(*boy1).num或者boy1->num（熟悉吧，这里算是补充一下知识点）都可以。一般配合malloc（与free）或者c++中的new（delete）函数使用，主要是结构体指针自创立开始指向的空间就不存在，所以我们得开辟一个空间给他们. 

1.1理解一些易混概念

        本来吧，其实我真想按课本讲一遍，但是感觉有点浪费时间，而且课本那些加深不了我的理解，所以干脆我就直接把我的理解说了，如果有错，希望各位大佬指正！

温馨提示：接下来的话可能有点绕口令！！

第一：节（结）点

我们知道一个节点包括了他的数据域和他的指针域

数据域存放他的data，指针域存放下一个节点的地址，其中在第一个的叫做头结点，头结点链接的第一个节点叫做首节点，最后一个节点叫做尾结点。经常会出现R指针，我管他叫标记指针，用于记住我们要操作的节点的下一个地址，免得链表丢失，至少现在我知道的就是这点，其中^表示NULL。

ok，接下来，来解决几个知识，保证我们看得到接下来的代码，懂了应该就会写了吧

1.对指针赋值相当于就是让指针指向哪里

1.1：比如Lode *r=L；让r指向头结点L。

1.2：pre=p；（pre和p都是指针），让pre指向p（指向的地址）

1.3：p=p->next p指向下一位（详细一点：p->next在等号后面表示解引用，指的是p指向的结构体的指针域的地址（表示这个结构体的下一个地址））

1.4：r->next=p 这个指的是让r对应的结构体指向p（而非指针r指向p，此时的r相当于标记指针）

1.5：s->next=p->next；p->next=s；像这种我们就推荐画图理解

1.6：p=L->next->next表示p指向L的下下指针域而L->next->next=NULL则指的是L的下一个节点的指针域为空,如下图所示

 

 2.链表的基本功能

相信大家已经对链表有了初步的了解，现在我们来一个一个实现他们

2.1链表创建与初始化

typedef char ch
typedef struct LNode
{
    ch data;
    struct LNode* next;
}Linknode;
初始化
void InitLnode(LinkNode *&L){
L=new LinkNode;
L->next=NULL;
}

 2.2插入

这里就不得不讲讲插入的两种方法

2.2.1头插法

思路示意图如下：

LinkList Headinster(LinkList &L,int n){
    LNode *s;
    int x=1;
	L= (LinkList)malloc(sizeof(LNode));
    L->data=x++;
    L->next=NULL;
    while(x!=n){
        s=(LNode*) malloc(sizeof(LNode));
        s->data=x;
        s->next=L;
        L=s;
        x++;
    }
    return L;
}

 

核心代码

s->next=L->next;		①
L->next=s;				②

 作用效果就是从头结点和首节点插入新的元素，从而导致先插进来的反而在后面

这里借用一下大佬的动图（侵权删）

2.2.2尾插法

顾名思义就是从尾部开始插入由于新的节点插入后成为新的尾部，所以我们需要用一个指针R去更新尾部节点（始终指向尾部）

大概像这样子

LinkList TailInster(LinkList &L,int n){
	int x=1;
	L= (LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	while(x!=n){
   		s=(LNode*) malloc(sizeof(LNode));
   		s->data=x;
  	 	r->next=s;
   		r=s;
   		x++;
	}
	r->next=NULL;
	return L;
}

核心代码

r->next=s;			//①r的指针域指向S（让新结点插入到链表）
r=s;				//②r指针指向s（保持r指针一直在链表尾端，方便插入新的结点）

 那么 现在我们继续写这个尾插法

//插入（使用尾插法）
void InsertLnode(LinkNode *&L,ch a[],int n)
{
    LinkNode *s,*r;
    r=L;
    for(int i=0;i<n;i++)
    {
        s=new LinkNode；
        s->next=a[i];
        r->next=s;
        r=s;
    }    
    r->next=NULL;
}

2.3链表的展示

void DisplayLinkNode(LinkNode *L)
{
    LinkNode *p=L->next;
    while(p!=NULL)
    {
        cout<<p->data<<"   ";
        p=p->next;
    }
    cout<<endl<<endl;
}

 2.4链表的长度

int LinkNodeLength(LinkNode *L)
{
    LinkNode *p=L;
    int n=0;    
    while(p->next!=NULL)//注意头结点不算我们的链表长度
    {
        n++;
        p=p->next;
    }
    return n; 
}

2.5链表中取值

bool Getlink(LinkNode *L,int n,ch &e)
{
    if(n<=0)
        return false;
    LinkNode *p=L;
    int j=0;
    while(j<n&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
    else
    {
        e=p->data;
        return true;
    }
}

记忆方法：创建指针，遍历一下，判断是否为空，否则为可取之值 

 2.6链表中删除

bool DeleteNode(LinkNode *&L,int n,ch &e)
{
   if(n<=0) 
        return false;
    LinkNode *p=L,q;
    int j=0;
    while(j<n-1&&p!=NULL)//注意删除代码停在删除元素的前面
    {
        j++;
        p=p->next;
    }
    if(p==NULL)
        return false;
     q=p->next;
     if(q==NULL)
        return false
     e=q->data;
     p->next=q->next;
     delete q;
     return true;  

}

记忆方法 建立两个指针，遍历到删除元素的前一个，用p指向删除元素，然后进行交换

2.7新的插入

bool insertnode(LinkNode *&L,int i,ch e)
{
     if(i<=0)
        return false;
    LinkNode *p=L,*s;
    int j=0;
    while(j<n&&p!=NULL)
    {
        j++;
        p=p->next;
    }
    if(p==NULL||p->next==NULL)
        return false;
    s=new LinkNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

记忆方法：创建一个新节点，类似头插法的方式插进去 

小作业 

#include <iostream>
using namespace std;
typedef char ch;
typedef struct LNode {
	ch data;
	struct LNode*next;//指针域：存放下一个节点的地址
} LinkNode;
//初始化
void InitList(LinkNode *&L) {
	L = new LinkNode;
	L->next = NULL;
}
//插入（尾插法）
void Insertlist(LinkNode *&L, ch a[], int n) { //传入想插入的数组(1,2,3,4),则此法插完后亦是（1,2,3，4）
	LinkNode *s, *r; //创建两个指针
	r = L; //r指向首节点L
	for (int i = 0; i < n; i++) {
		s = new LinkNode; //创建空间
		s->data = a[i]; //数据存储（值得注意的是s是指针）
		r->next = s; //r->next表示L的next指针域，其实就是赋值，将s的地址（s本身就是地址）赋给L的next域，相当于是L--s
		r = s; //然后将r指向s
	}
	r->next = NULL; //最后r指向末节，指针域为NULL
}
//输出
void Displaylist(LinkNode *L) {
	LinkNode *p = L->next; //这里注意一下，其实首节点是没有数据的，直接指向下一个节点打印
	while (p != NULL) {
		cout << p->data << "  ";
		p = p->next;
	}
	cout << endl << endl;
}
//输出长度
int Listlength(LinkNode *L) {
	int n = 0;
	LinkNode *p = L;
	while (p->next != NULL) {
		n++;
		p = p->next;
	}
	return n;
}
//判断是否为空
bool emptyelem(LinkNode *L) {
	if (L->next == NULL)
		return false;
	else
		return true;
}
//取值
bool Getelem(LinkNode *L, int n, ch &e) {
	if (n <= 0)
		return false;
	LinkNode *p = L;
	int j = 0;
	while (j < n && p != NULL) {
		j++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	e = p->data;
	return true;
}
//输出位置
int Locelem(LinkNode *L, ch e) {
	LinkNode *p = L->next;
	int j = 1;
	while (p != NULL && p->data != e) {
		p = p->next;
		j++;
	}
	if (p == NULL) {
		return 0;
	}

	return j;
}
//指定位置插入元素
bool insertlist(LinkNode *&L, int n, ch q) {
	if (n <= 0)
		return false;
	int j = 0;
	LinkNode *p = L, *s;
	while (j < n - 1 && p != NULL) {
		j++;
		p = p->next;
	}
	if (p==NULL||p->next == NULL)
		return false;
	else {
		s = new LinkNode;
		s->data = q;
		s->next = p->next;
		p->next = s;
		return true;
	}
}
//删除指定元素
bool Delem(LinkNode *&L, int n, ch &e) {
	if (n <= 0)
		return false;
	int j = 0;
	LinkNode *p = L, *q;
	while (j < n - 1 && p != NULL) {
		j++;
		p = p->next;
	}
	if (p == NULL)
		return false;
	q = p->next;
	if (q == NULL)
		return false;
	e = q->data;
	p->next = q->next;
	delete q;
	return true;
}
//释放
void Destroylist(LinkNode *&L) {
	delete L;
}

int main() {
	LinkNode *L1;
	InitList(L1);
	cout << "1.初始化单链表成功！！！" << endl << endl;
	//插入
	ch a[10] = {'a', 'b', 'c', 'd', 'e'};
	cout << "2.依次插入abcde." << "尾插法" << "    ";
	Insertlist(L1, a, 5);
	cout << "插入成功！！！" << endl << endl;
	//打印
	cout << "3.当前的单链表为：  ";
	Displaylist(L1);
	//输出长度
	int n = Listlength(L1);
	cout << "4.当前单链表的长度为：" << n << endl << endl;
	//判断链表是否为空
	cout << "5.当前链表";
	if (emptyelem(L1))
		cout << "不为空表" << endl << endl;
	else
		cout << "为空表" << endl << endl;
	//取值（输出元素）
	cout << "6.取值操作:";	int l;ch e;
	cout << "请输入您要取哪个位置的值：";cin >> l;
	if (Getelem(L1, l, e))
		cout << "取值成功！ " << "单链表第" << l << "位的元素是：" << e << endl << endl;
	else
		cout << "取值失败，您输入的位置" << l << "越界！！！" << endl << endl;
	//查找
	cout << "7.查找操作：";ch find;
	cout << "请输入您要查找的元素：  ";
	cin >> find;
	if (Locelem(L1, find) == 0)
		cout << "对不起，当前单链表中没有您查找的元素！！" ;
	else
		cout << "查找成功，您所查找的元素" << find << "在当前单链表的第" << Locelem(L1, find) << "位" ;
	cout<<endl<<endl;
	cout << "8.插入操作：";int k;ch q;
	cout << "请您输入一个数字和一个字符，代表在第几位插入一个字符：";cin >> k;cin >> q;
	if (!insertlist(L1, k, q))
		cout << "Warning:输入序号越界，插入失败！！！" << endl;
	else
		cout << "插入成功！！！" << endl << endl;
	cout << "9.当前单链表的元素有：";
	Displaylist(L1);
	cout << "10.删除操作：";int y;ch o;
	cout << "请您输入要删除的元素的序号：";cin >> y;
	if (!Delem(L1, y, o))
		cout << "对不起，您的输入的序号有误（越界），删除失败！" << endl << endl;
	else
		cout << "删除成功！成功删除第" << y << "个元素" << o << endl << endl;
	cout << "11.当前单链表的元素有：";Displaylist(L1);
	//释放
	cout << "12.销毁单链表：";Destroylist(L1);
	cout << "销毁成功！！！";
	return 0;
}

 全部失败的样例：9,p，8p，7

全部成功的样例：4，c，2p，6

所以建议大家自己打吧，看完上面的写这个代码就很轻松 

感谢您今天的捧场，敬请期待下次演出。 See you next  illusion.

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

吉时利keithley 2604B数字源表

吉时利keithley 2604B数字源表

181/2461/8938产品概述&#xff1a; Keithley 2604B 源表可让您比以前更快、更轻松、更经济地进行精密直流、脉冲和低频交流源测量测试。Keithley 2604B 的 IV 功能测试测试速度是竞争产品的两到四倍&#xff0c;其结合了&#xff1a; Keithley 的高速第三代源测量单元 (SMU)…
阅读更多...
Linux学习-进程

Linux学习-进程

目录 进程基本概念 进程相关命令 进程的创建 进程的调度 进程相关函数接口 进程的消亡 实例&#xff1a;创建九个子进程 目录 进程基本概念 进程相关命令 进程的创建 进程的调度 进程相关函数接口 进程的消亡 实例&#xff1a;创建九个子进程 exec函数…
阅读更多...
Typecho博客后台登陆界面美化

Typecho博客后台登陆界面美化

登录界面&#xff1a; 食用方法&#xff1a; 备份 admin 目录 压缩包内容上传到 admin 目录内。 结构:网站根目录 /admin/login.php 结构:网站根目录 /admin/style 修改 login.php 第35行&#xff0c;把“季春二九管理后台”替换成自己的信息 清理缓存&#xff0c;开始体验新的…
阅读更多...
罐头鱼AI矩阵获客批量混剪运营系统介绍

罐头鱼AI矩阵获客批量混剪运营系统介绍

罐头鱼AI矩阵——智能运营系统助力抖音视频创作 随着社交媒体的普及&#xff0c;视频内容创作成为了企业营销的重要手段。为了帮助您更高效地进行视频内容创作和发布&#xff0c;我们推出了罐头鱼AI矩阵&#xff0c;一款集智能混剪、关键词生成、发布管理等功能于一体的全新运营…
阅读更多...
交易的成功并非仅依赖于拥有强大的工具，而在于如何用好你的工具

交易的成功并非仅依赖于拥有强大的工具，而在于如何用好你的工具

任何领域伟大的成就往往源于个人不屈不挠地克服重重障碍的能力&#xff0c;这种毅力和决心并非普通人所具备&#xff0c;因此他们往往只能停留在普通和平凡的层面。 而对于那些渴望在交易领域取得卓越成就的人来说&#xff0c;坚持采用一套经过验证且有效的交易系统&#xff0c…
阅读更多...
ArtDD 一键下载 掘金、CSDN、开源中国、博客园文章 文章的Chrome 插件

ArtDD 一键下载 掘金、CSDN、开源中国、博客园文章 文章的Chrome 插件

有想一键下载博客园、掘金、CSDN、开源中国等博客自己的文章到本地的可以使用这个插件 插件会根据当前页面链接自动分辨出文章所属平台&#xff0c;可能有些文章详情链接是不支持的&#xff0c;例如博客园存在很多个版本的文章详情页链接格式&#xff0c;想要支持所有的链接是…
阅读更多...
设计模式之抽象工厂模式解析

设计模式之抽象工厂模式解析

抽象工厂模式 1&#xff09;问题 工厂方法模式中的每个工厂只生产一类产品&#xff0c;会导致系统中存在大量的工厂类&#xff0c;增加系统的开销。 2&#xff09;概述 a&#xff09;产品族 和 产品等级结构 产品等级结构&#xff1a;产品的继承结构&#xff1b; 产品族&…
阅读更多...
武汉星起航引领跨境电商新潮流，一站式孵化平台助力合作伙伴腾飞

武汉星起航引领跨境电商新潮流，一站式孵化平台助力合作伙伴腾飞

在全球经济一体化的大趋势下&#xff0c;跨境电商以其独特的优势逐渐成为连接各国市场的桥梁。随着市场竞争的加剧&#xff0c;传统的经营模式已难以满足日益复杂的业务需求&#xff0c;合作伙伴迫切需要更为全面、专业的指导和支持。正是在这样的背景下&#xff0c;武汉星起航…
阅读更多...
罐头鱼AI矩阵运营系统|视频批量混剪|矩阵获客

罐头鱼AI矩阵运营系统|视频批量混剪|矩阵获客

罐头鱼AI传单功能操作说明 个性化首页展示 登录状态一目了然灵活绑定账号数量快速查看最新上传视频素材和素材列表 抖音账号轻松绑定 明晰显示登录账号和已绑定账号灵活控制可绑定账号数量一键授权绑定抖音账号 账号管理列表 清晰管理查看绑定抖音账户列表 上传视频素材便捷管理…
阅读更多...
洛谷_P2678 [NOIP2015 提高组] 跳石头_python写法

洛谷_P2678 [NOIP2015 提高组] 跳石头_python写法

P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) d, n, m map(int,input().split())data [0] for i in range(n):value int(input())data.append(value) data.append(d)def check(mid):now 0cnt 0for i in range(1,n2):if abs(data[now]-da…
阅读更多...
Excel的数据分析工具

Excel的数据分析工具

Excel的数据分析工具 会生成新的工作簿 全选--数据透视表 插入切片器 使用作图工具 可以继续插入条件切片
阅读更多...
CodeMeter案例分享-工业自动化领域

CodeMeter案例分享-工业自动化领域

德国威步遵行于“完美保护、完美授权、完美安全”的企业宗旨&#xff0c;为各个领域的软件商、设备商的数字资产提供强有力的保护&#xff0c;有效防止软件盗版、逆向工程、代码篡改、恶意破坏以及商业间谍活动&#xff0c;帮助企业把全新的商业模式与业务流程完美整合并获得可…
阅读更多...
桌面日程安排软件，笔记本电脑常用软件有哪些？

桌面日程安排软件，笔记本电脑常用软件有哪些？

在如今快节奏的社会环境中&#xff0c;时间仿佛成了比金子还要珍贵的资源。我们每个人都像是一名指挥官&#xff0c;需调度好每一刻光阴&#xff0c;使其发挥最大效益。而在这场与时间的较量中&#xff0c;一款优秀的桌面日程安排软件就像您的私人助理&#xff0c;帮您精准规划…
阅读更多...
武汉星起航引领跨境电商新潮流，深耕亚马逊打造全方位合作新模式

武汉星起航引领跨境电商新潮流，深耕亚马逊打造全方位合作新模式

在全球化的浪潮下&#xff0c;跨境电商已成为连接各国市场的重要桥梁&#xff0c;为无数企业带来了前所未有的发展机遇。在这一领域&#xff0c;武汉星起航电子商务有限公司以其独特的战略眼光和实战经验&#xff0c;成为引领行业发展的佼佼者。公司自2017年起便深耕亚马逊平台…
阅读更多...
应用案例 | 基于三维机器视觉的销轴销套深框抓取上料解决方案

应用案例 | 基于三维机器视觉的销轴销套深框抓取上料解决方案

随着科技的不断发展&#xff0c;机器人技术不断革新&#xff0c;并逐渐渗透到各行业的各个环节。在机器人技术的帮助下&#xff0c;各行业的生产力不断增强&#xff0c;生产效率也得到了极大的提高。 销轴销套深框抓取是指在机械装配或生产过程中&#xff0c;对销轴和销套进行抓…
阅读更多...
【数据可视化】Echarts官方文档及常用组件

【数据可视化】Echarts官方文档及常用组件

个人主页 &#xff1a; zxctscl 如有转载请先通知 文章目录 1. 前言2. Echarts官方文档介绍3. ECharts基础架构及常用术语3.1 ECharts的基础架构3.2 ECharts的常用术语3.2.1 ECharts的基本名词3.2.2 ECharts的图表名词 4. 直角坐标系下的网格及坐标轴4.1 直角坐标系下的网格4.2…
阅读更多...
今日问题：动态分配内存出错

今日问题：动态分配内存出错

2024.3.22 在搜素了许多文章和查阅了许多博客后依然没有找到问题所在&#xff0c;最后无意之间翻看以前的关于动态内存管理的代码后发现&#xff1a; 没加头文件&#xff1a;#include<stdlib.h> 苦笑不得了属于是 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio…
阅读更多...
漏洞挖掘技术综述与人工智能应用探索：从静态分析到深度学习，跨项目挑战与未来机遇

漏洞挖掘技术综述与人工智能应用探索：从静态分析到深度学习，跨项目挑战与未来机遇

在网络安全和软件工程领域中&#xff0c;将机器学习应用于源代码漏洞挖掘是一种先进的自动化方法。该过程遵循典型的监督学习框架&#xff0c;并可细化为以下几个关键步骤&#xff1a; 数据预处理&#xff1a; 源代码解析与清理&#xff1a;首先对源代码进行文本解析&#xff…
阅读更多...
mysql 如何设计分库分表

mysql 如何设计分库分表

在MySQL中设计分库分表的方法通常涉及到水平拆分与垂直拆分两种主要方式。 水平拆分&#xff1a; 按照某一列进行水平拆分&#xff1a; 可以根据某一列&#xff08;如用户ID、时间等&#xff09;的取值范围将数据拆分到不同的数据库或表中。基于哈希值的水平拆分&#xff1a;…
阅读更多...
广告增量实时索引构建实践

广告增量实时索引构建实践

本期作者 1.前言 在广告检索系统中&#xff0c;增量索引&#xff08;实时索引&#xff09;是一类常见的技术&#xff0c;用于使广告信息的变更及时生效。其中一种主要的思路即由检索系统消费广告更新数据流&#xff0c;实时更新内存索引&#xff0c;对此行业中已有很多优秀方案…
阅读更多...
最新文章

Copyright @ 2022~2023