CTDL và giải thuật - Chèn giá trị X vào danh sách
Nhập vào một số nguyên dương n
, tiếp theo là n
số nguyên của một dãy số, hãy cài đặt nó vào một danh sách liên kết đơn. Tiếp theo nhập hai số nguyên k
và x
, (0 ≤ k ≤ n
), hãy chèn giá trị x
vào danh sách liên kết tại chỉ số k
và in ra màn hình danh sách đó, sau một phần tử có một khoảng trắng.
Ví dụ:
- Test mẫu 1:
Input Output 4
1 2 3 4
1 101 10 2 3 4
Vớil = [1, 2, 3, 4], k = 1, x = 10
thì kết quả mong muốn là:
"1 10 2 3 4 ".
- Test mẫu 2:
Input Output 3
1 2 3
0 1010 1 2 3
Vớil = [1, 2, 3], k = 0, x = 10
thì kết quả mong muốn là:
"10 1 2 3".
Lý thuyết.
Việc thêm phần tử vào danh sách liên kết rất đơn giản, chỉ với ĐPT là O(1).
Thêm phần tử vào đầu danh sách liên kết:
Để thêm một node temp
vào đầu danh sách liên kết l
rất đơn giản ta chỉ cần gán tạo mới một node temp
sau đó gắn temp->next = l
là được.
Code C++:
node *addHead(node *l, int x){
node *temp = new node;
temp->data = x;
temp->next = l;
l = temp;
return l;
}
Thêm phần tử vào cuối danh sách liên kết:
Code C++ mẫu:
node *addTail(node *l, int x){
node *p = l;
while (p->next != NULL){
p= p->next;
}
node *temp = new node;
temp->data = x;
temp->next = NULL;
p->next = temp;
return l;
}
Thêm phần tử vào ví trí khác ví trí đầu và cuối.
Để thêm phần tử vào chỉ số k, ta cần phần tìm node trỏ đến phần tử có chỉ số k-1
. Xem hình vẽ.
Chúng ta cần tìm con trỏ trỏ đến phần tử chỉ số k-1
và thay đổi liên kết giữa chúng như hình trên.
Code C++ mẫu:
node *addAt(node *l, int k, int x){
node *p = l;
for (int i = 0; i < k-1; i++){
p = p->next;
}
//
node *temp = new node;
temp->data = x;
temp->next = p->next;
p->next = temp;
return l;
}
Hướng dẫn bài tập.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
struct node{
int data;
node *next;
};
node *createNode(int x){
node *temp = new node;
temp->next = NULL;
temp->data = x;
return temp;
}
void printList(node *l){
node *p = l;
while (p != NULL){
cout << p->data << " ";
p = p->next;
}
}
node *addElement(node*p, int x){
node *temp = createNode(x);
p->next = temp;
return temp;
}
node *addHead(node *l, int x){
node *temp = new node;
temp->data = x;
temp->next = l;
l = temp;
return l;
}
node *addAt(node *l, int k, int x){
node *p = l;
for (int i = 0; i < k-1; i++){
p = p->next;
}
node *temp = new node;
temp->data = x;
temp->next = p->next;
p->next = temp;
return l;
}
node *addTail(node *l, int x){
node *p = l;
while (p->next != NULL){
p= p->next;
}
node *temp = new node;
temp->data = x;
temp->next = NULL;
p->next = temp;
return l;
}
int main(){
int n, x, k;
cin >> n;
cin >> x;
node *l = createNode(x);
node *p = l;
for (int i = 1; i < n; i++){
cin >> x;
p = addElement(p, x);
}
cin >> k >> x;
if (k == 0){
l = addHead(l, x);
} else if (k == n){
l = addTail(l, x);
} else{
l = addAt(l, k, x);
}
printList(l);
return 0;
}