Thêm phần tử vào đầu danh sách liên kết đơn C/C++ | Lập Trình Từ Đầu

Posted on by adminChuyên mục:Kiến thức Internet
Trong phần này, những thành phần của list link đơn được hiểu là những Node trong list. Hãy bảo vệ rằng bạn đã đọc bài tiên phong trước khi chuyển sang bài này !

1. Cách thêm thành phần vào đầu list link đơn

Giả sử list đơn khởi đầu của tôi gồm những node ( hay những thành phần ) như hình minh họa bên dưới :

Vấn đề đặt ra rằng tôi cần thêm một Node P vào danh sách liên kết đơn trên và đặt Node P này vào đầu danh sách liên kết đơn.

Như các bạn đã biết, một Node sẽ gồm hai thành phần đó là data và con trỏ next và để thực hiện việc thêm node vào đầu danh sách tôi cần thực hiện hai bước:

  • Bước đầu tiên: đặt con trỏ next của Node P vào Node hiện tại đang là phần tử đầu tiên của danh sách (ví dụ ở hình dưới phần tử A đang là phần tử đầu tiên): p->next = ds.pHead;
  • Bước thứ hai: Đặt pHead của danh sách bằng Node P cần chèn đầu: ds.pHead = p;

Xem hình dưới đề hiểu hơn hai bước trên !

Chú ý :
Trường hợp list đơn khởi đầu là rỗng và không có node ( thành phần ) nào, để thực thi việc thêm thành phần vào đầu list rất đơn thuần :

Ta chỉ việc đặt pHead (phần tử đầu) và pTail (phần tử cuối) bằng chính Node P cần chèn vào danh sách: ds.pHead = p; ds.pTail = p;

2. Hàm thêm thành phần vào đầu list link đơn

Hàm void ChenDau(LIST &ds, NODE *p) dưới đây nhận LIST &ds là danh sách cần thêm và NODE *p là phần tử hay Node cần chèn vào đầu danh sách:

void ChenDau(LIST &ds, NODE *p) {
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL){
        //chen dau va cuoi deu bang node p
        ds.pHead = p;
        ds.pTail = p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro next cua node p bang phan tu dang la dau tien cua danh sach
        p->next = ds.pHead;
        //gan pHead bang node p
        ds.pHead = p;
    }
}

3. Chương trình hoàn hảo thêm thành phần vào đầu list link đơn

Chương trình dưới đây gồm có không thiếu những hàm thiết yếu để triển khai việc thêm nguồn vào list link đơn :

#include 
#include 
struct Node
{
    //khai bao thanh phan du lieu co kieu int
    int data;
    //khai bao con tro next co kieu Node
    Node *next;
};
typedef struct Node NODE;

struct list{
    //thanh phan dau danh sach
    NODE *pHead;
    //thanh phan cuoi danh sach
    NODE *pTail;
};
typedef struct list LIST;

void KhoiTao(LIST &ds){
    //dat dia chi dau danh sach bang NULL
    ds.pHead = NULL;
    //dat dia chi cuoi danh sach bang NULL
    ds.pTail = NULL;
}

int KiemTraRong(LIST ds){
    //neu phan tu dau danh sach NULL
    if (ds.pHead == NULL){
        //tra ve 1 la co NULL
        return 1;
    }
    //truong hop nguoc lai tra ve khong null
    return 0;
}

NODE* TaoNode(int x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho
    if (p==NULL) {
        printf ("KHONG DU BO NHO");
        return NULL;
    }
    //gan thanh phan data = x
    p->data=x;
    //gan con tro next = NULL
    p->next=NULL;
    //tra ve node p da tao
    return p;
}

void ChenDau(LIST &ds, NODE *p) {
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL){
        //chen dau va cuoi deu bang node p
        ds.pHead = p;
        ds.pTail = p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro next cua node p bang phan tu dang la dau tien cua danh sach
        p->next = ds.pHead;
        //gan pHead bang node p
        ds.pHead = p;
    }
}

int main(){
    //khai bao mot danh sach
    LIST ds;
    //khoi tao danh sach
    KhoiTao(ds);
    //khai bao du lieu cua node
    int x = 10;
    //tao node p co du lieu x
    NODE *p = new NODE;
    p = TaoNode(x);
    //them node p vao dau danh sach
    ChenDau(ds,p);
}

Chú ý :

  • Một số hàm TaoNode(), KhoiTao(), KiemTraRong() đã được đề cập ở bài 1, bạn đọc quên vui lòng đọc lại!
  • Danh sách ở trên là danh sách liên kết đơn với kiểu dữ liệu mẫu là int
  • Để thực hiện kiểm tra phần tử vừa thêm vào danh sách vui lòng đọc đến bài duyệt phần tử trong danh sách liên kết đơn! (ở những bài tiếp theo)

admin