tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách - Nguyễn Đức Cương

Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách do Nguyễn Đức Cương biên soạn bao gồm những nội dung về khái niệm, khởi tạo danh sách, các thao tác trên danh sách (thêm, loại bỏ, sửa, tìm kiếm); duyệt danh sách; sắp thứ tự; tách, ghép danh sách; sao chép danh sách; hủy danh sách. | Mục tiêu CHƯƠNG - DANH SÁCH p Sau khi kết thúc chương sinh viên được Hiểu rõ hơn về CTDL danh sách. Cung cấp các kiến thức về các thao tác trên DS Cung cấp các kiến thức về DS tĩnh động . Lecturer Nguyễn Đức cương - FIT Email cuongnguyenduc@ Website http Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 2 Nội dung chính p Khái niệm Khởi tạo danh sách Các thao tác trên DS thêm loại bỏ sửa tìm kiếm Duyệt danh sách J- Sắp thứ tự Tách ghép danh sách p Sao chép danh sách Hủy danh sách. Ví dụ p Vídụ Hồ sơ các học sinh của một trường được tổ chức thành danh sách gồm nhiều hồ sơ của từng học sinh số lượng học sinh trong trường có thể thay đổi do vậy cần có các thao tác thêm hủy một hồ sơ để phục vụ công tác giáo vụ cần thực hiện các thao tác tìm hồ sơ của một học sinh in danh sách hồ sơ . Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 3 Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 4 Danh sách tĩnh - đặc Biểu diễn p Mảng 1 chiều Kích thước cố định fixed size Chèn 1 phần tử vào mảng rất khó Các phần tử tuần tự theo chỉ số 0 - n-1 Truy cập ngẫu nhiên random access chèn 0 12 3 4 n-2 n-1 p Khai báo const int Len 100 T DS Len Khởi tạo danh sách void init int elength p length 0 return p g 0 12 3 4 Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 5 Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 6 1 Các thao tác trên danh sách tĩnh p Nhập danh sách void CD_CreateList T M int Jen for int i 0 i len i cin M i g Các thao tác trên danh sách p Thêm 1 phần tử vào danh sách Khi thêm 1 phần tử chiều dài danh sách tăng lên. Có thao tác thêm vào đầu cuối hay tại 1 vị trí xác định của danh sách. Tìm kiếm 1 phần tử trong danh sách Thỏa mãn điều kiện nào đó Dùng các thuật toán tìm kiếm Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 7 Nguyễn Đức Cương - Khoa CNTT - cuongnguyenduc@ Slide 8 Các thao tác trên danh sách Loại bớt 1 phần tử trong danh sách Chiều dài danh sách