1.24学习总结

学习了数据结构链表

总结一下线性表的一些操作：
第一点创建一个线性表，就是定义一个结构体类型的变量，里面可以存数据和线性表当前的长度
第二点，读取线性表里面的元素
第三点插入和删除元素，插入元素主要在于实现元素后移的情况，把要插入元素位置后面的元素都后移一位
删除元素主要在于覆盖，把删除元素之后的元素向前覆盖一位?
线性表的优点：访问快，使用方法简单
缺点：需要连续的空间，访问较慢?

和typedef的运用

// typedef的运用 
typedef struct Student{
	int a;
}Stu1;//这里直接建立了一个结构体的类型 
//由于定义的是类型，所以在还需要创建一个结构体的类型
Stu1 stu1; 
//然后才能访问
stu1.a; 
struct Student{
	int a;
}Stu2;//这里定义的是一个结构体的变量 
//而这里由于是变量，所以可以直接访问
Stu2.a; 

模拟了一遍单链表的实现（手敲版），也使用STL容器实现了一遍

题目描述https://www.lanqiao.cn/problems/1110/learning/?page=1&first_category_id=1&problem_id=1110

小王子有一天迷上了排队的游戏，桌子上有标号为?1?101?10?的?1010?个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把那个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了?�M?次，每次都是选取标号为?�X?个放到最前面，求每次排完后玩具的编号序列。

要求一：采用单链表解决

输入描述

第一行是一个整数?�M，表示小王子排玩具的次数。

随后?�M?行每行包含一个整数?�X，表示小王子要把编号为?�X?的玩具放在最前面。

输出描述

共?�M?行，第?�i?行输出小王子第?�i?次排完序后玩具的编号序列。

输入输出样例

示例 1

输入

5
3
2
3
4
2

输出

3 1 2 4 5 6 7 8 9 10
2 3 1 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

这道题目就是简单的模拟链表，包括链表的建立，删除和头部插入

（手敲链表）这里是用new函数创建链表

#include<bits/stdc++.h>
#include <iostream>
using namespace std;
struct Node{
	int data;
	Node* next;
};
typedef Node* Nodeptr; 
int main()
{
	//建立链表（问题1，我应该如何把数据放到链表里面）
	//尾插法 
	Nodeptr head=NULL;
	for (int i=10;i>=1;--i)
	{
		Nodeptr newNode=new Node{i,head};
		head=newNode;
	}
	int m,n;
	cin>>m;//输入摆放次数
	for (int i=0;i<m;++i)
	{
		cin>>n;
		Nodeptr point=head;
		Nodeptr prev=NULL;
		while (point->data!=n && point!=NULL)
		{
			prev=point;
			point=point->next;
		}
		prev->next=point->next;
		point->next=head;
		head=point;
		Nodeptr position=head;
		for (int j=0;j<10;++j)
		{
			cout<<position->data<<" ";
			position=position->next;
		}
		cout<<endl;
	} 
	return 0;
}

//这里是用malloc函数创建但链表
#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
	int data;
	Node *next;
}Node;
*Node addNode(Node* head,int i)
{
	Node* newNode=(Node*)malloc(sizeof(Node));
	newNode->data=i;
	newNode->next=head;
	return newNode;
}
int main()
{
	Node* head=NULL;
	for (int i=0;i<10;++i)
	{
		head=addNode(head,i);
	}
}

（STL容器之list）

#include<bits/stdc++.h>
using namespace std;
void print(list<int >l)
{
	for (list<int >:: iterator it =l.begin();it!=l.end();++it)
	{
		cout<<*it<<" ";
	}
	cout<<endl;
}
int main()
{
	list<int>l;
	for (int i=1;i<=10;++i)
	{
		l.push_back(i);
	}
	int m,n;
	cin>>m;
	for (int i=0;i<m;++i)
	{
		cin>>n;
		l.remove(n);
		l.push_front(n);
		print(l);
	}
	return 0;
}

对比链表和线性表：

第一点：线性表在空间的分配上是连续的，而链表是不连续的

第二点：在查找上，线性表所需要的时间是O（1）而链表是O（n），线性表具有优势，而在插入和删除方面，线性表需要移动表中的其它元素来达到效果，因此需要O（n）的时间，而链表只需要改变节点之间的关系所以是O（1）

第三点：链表的空间不需要提前分配，元素个数不受限制

链表的其它形式与单链表的区别：

循环链表与单链表：区别在于循环链表的最后一个节点是指向头结点的

单链表与双向链表：区别就在于双向链表有两个指针，一个前驱指针，一个后继指针

题：https://www.luogu.com.cn/problem/B3631

题目描述

实现一个数据结构，维护一张表（最初只有一个元素?11）。需要支持下面的操作，其中?�x?和?�y?都是?11?到?106106?范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于?105105：

• 1 x y?：将元素?�y?插入到?�x?后面；
• 2 x?：询问?�x?后面的元素是什么。如果?�x?是最后一个元素，则输出?00；
• 3 x：从表中删除元素?�x?后面的那个元素，不改变其他元素的先后顺序。

输入格式

第一行一个整数?�q?表示操作次数。

接下来?�q?行，每行表示一次操作，操作具体间题目描述。

输出格式

对于每个操作 2，输出一个数字，用换行隔开。

输入输出样例

输入 #1复制

6
1 1 99
1 99 50
1 99 75
2 99
3 75
2 1

输出 #1复制

75
99

思路：相比手敲链表，这里用STL可能会更快一点，分析题目可以知道，这边有三种情况，插入输出和删除，同时也需要知道一点就是，insert函数是有返回值的，会返回插入元素的迭代器。

核心想法就是把每一个值的位置用pos存储，这样方便查找，把查找的时间从O（n）变成O（1）

#include<bits/stdc++.h>
using namespace std;
list<int>::iterator pos[1000005];
int main()
{
	list<int>l;
	int n;
	pos[1]=l.insert(l.end(),1);
	cin>>n;
	for (int i=0;i<n;++i)
	{
		int a;
		cin>>a;
		if (a==1)
		{
			int x,y;
			cin>>x>>y;
			list<int>::iterator temp=pos[x];
			pos[y]=l.insert(++temp,y);
		}
		else 
		{
			int x;
			cin>>x;
			if (a==2)
			{
				list<int>::iterator temp=pos[x];
				if (++temp!=l.end())
				{
					cout<<*temp<<endl;
				}
				else cout<<0<<endl;
			}
			if (a==3)
			{
				list<int>::iterator temp=pos[x];
				if (++temp!=l.end())
					l.erase(temp);
			}
		}	
	}
	return 0;
}