CTDL và giải thuật – Nhập/ Xuất danh sách liên kết

Posted on by mtoplistChuyên mục:Top List

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 5

    1 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

  • Kích thước cố định
  • Cần chỉ rõ kích thước trong khi khai báo
  • Kích thước thay đổi trong quá trình thêm/ xóa phần tử
  • Kích thước tối đa phụ thuộc vào bộ nhớ

Cấp phát bộ nhớ

  • Tĩnh: Bộ nhớ được cấp phát trong quá trình biên dịch
  • Động: Bộ nhớ được cấp phát trong quá trình chạy

Thứ tự & sắp xếp

  • Được lưu trữ trên một dãy ô nhớ liên tục
  • Được lưu trữ trên các ô nhớ ngẫu nhiên

Truy cập

  • Truy cập tới phần tử ngẫu nhiên trực tiếp bằng cách sử dụng chỉ số mảng: O(1)
  • Truy cập tới phần tử ngẫu nhiên cần phải duyệt từ đầu/cuối đến phần tử đó: O(n)

Tìm kiếm

  • Tìm kiếm tuyến tính hoặc tìm kiếm nhị phân
  • Chỉ có thể tìm kiếm tuyến tính

 

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;
}

mtoplist