双向链表实现与单向链表实现

Yuilice

2024-02-21 11:07:41

发布于：北京

38阅读

0回复

0点赞

双向链表


#include<bits/stdc++.h>
using namespace std;

struct Node{
	int data;
	Node *pre,*next ;
};

Node *head,*tail;

void add_root(int x){ // 添加元素到队尾
	if(tail == NULL){
		head = tail = new Node ;
		// tail -> pre = NULL;
	}else{
		Node *new_root = new Node ;
		new_root -> pre = tail;
		new_root -> next = NULL;
		tail -> next = new_root;
		tail = new_root;
	}
	tail -> data = x;
}

void Insert(int y,Node *step){ // 插入y到step后面
	Node *new_root = new Node ; // 申请新的空间
	new_root -> data = y;
	new_root -> next = step -> next;
	new_root -> pre = step ;
	step -> next = new_root ;
	if(step == tail)tail = new_root;
}

void print(Node *step,int x){
	while(step != NULL){
		if(step -> data == x){
			if(step == tail)cout << "0" << endl;
			else cout << step -> next -> data << endl;
			break;
		}
		step = step -> next ;
	}
	if(step == NULL)cout << "0" << endl;
}

int main(){
	freopen("list.in","r",stdin);
	freopen("list.out","w",stdout);
	head = tail = NULL;
	add_root(1);
	int t;
	cin >> t;
	head->pre = NULL;
	tail -> next = NULL;
	while(t--)
	{
		Node *step = head;
		int od ,x,y;
		cin >> od;
		if(od == 1){
			cin >> x >> y;
			while(step != NULL){ // 插入操作
				
				if(step -> data == x){
					Insert(y,step);
					break;
				}
				step = step -> next;
			}
			// cout << endl;
		}else if(od == 2){
			cin >> x;
			print(step,x);
		}else {
			cin >> x;
			step = head;
			while(step != NULL){
				if(step->data == x){
					if(step->next == NULL)break;
					step -> next = step -> next->next;
					break;
				}
				step = step->next;
			}
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

单向静态链表

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10; 

struct node{
	int data,next;
}a[N]; 

int head = 1,tail = N-1,p = 1;

void insert(int x,int y){
	int t = head;
	while(t != tail && a[t].data != x){
		t = a[t].next;  // 要么找到x，要么到结尾 
	}
	if(a[t].data == x){
		a[++p].data = y; // 新建一个数据
		a[p].next = a[t].next;
		a[t].next = p; 
	} 
} 

int check(int x){
	int t = head;
	while(t != tail && a[t].data != x){
		t = a[t].next;  // 要么找到x，要么到结尾 
	}
	if(a[t].data == x){
		if(a[t].next == tail) return 0;  // x是最后一个数据 
		else return  a[a[t].next].data;  //返回x下一个位置的数据 
	}
	return 0; 
}

void del(int x){
	int t = head;
	while(t != tail && a[t].data != x){
		t = a[t].next;  // 要么找到x，要么到结尾 
	}
	if(a[t].data == x){
		if(a[t].next != tail)  // x不是最后一个数据 
			a[t].next = a[a[t].next].next;
	}
}


int main(){
	freopen("list.in","r",stdin);
	freopen("list.out","w",stdout);
	a[head].data = 1; // 头
	a[head].next = tail; 
	int n;
	cin >> n;
	while(n--){
		int t,x,y;
		cin >> t >> x;
		if(t==1){
			cin >> y;
			insert(x,y);  // 在x后面插入y 
		}else if(t==2){
			cout << check(x) << endl;  //查询x后面的数 
		}else{
			del(x);  //删除x后面的数 
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}