CTDL và giải thuật - Nhập/ Xuất danh sách liên kết
Nhập vào một số nguyên 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 và in ra màn hình danh sách đó, sau mỗt phần tử có đúng một khoảng trắng.
Ví dụ:
- Test mẫu 1:
Input Output 5
1 2 3 4 51 2 3 4 5
Giới thiệu danh sách liên kết.
Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là rất quan trọng để hiểu cách danh sách liên kết hoạt động, vì vậy nếu bạn chưa có kiến thức về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một chút về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần nội dung cài đặt danh sách liên kết của bài này sẽ chỉ trình bày về danh sách liên kết đơn.
Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa một giá trị (Data) và một con trỏ (Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của linked list.
Hình ảnh mình họa một node:
Hình ảnh mình họa một listLinker:
So sánh mảng và danh sách liên kết:
Nội dung | Mảng | Danh sách liên kết |
Kích thước |
|
|
Cấp phát bộ nhớ |
|
|
Thứ tự & sắp xếp |
|
|
Truy cập |
|
|
Tìm kiếm |
|
|
Cách loại danh sách liên kết:
- Danh sách liên kết đơn- Linked List.
- Danh sách liên kết đôi - Doubly Linked List.
- Danh sách liên kết vòng - Circular Linked List.
Để hiểu sâu hơn về danh sách liên kết, mình sẽ hướng dẫn sâu cho các bạn về danh sách liên kết đơn.
Với các ngôn ngữ khác như Java, C#, Python thì không tồn tại khái niệm con trỏ nên các bạn có thể dùng thư viện có sẵn, nhưng để hiểu cách cài đặt thì có thể xem code mẫu phần C++ của mình.
Cài đặt danh sách liên kết đơn.
Ví dụ cho C++:
Khai báo node:
struct node{
int data;
node *next;
};
Tạo mới một node:
node *createNode(int x){
node *temp = new node; // tạo mới một node
temp->next = NULL; // node này chưa trỏ đến phần tử khác nên "next" nhận giá trị NULL
temp->data = x; // gán giá trị cho node
return temp;
}
Thêm một phần tử vào cuối listLinker khi biết con trỏ đang trỏ vào phần tử cuối:
node *addElement(node*p, int x){
node *temp = createNode(x); // Tạo 1 node mới có giá trị là x.
p->next = temp; // Thêm node đó và cuối danh sách.
return temp; // trả về node temp, vì temp giờ đã là node cuối của list.
}
(sẽ nói rõ việc thêm phần tử vào vị trí bất kỳ ở bài sau).
Duyệt các phần tử trong danh sách liên kết l
:
node *p = l;
while (p != NULL){
// xử lý p
p = p->next;
}
Lưu ý là khi xử lý một danh sách liên kết đơn ta nên dùng một node khác lưu danh sách đó, tránh tình trạng bị mất node đầu của danh sách.
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;
}
int main(){
int n, x;
cin >> n;
cin >> x;
node *l = createNode(x);
node *p = l;
for (int i = 1; i < n; i++){
cin >> x;
p = addElement(p, x);
}
printList(l);
return 0;
}