1. Trang Chủ
  2. Kỹ thuật lập trình
  3. Bài giảng Lập trình: Chương 3 - Vũ Song Tùng

Bài giảng Lập trình: Chương 3 - Vũ Song Tùng

Bài giảng Lập trình chương 3 trang bị cho người học những kiến thức cơ bản về cấu trúc dữ liệu như: Giới thiệu chung, mảng và quản lý bộ nhớ động, nội dung và mục đích của cấu trúc dữ liệu, cài đặt một số cấu trúc với C++. Mời các bạn cùng tham khảo. om .c Lập trình ng co an Chương 3: Cấu trúc dữ liệu th o ng du u cu 2/10/2017 CuuDuongThanCong.com https://fb.com/tailieudientucntt Nội dung bài giảng 3.1 Giới thiệu chung om 3.2 Mảng và quản lý bộ nhớ động .c 3.4 Nội dung và mục đích của cấu trúc d

Thể loại Tài liệu miễn phí Kỹ thuật lập trình

Số trang 98

Ngày tạo 10/4/2021 1:57:05 PM +00:00

Loại tệp PDF

Kích thước 1.06 M

Tên tệp

Tải Bài giảng Lập trình: Chương 3 - Vũ Song Tùng (.pdf)

Xem mẫu

  1. om .c Lập trình ng co an Chương 3: Cấu trúc dữ liệu th o ng du u cu 2/10/2017 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Nội dung bài giảng 3.1 Giới thiệu chung om 3.2 Mảng và quản lý bộ nhớ động .c 3.4 Nội dung và mục đích của cấu trúc dữ liệu ng co 3.4 Cài đặt một số cấu trúc với C++ an th o ng du u cu Chương 3: Cấu trúc dữ liệu 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. 3.1 Giới thiệu chung  Phần lớn các bài toán trong thực tế liên quan tới các om dữ liệu phức hợp, những kiểu dữ liệu cơ bản trong .c ngôn ngữ lập trình không đủ biểu diễn ng  Ví dụ: co – Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV,... an – Mô hình hàm truyền: Đa thức tử số, đa thức mẫu số th – Mô hình trạng thái: Các ma trận A, B, C, D ng – Đối tượng đồ họa: Kích thước, màu sắc, đường nét, phông o du chữ, ...  Phương pháp biểu diễn dữ liệu: định nghĩa kiểu dữ u cu liệu mới sử dụng cấu trúc (struct, class, union, ...) Chương 3: Cấu trúc dữ liệu 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Vấn đề: Biểu diễn tập hợp dữ liệu  Đ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 om trúc, ví dụ: .c – Danh sách sinh viên: Các dữ liệu sinh viên được sắp xếp theo ng thứ tự Alphabet co – Đố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 an th  Thông thường, các dữ liệu trong một tập hợp có cùng ng kiểu, hoặc ít ra là tương thích kiểu với nhau o  Kiểu mảng không phải bao giờ cũng phù hợp! du u cu Chương 3: Cấu trúc dữ liệu 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. Vấn đề: Quản lý dữ liệu  Sử dụng kết hợp một cách khéo léo kiểu cấu trúc và om kiểu mảng đủ để biểu diễn các tập hợp dữ liệu bất kỳ .c  Các giải thuật (hàm) thao tác với dữ liệu, nhằm quản ng lý dữ liệu một cách hiệu quả: co – Bổ sung một mục dữ liệu mới vào một danh sách, một bảng, an một tập hợp, ... th – Xóa một mục dữ liệu trong một danh sách, bảng, tập hợp,.. ng – Tìm một mục dữ liệu trong một danh sách, bảng tập hợp,... o theo một tiêu chuẩn cụ thể du – Sắp xếp một danh sách theo một tiêu chuẩn nào đó u – .... cu Chương 3: Cấu trúc dữ liệu 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. Quản lý DL thế nào là hiệu quả?  Tiết kiệm bộ nhớ om  Truy nhập nhanh, thuận tiện: Thời gian cần cho bổ .c 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) ng co 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 an th  Hiệu quả quản lý dữ liệu phụ thuộc vàong – Cấu trúc dữ liệu được sử dụng o – Giải thuật được áp dụng cho bổ sung, tìm kiếm, sắp xếp, xóa du bỏ u cu Chương 3: Cấu trúc dữ liệu 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. Các cấu trúc dữ liệu thông dụng  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ố om  Danh sách (list): Tập hợp các dữ liệu được móc nối đôi .c một với nhau và có thể truy nhập tuần tự ng  Cây (tree): Tập hợp các dữ liệu được móc nối với nhau co theo cấu trúc cây, có thể truy nhập tuần tự từ gốc an  Hàng đợi (queue): Tập hợp các dữ liệu có sắp xếp tuần th tự, chỉ bổ sung vào từ một đầu và lấy ra từ đầu còn lại o ng  Ngăn xếp (stack): Tập hợp các dữ liệu được sắp xếp du tuần tự, chỉ truy nhập được từ một đầu u cu  Bộ nhớ vòng (ring buffer): Tương tự như hàng đợi, nhưng dung lượng có hạn, nếu hết chỗ sẽ được ghi quay vòng Chương 3: Cấu trúc dữ liệu 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. 3.2 Mảng và quản lý bộ nhớ động  Mảng cho phép biểu diễn và quản lý dữ liệu một cách om khá hiệu quả: .c – Đọc và ghi dữ liệu rất nhanh qua chỉ số hoặc qua địa chỉ ng – Tiết kiệm bộ nhớ co  Các vấn đề của mảng tĩnh: an VD: Student student_list[100]; th – Số phần tử phải là hằng số (biết trước khi biên dịch, người sử ng dụng không thể nhập số phần tử, không thể cho số phần từ o du 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ặc u cu 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 Chương 3: Cấu trúc dữ liệu 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Mảng động  Mảng động là một mảng được cấp phát bộ nhớ theo om yêu cầu, trong khi chương trình chạy #include /* C */ .c int n = 50; ng ... co float* p1= (float*) malloc(n*sizeof(float)); /* C */ an double* p2= new double[n]; // C++ th  Sử dụng con trỏ để quản lý mảng động: Cách sử dụng ng không khác so với mảng tĩnh o p1[0] = 1.0; du p2[0] = 2.0; u cu  Sau khi sử dụng xong => giải phóng bộ nhớ: free(p1); /* C */ delete [] p2; // C++ Chương 3: Cấu trúc dữ liệu 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Cấp phát và giải phóng bộ nhớ động  C: om – Hàm malloc() yêu cầu tham số là số byte, trả về con trỏ .c 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. ng – Hàm free() yêu cầu tham số là con trỏ không kiểu (void*), co giải phóng vùng nhớ có địa chỉ đưa vào an  C++: th – Toán tử new chấp nhận kiểu dữ liệu phần tử kèm theo số ng lượng phần tử của mảng cần cấp phát bộ nhớ (trong vùng o du heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công. – Toán tử delete[] yêu cầu tham số là con trỏ có kiểu. u cu – 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. Chương 3: Cấu trúc dữ liệu 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Một số điều cần lưu ý  Con trỏ có vai trò quản lý mảng (động), chứ con trỏ không phải om 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 .c con trỏ và giải phóng con trỏ ng  Chỉ giải phóng bộ nhớ một lần co  Ví dụ: int* p; an p[0] = 1; // ?? new(p); th // ?? ng p = new int[100]; // OK o p[0] = 1; // OK du int* p2=p; // OK u delete[] p2; // OK cu p[0] = 1; //?? delete[] p; //?? p = new int[50]; // OK, new array ... Chương 3: Cấu trúc dữ liệu 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Cấp phát bộ nhớ động cho biến đơn  Ý 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 om một hình trong bản vẽ, bổ sung một khâu trong hệ thống,...) .c  Cú pháp ng int* p = new int; co *p = 1; p[0]= 2; // giong nhu tren an p[1]= 1; // ?? th int* p2 = new int(1); // có khởi tạo ng delete p; o delete p2; du Student* ps = new Student; u cu ps->code = 1000; ... delete ps; Chương 3: Cấu trúc dữ liệu 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. Ý nghĩa của sử dụng bộ nhớ động  Hiệu suất: om – Bộ nhớ được cấp phát đủ dung lượng theo yêu cầu và khi .c đượ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 ng máy tính (heap), chỉ phụ thuộc vào dung lượng bộ nhớ của co máy tính an – Bộ nhớ có thể được giải phóng khi không sử dụng tiếp. th  Linh hoạt: ng – 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ó. o du – 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ớ. u cu – Sự linh hoạt cũng dễ dẫn đến những lỗi "rò rỉ bộ nhớ". Chương 3: Cấu trúc dữ liệu 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. Ví dụ sử dụng bộ nhớ động trong hàm om Date* createDateList(int n) { Date* p = new Date[n]; .c return p; } ng void main() { co int n; cout > n; Date* date_list = createDateList(n); ng for (int i=0; i < n; ++i) { o ... du } for (....) { cout
  15. Các thuật toán trên mảng  Các thuật toán sắp xếp om  Thuật toán tìm kiếm chia đôi (tìm kiếm nhị phân) .c ng co an th o ng du u cu Chương 3: Cấu trúc dữ liệu 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Các thuật toán sắp xếp trên mảng  Các giải thuật sắp xếp cơ bản om – Sắp xếp chọn (selection-sort) .c – Sắp xếp nổi bọt (bubble, exchange-sort) – Sắp xếp chèn (insertion-sort) ng  Các giải thuật sắp xếp nâng cao-Sắp xếp nhanh co – Sắp xếp nhanh (quick-sort) an th – Sắp xếp vun đống (heap-sort) ng – Sắp xếp hòa trộn (merge-sort) o  Quy ước: du – Giả sử các phần tử khóa cần sắp xếp là các số u cu – Sắp xếp thực hiện theo thứ tự từ nhỏ đến lớn Chương 3: Cấu trúc dữ liệu 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Sắp xếp chọn ( selection-sort )  Nguyên tắc – Lượt 1: tìm khóa nhỏ nhất trong n khóa đưa lên vị trí thứ om nhất (đổi chỗ với khóa đầu tiên) .c – 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) ng – ... co – Lượt i: tìm khóa nhỏ nhất trong (n-i+1) khoá còn lại đưa lên an vị trí thứ i (đổi chỗ với khóa thứ i)  Ví dụ: th ng – Sắp xếp: 25, 36, 31, 49, 16, 70, 88, 60 o du 16, 36, 31, 49, 25, 70, 88, 60 16, 25, 31, 49, 36, 70, 88, 60 u cu 16, 25, 31, 49, 36, 70, 88, 60 ... Chương 3: Cấu trúc dữ liệu 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. Sắp xếp chèn ( Insertion-sort )  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í om 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. .c  Phân biệt hai trường hợp ng – 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 co vào các ô nhớ. Dãy khóa: 25, 36, 31, 49, 16, 70, 88, 60 1: 25 4: 25, 31, 36, 49 an 2: 25, 36 5: 16, 25, 31, 36, 49 th 3: 25, 31, 36 6: ... ng – Trường hợp các khóa đã có và cần sắp xếp lại: dùng ô nhớ phụ o (biến) X để lưu tạm các giá trị cần dịch chuyển. Hướng dịch chuyển: du dần về đầu. u – 1: 25, 36, 31, 49, 16, 70, 88, 60 4: 25, 31, 36, 49, 16, 70, 88, 60 cu – 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: ... Chương 3: Cấu trúc dữ liệu 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. Sắp xếp nổi bọt (Bubble-sort)  Nguyên tắc om – Duyệt bảng khoá (danh sách khoá) từ đáy lên đỉnh .c – Dọc đường nếu thứ tự 2 khoá liền kế không đúng => đổi chỗ ng  Ví dụ: co – 1: 25, 36, 31, 60, 16, 88, 49, 70 an – 2: 16, 25, 36, 31, 60, 49, 88, 70 th – 3: 16, 25, 31, 36, 49, 60, 70, 88ng  Nhận xét o du – Khoá nhỏ sẽ nổi dần lên sau mỗi lần duyệt => “nổi bọt” u – Sau một vài lần (không cần chạy n bước), danh sách khoá đã cu 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 Chương 3: Cấu trúc dữ liệu 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. Sắp xếp nhanh (quick-sort) hay Sắp xếp phân đoạn  Nguyên tắc – Chiến lược chia để trị om – 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
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường