【数据结构】链表

单链表操作

• 插入： 传入表头，待插入的值，插入的位置。其中位置 表示原链表第 到 之间，也可以理解为新插入的数占据原链表的 位置，然后原 位置及以后要向后移。
  • 算法流程： ①判边界：由上定义，边界值 表示头节点和第一个节点的中间插入，边界值 Head->data+1 表示在最后一个元素之后插入一个数
    ②表头表示链表大小的数据域Head->data++
    ③链表操作通常都多定义一个p来从头节点开始进行操作
    ④开始循环定位，注意while(--i)是先进行--再判断是否为 ，故循环会使 p 移动至 i-1 位置处
    ⑤new出一个新节点，先使新节点s->next=p->next表示新节点指向原来的第 个节点，然后p->next=s表示原第 个节点指向新节点。图示如下：
    

bool insertNode(Node* Head,int val,int i){
	if(i<1||i>Head->data+1){
		puts("error");
		return false;
	}
	
	Head->data++;
	Node* p=Head;
	
	while(--i){
		p=p->next;
	}
	Node* s=new Node;
	s->data=val;
	s->next=p->next;
	p->next=s;
	return true;
}

• 删除： 传入表头，删除的位置，其中 的边界和插入操作比起来右边界缩短了一节，因为删除操作也是通过对 操作来删除节点 的
  • 算法流程： ①判边界，同插入操作
    ②表头表示链表大小的数据--
    ③循环移动，同插入，最终定位到
    ④先将第 个节点用指针表示出来，即 Node* s=p->next，然后让第 个节点指向第 个节点，即p->next=s->next即可

bool removeNode(Node* Head,int i){
   if(i<1||i>Head->data){
   	puts("error");
   	return false;
   }
   Node* p=Head;
   p->data--;
   while(--i){
   	p=p->next;
   }
   Node* s=p->next;
   p->next=s->next;
   delete s;
   return true;
}

• 打印整个链表： 传入表头，循环遍历。注意要先输出再p=p->next，不然输出最后的时候会遇上一个没有数据的空指针
  • 算法流程： ①定义指针Node* p=Head->next使其指向第一个节点
    ②输出当前数据域，然后让指针指向下一个（不能反）

void printList(Node* Head){
	Node* p=Head->next;
	while(p){
		cout<<p->data<<" ";//注意 
		p=p->next;
	}
	cout<<endl;
}

• 创建链表： 一直调用插入即可

void createList(Node* &Head,int* value,int n){
	Node* p=Head;
	for(int i=n;i>=1;i--){
		insertNode(Head,value[i],1);
	}
}

• 删除整个链表： 读取头节点储存的节点个数，循环调用删除

void deleteList(Node* Head){
	int n=Head->data;
	while(n--){
		removeNode(Head,1);
	}
}

• 循环链表： 将最后一个节点的指针域由空改为指向头节点，可以创建头指针时让它指向自己，然后其他操作一致即可实现。

DS单链表–存储结构与操作

#include<iostream>
using namespace std;

struct Node{
	int data;
	Node* nxt;
};

bool insertNode(Node* Head,int val,int i){
	if(i<1||i>Head->data+1){
		puts("error");
		return false;
	}
	
	Head->data++;
	Node* p=Head;
	
	while(--i){
		p=p->nxt;
	}
	Node* s=new Node;
	s->data=val;
	s->nxt=p->nxt;
	p->nxt=s;
	return true; 
}

bool removeNode(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return false;
	}
	Node* p=Head;
	p->data--;
	while(--i){
		p=p->nxt;
	}
	Node* s=p->nxt;
	p->nxt=s->nxt;
	delete s;
	return true; 
}

void printList(Node* Head){
	Node* p=Head->nxt;
	while(p){
		cout<<p->data<<" ";
		p=p->nxt;
	} 
	cout<<endl;
}

void createList(Node* &Head,int value[],int n){
	Node* p=Head;
	for(int i=n;i>=1;i--){
		insertNode(Head,value[i-1],1); 
	}
}

void findVal(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return ;
	}
	Node* p=Head;
	while(i--){
		p=p->nxt;
	}
	cout<<p->data<<endl;
}

int main(){
	int n;
	cin>>n;
	int* a=new int[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	Node* Head=new Node;
	Head->nxt=NULL,Head->data=0;
	createList(Head,a,n);
	printList(Head);
	int pos,val;
	cin>>pos>>val;
	if(insertNode(Head,val,pos))
		printList(Head);
	cin>>pos>>val;
	if(insertNode(Head,val,pos))
		printList(Head);
	cin>>pos;
	if(removeNode(Head,pos))
		printList(Head);
	cin>>pos;
	if(removeNode(Head,pos))
		printList(Head);
	cin>>pos;
	findVal(Head,pos);
	cin>>pos;
	findVal(Head,pos);
	
	
	return 0;
}

B. DS单链表–结点交换

#include<iostream>
using namespace std;

struct Node{
	int data;
	Node* nxt;
};

bool insertNode(Node* Head,int val,int i){
	if(i<1||i>Head->data+1){
		puts("error");
		return false;
	}
	
	Head->data++;
	Node* p=Head;
	
	while(--i){
		p=p->nxt;
	}
	Node* s=new Node;
	s->data=val;
	s->nxt=p->nxt;
	p->nxt=s;
	return true; 
}

bool removeNode(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return false;
	}
	Node* p=Head;
	p->data--;
	while(--i){
		p=p->nxt;
	}
	Node* s=p->nxt;
	p->nxt=s->nxt;
	delete s;
	return true; 
}

void printList(Node* Head){
	Node* p=Head->nxt;
	while(p){
		cout<<p->data<<" ";
		p=p->nxt;
	} 
	cout<<endl;
}

void createList(Node* &Head,int value[],int n){
	Node* p=Head;
	for(int i=n;i>=1;i--){
		insertNode(Head,value[i-1],1); 
	}
}

void findVal(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return ;
	}
	Node* p=Head;
	while(i--){
		p=p->nxt;
	}
	cout<<p->data<<endl;
}

bool swapNode(Node* Head,int i,int j){
	if((i<1||i>Head->data)||(j<1||j>Head->data)){
		puts("error");
		return false;
	}
	Node* p1=Head;
	Node* p2=Head;
	while(--i){
		p1=p1->nxt;
	} 
	while(--j){
		p2=p2->nxt;
	}
	Node* t1=p1->nxt;
	Node* t2=p2->nxt;
	p1->nxt=t2;
	p2->nxt=t1;
	Node* tmp=t1->nxt;
	t1->nxt=t2->nxt;
	t2->nxt=tmp;
	return true;
}

int main(){
	int n;
	cin>>n;
	int* a=new int[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	Node* Head=new Node;
	Head->nxt=NULL,Head->data=0;
	createList(Head,a,n);
	printList(Head);
	int posa,posb;
	cin>>posa>>posb;
	if(swapNode(Head,posa,posb))
		printList(Head);
	cin>>posa>>posb;
	if(swapNode(Head,posa,posb))
		printList(Head);
	
	return 0;
}

C. DS单链表–合并

#include<iostream>
using namespace std;

struct Node{
	int data;
	Node* nxt;
};

bool insertNode(Node* Head,int val,int i){
	if(i<1||i>Head->data+1){
		puts("error");
		return false;
	}
	
	Head->data++;
	Node* p=Head;
	
	while(--i){
		p=p->nxt;
	}
	Node* s=new Node;
	s->data=val;
	s->nxt=p->nxt;
	p->nxt=s;
	return true; 
}

bool removeNode(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return false;
	}
	Node* p=Head;
	p->data--;
	while(--i){
		p=p->nxt;
	}
	Node* s=p->nxt;
	p->nxt=s->nxt;
	delete s;
	return true; 
}

void printList(Node* Head){
	Node* p=Head->nxt;
	while(p){
		cout<<p->data<<" ";
		p=p->nxt;
	} 
	cout<<endl;
}

void createList(Node* &Head,int value[],int n){
	Node* p=Head;
	for(int i=n;i>=1;i--){
		insertNode(Head,value[i-1],1); 
	}
}

void findVal(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return ;
	}
	Node* p=Head;
	while(i--){
		p=p->nxt;
	}
	cout<<p->data<<endl;
}

Node* mergeList(Node* HeadA,Node* HeadB){
	Node* HeadC=new Node;
	Node* pc=HeadC;
	HeadC->nxt=NULL,HeadC->data=0;
	Node* pa=HeadA->nxt;
	Node* pb=HeadB->nxt;
	while(pa!=NULL&&pb!=NULL){
		if(pa->data>pb->data){
			insertNode(HeadC,pb->data,HeadC->data+1);
			pb=pb->nxt;
		}
		else if(pa->data<pb->data){
			insertNode(HeadC,pa->data,HeadC->data+1);
			pa=pa->nxt;
		}
		else{
			insertNode(HeadC,pa->data,HeadC->data+1);
			pa=pa->nxt;		
			insertNode(HeadC,pb->data,HeadC->data+1);
			pb=pb->nxt;	
		}
	}
	while(pa!=NULL){
		insertNode(HeadC,pa->data,HeadC->data+1);
		pa=pa->nxt;		
	}
	while(pb!=NULL){
		insertNode(HeadC,pb->data,HeadC->data+1);
		pb=pb->nxt;		
	}
	return HeadC;
}

bool swapNode(Node* Head,int i,int j){
	if((i<1||i>Head->data)||(j<1||j>Head->data)){
		puts("error");
		return false;
	}
	Node* p1=Head;
	Node* p2=Head;
	while(--i){
		p1=p1->nxt;
	} 
	while(--j){
		p2=p2->nxt;
	}
	Node* t1=p1->nxt;
	Node* t2=p2->nxt;
	p1->nxt=t2;
	p2->nxt=t1;
	Node* tmp=t1->nxt;
	t1->nxt=t2->nxt;
	t2->nxt=tmp;
	return true;
}

int main(){
	int n;
	cin>>n;
	int* a=new int[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	int m;
	cin>>m;
	int* b=new int[m];
	for(int i=0;i<m;i++)
		cin>>b[i]; 
	Node* HeadA=new Node;
	HeadA->nxt=NULL,HeadA->data=0;
	createList(HeadA,a,n);
	Node* HeadB=new Node;
	HeadB->nxt=NULL,HeadB->data=0;
	createList(HeadB,b,m);
	Node* HeadC=mergeList(HeadA,HeadB);
	printList(HeadC);
	return 0;
}

D. DS循环链表—约瑟夫环(Ver. I – A)

#include<iostream>
using namespace std;

struct Node{
	int data;
	Node* nxt;
};

bool insertNode(Node* Head,int val,int i){
	if(i<1||i>Head->data+1){
		puts("error");
		return false;
	}
	

	Head->data++;
	Node* p=Head;
	
	while(--i){
		p=p->nxt;
	}
	Node* s=new Node;
	s->data=val;
	s->nxt=p->nxt;
	p->nxt=s;
	return true; 

}

bool removeNode(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return false;
	}
	Node* p=Head;
	p->data--;
	while(--i){
		p=p->nxt;
	}
	Node* s=p->nxt;
	p->nxt=s->nxt;
	delete s;
	return true; 
}

void printList(Node* Head){
	Node* p=Head->nxt;
	while(p){
		cout<<p->data<<" ";
		p=p->nxt;
	} 
	cout<<endl;
}

void createList(Node* &Head,int value[],int n){
	Node* p=Head;
	for(int i=n;i>=1;i--){
		insertNode(Head,value[i],1); 
	}
	while(p->nxt){
		p=p->nxt;
	}
	p->nxt=Head->nxt;
}


void findVal(Node* Head,int i){
	if(i<1||i>Head->data){
		puts("error");
		return ;
	}
	Node* p=Head;
	while(i--){
		p=p->nxt;
	}
	cout<<p->data<<endl;
}

Node* mergeList(Node* HeadA,Node* HeadB){
	Node* HeadC=new Node;
	Node* pc=HeadC;
	HeadC->nxt=NULL,HeadC->data=0;
	Node* pa=HeadA->nxt;
	Node* pb=HeadB->nxt;
	while(pa!=NULL&&pb!=NULL){
		if(pa->data>pb->data){
			insertNode(HeadC,pb->data,HeadC->data+1);
			pb=pb->nxt;
		}
		else if(pa->data<pb->data){
			insertNode(HeadC,pa->data,HeadC->data+1);
			pa=pa->nxt;
		}
		else{
			insertNode(HeadC,pa->data,HeadC->data+1);
			pa=pa->nxt;		
			insertNode(HeadC,pb->data,HeadC->data+1);
			pb=pb->nxt;	
		}
	}
	while(pa!=NULL){
		insertNode(HeadC,pa->data,HeadC->data+1);
		pa=pa->nxt;		
	}
	while(pb!=NULL){
		insertNode(HeadC,pb->data,HeadC->data+1);
		pb=pb->nxt;		
	}
	return HeadC;
}

bool swapNode(Node* Head,int i,int j){
	if((i<1||i>Head->data)||(j<1||j>Head->data)){
		puts("error");
		return false;
	}
	Node* p1=Head;
	Node* p2=Head;
	while(--i){
		p1=p1->nxt;
	} 
	while(--j){
		p2=p2->nxt;
	}
	Node* t1=p1->nxt;
	Node* t2=p2->nxt;
	p1->nxt=t2;
	p2->nxt=t1;
	Node* tmp=t1->nxt;
	t1->nxt=t2->nxt;
	t2->nxt=tmp;
	return true;
}

void JoseLoop(Node* Head,int n,int k,int s){
	Node* S=Head;
	Node* p=Head;
	for(int i=0;i<s-1;i++)
		S=S->nxt;
	p=S->nxt;
	

	if(k==1){
		for(int i=1;i<n;i++){
			cout<<p->data<<" ";
			p=p->nxt;
		}
	}
	else{
		while(p->nxt!=p){
			for(int i=1;i<k;i++){
				S=p;
				p=p->nxt;
			}
			cout<<p->data<<" ";
			S->nxt=p->nxt;
			p=p->nxt;
		}		
	}
	cout<<p->data<<" "<<'\n';

}

int main(){
	int n,k,s;
	while(cin>>n>>k>>s){
		int* a=new int[n+1];
		for(int i=1;i<=n;i++)
			a[i]=i;
		Node* Head=new Node;
		Head->nxt=NULL;
		Head->data=0;
		createList(Head,a,n);
		JoseLoop(Head,n,k,s);
	}
	

	return 0;

}

F. DS链表—学生宿舍管理（双向列表容器List）

#include<iostream>
#include<list>
#include<algorithm>
#include<unordered_map>
using namespace std;

int main(){
	list<int>room;
	list<int>Free;
	unordered_map<int,int>bk;
	unordered_map<int,string>rtop;
	unordered_map<string,int>ptor;
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++){
		string a;
		int b;
		cin>>a>>b;
		room.push_back(b);
		bk[b]++;
		rtop[b]=a;
		ptor[a]=b;
	}
	

	for(int i=101;i<=120;i++)
		if(!bk[i])
			Free.push_back(i);
	cin>>m;
	while(m--){
		string a;
		cin>>a;
		if(a[0]=='a'){
			string b;
			cin>>b;
			for(int i=101;i<=120;i++)
				if(!bk[i]){
					bk[i]++;
					int num=Free.front();
					Free.pop_front();
					ptor[b]=num;
					rtop[num]=b;
					room.push_front(num);
					break;
				}
		}
		else if(a[0]=='r'){
			int b;
			cin>>b;
			auto it=find(room.begin(),room.end(),b);
			room.erase(it);
		//	for(auto t:room)	cout<<t<<" ";
		//	cout<<endl;
			Free.push_back(b);
		} 
		else if(a=="display_used"){
			room.sort();
			int tmp=room.front();
			cout<<rtop[room.front()]<<"("<<room.front()<<")"; 
			room.pop_front();
			for(auto t:room){
				cout<<"-"<<rtop[t]<<"("<<t<<")";
			}
			cout<<endl;			
			room.push_front(tmp);
		}
		else{
			int tmp=Free.front();
			cout<<tmp;
			Free.pop_front();
			for(auto t:Free)
				cout<<'-'<<t;	
			Free.push_front(tmp);	
		}
		
	}


	return 0;

}

栈

#include <iostream>
using namespace std;

template<class T>
class Node{
public:
	T data;
	Node* nxt;
};
template<class T>
class Stack{
public:
	int MAX_size;
	int Cur_size;
	Node<T>* Top;
	void Stack_Init(int x){
		MAX_size=x;
		Top=new Node<T>;
		Top->nxt=NULL;
		Cur_size=0;
	}
	void push(T x){
		if(Cur_size>MAX_size){
			puts("error");
			return;
		}
		Node<T>* t=new Node<T>;
		t->data=x;
		t->nxt=Top;
		Top=t;
		Cur_size++;
	}
	int size(){
		return Cur_size; 
	} 
	void pop(){
		if(Cur_size==0){
			puts("error");
			return; 
		}
		Top=Top->nxt; 
		Cur_size--;
	}
	T top(){
		if(Cur_size==0){
			puts("error");
			return -1;
		}
		return Top->data;
	}
}; 

int main(){
	Stack<int> s;
	s.Stack_Init(10);
	for(int i=1;i<=5;i++)
		s.push(i);
	cout<<s.top()<<endl;
	for(int i=1;i<=2;i++)
		s.pop();
	cout<<s.top()<<endl;
	cout<<s.size()<<endl;
	for(int i=1;i<=5;i++){
		cout<<s.top()<<endl;
		s.pop();
	}
	
		
	
	
	
	return 0;
}