前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ACM刷题之路(十三)数据结构——链表

ACM刷题之路(十三)数据结构——链表

作者头像
Designer 小郑
发布2023-07-31 15:43:23
1510
发布2023-07-31 15:43:23
举报
文章被收录于专栏:跟着小郑学JAVA跟着小郑学JAVA

顺序表之后是链表,链表是线性表的第二种结构。

(单)链表根据《数据结构》这本书 需要会写初始化、插入、查找、删除、取长度的函数。

首先是结构体的定义:

链表的每一个节点由本身的数据、下一个节点的地址组成。

typedef的意思是取别名。把lei这个小名 给int  修改线性表数据类型的时候可以直接改动

代码语言:javascript
复制
typedef int lei;
struct ss
{
	lei data;
	ss *next;
};

第一个是初始化函数。这里写的是有头指针的链表,所以只需要new一个头结点,让头结点的next指向NULL。

代码语言:javascript
复制
ss* chushihua()
{
	ss*L=new ss;
	L->next=NULL;
	return L;
}

第二个是取长度函数。只要让一个临时指针指向头指针,然后一直遍历下去就好了,最终返回链表的长度。

代码语言:javascript
复制
int size(ss* L)
{
	int len=0;
	while(L->next !=NULL)
	{
		L=L->next;
		len++;
	}
	return len;
}

第三个是查找函数,根据书的要求,有两种查找函数,其一是根据编号来查找。

可以让L指针一直遍历下去,当L的下一个节点为空节点或者到达所需要的编号停止。

如果这个时候L不为空切cnt==所需要的序号,就说明该节点存在,返回即可;否则返回空指针表示不存在。

代码语言:javascript
复制
ss* find_num(ss *L,int xuhao)
{
	int cnt=0;
	while(L->next!=NULL && cnt<xuhao)
	{
		L=L->next;
		cnt++;
	}
	if(cnt==xuhao && L) return L;
	return NULL;
}

其二是根据值查找,这个就比较无脑了,一直遍历下去,直到找到或者找到结尾,如果找到就会返回,没找到也会自然而然的返回空指针。

代码语言:javascript
复制
ss* find_data(ss* L,lei data)
{
	L=L->next;
	while(L && L->data!=data)
	{
		L=L->next;
	}
	return L;
}

第四个是插入函数。先查找这个位置是否可以查,如果存在该位置的前一个为空的情况,就返回错误。

否则new一个新节点,新的节点的下一个指向现在n-1的节点的下一个,让现在n-1的节点指向新的节点,就这样转接完成,返回true。

代码语言:javascript
复制
bool charu(ss* L,lei data,int weizhi)
{
	ss *a;
	ss *b=L;
	int cnt=0;
	while(b && cnt < weizhi - 1 )
	{
		b=b->next;
		cnt++;
	}
	if(b==NULL||cnt!=weizhi - 1)
	{
		cout<<"插入位置错误"<<endl;
		return false;
	}
	a=new ss;
	a->data=data;
	a->next=b->next;
	b->next=a;
	return true;
}

第五个是删除函数。

先找到需要删除节点的前一个位置,如果发现要删除的节点不存在,则返回false。

如果存在,让删除节点的前一个节点的next指向需要删除节点的next,然后把需要删除的节点释放掉就可以了。

代码语言:javascript
复制
bool shanchu(ss *L,int weizhi)
{
	ss *a;
	ss *b=L;
	int cnt=0;
	while(b && cnt<weizhi-1)
	{
		b=b->next;
		cnt++;
	}
	if(b==NULL ||b->next == NULL|| cnt!=weizhi - 1)
	{
		cout<<"删除错误"<<endl;
		return false;
	}
	a=b->next;
	b->next = a->next;
	free(a);
	return true;
}

接下来是全部代码:

代码语言:javascript
复制
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef int lei;
struct ss
{
	lei data;
	ss *next;
};
ss* chushihua()
{
	ss*L=new ss;
	L->next=NULL;
	return L;
}
int size(ss* L)
{
	int len=0;
	while(L->next !=NULL)
	{
		L=L->next;
		len++;
	}
	return len;
}
ss* find_num(ss *L,int xuhao)
{
	int cnt=0;
	while(L->next!=NULL && cnt<xuhao)
	{
		L=L->next;
		cnt++;
	}
	if(cnt==xuhao && L) return L;
	return NULL;
}
ss* find_data(ss* L,lei data)
{
	L=L->next;
	while(L && L->data!=data)
	{
		L=L->next;
	}
	return L;
}
bool charu(ss* L,lei data,int weizhi)
{
	ss *a;
	ss *b=L;
	int cnt=0;
	while(b && cnt < weizhi - 1 )
	{
		b=b->next;
		cnt++;
	}
	if(b==NULL||cnt!=weizhi - 1)
	{
		cout<<"插入位置错误"<<endl;
		return false;
	}
	a=new ss;
	a->data=data;
	a->next=b->next;
	b->next=a;
	return true;
}
bool shanchu(ss *L,int weizhi)
{
	ss *a;
	ss *b=L;
	int cnt=0;
	while(b && cnt<weizhi-1)
	{
		b=b->next;
		cnt++;
	}
	if(b==NULL ||b->next == NULL|| cnt!=weizhi - 1)
	{
		cout<<"删除错误"<<endl;
		return false;
	}
	a=b->next;
	b->next = a->next;
	free(a);
	return true;
}
int main()
{
	ss *L=chushihua();
	cout<<"该链表的长度为:"<<size(L)<<endl;
	charu(L,1,1);
	charu(L,3,2);
	charu(L,5,3);
	cout<<"该链表的长度为:"<<size(L)<<endl;
	cout<<"编号为1的元素的地址:"<<find_num(L,1)<<endl;
	cout<<"编号为2的元素的地址:"<<find_num(L,2)<<endl;
	cout<<"值为3的元素的地址  :"<<find_data(L,3)<<endl;
	cout<<"该链表的长度为:"<<size(L)<<endl;
	cout<<"删除最后一个元素   "<<endl;
	shanchu(L,3);
	cout<<"该链表的长度为:"<<size(L)<<endl;
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-11-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档