算法知识-13-链表

链表的概念

链表是一种内存中非连续（或连续）的存储结构，通过指针链接其中的结点来实现串联。链表中的结点由两部分组成，一部分存放数据，另一部分存放指针。

一个节点两部分内容，那我们就要想到，一个元素，多种属性，这不就是结构体了
以上是一个结点，我们往往会遇到很多结点
一般对链表的操作就是插入与删除

链表插入

创建一个链表，按顺序存储1~5数字。在数字n前（1<n≤5）插入数字m(1<m<2
31
)，从首结点依次输出链表中的数据。

输入描述

一行两个整数，分别表示n和m。

输出描述

从首结点依次输出链表中的数据，数字之间空格分隔。

样例输入 1

3 9
样例输出 1

1 2 9 3 4 5

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data;
	node *next;
};
int main()
{
	node a = {1,NULL};
	node b = {2,NULL};
	node c = {3,NULL};
	node d = {4,NULL};
	node e = {5,NULL};
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	int n;
	node f;
	cin>>n>>f.data;
	node *p = &a;
    while(p!=NULL)
    {
        if(p->next->data==n)
        {
            f.next=p->next;
            p->next=&f;
            break;
        }
        p=p->next;
    }
    p = &a;
	while(p!=NULL)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	return 0;
}

链表删除

创建一个链表，按顺序存储1~5数字。删除含有数字n的结点(1<n≤5)，从链表首结点依次输出链表中的数据。

输入描述

一个整数表示n。

输出描述

从首结点依次输出链表中的数据，数字之间空格分隔。

样例输入 1

3
样例输出 1

1 2 4 5

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data;
	node *next;
};
int main()
{
	node a = {1,NULL};
	node b = {2,NULL};
	node c = {3,NULL};
	node d = {4,NULL};
	node e = {5,NULL};
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	int n;
	cin>>n;
	node *p = &a;
    while(p!=NULL)
    {
        if(p->next->data==n)
        {
            p->next=p->next->next;
            break;
        }
        p=p->next;
    }
    p = &a;
	while(p!=NULL)
	{
		cout<<p->data<<" ";
		p = p->next;
	}
	return 0;
}

示例题目

2923 3的倍数

小童想输入一些数字，输入-1停止输入。统计在这些数字中3的倍数有哪些，请你帮小童完成代码吧。

输入描述

一行，一些整数数字，最后一个数字为-1。

输出描述

一行，能被3整除的数字。

样例输入 1

1 2 3 4 5 6 7 8 9 -1
样例输出 1

3 6 9

这个题不用链表那是轻轻松松就过了，我们来看链表怎么做【作为链表的辅助练习】

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data;
	node *next;
}*head,*tail,*p;
int main(){
	int n;
	node *head = NULL, *tail = NULL;
	while(true){
		cin>>n;
		if(n==-1)	break;
		p=new node;
		p->data=n;
		p->next=NULL;
		tail->next=p;
		tail=p;
	}
	p=head;
	while(p->next!=NULL){
		p=p->next;
		if(p->data%3==0)	cout<<p->data<<' ';
	}
	return 0;
}

2921 统计个数

小鹿想输入一些整数数字，输入-1停止输入。在输入一个数字n，统计在这些数字中，n出现了多少次。请你编写代码帮助小鹿实现吧。

输入描述

共2行，第一行，一些整数数字，最后一个数字为-1。第二行，一个整数n，表示要查找的数字。

输出描述

一个整数，表示n出现的次数。

样例输入 1

6 1 2 3 4 6 5 3 3 2 1 3 -1
3
样例输出 1

4
这个题主要考的链表元素的查询，就用模板套就可以啦

#include<iostream>
using namespace std;
struct node{
	int data;
	node *next;
}*head,*tail,*p;
int main(){
	int n;
	tail=head=new node;
	while(true){
		cin>>n;
		if(n==-1)	break;
		p=new node;
		p->data=n;
		tail->next=p;
		p->next=NULL;
		tail=p;
	}
	int m,ans=0;
	cin>>m;
	p=head;
	while(p->next!=NULL){
		p=p->next;
		if(m==p->data)	ans++;
	}
	cout<<ans;
	return 0;
}