Cài đặt Danh Sách Liên Kết đơn C/C++ – Single Linked List

Một cấu trúc danh sách đơn giản nhất mà ta đã từng biết đó chính là phương pháp cài đặt danh sách liên kết kề sử dụng mảng. Việc cài đặt danh sách bằng mảng cho thấy sự kém hiệu quả trong nhiều vấn đề như: kích thước cố định, thừa (hoặc thiếu) vùng nhớ, các phần tử tuần tự không linh động. Vì vậy, cần có một cấu trúc dữ liệu đáp ứng được yêu cầu: linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống. Thế nên cấu trúc danh sách liên kết được ra đời để khắc phục các nhược điểm trên!

1.Danh sách liên kết đơn là gì?

Danh sách liên kết đơn (Single linked list) là chuỗi các Node (nút) được tổ chức theo thứ tự tuyến tính, các phần tử thuộc danh sách liên kết đơn được gọi là các Node và chúng nằm dải rác trong bộ nhớ.

Trong danh sách liên kết đơn mỗi phần tử đều liên kết với phần tử đứng sau nó trong danh sách:

Trong đó:

• Phần hình tròn màu xanh đầu tiên là bắt đầu danh sách
• Phần hình tròn màu đỏ ở cuối là địa chỉ NULL cũng là phần kết thúc danh sách
• Các hình chữ nhật được chia thành hai vùng được coi là một NODE
• A, B, C, D được coi là dữ liệu (data) của một NODE
• Các con trỏ được trỏ tới các vị trí của node tiếp theo trong danh sách liên kết đơn

2.Node trong danh sách liên kết đơn

Mỗi Node trong danh sách liên kết đơn được chia thành hai thành phần chính đó là:

• Phần data: lưu trữ dữ liệu của node
• Phần liên kết: Lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối cùng trong danh sách.

Cách khai báo một Node trong danh sách liên kết đơn bằng C/C++:

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;

Trong đó:

• int data: là dữ liệu của mỗi Node (ở đây dữ liệu này mang kiểu int, ta hoàn toàn có thể thay đổi thành float hay kiểu SinhVien tùy vào mục đích khác nhau)
• Node *next: Là con trỏ mang chính kiểu dữ liệu Node và có chức năng trỏ đến địa chỉ của Node tiếp theo trong danh sách
• Từ khóa typedef struct để dễ dàng trong việc gọi và sử dụng NODE sau này!

3.Cài đặt danh sách liên kết đơn

Các thư viện cần thiết cho việc cài đặt danh sách liên kết đơn là:

#include <stdio.h> #include <stdlib.h>

3.1 Khai báo một cấu trúc danh sách liên kết đơn

Trong danh sách liên kết đơn ban đầu, mặc định sẽ có hai thành phần và cũng chính là hai Node là: pHead và pTail

• Con trỏ pHead sẽ được dùng để lưu trữ địa chỉ phần tử đầu danh sách: NODE* pHead;
• Để tiện lợi, có thể sử dụng thêm một con trỏ pTail lưu địa chỉ phần tử cuối danh sách: NODE* pTail;

Cách khai báo một danh sách liên kết đơn mặc định có hai Node là NODE* pHead; và NODE* pTail;

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

Trong đó:

• NODE* pHead; là node đầu tiên của danh sách
• NODE* pTail; là node cuối cùng của danh sách

Chú ý rằng để quản lý một DSLK đơn ta chỉ cần biết địa chỉ phần tử đầu danh sách. Vì thế hãy ghi nhớ lại cách khai báo một node trong danh sách liên kết đơn (xem lại ở phần 2) và cách để khai báo một danh sách liên kết đơn gồm 2 node NODE* pHead; và NODE* pTail; chúng sẽ được sử dụng rất nhiều cho những thao tác với cấu trúc danh sách liên kết đơn ở những bài sau!

3.2 Hàm khởi tạo danh sách liên kết đơn

Mặc định ban đầu khi danh sách được khởi tạo, các thành phần NODE* pHead và NODE* pTail của danh sách được coi là rỗng (NULL). Vì vậy, hàm khởi tạo là thao tác gán giá trị con trỏ quản lý địa chỉ đầu (NODE* pHead) và cuối (NODE *pTail) của danh sách về con trỏ NULL.

Hàm void KhoiTao(LIST &ds) dưới đây nhận đối số đầu vào là tham chiếu LIST &ds sau đó thực hiện việc gán địa chỉ phần tử đầu danh sách và địa chỉ cuối danh sách về NULL

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

3.3 Hàm kiểm tra rỗng trong danh sách liên kết đơn

Một hàm kiểm tra rỗng có chức năng kiểm tra xem danh sách liên kết đơn đó đã có phần tử hay không có phần tử? Việc kiểm tra rỗng này để thuận tiện hơn cho việc lấy ra phần tử trong danh sách hoặc thêm mới một phần tử vào danh sách.

Hàm int KiemTraRong(LIST ds) dưới đây nhận đầu vào là LIST ds và thực hiện kiểm tra xem phần tử đầu và phần tử cuối của danh sách có là NULL hay không? Nếu là NULL thì danh sách đó được coi là rỗng (NULL). Tuy nhiện, vì trong danh sách liên kết đơn, các phần tử được truy cập tuần tự nên điều kiện cần kiếm tra được rút gọn thành nếu phần tử đầu tiên của danh sách NULL thì toàn bộ danh sách đều là 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; }

3.4 Hàm tạo một NODE trong danh sách liên kết đơn

Mỗi NODE trong danh sách liên kết đơn ta tưởng tượng giống như một phần tử của mảng vậy. Tuy nhiên một NODE lại khác một phần tử mảng ở việc có 2 thành phần đó là thành phần data và thành phần liên kết. Vì thế , để có được một NODE ta cần phải khai báo được 2 thành phần trên.

Hàm NODE* TaoNode(int x) dưới đây có đầu vào là int x hàm này thực hiện việc tạo ra một NODE mới trong danh sách liên kết đơn với thành phần data = x và thành phần liên kết trỏ đến NULL

NODE* TaoNode(int x) {     //tao mot node p moi     NODE *p;     p = new NODE;     //neu p==NULL thi khong du bo nho va ket thuc viec tao node     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; }

Chú ý:

• Int x được truyền vào hàm trên chỉ là một kiểu dữ liệu minh họa cho thành phần data của NODE. Tùy vào bài toán mà ta có thể truyền vào kiểu dữ liệu khác nhau ví dụ như float, char hay một kiểu SinhVien mà ta tự định nghĩa.
• Hàm trả về là một NODE đã được tạo thành công!

Hàm trên được sử dụng chính cho công việc thêm phần tử vào trong danh sách liên kết đơn ở những bài sau. Vì thế hay ghi nhớ lại hàm trên!

4.Chương trình cài đặt danh sách liên kết đơn hoàn chỉnh

Chương trình dưới đây là một chương trình cài đặt một danh sách liên kết đơn hoàn chỉnh (đầy đủ các hàm ở trên).

#include <stdio.h> #include <stdlib.h> 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; } int main(){ //khai bao mot danh sach LIST ds; //khoi tao danh sach KhoiTao(ds); //kiem danh sach co rong hay khong KiemTraRong(ds); }

Chú ý: Các hàm TaoNode(), KhoiTao(), KiemTraRong() và các struct list cũng như struct Node sẽ được sử dụng rất nhiều ở những bài tiếp theo vì thế việc hiểu và ghi nhớ chúng là bắt buộc!