Mục lục bài viết
Thủ Thuật Hướng dẫn Bài tập list link đơn trong C++ 2022
Update: 2022-01-15 01:26:03,Bạn Cần biết về Bài tập list link đơn trong C++. Bạn trọn vẹn có thể lại Báo lỗi ở cuối bài để Ad đc lý giải rõ ràng hơn.
Bài viết được sự được cho phép của tác giả Khiêm Lê
Tóm lược đại ý quan trọng trong bài
- Danh sách link đơn là gì?
- Đặc điểm của list link đơn
- Cài đặt list link đơn
- Tạo list link đơn
- Thêm thành phần vào list
- Xóa thành phần khỏi list
- Duyệt list và in
- Lấy giá trị node bất kỳ
- Tìm kiếm thành phần trong list
- Đếm số thành phần của list
- Xóa list
- Tổng kết
- Source code
Danh sách link đơn là gì?
Danh sách link đơn (Single Linked List) là một cấu trúc tài liệu động, nó là một list mà mỗi thành phần đều link với thành phần đúng sau nó trong list. Mỗi thành phần (được gọi là một node hay nút) trong list link đơn là một cấu trúc có hai thành phần:
- Thành phần tài liệu: lưu thông tin về bản thân thành phần đó.
- Thành phần link: lưu địa chỉ thành phần đứng sau trong list, nếu thành phần đó là thành phần ở đầu cuối thì thành phần này bằng NULL.
Tham khảo thêm: việc làm lập trình c++ lương cao tại Topdev
Minh họa list link đơn
Đặc điểm của list link đơn
Do list link đơn là một cấu trúc tài liệu động, được tạo ra nhờ việc cấp phép động nên nó có một số trong những điểm lưu ý tại đây:
- Được cấp phép bộ nhớ khi chạy chương trình
- Có thể thay đổi kích thước qua việc thêm, xóa thành phần
- Kích thước tối đa tùy từng bộ nhớ khả dụng của RAM
- Các thành phần được tàng trữ ngẫu nhiên (không liên tục) trong RAM
Và do tính link của thành phần đầu và thành phần đứng sau nó trong list link đơn, nó có những điểm lưu ý sau:
- Chỉ cần nắm được thành phần đầu và cuối là trọn vẹn có thể quản trị và vận hành được list
- Truy cập tới thành phần ngẫu nhiên phải duyệt từ trên đầu đến vị trí đó
- Chỉ trọn vẹn có thể tìm kiếm tuyến tính một thành phần
1001 Tips: Con trỏ và hàm (Pointer & Function) trong C++
Code trò chơi rắn săn mồi trên console bằng C++
Cài đặt list link đơn
Trước khi đi vào setup list link đơn, hãy chứng minh và khẳng định rằng bạn đã nắm vững phần con trỏ và cấp phép động trong C++. Do list link đơn là một cấu trúc tài liệu động, nếu người mua không nắm vững con trỏ và cấp phép động sẽ rất khó để bạn hiểu được nội dung bài viết này. Nếu bạn cảm thấy chưa tự tin, hãy dành ít thời hạn để xembài viết nàycủa mình. Còn hiện giờ thì khởi đầu thôi!
Tạo node
Danh sách link đơn được tạo thành từ nhiều node, do đó, toàn bộ chúng ta sẽ cùng đi từ node trước. Một node gồm hai thành phần là thành phần tài liệu và thành phần link. Thành phần tài liệu trọn vẹn có thể là kiểu tài liệu có sẵn hoặc bạn tự định nghĩa (struct hay class), trong nội dung bài viết này để đơn thuần và giản dị mình sẽ sử dụng kiểu int cho phần tài liệu. Thành phần link là địa chỉ đương nhiên sẽ là con trỏ, con trỏ này trỏ đến node tiếp theo, do đó, con trỏ này là con trỏ trỏ vào một trong những node.
struct Node
int data;
Node* next;
;
Để tạo một node mới, ta tiến hành cấp phép động cho node mới, khởi tạo giá trị ban sơ và trả về địa chỉ của node mới được cấp phép.
Node* CreateNode(int init_data)
Node* node = new Node;
node->data = init_data;
node->next = NULL; // node vừa tạo chưa thêm vào list nên chưa link với thành phần nào cả nên phần link gán bằng NULL
return node;
Tạo list link đơn
Ta đã đã có được thành phần tạo ra list link đơn là node, tiếp theo toàn bộ chúng ta cần quản trị và vận hành chúng bằng phương pháp biết được thành phần đầu và cuối. Vì mỗi thành phần đều link với thành phần kế vậy nên tả chỉ việc phải ghi nhận thành phần đầu và cuối là trọn vẹn có thể quản trị và vận hành được list này. Vậy đơn thuần và giản dị ta cần tạo một cấu trúc tàng trữ địa chỉ thành phần đầu (head) và thành phần cuối (hay thành phần đuôi tail).
struct LinkedList
Node* head;
Node* tail;
;
Khi mới tạo list, list sẽ không còn tồn tại thành phần nào, do đó head và tail không trỏ vào đâu cả, ta sẽ gán chúng bằng NULL. Ta xây dựng hàm tạo list như sau:
void CreateList(LinkedList& l)
l.head = NULL;
l.tail = NULL;
Bây giờ để tạo một list, ta làm như sau:
LinkedList list;
CreateList(list); // Gán head và tail bằng NULL
Thêm thành phần vào list
Thêm vào đầu
Để thêm node vào đầu list, thứ nhất ta cần kiếm tra xem list đó có rỗng hay là không, nếu list rỗng, ta chỉ việc gán head và tail của list bằng node đó. trái lại nếu list không rỗng, ta tiến hành trỏ thành phần link vào head, tiếp sau đó gán lại head bằng node mới.
void AddHead(LinkedList& l, Node* node)
if (l.head == NULL)
l.head = node;
l.tail = node;
else
node->next = l.head;
l.head = node;
Thêm thành phần vào đầu list link đơn
Như trong hình trên, toàn bộ chúng ta thêm node có data bằng 0 vào list. Ta tiến hành trỏ next của node đó vào head của list (đó là node thứ nhất của list có data bằng 1), tiếp sau đó ta trỏ head vào node có data 0 vừa mới được thêm. Vậy là thành phần này đã nằm ở vị trí đầu list rồi.
Thêm vào thời điểm cuối
Tương tự, để thêm node vào thời điểm cuối list, thứ nhất ta kiểm tra xem list rỗng hay là không, rỗng thì gán head và tail đều bằng node mới. Nếu không rỗng, ta tiến hành trỏ tail->next vào node mới, tiếp sau đó gán lại tail bằng node mới (vì hiện giờ node mới thêm đó là tail).
void AddTail(LinkedList& l, Node* node)
if (l.head == NULL)
l.head = node;
l.tail = node;
else
l.tail->next = node;
l.tail = node;
Thêm thành phần vào thời điểm cuối list link đơn
Trong hình trên, toàn bộ chúng ta tiến hành thêm node có data bằng 6 vào list. Tail hiện tại là node có data 5, tiến hành gán tail->next bằng node mới để nối thêm nó vào đuôi list, thời gian lúc bấy giờ node mới trở thành thành phần cuối list nên ta gán tail lại bằng node mới.
Thêm vào sau node bất kỳ
Để thêm một node p. vào sau node q bất kỳ, thứ nhất ta cần kiếm tra xem node q có NULL hay là không, nếu node q là NULL tức là list rỗng, vậy thì ta sẽ thêm vào đầu list. Nếu node q không NULL, tức là tồn tại trong list, ta tiến hành trỏ p.->next = q->next, tiếp sau đó q->next = p.. Tiếp theo toàn bộ chúng ta kiểm tra xem node q trước đó liệu có phải là node cuối hay là không, nếu node q là node cuối thì thêm p. vào, p. sẽ thành node cuối nên ta gán lại tail = p..
void InsertAfterQ(LinkedList& l, Node* p., Node* q)
if (q != NULL)
p.->next = q->next;
q->next = p.;
if (l.tail == q)
l.tail = p.;
else
AddHead(l, p.);
Thêm thành phần vào sau nút Q. trong list link đơn
Trong hình trên, ta thêm node có data bằng 4 (node p.) vào sau node có data bằng 3 (node q). Ta trỏ next của node p. vào next của node q tức là node có data bằng 5, tiếp sau đó trỏ next của node q vào node p. vậy là node p. đã được thêm vào list.
Xóa thành phần khỏi list
Xóa ở đầu
Để xóa thành phần ở đầu list, ta kiểm tra xem list đó có rỗng hay là không, nếu rỗng, ta không cần xóa, trả về kết quả là 0. Nếu list không rỗng, ta tiến hành lưu node head lại, tiếp sau đó gán head bằng next của node head, tiếp sau đó xóa node head đi. Tiếp theo ta cần kiểm tra xem list vừa bị xóa đi node head có rỗng hay là không, nếu rỗng ta gán lại tail bằng NULL luôn tiếp sau đó trả về kết quả 1.
int RemoveHead(LinkedList& l, int& x)
if (l.head != NULL)
Node* node = l.head;
x = node->data; // Lưu giá trị của node head lại
l.head = node->next;
delete node; // Hủy node head đi
if (l.head == NULL)
l.tail = NULL;
return 1;
return 0;
Lưu ý trước lúc xóa node head đi, ta dùng biến tham chiếu x để tàng trữ lại giá trị của node bị hủy để sử dụng.
Xóa thành phần đầu list link đơn
Trong hình trên, mình tiến hành xóa node thứ nhất có data bằng 0. Mình trỏ head đến next của node 0 (hiện giờ đang là head), thì head thời gian lúc bấy giờ sẽ là node 1, tiếp sau đó mình hủy đi node 0 là được.
Xóa ở sau node bất kỳ
Để xóa một node p. sau node q bất kỳ, ta kiểm tra xem node q có NULL hay là không, nếu node q NULL thì không tồn tại trong list, do đó trả về 0, không xóa. Nếu node q khác NULL nhưng next của q là NULL, tức là p. bằng NULL thì không xóa, trả về 0 (do sau q không tồn tại node nào cả, q là tail). Nếu node p. tồn tại, ta tiến hành kiểm tra xem node p. liệu có phải là tail hay là không, nếu node p. là tail thì gán lại tail là q, tức là node trước đó để xóa node p. đi.
int RemoveAfterQ(LinkedList& l, Node* q, int& x)
if (q != NULL)
Node* p. = q->next;
if (p. != NULL)
if (l.tail == p.)
l.tail = q;
q->next = p.->next;
x = p.->data;
delete p.;
return 1;
return 0;
return 0;
Trong hình trên, ta tiến hành xóa node có data 3 (node p.) sau node có data 2 (node q). Ta trỏ next của node q vào next của node p. tức là node có data 4, tiếp sau đó xóa node p. đi là xong.
Duyệt list và in
Sau khi có những thao tác thêm, xóa, toàn bộ chúng ta trọn vẹn có thể in ra list để kiểm tra xem có hoạt động giải trí và sinh hoạt đúng hay là không. Để in list, ta duyệt từ trên đầu đến cuối list và in ra trong lúc duyệt. Ta gán một node bằng head, tiếp sau đó kiểm tra xem node đó có NULL hay là không, không thì in ra data của node đó, tiếp sau đó gán tiếp node đó bằng next của nó tức node đó hiện giờ là node tiếp theo, cứ như vậy cho tới hết.
void PrintList(LinkedList l)
if (l.head != NULL)
Node* node = l.head;
while (node != NULL)
cout << node->data << ‘ ‘;
node = node->next; // Chuyển sang node tiếp theo
Lấy giá trị node bất kỳ
Để lấy giá trị thành phần trong list, ta tiến hành duyệt tương tự như khi in thành phần. Ta sẽ tạo một biến đếm để biết vị trí hiện tại, duyệt qua những node cho tới khi node bằng NULL hoặc biến đếm bằng với vị trí node cần lấy. Kiểm tra xem nếu node khác NULL và biến đếm bằng vị trí cần lấy, ta sẽ trả về địa chỉ của node đó, ngược lại trả về NULL (list rỗng hoặc là vị trí cần lấy nằm ngoài phạm vi của list).
Node* GetNode(LinkedList& l, int index)
Node* node = l.head;
int i = 0;
while (node != NULL && i != index)
node = node->next;
i++;
if (i == index && node != NULL)
return node;
return NULL;
Tìm kiếm thành phần trong list
Ý tưởng tìm kiếm thành phần cũng là duyệt list, nếu như chưa tìm thấy thì tiếp tục duyệt. Sau khi kết thúc duyệt, ta chỉ việc kiểm tra xem node duyệt có bằng NULL hay là không, nếu không tức là đã tìm thấy, ta sẽ trả về địa chỉ của node đó.
Node* Search(LinkedList l, int x)
Node* node = l.head;
while (node != NULL && node->data != x)
node = node->next;
if (node != NULL)
return node;
return NULL;
Đếm số thành phần của list
Đếm số thành phần thì cũng tương tự, ta vận dụng duyệt từ trên đầu đếm cuối và đếm số node.
int Length(LinkedList l)
int count = 0;
Node* node = l.head;
while (node != NULL)
count++;
node = node->next;
return count;
Xóa list
Để xóa list, ta cần hủy toàn bộ những node tức là duyệt và hủy từng node. Ở đây mình sẽ dùng lại hàm RemoveHead. Đầu tiên, ta gán một node bằng head, kiểm tra nếu node đó khác NULL thì gọi RemoveHead và gán lại node bằng head tiếp, cứ lặp như vậy cho tới khi node đó NULL thì thôi. Sau khi xóa hết toàn bộ thành phần thì gán lại tail bằng NULL.
void DestroyList(LinkedList& l)
int x;
Node* node = l.head;
while (node != NULL)
RemoveHead(l, x);
node = l.head;
l.tail = NULL;
Tổng kết
Vậy là trong bài này, tôi đã trình làng với những bạn về list link đơn và một số trong những thao tác cơ bản trên list. Các bạn không nhất thiết phải tuân Theo phong cách của tớ, có thật nhiều phương pháp để tiến hành rất khác nhau, chỉ việc bạn nắm vững về con trỏ và cấp phép động trong C++. Nếu thấy hay, hãy nhớ là san sẻ cho bạn hữu. Cảm ơn những bạn đã theo dõi nội dung bài viết!
Source code
LinkedList.hpp
#ifndef LinkedList_hpp
#define LinkedList_hpp
struct Node
int data;
Node* next;
;
struct LinkedList
Node* head;
Node* tail;
;
Node* CreateNode(int init_data);
void CreateList(LinkedList& l);
void AddHead(LinkedList& l, Node* node);
void AddTail(LinkedList& l, Node* node);
void InsertAfterQ(LinkedList& l, Node* p., Node* q);
int RemoveHead(LinkedList& l, int& x);
int RemoveTail(LinkedList& l, int& x);
int RemoveAfterQ(LinkedList& l, Node* q, int& x);
Node* GetNode(LinkedList l, int index);
void PrintList(LinkedList l);
Node* Search(LinkedList l, int x);
int Length(LinkedList l);
void DestroyList(LinkedList& l);
#endif
LinkedList.cpp
#include
#include “LinkedList.hpp”
using namespace std;
Node* CreateNode(int init_data)
Node* node = new Node;
node->data = init_data;
node->next = NULL;
return node;
void CreateList(LinkedList& l)
l.head = NULL;
l.tail = NULL;
void AddHead(LinkedList& l, Node* node)
if (l.head == NULL)
l.head = node;
l.tail = node;
else
node->next = l.head;
l.head = node;
void AddTail(LinkedList& l, Node* node)
if (l.head == NULL)
l.head = node;
l.tail = node;
else
l.tail->next = node;
l.tail = node;
void InsertAfterQ(LinkedList& l, Node* p., Node* q)
if (q != NULL)
p.->next = q->next;
q->next = p.->next;
if (l.tail == q)
l.tail = p.;
else
AddHead(l, p.);
int RemoveHead(LinkedList& l, int& x)
if (l.head != NULL)
Node* node = l.head;
x = node->data;
l.head = node->next;
delete node;
if (l.head == NULL)
l.tail = NULL;
return 1;
return 0;
int RemoveAfterQ(LinkedList& l, Node* q, int& x)
if (q != NULL)
Node* p. = q->next;
if (p. != NULL)
if (l.tail == p.)
l.tail = q;
q->next = p.->next;
x = p.->data;
delete p.;
return 1;
return 0;
return 0;
Node* GetNode(LinkedList l, int index)
Node* node = l.head;
int i = 0;
while (node != NULL && i != index)
node = node->next;
i++;
if (i == index && node != NULL)
return node;
return NULL;
void PrintList(LinkedList l)
if (l.head != NULL)
Node* node = l.head;
while (node != NULL)
cout << node->data << ‘ ‘;
node = node->next;
Node* Search(LinkedList l, int x)
Node* node = l.head;
while (node != NULL && node->data != x)
node = node->next;
if (node != NULL)
return node;
return NULL;
int Length(LinkedList l)
int count = 0;
Node* node = l.head;
while (node != NULL)
count++;
node = node->next;
return count;
void DestroyList(LinkedList& l)
int x;
Node* node = l.head;
while (node != NULL)
RemoveHead(l, x);
node = l.head;
l.tail = NULL;
main.cpp
#include
#include “LinkedList.hpp”
using namespace std;
int main()
// Create a linked list
LinkedList list;
CreateList(list);
// Add sample data to list
Node* node;
for (auto i = 1; i <= 10; i++)
// Create new node with init data is i
node = CreateNode(i);
// Add node to head
// List that is added node by AddHead will be reversed
//AddHead(list, node);
// Add node to Tail
AddTail(list, node);
// Print list
PrintList(list);
cout << endl;
// Get list’s length
int len = Length(list);
cout << “Length of list: “ << len << endl;
// Get node at index 7
Node* nodeAtIdx7 = GetNode(list, 7);
if (nodeAtIdx7 != NULL)
cout << “Data at node have idx 7: “ << nodeAtIdx7->data << endl;
// Search for 4 in list
Node* search4InList = Search(list, 4);
if (search4InList != NULL)
cout << “4 was founded” << endl;
else
cout << “4 not Found” << endl;
// Remove node after 4 in list
int x;
int res = RemoveAfterQ(list, search4InList, x);
if (res)
cout << “Data of node has been removed: “ << x << endl;
cout << “List after removed: “;
PrintList(list);
cout << endl;
else
cout << “Nothing is removed” << endl;
// Insert 2409 after node 4
Node* node2409 = CreateNode(2409);
InsertAfterQ(list, node2409, search4InList);
cout << “List after insert 2409 after 4: “;
PrintList(list);
cout << endl;
// Remove Head
res = RemoveHead(list, x);
if (res)
cout << “Data of node has been removed: “ << x << endl;
cout << “List after removed head: “;
PrintList(list);
cout << endl;
else
cout << “Nothing is removed” << endl;
// Destroy all node
DestroyList(list);
return 0;
Reply
2
0
Chia sẻ
– Một số từ khóa tìm kiếm nhiều : ” Review Bài tập list link đơn trong C++ tiên tiến và phát triển nhất , Chia Sẻ Link Tải Bài tập list link đơn trong C++ “.
Thảo Luận vướng mắc về Bài tập list link đơn trong C++
You trọn vẹn có thể để lại phản hồi nếu gặp yếu tố chưa hiểu nghen.
#Bài #tập #danh #sách #liên #kết #đơn #trong
Bình luận gần đây