Trang 1
goupee.vn goupee.com Lập trình Chương3: Cấu trúc dữ liệu cuu duong than cong . com fb.com/goupee.vn 2/10/2017 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Nội dung tài liệu
Trang 2
goupee.vnNộidungbài giảng goupee.com 3.1 Giới thiệu chung 3.2 Mảng và quản lý bộ nhớ động 3.4 Nội dung và mục đích của cấu trúc dữ liệu 3.4 Cài đặt một số cấu trúc với C++ cuu duong than cong . com fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 3
goupee.vn3.1Giới thiệu chung goupee.com Phần lớn các bài toán trong thực tế liên quan tới các dữ liệu phức hợp, những kiểu dữ liệu cơ bản trong ngôn ngữ lập trình không đủ biểu diễn Ví dụ: – Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV,... – Mô hình hàm truyền: Đa thức tử số, đa thức mẫu số – Mô hình trạng thái: Các ma trận A, B, C, D – Đối tượng đồ họa: Kích thước, màu sắc, đường nét, phông chữ, ... Phương pháp biểu diễn dữ liệu: định nghĩa kiểu dữcuu duong than cong . com liệu mới sử dụng cấu trúc (struct, class, union, ...) fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 4
goupee.vnVấn đề:Biểu diễn tập hợp dữ liệu goupee.com Đa số những dữ liệu thuộc một ứng dụng có liên quan với nhau => cần biểu diễn trong một tập hợp có cấu trúc, ví dụ: – Danh sách sinh viên: Các dữ liệu sinh viên được sắp xếp theo thứ tự Alphabet – Đối tượng đồ họa: Một cửa sổ bao gồm nhiều đối tượng đồ họa, một bản vẽ cũng bao gồm nhiều đối tượng đồ họa Thông thường, các dữ liệu trong một tập hợp có cùng kiểu, hoặc ít ra là tương thích kiểu với nhau Kiểu mảng không phải bao giờ cũng phù hợp! cuu duong than cong . com fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 5
goupee.vnVấn đề:Quản lý dữ liệu goupee.com Sử dụng kết hợp một cách khéo léo kiểu cấu trúc và kiểu mảng đủ để biểu diễn các tập hợp dữ liệu bất kỳ Các giải thuật (hàm) thao tác với dữ liệu, nhằm quản lý dữ liệu một cách hiệu quả: – Bổ sung một mục dữ liệu mới vào một danh sách, một bảng, một tập hợp, ... – Xóa một mục dữ liệu trong một danh sách, bảng, tập hợp,.. – Tìm một mục dữ liệu trong một danh sách, bảng tập hợp,... theo một tiêu chuẩn cụ thể – Sắp xếp một danh sách theo một tiêu chuẩn nào đó – .... cuu duong than cong . com fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 6
goupee.vnQuản lý DLthế nào là hiệu quả? goupee.com Tiết kiệm bộ nhớ Truy nhập nhanh, thuận tiện: Thời gian cần cho bổ sung, tìm kiếm và xóa bỏ các mục dữ liệu phải ngắn Linh hoạt: Số lượng các mục dữ liệu không (hoặc ít) bị hạn chế cố định, không cần biết trước khi tạo cấu trúc, phù hợp với cả bài toán nhỏ và lớn Hiệu quả quản lý dữ liệu phụ thuộc vào – Cấu trúc dữ liệu được sử dụng – Giải thuật được áp dụng cho bổ sung, tìm kiếm, sắp xếp, xóa bỏ cuu duong than cong . com fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 7
goupee.vnCác cấu trúc dữ liệu thông dụng goupee.com Mảng (nghĩa rộng): Tập hợp các dữ liệu có thể truy nhập tùy ý theo chỉ số Danh sách (list): Tập hợp các dữ liệu được móc nối đôi một với nhau và có thể truy nhập tuần tự Cây (tree): Tập hợp các dữ liệu được móc nối với nhau theo cấu trúc cây, có thể truy nhập tuần tự từ gốc Hàng đợi (queue): Tập hợp các dữ liệu có sắp xếp tuần tự, chỉ bổ sung vào từ một đầu và lấy ra từ đầu còn lại Ngăn xếp (stack): Tập hợp các dữ liệu được sắp xếp tuần tự, chỉ truy nhập được từ một đầu Bộ nhớ vòng (ring buffer): Tương tự như hàng đợi,cuu duong than cong . com nhưng dung lượng có hạn, nếu hết chỗ sẽ được ghi quay vòng fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 8
goupee.vn3.2Mảng và quản lýbộ nhớ độnggoupee.com Mảng cho phép biểu diễn và quản lý dữ liệu một cách khá hiệu quả: – Đọc và ghi dữ liệu rất nhanh qua chỉ số hoặc qua địa chỉ – Tiết kiệm bộ nhớ Các vấn đề của mảng tĩnh: VD: Student student_list[100]; – Số phần tử phải là hằng số (biết trước khi biên dịch, người sử dụng không thể nhập số phần tử, không thể cho số phần từ là một biến) => kém linh hoạt – Chiếm chỗ cứng trong ngăn xếp (đối với biến cục bộ) hoặccuu duong than cong . com trong bộ nhớ dữ liệu chương trình (đối với biến toàn cục) => sử dụng bộ nhớ kém hiệu quả, kém linh hoạt fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 9
goupee.vnMảng động goupee.com Mảng động là một mảng được cấp phát bộ nhớ theo yêu cầu, trong khi chương trình chạy #include <stdlib.h> /* C */ int n = 50; ... float* p1= (float*) malloc(n*sizeof(float)); /* C */ double* p2= new double[n]; // C++ Sử dụng con trỏ để quản lý mảng động: Cách sử dụng không khác so với mảng tĩnh p1[0] = 1.0; p2[0] = 2.0; Sau khi sử dụng xong => giải phóng bộ nhớ:cuu duong than cong . com free(p1); /* C */ delete [] p2; // C++ fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 10
goupee.vnCấp phát và giải phóng bộ nhớ động goupee.com C: – Hàm malloc() yêu cầu tham số là số byte, trả về con trỏ không kiểu (void*) mang địa chỉ vùng nhớ mới được cấp phát (nằm trong heap), trả về 0 nếu không thành công. – Hàm free() yêu cầu tham số là con trỏ không kiểu (void*), giải phóng vùng nhớ có địa chỉ đưa vào C++: – Toán tử new chấp nhận kiểu dữ liệu phần tử kèm theo số lượng phần tử của mảng cần cấp phát bộ nhớ (trong vùng heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công. – Toán tử delete[]cuu duong than cong . comyêu cầu tham số là con trỏ có kiểu. – Toán tử new và delete còn có thể áp dụng cho cấp phát và giải phóng bộ nhớ cho một biến đơn, một đối tượng chứ không nhất thiết phải một mảng. fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 11
goupee.vnMột số điều cần lưu ý goupee.com Con trỏ có vai trò quản lý mảng (động), chứ con trỏ không phải là mảng (động) Cấp phát bộ nhớ và giải phóng bộ nhớ chứ không phải cấp phát con trỏ và giải phóng con trỏ Chỉ giải phóng bộ nhớ một lần Ví dụ: int* p; p[0] = 1; // ?? new(p); // ?? p = new int[100]; // OK p[0] = 1; // OK int* p2=p; // OK delete[] p2;cuu duong than cong . com// OK p[0] = 1; //?? delete[] p; //?? p = new int[50]; // OK, new array ... fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 12
goupee.vnCấp phát bộ nhớ động cho biến đơn goupee.com Ý nghĩa: Các đối tượng có thể được tạo ra động, trong khi chương trình chạy (bổ sung sinh viên vào danh sách, vẽ thêm một hình trong bản vẽ, bổ sung một khâu trong hệ thống,...) Cú pháp int* p = new int; *p = 1; p[0]= 2; // giong nhu tren p[1]= 1; // ?? int* p2 = new int(1); // có khởi tạo delete p; delete p2; Student* ps = new Student; ps->code = cuu duong than cong . com1000; ... delete ps; fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 13
goupee.vnÝ nghĩa của sử dụng bộ nhớ động goupee.com Hiệu suất: – Bộ nhớ được cấp phát đủ dung lượng theo yêu cầu và khi được yêu cầu trong khi chương trình đã chạy – Bộ nhớ được cấp phát nằm trong vùng nhớ tự do còn lại của máy tính (heap), chỉ phụ thuộc vào dung lượng bộ nhớ của máy tính – Bộ nhớ có thể được giải phóng khi không sử dụng tiếp. Linh hoạt: – Thời gian "sống" của bộ nhớ được cấp phát động có thể kéo dài hơn thời gian "sống" của thực thể cấp phát nó. – Có thể một hàm gọi lệnh cấp phát bộ nhớ, nhưng một hàm khác giải phóng bộ nhớ.cuu duong than cong . com – Sự linh hoạt cũng dễ dẫn đến những lỗi "rò rỉ bộ nhớ". fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 14
goupee.vnVí dụ sử dụng bộ nhớ động trong hàm goupee.com Date* createDateList(int n) { Date* p = new Date[n]; return p; } void main() { int n; cout << "Enter the number of your national holidays:"; cin >> n; Date* date_list = createDateList(n); for (int i=0; i < n; ++i) { ... } for (....)cuu duong than cong . com{ cout << ....} delete [] date_list; } fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 15
goupee.vnCácthuậttoán trênmảng goupee.com Các thuật toán sắp xếp Thuật toán tìm kiếm chia đôi (tìm kiếm nhị phân) cuu duong than cong . com fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 16
goupee.vnCácthuậttoánsắ pxếp trênmảng goupee.com Các giải thuật sắp xếp cơ bản – Sắp xếp chọn (selection-sort) – Sắp xếp nổi bọt (bubble, exchange-sort) – Sắp xếp chèn (insertion-sort) Các giải thuật sắp xếp nâng cao-Sắp xếp nhanh – Sắp xếp nhanh (quick-sort) – Sắp xếp vun đống (heap-sort) – Sắp xếp hòa trộn (merge-sort) Quy ước: – Giả sử các phần tử khóa cần sắp xếp là các số – Sắp xếp thực hiện theo thứ tự từ nhỏ đến lớncuu duong than cong . com fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 17
goupee.vnSắ pxếpchọ n ( selection-sort ) goupee.com Nguyên tắc – Lượt 1: tìm khóa nhỏ nhất trong n khóa đưa lên vị trí thứ nhất (đổi chỗ với khóa đầu tiên) – Lượt 2: tìm khóa nhỏ nhất trong n-1 khoá còn lại đưa lên vị trí thứ 2 (đổi chỗ với khóa thứ 2) – ... – Lượt i: tìm khóa nhỏ nhất trong (n-i+1) khoá còn lại đưa lên vị trí thứ i (đổi chỗ với khóa thứ i) Ví dụ: – Sắp xếp: 25, 36, 31, 49, 16, 70, 88, 60 16, 36, 31, 49, 25, 70, 88, 60 16, 25cuu duong than cong . com, 31, 49, 36, 70, 88, 60 16, 25, 31, 49, 36, 70, 88, 60 ... fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 18
goupee.vnSắ pxếpchè n ( Insertion-sort ) goupee.com Nguyên tắc – Giả sử đoạn đầu đã được sắp xếp, thêm một khóa mới => tìm vị trí thích hợp cho khóa mới. Cứ làm như vậy từ 2 đến n khóa. – So sánh và sắp xếp dần từ đằng sau danh sách khóa. Phân biệt hai trường hợp – Trường hợp cần đưa lần lượt các khóa vào: nhập các khóa lần lượt vào các ô nhớ. Dãy khóa: 25, 36, 31, 49, 16, 70, 88, 60 1: 25 4: 25, 31, 36, 49 2: 25, 36 5: 16, 25, 31, 36, 49 3: 25, 31, 36 6: ... – Trường hợp các khóa đã có và cần sắp xếp lại: dùng ô nhớ phụ (biến) X để lưu tạm các giá trị cần dịch chuyển. Hướng dịch chuyển: dần về đầu. – 1: 25, 36, 31, 49, 16, 70, 88, 60cuu duong than cong . com4: 25, 31, 36, 49, 16, 70, 88, 60 – 2: 25, 36, 31, 49, 16, 70, 88, 60 5: 16, 25, 31, 36, 49, 70, 88, 60 – 3: 25, 31, 36, 49, 16, 70, 88, 60 6: ... fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 19
goupee.vnSắ pxếpnổ ibọ t (Bubble-sort) goupee.com Nguyên tắc – Duyệt bảng khoá (danh sách khoá) từ đáy lên đỉnh – Dọc đường nếu thứ tự 2 khoá liền kế không đúng => đổi chỗ Ví dụ: – 1: 25, 36, 31, 60, 16, 88, 49, 70 – 2: 16, 25, 36, 31, 60, 49, 88, 70 – 3: 16, 25, 31, 36, 49, 60, 70, 88 Nhận xét – Khoá nhỏ sẽ nổi dần lên sau mỗi lần duyệt => “nổi bọt” – Sau một vài lần (không cần chạy n bước), danh sách khoá đãcuu duong than cong . com có thể được sắp xếp => Có thể cải tiến thuật toán, dùng 1 biến lưu trạng thái, nếu không còn gì thay đổi (không cần đổi chỗ) => ngừng fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trang 20
goupee.vnSắp xếp nhanh (quick -sort) hay Sắp xếp phân đoạn goupee.com Nguyên tắc – Chiến lược chia để trị – Chọn mốc (bất kỳ) để phân thành từng đoạn (partition) (2 đoạn) – Khoá của mốc sẽ đứng giữa: Left Keys <= key(mốc) <= Right Keys Thuật toán – 1: Quy ước: luôn chọn phần tử đầu tiên làm mốc. – 2: Tìm vị trí thực của khóa mốc để phân thành 2 đoạn: 1: Dùng 2 chỉ số: i, j chạy từ hai đầu DS. Chạy i từ đầu DS trong khi khóa còn nhỏ hơn khóa mốc 2: Nếu khóa >= khóa mốc: chạy j. Lưu phần tử hiện tại = X 3: Chạy j trong khi khóa lớn hơn khóa mốc 4: Nếu khóa <= khóa mốc: dừng và đổi chỗ phần tử hiện tại cho Xcuu duong than cong . com 5: Tiếp tục thực hiện như vậy cho đến khi i>=j thì đổi chỗ Kj cho khóa mốc. Lúc đó khóa mốc sẽ nằm đúng vị trí. – 3: Làm giống như vậy cho các đoạn tiếp theo fb.com/goupee.vn Chương 3: Cấu trúc dữ liệu 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!