TAILIEUCHUNG - Kỹ thuật lập trình - Chương 5

Tài liệu tham khảo giáo trình kỹ thuật lập trình gồm 6 chương - Chương 5 Các thuật toán trên cấu trúc danh sách liên kết (LINKED LIST) | Kỳ thuật lập trì nh 97 CHƯƠNG 5 CÁC THUẬT TOÁN TRÊN CAU TRÚC DANH SÁcH liên kết LINKED LIST I. KHÁI NIỂM Cấu trúc danh sách liên kết là cấu trúc động việc cấp phát nút và giải phó ng nú t trê n danh sá ch xả y ra khi ch- ơng trì nh đ ang chạ y. Ta thu ờng cấp phá t nút cho danh sách liên kết bằng biến động. Các phần tử sẽ đuợc cấp phát vùng nhớ trong quá trì nh thực thi chuơng trì nh do đó chúng có thể nằm rải rác ở nhiều nơi khác nhau trong bộ nhớ không liên tục . 3 1 First Na First - 2 4 Cá c phầ n tử trong danh sá ch đuợc kết nối với nhau theo chùm liê n kết nhu hì nh trê n - First là con trỏ chỉ đến phần tử đầu của danh sách liên kết - Phần tử cuối của danh sách liên kết với vùng liên kết có giá trị NULL -Mỗi nút của danh sách có tru ờng info chứa nội dung của nút và tru ờng next là con trỏ chỉ đến nút kế tiếp trong danh sách. Lưu ý - Cấu trúc danh sách liên kết là cấu trúc động các nút đ u ợc cấp phát hoặc bị giải phóng khi chuơng trì nh đang chạy. - Danh sá ch liê n kết rất thí ch hợp khi thực hiệ n cá c phép toá n trê n danh sá ch thuờng bị biến động. Trong truờng hợp xóa hay thê m phần tử trong danh sá ch liê n kết thì ta không dời cá c phần tử đi nhu trong mảng mà chỉ việ c hiệ u chỉ nh lại truờng next tại các nút đang thao tác. Thời gian thực hiện các phép toán thêm vào và loại bỏ không phụ thuộc vào số phần tử của danh sách liên kết. Kỳ thuật lập trì nh 98 - Tuy nhiên danh sách liên kết cũng có các điểm hạn chế sau Vì mỗi nút của danh sá ch liê n kết phải chứa thê m truờng next nê n danh sá ch liê n kế t phả i tốn thê m bộ nhớ. Tì m kiếm trê n danh sá ch liê n kết không nhanh vì ta chỉ đuợc truy xuất tuần tự từ đầu danh sách. Khai bá o Mộ t phầ n tử của danh sá ch liê n kết ít nhấ t phả i có hai thà nh phầ n nội dung củ a phầ n tử info và thà nh phầ n next liê n kế t phầ n tử này với phầ n tử khá c. Giả sử ta khai bá o kiể u NODEPTR là kiể u con trỏ chỉ đến nút trong 1 danh sách liên kết mỗi phần tử có 2 thành phần info int và next . struct node int info

• Kỹ thuật lập trình
• lập trình java
• lập trình hướng đối tượng
• ngôn ngữ lập trình
• java căn bản
• giáo trình java
• kinh nghiệm lập trình java
• kỹ thuật lập trình java
• hướng dẫn lập trình java
• tài liệu lập trình java
• lý thuyết lập trình java