投稿
  1. 首页
  2. java

链表-通俗易懂-我写的很认真呀

code • 2022-4-28 • java • 阅读 55

链表-通俗易懂-我写的很认真呀,第1张

链表 一般链表 链表的建立

三个人去电影院看电影,

电影院没人之前,门卫就只知道电影院就老板一人

门卫登记了来往电影院的顾客,门卫的功能主要是给进来的人安排位置

然后把来往人员的名册给了老板,老板的功能主要是看电影院有多少人

来的人一般很多,门卫只是记得谁最后一个进来

老板也不想记住那么多,就只对第一个进来印象深刻

但是电影院的座位都差不多坐起了,没有挨在一起的连续3个位置,于是他们只能分开做坐

门卫分别给3个人安排了位置

A同学对B同学说:“我记住你的位置了,电影结束后我去找你”,A同学记住了B同学的位置

B同学对C同学说:“我记住你的位置了,电影结束后我去找你”,B同学记住了C同学的位置…

通过这种记忆方式减少了记忆力的损耗

星星代表了位置有人,其它是暂时没有人的空位子

这里涉及了数据类型:

(人物名字+位置编号)的一个结构体类型

(老板结构体+门卫结构体指针,)的类型

typedef struct cinema
{
	string name;
	cinema* Position;
	cinema()
	{
		name = "YOur name";
		Position = NULL;
	}	
}s_type,*Location;

typedef struct safe
{
	s_type boss;
	Location Guard;
	safe()
	{
		boss.name = "Boss";
		Guard = &boss;
	}
}safe;

在C语言里面,位置的安排需要动态内存分配

电影院老板和门卫是一个不变的常亮,一开始就定义

C语言里面称之为头指针,寻址指针

typedef struct cinema
{
	string name;
	cinema* Position;
	cinema()
	{
		name = "YOur name";
		Position = NULL;
	}	
}s_type,*Location;

string name;是人物的名字,在链表里面叫节点指向的值

cinema* Position;是A同学脑中有关B同学的位置信息,在链表里面叫next节点指针

然后里面有个初始化的函数

typedef struct safe
{
	s_type boss;
	Location Guard;
	safe()
	{
		boss.name = "Boss";
		Guard = &boss;
	}
}safe

这是一个老板和,门卫的结构体

门卫室一个指针变量,负责安排位置和记录来往的人

链表建立

用到的函数

int In(safe& check,string b_name)
{ 
	Location new_friend = new cinema;	//C++
	//s_xy new_friend =(s_xy)calloc(1,sizeof(Appointment_schedule));	//C
	if (new_friend == NULL)
		return -1;  ///没有位置可以坐了

	new_friend->name = b_name; //新的位置是名字叫b_name的
	new_friend->Position = NULL; //新来的都坐最后面,只要你不是VIP的插入方式
	check.Guard->Position= new_friend; //门卫喊上一人记住新来的位置
	check.Guard= new_friend;//门卫记住新来的位置

	return 1;
}

vs2022调试

可以看到,小帅记住小美的位置

小美记住记住小花的位置,

小花记住NULL

上面我们是用的引用的方式

为什么是引用??? 可以简化代码,如果不用引用就错了,除非你用指针

关于为什么要加==&==,首先你用的是是参数chekc一个结构体

如果不用引用,你传递过去的是一个check结构体的副本

你在对副本 *** 作

但是副本与原本有什么区别呢???

所以上面用引用的方式对Guard的修改才会影响到父本的成员

如果电影院没位置了,就分配失败

链表的删除

假设要走一个人

只要B同学不是最后一个走的人,他就不会被门卫发现

如果他要走,先给老板一声,再就给门卫说一声,然后那个位置就空着了

门卫就把走的那个人的上一位给记住,李四走了,那么门卫就记住张三的位置

下一次给新来一个顾客,就分配位置在张三旁边

这里会修改Guard的值,那么要用节引用或者指针

这里会修改Boss的值,那么要用节引用或者指针

第一个人或者后面的人要走

老板就会翻看花名册,第一个人是刘一,第二个是陈二,然后张三,李四,王五

然后一个一个往下看,如果老本要查看王五,他就必须找到上一个李四,因为李四后面是王五

它无法一次性看到王五,因为他只记得第一个人,从第一个人人往下翻看遍历

B同学要走了,B同学给老板说一声

为了做的妥妥当当,他就告诉A同学,你不要记住我的位置了,你去记住C同学的位置,然后我就溜了

B同学那个位置就空了,待会有人来就坐B同学那个位置,

如果电影院一个人都没有,那么就不可能出现溜人的情况

int Out(safe& check, string who)
{

	Location note_pad = &check.boss; //老板一个一个的翻看花名册
	Location obj; //要清空的那个位置
	if (check.Guard == NULL) //如果电影院一个人都没有,那么就不可能出现溜人的情况
		return -1;

	while (1)
	{
		if (note_pad->Position->name.compare(who) == 0) //查找花名册上有没有那个人
		{
			obj = note_pad->Position; //找到了张三在 最新的note_pad上,然后要删除李四note_pad->Position
			if (obj->Position != NULL) //如果不是最后一个人,就不需要通知门卫
				note_pad->Position = note_pad->Position->Position; //B新同学告诉A同学你去记住C同学的位置
			else
			{//最后一个人要走
				note_pad->Position = NULL; //C要走了,B同学也就不需要记住谁谁的位置了,就记住NULL就可以了
				check.Guard = note_pad;   //门卫就记住了B同学的位置
			}
			delete obj;//清空位置
			return 1;
		}
		note_pad = note_pad->Position;//没找到就继续翻看下一个
		if (note_pad == NULL) //翻看到最后一个都还是没找到,那就没有这个人
			break;
	}
	return -1;
}
链表的尺度计数

老板看一下电影院的位置和花名册的名单,

第一个是刘一,他被老板记住了,他的位置在xxxx处

第二个陈二,他在刘一后面,他的位置是xxxx

第三个是张三,他在陈二后面,他的位置是xxxx

…

第十个是郑十,它后面没有人

int Get_lentgth(safe check)
{
	int len = 0;

	Location b_ptr = &check.boss; //老板翻看花名册,看电影院的位置
	while (b_ptr->Position != NULL)//第十个是郑十,它后面没有人
	{
		len++;
		b_ptr = b_ptr->Position;//第一个..第二个..第三个是
	}
	return len;
}
链表的插入

新来一个VIP的插入

如果你是插在最后一个位置,那就相当于没有插入,直接进是链表的建立模式,VIp就浪费了

如果你插入在空号的位置,对不起,你必须要么在前面,要么在最后面

空的位置等价于最后一个位置

如果你插在前面那个位置,你就告诉老板,我要插在5号位置后面

老板就翻看花名册,一个一个的看,看5号是谁,然后告诉5号,你就记住新来的顾客的位置,然后告诉VIP用户

你记住原来6号的位置就可以了,然后你就是6号了,原来6号就是7号了

int Rush_in(safe& check,string b_name,int index)
{
	int i ;
	s_xy ptr=&check.boss;
	s_xy temp = NULL;
	int len=Get_lentgth(check);

	if (index >= len) //插在空的位置或者最后一个位置
	{
		In(check, b_name);
		return 1;
	}
		

	for (i=0; i < index; i++) //假设插在2号位置后面,boss翻看刘一,i=1,翻看陈二,i=2,循环结束
		ptr = ptr->xy;
    
	temp = ptr->xy; //临时记录一下陈二后面那个人的位置,也就是张三
	ptr->xy = new Appointment_schedule; //新安排一个VIP位置,陈二就记住VIP位置
	ptr->xy->name = b_name;//VIP位置属于b_name的
	ptr->xy->xy = temp; //VIP记住张三的位置

	return 1;
}

为什么要用引用,我们不是对副本的指针 *** 作吗?

确实是,但是VIp插在0后位置后面的话,那么就会修改Boss的指向,也就是Boss记住VIP的位置,VIP记住刘一的位置

所以会修改父本的结构体,这里就要用到引用

链表的清空

如果电影院一个人都没有那就不需要清空

清空的话,要通知老板,通知门卫

老板看一下刘一,记住陈二,用笔划掉刘一名字

老板看一下陈二,记住张三的位置,用笔划掉陈二的位置

…

知道老板看一下郑十的位置,发现后面没人了,就请郑十,然后结束了

int over(safe& check)
{

	if (check.Guard == NULL) //如果电影院一个人都没有那就不需要清空
		return -1;
	s_xy obj = check.boss.xy; //老板打开花名册,然后记住看一下要划掉谁
	s_xy local =obj->xy;	//老板记住记住下一个要被划掉的是谁待会就划掉它
	while (1)
	{
		if (local == NULL) //下一个位置没人
		{
			delete obj;//字节划掉最后一个记住的名字
			break;//清空结束
		}
		delete obj; //划掉我看到的人
		obj = local;//看一下我要划掉谁
		local = local->xy;//记住下一个我要划掉谁
        //如果不这样做,老板就不知道把谁给划掉了
	}
	check.Guard =  &check.boss;
	check.boss.xy =NULL;
    //电影院除了老板就没人了
	return 1;
}

终极版本

#include
#include
#include
using namespace std;


typedef struct cinema
{
	string name;
	cinema* Position;
	cinema()
	{
		name = "YOur name";
		Position = NULL;
	}	
}s_type,*Location;

typedef struct safe
{
	s_type boss;
	Location Guard;
	safe()
	{
		boss.name = "Boss";
		Guard = &boss;
	}
}safe;

int In(safe& check,string b_name)
{ 
	Location new_friend = new cinema;	//C++
	//s_xy new_friend =(s_xy)calloc(1,sizeof(Appointment_schedule));	//C
	if (new_friend == NULL)
		return -1;

	new_friend->name = b_name;
	new_friend->Position = NULL;
	check.Guard->Position= new_friend;
	check.Guard= new_friend;

	return 1;
}

int Out(safe& check, string who)
{

	Location note_pad = &check.boss;
	Location obj;
	if (check.Guard == NULL)
		return -1;

	while (1)
	{
		if (note_pad->Position->name.compare(who) == 0)
		{
			obj = note_pad->Position;
			if (obj->Position != NULL)
				note_pad->Position = note_pad->Position->Position;
			else
			{
				note_pad->Position = NULL;
				check.Guard = note_pad;
			}
			delete obj;
			return 1;
		}
		note_pad = note_pad->Position;
		if (note_pad == NULL)
			break;
	}
	return -1;
}
int Get_lentgth(safe check)
{
	int len = 0;

	Location b_ptr = &check.boss;
	while (b_ptr->Position != NULL)
	{
		len++;
		b_ptr = b_ptr->Position;
	}
	return len;
}
int Rush_in(safe& check,string b_name,int index)
{
	int i ;
	Location ptr=&check.boss;
	Location temp = NULL;
	int len=Get_lentgth(check);

	if (index >= len)
	{
		In(check, b_name);
		return 1;
	}
		

	for (i=0; i < index; i++)
		ptr = ptr->Position;
	temp = ptr->Position;
	ptr->Position = new cinema;
	ptr->Position->name = b_name;
	ptr->Position->Position = temp;

	return 1;
}
int over(safe& check)
{

	if (check.Guard == NULL)
		return -1;
	Location obj = check.boss.Position;
	Location local =obj->Position;
	while (1)
	{
		if (local == NULL)
		{
			delete obj;
			break;
		}
		delete obj;
		obj = local;
		local = local->Position;
	}
	check.Guard = &check.boss;
	check.boss.Position = NULL;
	return 1;
}
int main()
{
	safe check;
	In(check, "刘一");
	In(check, "陈二");
	In(check, "张三 ");
	In(check, "李四");
	In(check, "王五");

	Out(check, "刘一");

	In(check, "赵六 ");
	In(check, "孙七");
	In(check, "周八");
	In(check, "吴九");

	Out(check, "周八");

	In(check, "郑十");
	Out(check, "郑十");

	Rush_in(check, "小美", 0);
	Rush_in(check, "小明", 4);
	Rush_in(check, "小明",20);

	over(check);

	return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/736501.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-28
下一篇 2022-04-28

发表评论

登录后才能评论

评论列表（0条）

保存