Các thao tác trên danh sách liên kết đơn C++

Posted on Updated on by adminChuyên mục:Kiến thức Internet

Rate this post

Một số thao tác trên danh sách liên kết đơn C++ bạn cần chú ý tới.

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.

các thao tác trên danh sách liên kết đơn c++

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 tài liệu động, một danh sách mà trong đó mỗi thành phần sẽ luôn liên kết với thành phần ở phía kế sau nó trong danh sách .
Mỗi thành phần 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 tài liệu : Chuyên lưu thông tin về chính thành phần đấy .
– Thành phần liên kết : Chuyên lưu địa chỉ thành phần đứng sau nó ở trong danh sách, nếu thành phần đó là thành phần ở đầu cuối thì thành phần này bằng NULL .

các thao tác trên danh sách liên kết đơn c++

Đặ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 tài liệu di động, được tạo nên nhờ vào việc cấp phát động cho nên vì thế sẽ có một số ít đặc thù sau :
– Sẽ được cấp phép bộ nhớ khi chạy .
– Có thể biến hóa được size trải qua việc thêm hoặc xóa thành phần .
– Bộ nhớ khả dụng của RAM sẽ có quyết định hành động tới kích cỡ tối đa .
– Các thành phần được ngẫu nhiên tàng trữ ( không liên tục ) ở trong RAM .
Và dựa vào tính liên kết của thành phần đầu và thành phần liền kề sau nó trong danh sách đơn mà có các đặc thù 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 thành phần 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ỉ hoàn toàn có thể tìm tuyến tính một thành phần mà thôi .

các thao tác trên danh sách liên kết đơn c++

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 thi một số ít thao tác để quản trị 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, thành phần 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ỏ tiếp nối vào phần đầu của danh sách .
– Bước 2 : Cần gán con trỏ đầu = p .
– void ThemDau ( LIST và 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 triển khai 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 và 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.

Để hoàn toàn 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à sống sót trong danh sách và bạn thực thi trỏ p -> next = q -> next, sau đó q -> next = p .
Tiếp đó bạn thực thi 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 và 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 ) ; }

các thao tác trên danh sách liên kết đơn c++

Xóa phần tử ở đầu của danh sách liên kết.

Nếu muốn xóa thành phần ở đầ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ề hiệu quả là 0. Còn nếu danh sách không rỗng, người dùng hãy thực thi 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ề tác dụng 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 sống sót 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 .

các thao tác trên danh sách liên kết đơn c++

Kết luận

Như 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.

admin