Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3.1 - Trần Minh Thái
Số trang: 66
Loại file: pptx
Dung lượng: 251.99 KB
Lượt xem: 8
Lượt tải: 0
Xem trước 7 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Chương 3.1 trang bị cho người học những kiên thức về danh sách liên kết đơn trong cấu trúc dữ liệu và giải thuật. thông qua chương học này, các bạn có thể nắm vững khái niệm về kiểu dữ liệu tĩnh và động, nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn, cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/C++.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3.1 - Trần Minh Thái Chương 3.1. Danh sách liên kết đơnTrầnMinhTháiEmail:minhthai@itc.edu.vnWebsite:www.minhthai.edu.vn Cập nhật: ngày 20 tháng 10 năm 2012Mục tiêu• Nắm vững khái niệm về kiểu dữ liệu tĩnh và động• Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn• Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ 2Vấn đề kiểu dữ liệu tĩnh 6 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8? Làm sao để chèn thêm số 6 vào vị trí 5 củamảng 3Vấn đề kiểu dữ liệu tĩnh 6 ? Giả sử cần thêm tiếp 1 phần tử 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 9 Bổ sung 4 thêmBài tậpHãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử cógiá trị x vào vị trí vt trong mảng số nguyên a, kích thước n, theomẫu hàm như sau: void ChenX(int a[], int &n, int x, int vt); 5Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 ? Làm sao để xóa phần tử 9 6Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 7Bài tập• Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau: void XoaX (int a[], int &n, int x); 8Vấn đề kiểu dữ liệu tĩnh i Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n) 9 Vấn đề kiểu dữ liệu tĩnh• Giải quyết vấn đề phức tạp khi chèn/ xóa?• Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa?• Giải quyết vấn đề vùng nhớ không liên tục?• Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến? DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG 10Biến tĩnh và biến động trong C++• Biến tĩnh tên biến;• Vd: int a; float y; char s[20]; ü Tồn tại trong phạm vi khai báo ü Được cấp phát vùng nhớ trong vùng dữ liệu ü Kích thước cố định 11Biến tĩnh và biến động trong C++• Biến động *tên biến;• Vd: int *a; float *y; ü Chứa địa chỉ của một đối tượng dữ liệu ü Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào người lập trình ü Kích thước có thể thay đổi 12 Biến tĩnh và biến động trong C++• Biến động ü Cấp phát bộ nhớ: new int [kích thước] ü Giải phóng bộ nhớ: delete vùng nhớ• Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng 13Danh sách liên kết (DSLK) Các phần tử kết 1 dính với nhau bằng “sợi dây 7 liên kết” 2 6 3 10 8 5 9 14 41726310 8 Để đơn giản5 hơn trong9 việc minh họa4 15Đặc điểm DSLK• Một dãy tuần tự các nút (Node)• Giữa hai nút có con trỏ liên kết• Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ• Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) 16Đặc điểm DSLK• Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết• Quản lý phần tử đầu tiên bằng con trỏ pHead• Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết 17 Cấu tạo của DSLK NodeList pHead pTail 18 Cấu tạo của DSLK• Quản lý toàn ...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3.1 - Trần Minh Thái Chương 3.1. Danh sách liên kết đơnTrầnMinhTháiEmail:minhthai@itc.edu.vnWebsite:www.minhthai.edu.vn Cập nhật: ngày 20 tháng 10 năm 2012Mục tiêu• Nắm vững khái niệm về kiểu dữ liệu tĩnh và động• Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn• Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ 2Vấn đề kiểu dữ liệu tĩnh 6 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8? Làm sao để chèn thêm số 6 vào vị trí 5 củamảng 3Vấn đề kiểu dữ liệu tĩnh 6 ? Giả sử cần thêm tiếp 1 phần tử 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 9 Bổ sung 4 thêmBài tậpHãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử cógiá trị x vào vị trí vt trong mảng số nguyên a, kích thước n, theomẫu hàm như sau: void ChenX(int a[], int &n, int x, int vt); 5Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 ? Làm sao để xóa phần tử 9 6Vấn đề kiểu dữ liệu tĩnh 15 10 9 5 7 3 2 1 1 2 3 4 5 6 7 8 7Bài tập• Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau: void XoaX (int a[], int &n, int x); 8Vấn đề kiểu dữ liệu tĩnh i Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n) 9 Vấn đề kiểu dữ liệu tĩnh• Giải quyết vấn đề phức tạp khi chèn/ xóa?• Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa?• Giải quyết vấn đề vùng nhớ không liên tục?• Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến? DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG 10Biến tĩnh và biến động trong C++• Biến tĩnh tên biến;• Vd: int a; float y; char s[20]; ü Tồn tại trong phạm vi khai báo ü Được cấp phát vùng nhớ trong vùng dữ liệu ü Kích thước cố định 11Biến tĩnh và biến động trong C++• Biến động *tên biến;• Vd: int *a; float *y; ü Chứa địa chỉ của một đối tượng dữ liệu ü Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào người lập trình ü Kích thước có thể thay đổi 12 Biến tĩnh và biến động trong C++• Biến động ü Cấp phát bộ nhớ: new int [kích thước] ü Giải phóng bộ nhớ: delete vùng nhớ• Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng 13Danh sách liên kết (DSLK) Các phần tử kết 1 dính với nhau bằng “sợi dây 7 liên kết” 2 6 3 10 8 5 9 14 41726310 8 Để đơn giản5 hơn trong9 việc minh họa4 15Đặc điểm DSLK• Một dãy tuần tự các nút (Node)• Giữa hai nút có con trỏ liên kết• Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ• Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) 16Đặc điểm DSLK• Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết• Quản lý phần tử đầu tiên bằng con trỏ pHead• Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết 17 Cấu tạo của DSLK NodeList pHead pTail 18 Cấu tạo của DSLK• Quản lý toàn ...
Tìm kiếm theo từ khóa liên quan:
Cấu trúc dữ liệu Bài giảng cấu trúc dữ liệu Danh sách liên kết đơn Kiểu dữ liệu tĩnh Biến động trong C++ Cấu tạo của danh sách liên kếtGợi ý tài liệu liên quan:
-
Đề cương chi tiết học phần Cấu trúc dữ liệu và giải thuật (Data structures and algorithms)
10 trang 302 0 0 -
Bài giảng Phân tích thiết kế phần mềm: Chương 1 - Trường ĐH Ngoại ngữ - Tin học TP.HCM
64 trang 148 0 0 -
Giải thuật và cấu trúc dữ liệu
305 trang 139 0 0 -
Tập bài giảng Thực hành kỹ thuật lập trình
303 trang 137 0 0 -
Giáo trình Cấu trúc dữ liệu và thuật toán (Tái bản): Phần 1
152 trang 136 0 0 -
Tài liệu tham khảo: Cấu trúc dữ liệu và giải thuật
229 trang 101 0 0 -
Lập trình C - Cấu trúc dữ Liệu
307 trang 71 0 0 -
49 trang 67 0 0
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Ngô Công Thắng
8 trang 64 0 0 -
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3 - Một số mô hình thuật toán
42 trang 64 0 0