Trong bài ngày hôm nay, mình sẽ giới thiệu cho các bạn về danh sách liên kết đơn và một số thao tác trên danh sách liên kết đơn C++ mà bạn cần lưu ý. Có rất nhiều cách để thực hiện các thao tác trên, bạn không nhất thiết phải làm theo cách của mình nhưng quan trọng là bạn cần nắm vững được kiến thức về con trỏ và các cấp phát động trong C++.
Đừng quên chia sẻ cho bạn bè và người thân nếu cảm thấy kiến thức bổ ích nhé.
Một số các thao tác trên danh sách liên kết đơn C++ cơ bản
Thêm phần tử vào đầu danh sách:
– Đầu vào: DSLK đơn l, phần tử p cần thêm
– Kết quả: DSLK đơn l sau khi thêm
– Giải thuật:
* Trường hợp 1: Nếu đơn l rỗng thì con trỏ đầu và cuối của danh sách bằng p
* Trường hợp 2: (l khác rỗng)
Bước 1: p trỏ kế tiếp vào đầu danh sách
Bước 2: Gán con trỏ đầu = p
– Cài đặt: void ThemDau(LIST &l, NODE *p) { if(l.pHead==NULL) l.pHead=l.pTail=p; else { p->pNext = l.pHead; l.pHead = p; } }
Minh họa thêm phần tử vào đầu danh sách
Thêm phần tử vào cuối danh sách
– Đầu vào: DSLK đơn l, phần tử p cần thêm
– Kết quả: DSLK đơn l sau khi thêm
– Giải thuật:
* Trường hợp 1: Nếu đơn l rỗng thì con trỏ đầu và cuối của danh sách bằng p
* Trường hợp 2: (l khác rỗng)
Bước 1: Con trỏ cuối của danh sách trỏ kế tiếp vào p
Bước 2: Gán con trỏ cuối = p
– Cài đặt: void ThemCuoi(LIST &l, NODE *p) { if(l.pHead==NULL) l.pHead=l.pTail=p; else { l.pTail->pNext =p; l.pTail = p; } }
Minh họa thêm phần tử vào cuối danh sách
Thêm phần tử vào sau một phần tử cho trước
– Đầu vào: DSLK đơn l, phần tử k cần thêm và phần tử p
– Kết quả: DSLK đơn l sau khi thêm k sau p
– Giải thuật:
* Trường hợp 1: Nếu p là con trỏ cuối của danh sách thì Thêm k vào cuối danh sách l
* Trường hợp 2: là p khác con trỏ cuối
Bước 1: pSau là con trỏ đứng sau p
Bước 2: Cho p trỏ tới k
Bước 3: Cho k trỏ tới pSau
– Cài đặt: void ThemkSaup(LIST &l, NODE *p, NODE *k) { if(p==l.pTail) ThemCuoi(l, k); else { NODE *pSau = p->pNext; p->pNext = k; k->pNext = pSau; } }
Ảnh minh họa thêm phần tử vào sau một phần tử cho trước
Thêm phần tử k vào trước một phần tử p cho trước
– Đầu vào: DSLK đơn l là phần tử k cần thêm và phần tử p
– Kết quả: DSLK đơn l là sau khi thêm k ở trước p
– Giải thuật:
Bước 1: Thêm k vào sau p
Bước 2: Hoán vị giá trị của p và k – Cài đặt: void ThemkTruocp(LIST &l, NODE *p, NODE *k) { ThemkSaup(l, p, k); int tam = p->Key; p->Key = k->Key; k->Key = tam; }
Xóa phần tử đầu
– Đầu vào: DSLK đơn l
– Kết quả: DSLK đơn l sau khi xóa phần tử đầu
– Giải thuật:
* Trường hợp 1: Nếu l rỗng thì kết thúc
* Trường hợp 2: (l khác rỗng)
Bước 1: pXoa là con trỏ đầu của danh sách
Bước 2: Cho con trỏ đầu trỏ vào phần tử kế tiếp
Bước 3: Xóa pXoa B4: Nếu con trỏ đầu = NULL thì gán con trỏ cuối = NULL
Ảnh minh họa xóa phần tử đầu liên kết
Danh sách liên kết đơn
Danh sách liên kết đơn hay còn gọi là Single Linked List, đây là một cấu trúc dữ liệu động, một danh sách mà mỗi phần tử luôn liên kết với phần tử đứng kế sau nó trong danh sách.
Mỗi phần tử hay còn gọi là một node hoặc nút trong danh sách liên kết đơn. Đây là một cấu trúc bao gồm hai thành phần chính:
- Thành phần dữ liệu chuyên lưu thông tin về chính phần tử đó.
- Thành phần liên kết thì lại chuyên lưu địa chỉ phần tử đứng sau nó trong danh sách, và nếu như phần tử đó đã là phần tử cuối cùng thì thành phần này = NULL.
Nếu phần tử cuối thì thành phần bằng NULL
Các đặc điểm của danh sách liên kết đơn cần phải biết
Khi muốn tìm hiểu thao tác trên danh sách liên kết đơn C++ thì bạn nên nắm được một số đặc điểm cơ bản của danh sách liên kết đơn:
- Khi chạy chương trình thì sẽ được cấp phát bộ nhớ
- Thông qua việc thêm hoặc xóa phần tử thì có thể thay đổi được kích thước
- Bộ nhớ khả dụng của RAM sẽ quyết định kích thước tối đa
- Các phần tử sẽ được ngẫu nhiên lưu trữ một cách không liên tiếp trong RAM
Dựa vào tính liên kết của phần tử đầu và phần tử đứng sau nó nên có các đặc điểm sau:
- Để có thể quản lý được danh sách chỉ cần nắm được phần tử đầu và cuối
- Đối với phần tử ngẫu nhiên cần phải duyệt từ đầu đến vị trí đó
- Khi tìm kiếm thì chỉ có thể tìm kiếm tuyến tính một phần tử mà thôi.
Bài viết bên trên chỉ liệt kê một vài thao tác trên danh sách liên kết đơn C++ cơ bản mà bạn cần lưu ý. Nếu bạn muốn biết thêm nhiều thông tin nữa hay theo dõi ở những bài viết trên nhé!
