C++ Data Structure: Linked List

Hi. Chào mừng các bạn đến với chủ đề:

Data Structure C++ tai blog: Phattrienphanmem123az.com

Bài đầu tiên chúng ta sẽ cùng tìm hiểu về thuật toán Linked List, còn được gọi là Danh sách liên kết.

1. Lý thuyết cơ bản về Linked list.

Là một dạng cấu trúc dữ liệu tuyến tính.

Mỗi phần tử trong danh sách được liên kết bởi việc sử dụng một con trỏ.

Hãy nhìn hình minh họa sau đây.

Mỗi phần tử của linked list sẽ gồm 2 phần cơ bản.

+ Một phần chứa dữ liệu.

+ Và một con trỏ next để chưa địa chỉ của phần tử tiếp theo.

Như vậy next của A sẽ lưu trữ địa chỉ của B, next của B sẽ lưu trữ địa chỉ của C và cứ thế cho đến phần tử cuối cùng, next của D sẽ trỏ tới NULL.

– Nó khác hoàn toàn so với cơ chế lưu trữ dữ liệu của mảng. Link list không thể truy xuất từng phần tử theo chỉ số như mảng.

– Khá linh hoạt trong việc lưu trữ một tập hợp các phần tử, vì có thể viết các hàm thêm mới phần tử và loại bỏ phần tử.

2. Triển khai linked list trên C++ với dữ liệu cơ bản: int.



#include <iostream>
#include <conio.h>

class PTLinkedList
{
    struct Node    // Khai báo 1 cấu trúc dữ liệu cho 1 node
    {
        int data_;
        Node* p_next_;
    };

public:
    PTLinkedList() { p_head_ = NULL; }
    ~PTLinkedList()
    {
        Node* head = p_head_;
        while (head)
        {
            Node* temp = head;
            head = head->p_next_;
            delete temp;
            temp = NULL;
        }
    }

    void AddValue(int val)  // Thêm 1 phần tử mới vào đầu danh sách
    {
        Node* new_node = new Node();
        new_node->data_ = val;
        new_node->p_next_ = p_head_;
        p_head_ = new_node;
    }
    void Remove()  // Loại bỏ phần từ đầu danh sách
    {
        if (p_head_ != NULL)
        {
            Node* temp = p_head_;
            p_head_ = p_head_->p_next_;
            delete temp;
        }
    }
    
    void Show()  // Viết thêm một hàm hiển thị
    {
        Node* temp = p_head_;
        while (temp != NULL)
        {
            int value = temp->data_;
            std::cout << "  " << value;
            temp = temp->p_next_;
        }
    }
private:
    Node* p_head_;   // Luôn có 1 con trỏ pHead quản lý phần tử đầu.
};

#include <iostream>

#include <conio.h>

class PTLinkedList

{

struct Node // Khai báo 1 cấu trúc dữ liệu cho 1 node

{

int data_;

Node* p_next_;

};

public:

PTLinkedList() { p_head_ = NULL; }

~PTLinkedList()

{

Node* head = p_head_;

while (head)

{

Node* temp = head;

head = head->p_next_;

delete temp;

temp = NULL;

}

void AddValue(int val) // Thêm 1 phần tử mới vào đầu danh sách

{

Node* new_node = new Node();

new_node->data_ = val;

new_node->p_next_ = p_head_;

p_head_ = new_node;

}

void Remove() // Loại bỏ phần từ đầu danh sách

{

if (p_head_ != NULL)

{

Node* temp = p_head_;

p_head_ = p_head_->p_next_;

delete temp;

}

void Show() // Viết thêm một hàm hiển thị

{

Node* temp = p_head_;

while (temp != NULL)

{

int value = temp->data_;

std::cout << " " << value;

temp = temp->p_next_;

}

private:

Node* p_head_; // Luôn có 1 con trỏ pHead quản lý phần tử đầu.

};

Sử dụng linked list trong hàm main.



int main()
{
    PTLinkedList data_list;
    data_list.AddValue(5);
    data_list.AddValue(6);
    data_list.AddValue(7);
    data_list.AddValue(8);
    data_list.AddValue(9);

    data_list.Show();

    data_list.Remove();

    std::cout << std::endl;
    data_list.Show();

    _getch();
    return 0;
}

int main()

{

PTLinkedList data_list;

data_list.AddValue(5);

data_list.AddValue(6);

data_list.AddValue(7);

data_list.AddValue(8);

data_list.AddValue(9);

data_list.Show();

data_list.Remove();

std::cout << std::endl;

data_list.Show();

_getch();

return 0;

}

3. Sử dụng template xây dựng linked list tổng quát nhất.

Khi làm demo hay các ví dụ minh họa, chúng ta thường sử dụng dữ liệu thuần như int, float, để minh họa cho linked list.

Nhưng khi đưa linked list vào sử dụng cho các dữ liệu án, dữ liệu không còn là dữ liệu thuần, mà nó có thể là một kiểu dữ liệu đối tượng bất kỳ.

Do đó chúng ta phải xây dựng được linked list một cách tổng quát.

Và template là kỹ thuật giúp chúng ta thực hiện được điều này.

a. Sử dụng class thay cho struct để xây dựng dữ liệu NodeData.

(Node data gồm 2 phần, dữ liệu và con trỏ next)



template <typename T>
class NodeData
{
public:
    NodeData() : next_(NULL) { ; }
    void         set_data(T val) { data_ = val; }
    T            get_data() const { return data_; }
    void         set_next(NodeData<T>* next) { next_ = next; }
    NodeData<T>* get_next() const { return next_; };
private:
    T            data_;  // dữ liệu kiểu template
    NodeData<T>* next_;
};

template <typename T>

class NodeData

{

public:

NodeData() : next_(NULL) { ; }

void set_data(T val) { data_ = val; }

T get_data() const { return data_; }

void set_next(NodeData<T>* next) { next_ = next; }

NodeData<T>* get_next() const { return next_; };

private:

T data_; // dữ liệu kiểu template

NodeData<T>* next_;

};

b. Xây dựng class linked list mà mỗi phần tử của nó là một NodeData.



template<typename T>
class LinkedList
{
public:
    LinkedList() : p_head_(NULL) {};
    ~LinkedList() { ; };

    void InsetFront(T val)     // Hàm chèn phần tử vào trước danh sách
    {
        NodeData<T>* temp = new NodeData<T>();
        temp->set_data(val);
        temp->set_next(p_head_);
        p_head_ = temp;
    }

    void RemoveFront()   // Remove phần tử đầu danh sách
    {
        if (p_head_ != NULL)
        {
            NodeData<T>* temp = p_head_;
            p_head_ = p_head_->get_next();
            delete temp;
        }
    }

    NodeData<T>* head() { return p_head_; };

public:
    NodeData<T>* p_head_;    // Luôn có con trỏ pHead trỏ vào phần tử đầu tiên. 
                             // Có thể coi đây là linked list dạng single
};

template<typename T>

class LinkedList

{

public:

LinkedList() : p_head_(NULL) {};

~LinkedList() { ; };

void InsetFront(T val) // Hàm chèn phần tử vào trước danh sách

{

NodeData<T>* temp = new NodeData<T>();

temp->set_data(val);

temp->set_next(p_head_);

p_head_ = temp;

}

void RemoveFront() // Remove phần tử đầu danh sách

{

if (p_head_ != NULL)

{

NodeData<T>* temp = p_head_;

p_head_ = p_head_->get_next();

delete temp;

}

NodeData<T>* head() { return p_head_; };

public:

NodeData<T>* p_head_; // Luôn có con trỏ pHead trỏ vào phần tử đầu tiên.

// Có thể coi đây là linked list dạng single

};

c. Bắt đầu triển khai sử dụng linked list.

Ví dụ tôi sẽ không sử dụng với kiểu dữ liệu thuần như dạng int hay float. Tôi sẽ xây dựng 1 kiểu dữ liệu trừu tượng.

Ví dụ dữ liệu là một lớp thông tin của một cá nhân bao gồm: Tên, tuổi, giới tính.



class Person
{
public:
    Person() { ; };
    Person(std::string name, unsigned int age, bool sex);
    ~Person() { ; };
    void operator =(Person& p);
    std::string get_name() const { return name_; }
    unsigned int get_age() const { return age_; }
    bool get_sex() const { return sex_; }

    void ShowInfo()
    {
        std::cout << "  Name = " << name_.c_str();
        std::cout << "  Age = " << age_;
        std::cout << "  Sex = " << ((sex_ == 1) ? "Male" : "Female");
    }
private:
    std::string name_;
    unsigned int age_;
    bool sex_;
};

Person::Person(std::string name, unsigned int age, bool sex)
{
    name_ = name;
    age_ = age;
    sex_ = sex;
}

void Person::operator =(Person& p) //Lưu ý là khi xây dựng các lơp đối tượng, hãy dựng các phép toán cho lớp.
{
    this->name_ = p.name_;
    this->age_ = p.age_;
    this->sex_ = p.sex_;
}

class Person

{

public:

Person() { ; };

Person(std::string name, unsigned int age, bool sex);

~Person() { ; };

void operator =(Person& p);

std::string get_name() const { return name_; }

unsigned int get_age() const { return age_; }

bool get_sex() const { return sex_; }

void ShowInfo()

{

std::cout << " Name = " << name_.c_str();

std::cout << " Age = " << age_;

std::cout << " Sex = " << ((sex_ == 1) ? "Male" : "Female");

}

private:

std::string name_;

unsigned int age_;

bool sex_;

};

Person::Person(std::string name, unsigned int age, bool sex)

{

name_ = name;

age_ = age;

sex_ = sex;

}

void Person::operator =(Person& p) //Lưu ý là khi xây dựng các lơp đối tượng, hãy dựng các phép toán cho lớp.

{

this->name_ = p.name_;

this->age_ = p.age_;

this->sex_ = p.sex_;

}

Như vậy linked list của tôi sẽ là một tập hợp lưu trữ các đối tượng con người.

Mỗi thành phần của linked list sẽ có dữ liệu T là kiểu person, và một con trỏ next trỏ sang phần tử tiếp theo.

Như vậy việc sử dụng template giúp ta tổng quát được cấu trúc linked list.

Bạn có thể sử dụng linked list với bất cứ kiểu dữ liệu nào.

d. Bắt đầu sử dụng linked list với kiểu dữ liệu person.



    LinkedList<Person> data_list;
    Person person1("Pham A", 20, 1);
    Person person2("Pham B", 20, 0);
    Person person3("Pham C", 20, 1);
    Person person4("Pham D", 20, 0);

    data_list.InsetFront(person1);
    data_list.InsetFront(person2);
    data_list.InsetFront(person3);
    data_list.InsetFront(person4);

    // In danh sách.
    NodeData<Person>* p_head = data_list.head();
    if (p_head != NULL)
    {
        NodeData<Person>* temp = p_head;
        while (temp != NULL)
        {
            temp->get_data().ShowInfo();
            std::cout << "\n\n\n";
            temp = temp->get_next();
        }
    }