Trong bài này chúng ta sẽ tìm hiểu 2 phần chính:
+/ Danh sách liên kết đơn +/ Danh sách liên kết kép Trong mỗi phần chúng ta sẽ tìm hiểu các vấn đề cơ bản sau:
1/ Danh sách liên kết cài bằng mảng Loại danh sách này thường được gọi là danh sách kế tiếp. Bây giờ ta sẽ làm việc với các vấn đề:  1.1/ Cài đặt (khai báo) danh sách Để khai báo danh sách này ta cần có 1 mảng có số phần tử tối đa là N có kiểu dữ liệu là item (item này là kiểu dữ liệu tổng quan, khi làm nó sẽ là kiểu int, float hay kiểu cấu trúc sinh viên). Cần thêm 1 biến size thể hiện số phần tử hiện có của danh sách. Cụ thể như sau: 1.2/ Khởi tạo danh sách rỗng Danh sách của ta rỗng khi số phần tử trong danh sách bằng 0. Vì vậy chỉ cần khai báo trường size của ta bằng 0 là được. 1.3/ Kiểm tra danh sách rỗng, danh sách đầy Để kiểm tra danh sách rỗng hay đầy ta chỉ việc xem số phần tử của danh sách có bằng 0 hay không (rỗng) và có bằng N hay không (đầy). 1.4/ Chèn phần tử vào vị trí k trong danh sách Trước khi chèn phần tử vào trong danh sách chúng ta nên xây dựng 1 hàm trả về dữ liệu (nhập vào dữ liệu) của phần tử cần chèn đó. Sau đó tiến hành chèn: Trong quá trình chèn chúng ta cần kiểm tra xem danh sách đầy chưa, nhập vị trí k cần chèn và kiểm tra nó, nếu phù hợp (0<k<=N) thì sẽ tiến hành chèn. Để chèn được phần tử x vào vị trí k trong danh sách (trong mảng) ta cần dùng 1 vòng for để di chuyển các phần tử từ vị trí k về phía cuối mảng, sau đó chèn x vào vị trí k. Cuối cùng ta tăng size lên 1 đơn vị. 1.5/ Nhập danh sách Nhập như bình thường với mảng 1.6/ Tìm phần tử x trong danh sách Ta duyệt từ đầu đến cuối danh sách nếu có giá trị x thì đưa ra vị trí của nó. 1.7/ Xóa phần tử thứ k trong danh sách Trước khi xóa ta phải kiểm tra xem danh sách có rỗng không. Nếu không rỗng ta nhập vào vị trí cần xóa và kiểm tra (phù hợp nếu 0<k<=N). Ta dùng vòng for chạy đến vị trí thứ k, sau đó dồn các phần tử từ k+1 về trước 1 đơn vị. tuy nhiên ta cần lưu lại giá trị của phần tử xóa trước khi xóa để giữ lại thông tin nếu ta cần dùng đến nó. Cuối cùng là giảm size xuống 1 đơn vị. 1.8/ Xóa phần tử có nội dung x trong danh sách Để xóa phần tử có nội dung x trong danh sách ta tiến hành tìm phần tử x trước bằng hàm search sau đó giá trị trả về là vị trí của x, ta tiếp tục sử dụng hàm del_k để xóa phần tử ở vị trí mà ta tìm được. Vậy là chúng ta đã xây dựng xong các thao tác cơ bản trên danh sách cài đặt bằng mảng. Các bạn ghép các hàm vào cùng với hàm main() gọi các hàm trên là ok. Các bạn có thể tham khảo tại đây: http://ideone.com/VyjxYo 2. Danh sách liên kết đơn (gọi nhanh là danh sách liên kết - DSLK) Trong các bài trước mình viết code tất cả đều là chuẩn C, nhưng từ bây giờ mình sẽ xen lẫn chút cấu trúc của C++ trong đó. Một số vấn đề ta cần làm trong DSLK: 2.1 Giống như trong phần danh sách liên kết xây dựng bởi mảng, bây giờ ta sẽ cài đặt danh sách: Danh sách liên kết có thể được mô tả như sau: 2.2 Khởi tạo danh sách rỗng Trong các bài trước để có thể thay đổi được giá trị của đối mà ta truyền vào hàm ta thưòng dùng biến con trỏ (Đây là một cách truyền địa chỉ cho biến trong hàm ở C++.) 2.3 Kiểm tra danh sách rỗng hay không Cái này khỏi giải thích nhiều: 2.4 Tính độ dài danh sách Ta dùng 1 Node để duyệt từ đầu đến cuối, vừa duyệt vừa đếm 2.5 Tạo 1 Node trong danh sách Việc tạo 1 Node chứa thông tin trong danh sách sẽ giúp ta dễ dàng chèn, xóa và quản lý danh sách hơn. Trước tiên ta sẽ phải cấp phát vùng nhớ cho Node và sau đó gán Data vào là ok 2.6 Chèn Node P vào vị trí đầu tiên Để chèn P vào đầu danh sách trước tiên ta cho P trỏ đến L, sau đó chỉ việc cho L trỏ lại về P là ok 2.7 Chèn Node P vào vị trí k trong danh sách: Trước tiên ta kiểm tra vị trí chèn có hợp lệ không, nếu hợp lệ kiểm tra tiếp chèn vào vị trí 1 hay k >1 . Với k >1 ta thực hiện duyệt bằng Node Q đến vị trí k-1 sau đó cho P->Next trỏ đến Node Q->Next, tiếp đến cho Q->Next trỏ đến P 2.8 Tìm phần tử co giá trị x trong danh sách: Ta duyệt danh sách cho đến khi tìm thấy hoặc kết thúc và trả về vị trí nếu tìm thấy, ngược lại trả về 0 2.9 Xóa phần tử ở vị trí đầu tiên Trước tiên ta lưu giá trị của phần tử đầu tiên vào biến x, sau đó tiền hành cho L trỏ đến L->Next 2.10 Xóa phần tư ở vị trí k Dùng P duyệt đến vị trí k-1 và tiến hành cho P->Next trỏ đến phần tư kế tiếp k mà bỏ qua k. Lưu ý trong hình mình quên không lưu lại giá trị cần xóa tuy nhiên các bạn cần lưu lại như khi xóa ở vị trí đầu tiên. 2.11 Xóa phần tử có giá trị x Đon giản là ta tìm x trong danh sách bằng hàm Search và xóa tại vị trí tìm thấy mà ta nhận được Đến đây coi như đã hoàn thiện phần danh sách liên kết đơn. Các bạn có thể tham khảo code hoàn chỉnh tại đây: http://ideone.com/BMPAja 3. Danh sách liên kết kép Danh sách liên kết kép cũng là một dạng danh sách liên kết nhưng mỗi phần tử liên kết với phần tử đứng trước và sau nó trong danh sách 3.1 Cài đặt danh sách: Cấu trúc của 1 Node trong danh sách liên kết kép tương đối giống với DSLKD nhưng có thêm một con trỏ trỏ về Node trước nó Cấu trúc của DSLKK không như DSLKD có 1 Con trỏ trỏ đến đầu DS, nhưng DSLKK ngoài con trỏ trỏ đến đầu danh sách còn có thêm 1 con trỏ trỏ đến Node cuối của danh sách 3.2 Một số thao tác chính 3.3 Khởi tạo và kiểm tra rỗng Khởi tạo ta cho 2 con trỏ đầu và cuối trỏ vê NULL, Khi kiểm tra rỗng thi chỉ cần xem con trỏ đầu có trỏ về NULL không là đủ 3.4 Độ dài danh sách: Để tìm độ dài của DSLKK ta hoàn toàn có thể làm giống như DSLKD, tức dùng con trỏ duyệt từ đầu đến cuối, nhưng trong DSLKK ta có thể dùng 2 con trỏ ở đầu và cuối để đếm 3.5 Tạo 1 Node P chứa thông tin 3.6 Chèn phần tử vào vị trí đầu tiên: Trước khi chèn vào đầu danh sách cần kiểm tra xem danh sách rỗng hay không. Nếu danh sách rỗng ta cho Head và Tail đều trỏ đến P. Nếu không rỗng thực hiện chèn. 3.7 Chèn phần tử vào cuối danh sách tương tự như đầu danh sách 3.8 Chèn phần tử vào vị trí k Trước khi chèn vào vị trí k cần kiểm tra vị trí k có phù hợp, có phải đầu danh sách hay cuối danh sách. Nếu chèn vào giữa danh sách ta thực hiện theo 4 bước 3.9 Xóa phần tử đầu, cuối danh sách 3.10 Xóa phần tử ở vị trí k Trước khi xóa ở vị trí k cần kiểm tra vị trí k có phù hợp, có phải đầu danh sách hay cuối danh sách hay ở giữa 3.11 Tìm phần tử x trong DS 3.12 Xóa phần tử x trong DS Vậy là phần này coi như chúng ta đa tìm hiểu xong danh sách liên kết: (DSLK mảng, DSLK đơn, DSLK kép). |
