ACM刷题之路（十三）数据结构——链表

秒速五厘米 2023-10-21 07:53 42阅读 0赞

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

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

首先是结构体的定义：

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

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

typedef int lei;
    struct ss
    {
    	lei data;
    	ss *next;
    };

--------------------

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

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;
    }

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

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

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

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;
    }

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

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

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，然后把需要删除的节点释放掉就可以了。

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;
    }

接下来是全部代码：

#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;
    }