Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.3 kB
0
Indexable
Never
#include <iostream>
Yêu cầu xây dựng một list các số nguyên, gồm các thao tác chính chèn, xóa và in. Các thao tác gồm có:






- f K: chèn vào đầu list số K.






- i j K: chèn vào vị trí j số K, (j >= 0, chỉ số vị trí được đánh số từ 0). Nếu j vượt quá vị trí của phần tử cuối cùng thì số đó được chèn vào cuối list.






- r: xóa phần tử đầu tiên của list. Nếu list rỗng thì không làm gì.






- d j: xóa phần tử ở vị trí j (j >= 0). Nếu j vượt quá vị trí của phần tử cuối cùng thì không làm gì. 






- p j: in ra j phần tử đầu tiên của list (từ 0 đến j-1), nếu j vượt quá vị trí của phần tử cuối cùng thì in ra đến phần tử cuối cùng.






Input






Dòng đầu tiên là số lượng test case T. Thông tin về mỗi test case như sau:






- Dòng đầu tiên là số lượng thao tác N (N <= 30,000).






- N dòng tiếp theo là thông tin về các thao tác như mô tả ở trên.






Output






In ra các số tương ứng với mỗi thao tác in, nếu list rỗng in ra "empty" (trên cùng 1 dòng)



/*
210
r
f 9040
r
r
r
i 99 3548
r
r
r
f 11323
r
i 35 4833
r
f 31673
i 172 26924
i 57 15573
f 9161
i 34 23655
r
r
d 161
d 107
i 79 8909
r
r
r
f 1655
r
d 85
f 10291
r
f 23199
i 53 4734
p 438
i 158 467
d 167
d 133
r
r
r
r
d 79
d 153
i 53 29314
r
r
d 8
r
f 6038
p 157
d 208
r
i 176 20328
d 83
r
f 10322
i 126 3557
d 2
d 199
p 401
i 85 5002
p 88
d 172
r
r
f 21425
p 49
d 0
d 33
d 139
r
d 147
d 128
r
f 20671
d 205
f 10808
d 36
r
r
i 75 2161
r
r
f 26154
d 166
f 2168
d 108
d 17
r
f 20159
d 157
i 83 32270
d 162
d 182
d 73
r
d 132
i 92 13031
r
d 170
f 29170
d 140
d 160
d 204
p 76
r
r
f 1018
f 2800
r
r
d 73
i 76 7882
i 105 14474
r
r
r
d 185
r
r
d 137
r
d 110
d 30
r
d 150
i 37 12760
p 108
d 170
i 85 27384
f 12835
r
r
d 126
d 139
f 29617
r
d 189
d 112
i 14 16962
r
r
d 71
r
d 92
i 39 20175
r
i 120 31783
d 13
r
f 25705
d 90
d 75
d 7
f 18443
f 9313
r
r
d 101
i 177 19090
d 33
f 22044
d 62
i 49 28503
f 5997
d 127
d 160
i 55 6077
r
f 15759
i 205 4084
f 6287
i 193 21221
f 22171
r
i 194 7591
f 25205
d 82
r
r
d 152
d 142
d 194
d 98
d 183
f 25087
d 93
r
d 28
f 2943
d 9
r
d 78
r
i 0 21430
r
r
p 353
f 19923
r
f 32726
d 131
r
r
r
r
d 69
r
d 185
d 154


*/

struct Node{
	int data;
	struct Node* next;
	Node(){
		data = 0;
		next = nullptr;
	}
	Node(int data){
		this->data = data;
		this->next = nullptr;
	}
};
void push(struct Node** head, int data, int& size){
	struct Node* newNode = new Node(data);
	newNode->next = *head;
	*head = newNode;
	size++;
}

void insert(struct Node** head, int pos, int data, int& size){
	if(*head == nullptr){
		struct Node* newNode = new Node(data);
		newNode->next = *head;
		*head = newNode;
		size++;
		return;
	}
	if(pos > size){
		struct Node* tm = *head;
		struct Node* newNode = new Node(data);
		while (tm->next)
		{
			tm = tm->next;
		}
		tm->next = newNode;
		size++;
		return;
	}
	struct Node* tm = *head;
	struct Node* pr = *head;
	while (pos--)
	{
		pr = tm;
		tm = tm->next;
	}
	struct Node* st = new Node(data);
	st->next = tm;
	pr->next = st;
	size++;
} 

void pop(struct Node** head, int& size){
	if(size == 0){
		return;
	}
	struct Node* tm = *head;
	tm = tm->next;
	*head = tm;
	size--;
	return;
}

void deleteNode(struct Node** head, int pos, int& size){
	if(*head == nullptr || pos >= size){
		return;
	}
	if(pos == 0){
		struct Node* tm = *head;
		tm = tm->next;
		*head = tm;
		size--;
		return;
	}
	struct Node* tm = *head;
	struct Node* pre = *head;
	while (pos--)
	{
		pre = tm;
		tm = tm->next;
	}
	if(tm != nullptr){
		struct Node* rm = tm;
		tm = tm->next;
		delete rm;
	}
	pre->next = tm;
	size--;
}

void print(struct Node* head, int pos, int size){
	if(size == 0 || head == nullptr){
		std::cout << "empty ";
		return;
	}
	if(pos <= size){
		struct Node* tm = head;
		while (pos-- && tm)
		{
			std::cout << tm->data << " ";
			tm = tm->next;
		}
		return;
	}
	struct Node* tm = head;
	while (tm != nullptr)
	{
		std::cout << tm->data << " ";
		tm = tm->next;
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int T, N;
	std::cin >> T;
	for(int tc = 1; tc <= 1; ++tc){
		std::cin >> N;
		struct Node* head = nullptr;
		int size = 0;
		char c = '\0';
		int j, K;
		std::cout << "#" << tc << " "; 
		while (N--)
		{
			std::cin >> c;
			switch (c)
			{
			case 'f':
				std::cin >> K;
				push(&head, K, size);
				break;
			case 'i':
				std::cin >> j >> K;
				insert(&head, j, K, size);
				break;
			case 'r':
				pop(&head, size);
				break;
			case 'd':
				std::cin >> j;
				deleteNode(&head, j, size);
				break;
			case 'p':
				std::cin >> j;
				print(head, j, size);
				break;
			}
		}
		std::cout << std::endl;
	}
	return 0;
}