Một số thao tác trên danh sách liên kết đơn C++ bạn cần chú ý tới. Show
Liên kết đơn C++ là một cấu trúc dữ liệu quan trọng, vì vậy danh sách các liên kết đơn C++ nhận được sự quan tâm rất lớn từ mọi người. Trong bài viết hôm nay, chúng tôi sẽ giới thiệu tới bạn một các thao tác trên danh sách liên kết đơn C++ cùng các đặc điểm của loại liên kết này.  Như thế nào là danh sách liên kết đơn?Danh sách liên kết đơn hay còn được gọi là Single Linked List, nó là một cấu trúc dữ liệu động, một danh sách mà trong đó mỗi phần tử sẽ luôn liên kết với phần tử ở phía kế sau nó trong danh sách. Mỗi phần tử còn gọi là một node hoặc nút nằm trong danh sách liên kết đơn, và một cấu trúc sẽ có hai thành phần chính gồm: – Thành phần dữ liệu: Chuyên lưu thông tin về chính phần tử đấy. – Thành phần liên kết: Chuyên lưu địa chỉ phần tử đứng sau nó ở trong danh sách, nếu phần tử đó là phần tử cuối cùng thì thành phần này bằng NULL. Đặc điểm cơ bản của danh sách liên kết đơn C++Bởi danh sách đơn là một cấu trúc dữ liệu di động, được tạo nên nhờ vào việc cấp phát động cho nên sẽ có một số đặc điểm sau: – Sẽ được cấp phát bộ nhớ khi chạy. – Có thể thay đổi được kích thước thông qua việc thêm hoặc xóa phần tử. – Bộ nhớ khả dụng của RAM sẽ có quyết định tới kích thước tối đa. – Các phần tử được ngẫu nhiên lưu trữ ( không liên tiếp) ở trong RAM. Và dựa vào tính liên kết của phần tử đầu và phần tử liền kề sau nó trong danh sách đơn mà có các đặc điểm như: – Chỉ cần nắm được danh sách chỉ dẫn đầu và cuối là đã có thể quản lý được danh sách. – Đối với phần tử ngẫu nhiên bạn cần phải duyệt từ đầu đến vị trí đấy. – Khi tìm kiếm thì chỉ có thể tìm tuyến tính một phần tử mà thôi. Các thao tác cơ bản trên danh sách đơn C++Khi đã có được thành phần tạo nên danh sách đơn thì bạn cần thực hiện một số thao tác để quản lý danh sách này. Thao tác thêm phần tử vào phần đầu của danh sách liên kết.– Đầu vào: Danh sách liên kết đơn l, phần tử p cần thêm vào. – Kết quả: Danh sách liên kết đơn l sau khi thêm. – Giải thuật gồm 2 trường hợp là: + Trường hợp 1: Nếu đơn l rỗng thì con trỏ đầu và cuối của danh sách sẽ bằng p. + Trường hợp 2: l khác rỗng. – Bước 1: p trỏ kế tiếp vào phần đầu của danh sách. – Bước 2: Cần gán con trỏ đầu = p . – void ThemDau(LIST &l, NODE *p) { if(l.pHead==NULL) l.pHead=l.pTail=p; else { p -> pNext = l.pHead; l.pHead = p; } } Thao tác thêm phần tử vào cuối của danh sách liên kết.Tương tự như thêm vào đầu danh sách, để thêm node vào cuối danh sách bạn cần kiểm tra xem danh sách rỗng hay không rỗng. Nếu rỗng thì cần gán head và tail bằng node mới. Còn nếu không rỗng thì bạn thực hiện trỏ tail -> next vào node mới, tiếp đó gán lại tail bằng node mới ( bởi bấy giờ node mới thêm chính là tail). – void ThemCuoi(LIST &l, NODE *p) { if(l.pHead= =NULL) l.pHead=l.pTail=p; else { l.pTail->pNext =p; l.pTail = p; } } Thêm vào sau node bất kỳ trong danh sách.Để có thể thêm một node p vào sau node q bất kỳ nào trong danh sách, trước hết bạn cần kiểm tra xem node q có NULL hay không. Nếu node q là NULL thì nghĩa là danh sách rỗng, và bạn sẽ thêm vào đầu danh sách. Còn nếu node q không NULL, thì nghĩa là tồn tại trong danh sách và bạn thực hiện trỏ p -> next = q -> next, sau đó q -> next = p. Tiếp đó bạn tiến hành kiểm tra xem node q trước đó có phải là node cuối hay không. Trong trường hợp node q là node cuối thì hãy thêm p vào, lúc đó p sẽ thành node cuối nên bạn 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);} Xóa phần tử ở đầu của danh sách liên kết.Nếu muốn xóa phần tử ở đầu danh sách thì bạn cần kiểm tra xem danh sách đó có rỗng hay không rỗng, Nếu rỗng thì bạn không cần xóa trả về kết quả là 0. Còn nếu danh sách không rỗng, người dùng hãy thực hiện lưu node head lại, tiếp đó cần gán head bằng next của node head, tiếp đó là xóa node head đi. Tiếp theo, bạn sẽ cần kiểm tra lại xem danh sách vừa bị xóa đi node head có rỗng hay không rỗng. Nếu trường hợp rỗng thì cần gán lại tail bằng NULL luôn rồi trả về kết quả 1. Xóa phần tử ở sau node bất kỳ trong danh sách.Muốn xóa một node p sau node q bất kỳ thì trước hết bạn kiểm tra xem node q có NULL không. Nếu node q NULL thì không tồn tại ở danh sách và trả về 0, không xóa. Còn nếu node q khác NULL, nhưng next của q là NULL nghĩa là p bằng NULL thì không xóa và về 0. Nếu node p tồn tại thì bạn kiểm tra xem node p có tail hay không, nếu là tail thì hãy gán lại tail là q. Kết luậnNhư vậy với những thông tin hôm nay, chúng tôi đã giới thiệu tới bạn các thông tin cơ bản về danh sách liên kết đơn C++ và các thao tác trên danh sách liên kết đơn C++ đơn giản. Mong rằng đây sẽ là những chia sẻ có ích với bạn trong quá trình thao tác với danh sách dữ liệu này.
Bạn đã biết gì về danh sách liên kết đơn trong C++? Nó có gì giống và khác với mảng? Hãy cùng tìm hiểu trong bài viết này nhé! 1. Danh sách liên kết đơn là gì?Về cơ bản, danh sách liên kết đơn (Singly linked list) có chức năng giống với mảng (array) như thêm, xóa phần tử,...Tuy nhiên danh sách liên kết là một cấu trúc dữ liệu đệ quy. Một danh sách liên kết sẽ bao gồm các "node". Mỗi "node" gồm 2 thành phần là dữ liệu (data) và con trỏ để trỏ tới "node" tiếp theo nhằm tạo mối liên kết. Nếu số lượng mối liên kết của mỗi "node" là một thì danh sách trên được gọi là danh dách liên kết đơn. 2. Danh sách liên kết đơn và mảngMột số ưu điểm của danh sách liên đơn so với mảng:
Thử tưởng tượng bạn là một nhân viên bán vé xe. Xe của bạn hiện đang còn trống các chỗ như hình minh họa. Giả sử có 1 gia đình 16 người đến đặt vé và yêu cầu đặt ra là vị trí ngồi của họ phải liên tiếp nhau. Sẽ chẳng có cách nào cho bạn đế đáp ứng yêu cầu đó mặc dù số lượng chỗ trống của bạn là đủ bởi yêu cầu các vị trí phải liên tiếp nhau. Lúc này nếu không tìm được khách hàng thích hợp thì chuyến xe của bạn vẫn sẽ khởi hành và lãng phí 16 ghế trống đó. Nhưng nếu như đó là 16 vị khách ngẫu nhiên và không phải ràng buộc bởi điều kiện vị trí ngồi liên tiếp nhau thì bạn có thể dễ dàng bố trí các hành khách này vào các vị trí trống để lấp đầy xe. Yêu cầu các vị trí liên tiếp nhau cũng chính là đặc điểm của mảng. Như vậy sau một thời gian thực hiện các thao tác xin cấp phát và giải phóng hiện trạng bộ nhớ của bạn có thể bị phân mảnh. Lúc này, nếu chương trình xin cấp phát một vùng nhớ có kích thước m bytes nhưng không có vùng nhớ liên tục nào có kích thước lớn hơn hoặc bằng m bytes(cho dù tổng vùng nhớ còn trống thì đủ) thì hệ thống cũng không thể cấp phát được. Danh sách liên kết đơn có thể giải quyết được vấn đề này bởi lẽ kích thước của một "node" thường khá nhỏ cộng với việc vùng nhớ của các "node" có thể nằm rải rác trong heap.
Thử nhớ lại để xóa một phần tử của mảng gồm n phần tử tại vi trí thứ i bạn phải làm gì? Bạn phải gán đè các giá trị từ j + 1 vào j (với j chạy từ i đến n - 1) sau đó giảm n xuống 1 đơn vị. Với mảng tĩnh thực chất việc xóa phần tử chỉ là việc bạn dồn các phần tử khác lên một đơn vị đè lên vị trí muốn xóa, phần tử cuối cùng vẫn tồn tại ở đó và chiếm dụng bộ nhớ. Với mảng động, bạn có thể khắc phục được tình trạng phần tử cuối cùng vẫn tồn tại bằng cách xin cấp phát lại một vùng nhớ mới có kích thước của n - 1 phần tử, chuyển n - 1 phần tử ở vùng nhớ hiện tại sang vùng nhớ mới sau đó giải phóng vùng nhớ cũ. Tuy nhiên, với cả mảng động và mảng tĩnh chúng ta đều phải dời tất cả phần tử (kể từ vị trí cần xóa + 1) sang trái 1 đơn vị. Xét về khía cạnh độ phức tạp của giải thuật thì trong trường hợp này, thao tác gán đè có chi phí rất cao(chi phí tuyến tính) bởi chương trình phải chuyển dời một dãy phần tử. Với việc thêm một phần tử vào mảng chúng ta cũng phải thực hiện những bước tương tự như trên. Với danh sách liên kết đơn việc thêm hay chèn này được thực hiện khá dễ dàng, đó chỉ đơn giản là bạn phải thay đổi các mối liên kết (giải phóng vùng nhớ với của phần tử bị xóa với việc xóa phần tử). Về cơ bản thì những thao tác này chỉ có chi phí hằng số. Vậy rốt cuộc danh sách liên kết đơn có nhược điểm nào không? Câu trả lời là có, bởi nếu không thì mảng đã không tồn tại. Chính những ưu điểm của mảng lại là nhược điểm của danh sách liên kết đơn:
3. Xây dựng và một số thao tác trên danh sách liên kết đơn:Một "node" của danh sách liên kết đơn được xây dựng như sau (ở đây để đơn giản mình sẽ để data có kiểu dữ liệu int). typedef struct node* point; // typedef lại để code được rõ ràng và gọn gàng hơn struct node{ int data; point next; };Để thuận tiện cho việc xây dựng các hàm thêm và xóa mình sẽ xây dựng hàm getNode, hàm này nhằm mục đích tạo ra 1 "node" có phần dữ liệu là x, giá trị hàm trả về là địa chỉ "node" đó. point getNode(int x) { point p; p = (point)malloc(sizeof(node)); if(p != NULL) { p->data = x; p->next = NULL; } return p; }Để quản lí danh sách liên kết đơn, người ta thường dùng 1 con trỏ trỏ vào "node" đầu tiên của danh sách (ở đây mình đặt tên là head), bên cạnh đó để tiện cho việc quản lí có thể dùng thêm 1 con trỏ trỏ vào "node" cuối cùng của danh sách (tail). Yêu cầu phải được đảm bảo là trong suốt quá trình thực hiện chương trình head luôn trỏ đến "node" đầu tiên, tail luôn trỏ tới "node" cuối cùng của danh sách. Nếu không đảm bảo được điều này, danh sách liên kết có thể dẫn đến những sự cố không mong muốn. Khi khai báo point head = NULL, tail = NULL;cho ta biết rằng danh sách này là danh sách rỗng. Thêm 1 phần tử vào đầu danh sách void addFirst(point &head, point &tail, int x) { point r = getNode(x); if(head == NULL) head = tail = r; else { r->next = head; head = r; } }Thêm 1 phần tử vào cuối danh sách void addLast(point &head,point &tail, int x) { point r = getNode(x); if(head == NULL) head = tail = r; else { tail->next = r; tail = r; } }Thêm 1 phần tử có giá trị x vào sau "node" p void addAfter(point p, int x) { point q = getNode(x); q->next = p->next; p->next = q; }Xóa 1 phần tử ở đầu danh sách void deleteFirst(point &head) { if(head == tail) { free(head); head = tail = NULL; } else { point temp = head->next; free(head); head = temp; } }Xóa 1 phần tử ở cuối danh sách void deleteLast(point &head, point &tail) { if(head == tail) { free(head); head = tail = NULL; } else { point p = head; while(p->next != NULL) p = p->next; free(tail); tail = p; p->next = NULL; } }Hủy danh sách liên kết đơn void delList(point &head) { point temp = NULL; while(head) { temp = head; head = head->next; free(temp); } }4.Tạm kếtTrên đây là những trình bày sơ lược của mình về danh sách liên kết đơn. Hi vọng những chia sẻ của mình có thể đem đến cho các bạn một cái nhìn tổng quan về danh sách liên kết đơn. Chúc các bạn học tốt! |
