CTDL Và Giải Thuật - Xóa Phần Tử K Trong 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 cho một số nguyên k, (0 ≤ k < n), hãy xóa phần tử ở 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	1 3 4

  Với l = [1, 2, 3, 4], k = 1 thì kết quả mong muốn là: "1 3 4 ".
• Test mẫu 2:

  Input	Output
  3 1 2 3 0	2 3

  Với l = [1, 2, 3], k = 0 thì kết quả mong muốn là: "2 3".

Lý thuyết.

Việc xóa phần tử trong dach sách liên kết cũng rất đơn giản với độ phức tạp là O(n).

Xóa phần tử đầu tiên của danh sách liên kết đơn.

Để xóa phần tử đầu tiên trong danh sách liên kết l, ta chỉ cần gán l = l->next, và nhớ giải phóng bộ nhớ của node đã xóa.

Code C++ mẫu:

node *deleteHead(node *l){ node *p = l; p = p->next; delete(l); return p; }

Xóa phần tử cuối cùng trong danh sách liên kết đơn.

Để xóa phần tử cuối cùng trong listLinker ta cần tìm node của phần tử trước phần tử cuối và gán next của nó bằng NULL, cũng phải xóa bỏ vùng nhớ đã cấp phát cho node cuối cùng.

Code C++ mẫu:

node *deleteTail(node *l){ node *p = l; while (p->next->next != NULL){ p = p->next; } delete(p->next); p->next = NULL; return l; }

Xóa phần tử ở vị trí khác đầu và cuối trong danh sách liên kết đơn:

Để xóa phần tử ở vị trí k ta cần phải tìm node p của phần tử k-1 và gán p->next = p->next->next như hình vẽ.

Code C++ mẫu:

node *deleteAt(node *l, int k){ node *p = l; for (int i = 0; i < k-1; i++){ p = p->next; } node *temp = p->next; p->next = p->next->next; delete(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 *deleteHead(node *l){ node *p = l; p = p->next; delete(l); return p; } node *deleteTail(node *l){ node *p = l; while (p->next->next != NULL){ p = p->next; } delete(p->next); p->next = NULL; return l; } node *deleteAt(node *l, int k){ node *p = l; for (int i = 0; i < k-1; i++){ p = p->next; } node *temp = p->next; p->next = p->next->next; delete(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; if (k == 0){ l = deleteHead(l); } else if (k == n-1){ l = deleteTail(l); } else{ l = deleteAt(l, k); } printList(l); return 0; }