Danh sách liên kết đơn C++

Trình bày: Lê Minh Trí

Định nghĩa: Danh sách liên kết đơn (Single Linked List) là một cấu trúc dữ liệu động, nó là một danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách. Mỗi phần tử (được gọi là một node hay nút) trong danh sách liên kết đơn là một cấu trúc có hai thành phần:
- Thành phần dữ liệu: lưu thông tin về bản thân phần tử đó.
- Thành phần liên kết: lưu địa chỉ phần tử đứng sau trong danh sách, nếu phần tử đó là phần tử cuối cùng thì thành phần này bằng NULL.
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →

Cấu trúc dữ liệu của danh sách liên kết đơn:

Khai báo danh sách liên kết đơn dùng 2 con trỏ:



















// Định nghĩa cấu trúc của 1 node
struct node {
    // info chứ dữ liệu
    KDL info; 

    // con trỏ pNext giữ địa chỉ node kế tiếp
    struct node *pNext;
};
typedef struct node NODE;

// Định nghĩa cấu trúc danh sách List
struct list {
    // Con trỏ pHead giữ địa chỉ node đầu tiên
    NODE *pHead;

    // Con trỏ pTail giữ địa chỉ node cuối cùng
    NODE *pTail;
};
typedef struct list LIST;

Khai báo danh sách liên kết đơn dùng 1 con trỏ:












// Định nghĩa cấu trúc của 1 node
struct node {
    // info chứa dữ liệu 
    KDL info;

    // Con trỏ pNext giữ địa chỉ ô nhớ của node kế  tiếp
    struct node *pNext;
};
typedef struct node NODE;

// ĐỊnh nghĩa LIST là kiểu dữ liệu chứa địa chỉ ô nhớ đầu tiên (pHead) của node
typedef NODE* LIST;

Khởi tạo danh sách liên kết đơn: là tạo ra danh sách rỗng không chứ node nào hết.

Khởi tạo danh sách liên kêt đơn dùng 2 con trỏ:






void Init(LIST &l) {

    l.pHead = NULL;
    l.pTail = NULL;
    
}

Khởi tạo danh sách liên kết đơn dùng 1 con trỏ:





void Init(LIST &l) {

    l = NULL;

}

Kiểm tra danh sách liên kết đơn rỗng: là hàm kiểm tra khi danh sách rỗng thì trả về giá trị 1 ngược lại trả về giá trị 0.

Hàm kiểm tra danh sách liên kết đơn rỗng dùng 2 con trỏ:






int IsEmpty(LIST &l) {
    // Mảng rỗng không có phần tử do đó pHead mang giá trị NULL
    if (l.pHead == NULL) 
        return 1;
    return 0;
}

Hàm kiểm tra danh sách liên kết đơn rỗng dùng 1 con trỏ:





int IsEmpty(LIST &l) {
    // Mảng rỗng không có phần tử do đó l mang giá trị NULL
    if (l==NULL) return 1;
    return 0;
}

Tạo node cho danh sách liên kết đơn: là xin cấp phát bộ nhớ có kích thước của 1 node để chứa dữ liệu cho trước.

Định nghĩa hàm trừu tượng:








NODE* GetNode(KDL x) {
    NODE *p = new NODE;
    if (p == NULL) return NULL;
    p->info = x;
    p->pNext = NULL;
    // Trả về địa chỉ của Node mới được tạo
    return p;
}

Thêm một node vào cuối danh sách liên kết đơn: là gắn node đó vào cuối danh sách.

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Hàm thêm một node vào cuối danh sách liên kết đơn dùng 2 con trỏ:









void AddTail(LIST &l, NODE *p) {
    if (l.pHead==NULL) {
        l.pHead = l.pTail = p;
    } 
    else {
        l.pTail->pNext = p;
        l.pTail = p;
    }
}

Hàm thêm một node vào cuối danh sách liên kết đơn dùng 1 con trỏ:













void AddTail(LIST &l, NODE *p) {
    if(l == NULL) 
        l = p;
    else {
        //Tạo biến con trỏ chứa địa chỉ ô nhớ đầu tiên của list
        NODE *q = l;
        //Tìm địa chỉ node cuối
        while(q->pNext != NULL) {
            q = q->pNext;
        }
        q->pNext = p;
    }
}

Thêm một node vào đầu danh sách liên kết đơn: là gắn node đó vào đầu danh sách.

Hàm thêm một node vào đầu danh sách liên kết dùng 2 con trỏ:








void AddHead(LIST &l,NODE *p) {
    if(l.pHead == NULL) 
        l.pHead=l.pTail=p;
    else {
        p->pNext = l.pHead;
        l.pHead = p;
    }
}

Hàm thêm node vào đầu danh sách liên kết dùng 1 con trỏ:









void AddHead(LIST &l,NODE *p) {
    if(l == NULL){
        l=p;
    }
    else {
        p->pNext = l;
        l=p;
    }
}

Thêm một node vào cuối một node bất kỳ trong danh sách liên kết:

Định nghĩa hàm dùng 2 con trỏ:









void InsertAfterNode(LIST &l,NODE *p,NODE *q) {
    if(p != NULL){
        q->pNext = p->pNext;
        p->pNext = q;
        if(l.pTail == p){
            AddTail(l,q);
        }
    } else AddHead(l,q);
}

Định nghĩa hàm dùng 1 con trỏ:













void InsertAfterNode(LIST &l,NODE *p,NODE *q) {
    if(p != NULL){
        q->pNext = p->pNext;
        p->pNext = q;
        NODE *t=l;
        while(t->pNext != NULL){
            t=t->pNext;
        }
        if(t == p){
            AddTail(l,q);
        }
    } else AddHead(l,q);
}

Nhập từ bàn phím danh sách liên kết đơn: là lần lượt nhập thông tin từng node từ bàn phím.

Định nghĩa hàm:















void Input(LIST &l)
{
    int n;
    cout<<"Nhap so phan tu: ";
    cin>>n;
    // Gọi hàm khởi tạo danh sách rỗng
    Init(l);
    for(int i = 1; i<=n ; i++){
        KDL x;
        Nhap(x);
        // Gọi hàm GetNode để lưu thông tin vào node và trả về địa chỉ của node mới
        NODE *p = GetNode(x);
        if(p != NULL) AddTail(l, p);
    }
}

Duyệt tuần tự danh sách liên kết đơn: là duyệt qua tất cả các node trong dach sách 1 lần.

Định nghĩa hàm trừu tượng dùng 2 con trỏ:








KDL <Tên hàm>(LIST l) {
    ...
    NODE *p = l.pHead;
    while(p != NULL){
        p=p->pNext;
    }
    ...
}

Định nghĩa hàm trừu tượng dùng 1 con trỏ:








KDL <Tên hàm>(LIST l) {
    ...
    NODE *p = l;
    while(p != NULL){
        p=p->pNext;
    }
    ...
}

Xoá node ở đầu danh sách: là hàm xoá node đầu tiên trong danh sách liên kết đơn, trả về 1 nếu xoá thành công, trả về không nếu không thể xoá.

Định nghĩa hàm xoá node ở đầu danh sách liên kết dùng 2 con trỏ:














int RemoveHead(LIST &l, int &x) {
    if(l.pHead != NULL){
        NODE *p = l.pHead;
        // Lưu lại data khi cần dùng
        x= p->info;
        l.pHead = p->pNext;
        delete p;
        if(l.pHead == NULL){
            l.pTail = NULL;
        }
        return 1;
    }
    return 0;
}

Định nghĩa hàm xoá node ở đầu danh sách liên kết đơn dùng 1 con trỏ:










int RemoveHead(LIST &l, int &x) {
    if(l != NULL){
        NODE *p = l;
        // Lưu lại data khi cần dùng
        x= p->info;
        l = p->pNext;
        delete p;
        return 1;
    }
    return 0;

Định nghĩa hàm xoá node ở sau một node bất kì trong danh sách:















int RemoveNode(LIST &l,NODE *p, int &x) {
    if(p != NULL){
        NODE *q=p->pNext;
        if(q != NULL){
            if(l.pTail ==q){
                l.pTail = p;
                p->pNext = q->pNext;
                x=  q->info;
                delete q;
                return 1;
            }
        return 0;
    }
    return 0;
}

Danh sách liên kết đơn C++

Trình bày: Lê Minh Trí

Read more

Cấu trúc dữ liệu và giải thuật - Buổi 03

Ôn tập về con trỏ trong C++

Cấu trúc dữ liệu và giải thuật - Buổi 02

Cấu trúc dữ liệu và giải thuật - Buổi 01