Danh sách liên kết

Danh sách liên kết đơn (Single linked list) là chuỗi những Node (nút) được tổ chức triển khai theo đồ vật tự tuyến tính, các bộ phận thuộc danh sách liên kết đơn được điện thoại tư vấn là các Node và chúng nằm dải rác rưởi trong cỗ nhớ.

Bạn đang xem: Danh sách liên kết

Trong danh sách links đơn mỗi phần tử đều links với thành phần đứng sau nó trong danh sách:

Trong đó:

Phần hình tròn màu xanh đầu tiên là ban đầu danh sáchPhần hình tròn màu đỏ sinh hoạt cuối là địa chỉ cửa hàng NULL cũng là phần chấm dứt danh sáchCác hình chữ nhật được chia thành hai vùng được xem như là một NODEA, B, C, D được xem như là dữ liệu (data) của một NODECác con trỏ được trỏ tới những vị trí của node tiếp sau trong danh sách link đơn2.Node trong danh sách liên kết đơn

Mỗi Node vào danh sách link đơn được phân thành hai thành phần thiết yếu đó là:

Phần data: lưu trữ dữ liệu của nodePhần liên kết: Lưu trữ add của thành phần kế tiếp vào danh sách, hoặc tàng trữ giá trị NULL nếu như là thành phần cuối thuộc trong danh sách.

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

struct Node //khai bao thanh phan du lieu teo kieu int int data; //khai bao bé tro next teo kieu Node Node *next;;typedef struct Node NODE;Trong đó:

int data: là dữ liệu của từng Node (ở đây dữ liệu này sở hữu kiểu int, ta hoàn toàn có thể biến đổi thành float hay thứ hạng SinhVien tùy vào mục đích khác nhau)Node *next: Là nhỏ trỏ mang chính kiểu tài liệu Node và có công dụng trỏ đến địa chỉ của Node tiếp sau trong danh sáchTừ khóa typedef struct để dễ ợt trong câu hỏi gọi và thực hiện NODE sau này!3.Cài để danh sách links đơnCác thư viện quan trọng cho việc thiết đặt danh sách link đơn là:

#include #include

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

Trong danh sách links đơn ban đầu, mang định sẽ có hai thành phần cùng cũng chính là hai Node là: pHead cùng pTail

Con trỏ pHead vẫn được dùng làm lưu trữ địa chỉ phần tử đầu danh sách: NODE* pHead;Để nhân thể lợi, hoàn toàn có thể sử dụng thêm một bé trỏ pTail lưu địa chỉ cửa hàng 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 tất 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áchNODE* pTail; là node sau cuối của danh sách

Chú ý rằng để thống trị một DSLK 1-1 ta chỉ việc biết địa chỉ phần tử đầu danh sách. Vì thế hãy ghi nhớ lại biện pháp 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 links đơn gồm 2 node NODE* pHead; và NODE* pTail; chúng sẽ được sử dụng tương đối nhiều cho những thao tác với cấu trúc danh sách link đơn làm việc những bài sau!

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

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

Xem thêm: Photpho Có Hai Dạng Thù Hình Quan Trọng Là, Các Dạng Thù Hình Quan Trọng Của P Là

Hàm void KhoiTao(LIST &ds) dưới đây nhận đối số đầu vào là tham chiếu LIST &ds sau đó tiến hành việc gán địa chỉ cửa hàng phần tử đầu danh sách và showroom 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 chất vấn rỗng trong danh sách liên kết đơn

Một hàm kiểm soát rỗng có chức năng kiểm tra xem danh sách links đơn đó đã có bộ phận hay không tồn tại phần tử? việc kiểm tra trống rỗng này để tiện lợi hơn cho vấn đề lấy ra phần tử trong list hoặc thêm mới 1 phần tử vào danh sách.

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

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

Xem thêm: Những Đại Diện Nào Thuộc Ngành Giun Đốt, Hãy Kể Tên Một Số Đại Diện Của Ngành Giun Đốt

Hàm NODE* TaoNode(int x) dưới phía trên có đầu vào là int x hàm này tiến hành việc tạo nên một NODE bắt đầu trong danh sách liên kết đơn với thành phần data = x với thành phần liên kết trỏ cho 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à 1 trong những kiểu dữ liệu minh họa mang đến thành phần data của NODE. Tùy vào vấn đề mà ta hoàn toàn có thể truyền vào loại dữ liệu khác biệt ví dụ như float, char hay một vẻ bên ngoài SinhVien mà ta từ bỏ định nghĩa.Hàm trả về là một NODE đang được tạo thành công!

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

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

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

#include #include struct Node //khai bao thanh phan du lieu teo 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 menu LIST;void KhoiTao(LIST &ds) //dat dia bỏ ra dau danh sach bang NULL ds.pHead = NULL; //dat dia bỏ ra 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 teo NULL return 1; //truong hop nguoc lai tra ve sầu khong null return 0;NODE* TaoNode(int x) //tao mot node phường moi NODE *p; phường = 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 bé tro next = NULL p->next=NULL; //tra ve node phường da tao return p;int main() //khai bao mot danh sach list ds; //khoi tao danh sach KhoiTao(ds); //kiem danh sach co rong tốt khong KiemTraRong(ds);Chú ý: những hàm TaoNode(), KhoiTao(), KiemTraRong() và các struct list cũng giống như struct Node sẽ được sử dụng không ít ở những bài bác tiếp theo chính vì như vậy việc hiểu và ghi nhớ bọn chúng là bắt buộc!