Lập trình C: Bài 13 – Danh sách liên kết đơn cài bằng con trỏ

Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 130 responses


Danh sách liên kết có thể được cài đặt bằng mảng hoặc bằng con trỏ. Trong bài viết này mình sẽ hướng dẫn các bạn sử dụng con trỏ :), Loại danh sách này gọi tắt là danh sách liên kết đơn

Trong các bài trước mình viết code tất cả đều là chuẩn C, nhưng từ bây giờ mình sẽ xen lẫn chút cấu trúc của C++ nên code trong bài này bạn để trong file *.cpp nhé.

Danh sách liên kết có thể được mô tả như sau:

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

Trong đó Data là dữ liệu của mỗi Node, có thể là Sinh viên, công nhân,… (có kiểu item, và mình làm đơn giản với số nguyên), Next là con trỏ trỏ tới phần tử tiếp theo.

[qads]

1. Cài đặt danh sách

code by nguyenvanquan7826
1
2
3
4
5
6
7
typedef int item; //kieu cac phan tu dinh nghia la item
typedef struct Node //Xay dung mot Node trong danh sach
{
    item Data; //Du lieu co kieu item
    Node *next; //Truong next la con tro, tro den 1 Node tiep theo
};
typedef Node *List; //List la mot danh sach cac Node

2 Khởi tạo danh sách rỗng

code by nguyenvanquan7826
1
2
3
4
void Init (List &L) // &L lay dia chi cua danh sach ngay khi truyen vao ham
{
    L=NULL; //Cho L tro den NULL
}

Trong các bài trước để có thể thay đổi được giá trị của đối mà ta truyền vào hàm ta thưòng dùng biến con trỏ (*) và trong lời gọi hàm ta cần có & trước biến tuy nhiên khi chúng ta sử dụng cách truyền địa chỉ ngay khi khởi tạo hàm thì trong lời gọi hàm ta tiên hành truyền biến bình thưòng mà không phải lấy địa chỉ (thêm &) trước biến nữa.
(Đây là một cách truyền địa chỉ cho biến trong hàm ở C++.)

3 Kiểm tra danh sách rỗng hay không

Cái này khỏi giải thích nhiều:

code by nguyenvanquan7826
1
2
3
4
int Isempty (List L)
{
    return (L==NULL);
}

4 Tính độ dài danh sách

Ta dùng 1 Node để duyệt từ đầu đến cuối, vừa duyệt vừa đếm

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
int len (List L)
{
    Node *P=L; //tao 1 Node P de duyet danh sach L
    int i=0; //bien dem
    while (P!=NULL) //trong khi P chua tro den NULL (cuoi danh sach thi lam)
    {
        i++; //tang bien dem
        P=P->next; //cho P tro den Node tiep theo
    }
    return i; //tra lai so Node cua l
}

5 Tạo 1 Node trong danh sách

Việc tạo 1 Node chứa thông tin trong danh sách sẽ giúp ta dễ dàng chèn, xóa và quản lý danh sách hơn. Trước tiên ta sẽ phải cấp phát vùng nhớ cho Node và sau đó gán Data vào là ok

code by nguyenvanquan7826
1
2
3
4
5
6
7
Node *Make_Node (Node *P, item x) //tao 1 Node P chua thong tin la x
{
    P = (Node *) malloc (sizeof (Node)); //Cap phat vung nho cho P
    P->next = NULL; //Cho truong Next tro den NULL
    P->Data = x; //Ghi du lieu vao Data
    return P;
}

6 Chèn Node P vào vị trí đầu tiên

Để chèn P vào đầu danh sách trước tiên ta cho P trỏ đến L, sau đó chỉ việc cho L trỏ lại về P là ok

Chèn vào đầu danh sách liên két
Chèn vào đầu danh sách liên két
code by nguyenvanquan7826
1
2
3
4
5
6
7
void Insert_first (List &L, item x)  //Chen x vao vi tri dau tien trong danh sach
{
    Node *P;
    P = Make_Node(P,x); //tao 1 Node P
    P->next = L; //Cho P tro den L
    L = P; //L tro ve P
}

7. Chèn Node P vào vị trí k trong danh sách

Trước tiên ta kiểm tra vị trí chèn có hợp lệ không, nếu hợp lệ kiểm tra tiếp chèn vào vị trí 1 hay k >1 . Với k >1 ta thực hiện duyệt bằng Node Q đến vị trí k-1 sau đó cho P->Next trỏ đến Node Q->Next, tiếp đến cho Q->Next trỏ đến P

Chèn phàn tử vào vị trí k trong danh sách liên kết
Chèn phàn tử vào vị trí k trong danh sách liên kết
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
void Insert_k (List &L, item x, int k) //chen x vao vi tri k trong danh sach
{
    Node *P, *Q = L;
    int i=1;
    if (k<1 || k> len(L)+1) printf("Vi tri chen khong hop le !"); //kiem tra dieu kien
    else
    {
        P = Make_Node(P,x); //tao 1 Node P
        if (k == 1) Insert_first(L,x); //chen vao vi tri dau tien
        else //chen vao k != 1
        {
            while (Q != NULL && i != k-1) //duyet den vi tri k-1
            {
                i++;
                Q = Q->next;
            }
            P->next = Q->next;
            Q->next = P;
        }
    }
}

8 Tìm phần tử co giá trị x trong danh sách

Ta duyệt danh sách cho đến khi tìm thấy hoặc kết thúc và trả về vị trí nếu tìm thấy, ngược lại trả về 0

code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
int Search (List L, item x) //tim x trong danh sach
{
    Node *P=L;
    int i=1;
    while (P != NULL && P->Data != x) //duyet danh sach den khi tim thay hoac ket thuc danh sach
    {
        P = P->next;
        i++;
    }
    if (P != NULL) return i; //tra ve vi tri tim thay
    else return 0; //khong tim thay
}

9 Xóa phần tử ở vị trí đầu tiên

Trước tiên ta lưu giá trị của phần tử đầu tiên vào biến x, sau đó tiền hành cho L trỏ đến L->Next

Xóa phần tử đầu tiên trong danh sách
Xóa phần tử đầu tiên trong danh sách
code by nguyenvanquan7826
1
2
3
4
5
void Del_frist (List &L, item &x) //Xoa phan tu dau tien
{
    x = L->Data; //lay gia tri ra neu can dung
    L = L->next; //Cho L tro den Node thu 2 trong danh sach
}

10. Xóa phần tư ở vị trí k

Dùng P duyệt đến vị trí k-1 và tiến hành cho P->Next trỏ đến phần tư kế tiếp k mà bỏ qua k. Lưu ý trong hình mình quên không lưu lại giá trị cần xóa tuy nhiên các bạn cần lưu lại như khi xóa ở vị trí đầu tiên.

Xóa phần tử thứ k trong danh sách liên kết
Xóa phần tử thứ k trong danh sách liên kết
code by nguyenvanquan7826
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
void Del_k (List &L, item &x, int k) //Xoa Node k trong danh sach
{
    Node *P=L;
    int i=1;
    if (k<1 || k>len(L)) printf("Vi tri xoa khong hop le !"); //kiem tra dieu kien
    else
    {
        if (k==1) Del_frist(L,x); //xoa vi tri dau tien
        else //xoa vi tri k != 1
        {
            while (P != NULL && i != k-1) //duyet den vi tri k-1
            {
                P=P->next;
                i++;
            }
            P->next = P->next->next; //cho P tro sang Node ke tiep vi tri k
        }
    }
}

11. Xóa phần tử có giá trị x

Đon giản là ta tìm x trong danh sách bằng hàm Search và xóa tại vị trí tìm thấy mà ta nhận được

code by nguyenvanquan7826
1
2
3
4
void Del_x (List &L, item x) //xoa phan tu x trong danh sach
{
    while (Search(L,x)) Del_k (L,x,Search(L,x)); //trong khi van tim thay x thi van xoa
}

12. Chương trình hoàn chỉnh (full)

[rps-include post=”2703″ shortcodes=”false”]