数据结构：链表（洛谷P3613题解）

一、链表的特点

链表可以用来处理数据下标不连续，数据长度动态增加的情况。
常见的有单向链表、双向链表和环形链表，本文记载单向链表的实现。
单向链表中，有显式的域，data用来存储该节点的数据，next指针指向下一个节点的地址，节点地址就是该节点在内存中的地址。

二、链表的实现

本文中采用c++实现链表的基本结构。
1.节点的基本结构

struct Node{
	int data;//数据类型根据需要更改
	Node *next;//指向下一个节点的指针。
}

2.插入节点至链表的结尾

#include <bits/stdc++.h>
using namespace std;
struct Node{
	int data;//数据类型根据需要更改
	Node *next;//指向下一个节点的指针。
};
Node *head,*p,*r;//链表的头、当前、尾指针
int x;
int main(){ 
	cin>>x;
	head=new Node;
	r=head;
	while(x!=-1){//输入-1代表输入结束
		p=new Node;
		p->data=x;
		p->next=NULL;
		r->next=p;
		r=p;
		cin>>x; 
	}
	
	return 0;
}

3.查询链表中的元素

while（p->next!=NULL）{
	if(p->date==target){
		cout<<"查询到结果“<<endl;
	}
}

三、非典型例子

洛谷：P3613 【深基15.例2】寄包柜
https://www.luogu.com.cn/problem/P3613
采用如下链表配合数组实现，每一个柜子用一个链表存储（链表内部根据柜子编号升序排列，提高查找效率），柜子的根节点存在一个数组中，方便后期查找，

#include<bits/stdc++.h>
using namespace std;
struct Node {
	int index;
	int value;
	Node *next;
} a[100001];
Node *head,*p,*r;

int main() {
	int n,q;
	int operate,obj,index,value;//操作、格子对象、插入（查询）位置 、插入的值
	cin>>n>>q;
	for(int i=1; i<=n; i++) {
		a[i].next=NULL;
	}

	for(int i=1; i<=q; i++) {
		cin>>operate;
		if(operate==1) {//插入
			//插入时，先判断该索引位置是否有元素，有-》判断插入value值是否为空，空-》删除该节点 ；
			//index从小往大了增加 ；
			//相同位置插入，替换节点
			cin>>obj>>index>>value;
			//生成一个新节点
			p=new Node;
			p->next=NULL;
			p->index=index;
			p->value=value;
			bool flag=false;//定义是否已经查入过节点了
			//插入点初始化为数据根节点
			r=&a[obj];
			//判断是否有下一个节点
			while(r->next!=NULL&&r->next->next!=NULL) {
				//移动插入点到下一个节点
				Node *father,*son;
				father = r;
				r=r->next;
				son=r->next;
				//如果插入点节点的index==当前新输入的index,替换该节点
				if(r->index==index) {
					//输入的节点值为0，需要删除插入点节点
					if(p->value==0) {
						//删除节点,把下一个节点连接到当前节点的父亲节点。
						father->next=r->next;
					} else {
						r->value=value;
					}
					flag=true;
					break;
				} else if(p->index>r->index&&son->index>p->index) {
					//插入点在当前节点和下一个节点的中间
					p->next=son;
					r->next=p;
					flag=true;
					break;
				} else if(p->index<r->index) {
					p->next=r;
					father->next=p;
					flag=true;
					break;
				}
			}
			if(!flag) {

				if(r->next!=NULL) {
					r=r->next;
				}
				if(r->index==p->index){
					r->value=p->value;
				}else{
					r->next=p;
				    flag=true;
				}
				
			}

		} else {
			cin>>obj>>index;
			Node *node=&a[obj];
			while(node->next!=NULL) {
				node=node->next;
				if(node->index==index) {
					printf("%d\n",node->value);
					break;
				}
			}
		}

	}

//查看链表结构
//	Node *temp;
//	for(int i=1; i<=20; i++) {
//		temp=&a[i];
//		printf("第%d个链表：",i);
//		while(temp->next!=NULL) {
//			temp=temp->next;
//			printf("[元素%d，值%d] ",temp->index,temp->value);
//
//		}
//		printf("\n");
//	}

	return 0;
}