›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Trần Thị Kim Chi

ppt 106 trang hapham 2290
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Trần Thị Kim Chi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_cau_truc_du_lieu_va_giai_thuat_tran_thi_kim_chi.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Trần Thị Kim Chi

  1. TRƯỜNG ĐH CÔNG NGHIỆP TP. HCM TT CNTT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT DATA STRUCTURES & ALGORITHMS Giáo viên: Trần Thị Kim Chi
  2. Giới thiệu n Mục tiêu n Nắm vững khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng. n Nắm vững và cài đặt được các kiểu dữ liệu trừu tượng cơ bản như danh sách, ngăn xếp, hàng đợi, cây, tập hợp, bảng băm, đồ thị bằng một ngôn ngữ lập trình căn bản. n Vận dụng được các kiểu dữ liệu trừu tượng để giải quyết bài toán đơn giản trong thực tế. n Ngôn ngữ lập trình minh hoạ n Mã giả (pseudocode) n C++
  3. Nội dung chương trình Phân bổ thời gian Số Ghi TT Nội dung tiết Lý Thực Tự chú thuyết hành học 1 Tổng quan 3 3 0 6 2 Đệ quy 6 3 3 10 3 Tìm kiếm 10 6 4 12 4 Sắp xếp 5 3 3 10 5 Chồng (Stacks) 6 3 3 10 6 Hàng đợi (Queues) 6 3 3 12 7 Danh sách và chuỗi 10 6 4 15 8 Các bảng và phục hồi thông tin 10 6 4 10 9 Cây nhị phân 14 9 5 10 10 Cây nhiều nhánh 5 3 2 10 TỔNG 75 45 30 105
  4. Kiến thức tiên quyết n Đã học môn phương pháp lập trình. n Kiến thức về kỹ thuật lập trình. n Sử dụng thành thạo ngôn ngữ C++
  5. Tài liệu n Tài liệu học tập: [1] C & Data Structures, P. S. Deshpande, O. G. Kakde - CHARLES RIVER MEDIA, INC. Hingham, Massachusetts. [2] Robert L.Kruse, Alexander J.Ryba, Data Structures And Program Design In C++, Prentice-Hall International Inc., 1999. [3] Bài giảng & Bài thực hành CTDL - Trường ĐHCN. n Tài liệu tham khảo: [1] Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường DHKHTN – DHQG TP.HCM. [2] Cấu trúc dữ liệu, Nguyễn Trung Trực, Trường DHBK – DHQG TP.HCM [3] Nguyễn Ngô Bảo Trân, Giáo trình cấu trúc dữ liệu và giải thuật – Trường Đại học Bách Khoa TP.HCM, 2005.
  6. Tiêu chuẩn đánh giá Kiểm tra và Thi Điểm Tuần Kiểm tra thường xuyên 10% Bất kỳ Thi giữa kỳ 20% Tuần5 Thi cuối kỳ 50% Tuần 9 Báo cáo tiểu luận 20% Hàng tuần Yêu cầu đối với sinh viên: • Dự lớp: lý thuyết trên 80% , thực hành bắt buộc 100% • Bài tập: hoàn thành các bài tập trên lớp và ở nhà • Tham gia đầy đủ các buổi thảo luận của nhóm
  7. Trao đổi thông tin Địa chỉ mail: • Kimchi_12041972@yahoo.com Địa chỉ download tài liệu: •
  8. Chương 1 Tổng quan 1.1. Khái niệm cấu trúc dữ liệu & giải thuật 1.2. Đánh giá cấu trúc dữ liệu và giải thuật 1.3. Ôn lại ngôn ngữ C++ 1.4. Các kiểu dữ liệu 1.5. Kiểu dữ liệu trừu tượng 1.6. Hàm 1.7. Tổng kết 1.8. Câu hỏi và bài tập
  9. Cấu trúc dữ liệu n Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra (output data). Mỗi dữ liệu có một kiểu dữ liệu riêng. Kiểu dữ liệu có thể là kiểu cơ bản hay kiểu trừu tượng n Cấu trúc dữ liệu là sự sắp xếp có logic của thành phần dữ liệu được kết hợp với nhau và là tập hợp các thao tác chúng ta cần để truy xuất các thành phần dữ liệu. n Ví dụ: thư viện n Bao gồm các sách n Truy cập/tìm kiếm một cuốn sách nào đó đòi hỏi phải biết cách sắp xếp của các sách n Người dùng truy cập sách chỉ thông qua người quản lý thư viện.
  10. Cấu trúc dữ liệu Một cấu trúc dữ liệu tốt phải thỏa mãn: n Phản ánh đúng thực tế: Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn CTDL lưu trữ thể hiện chính xác đối tượng thực tế. n Phù hợp với các thao tác trên đó: Tăng tính hiệu quả của đề án, việc phát triển các thuật toán đơn giản, tự nhiên hơn => chương trình đạt hiệu quả cao hơn về tốc độ xử lý. n Tiết kiệm tài nguyên hệ thống: CTDL chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm được chức năng của nó. Loại tài nguyên cần quan tâm là : CPU và bộ nhớ.
  11. Những cấu trúc dữ liệu cơ bản n Các cấu trúc bao gồm n Danh sách liên kết (linked lists) n Ngăn xếp (Stack), Hàng đợi (Queue) n Cây nhị phân (binary trees) n
  12. Giải thuật giải là gì? n Giải thuật (Algorithm): n Còn gọi là thuật toán là tập các bước có thể tính toán được để đạt được kết quả mong muốn. n Giải thuật được xây dựng trên cơ sở của cấu trúc dữ liệu đã được chọn. n Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). n Ví dụ: Sắp xếp các phần tử 2 4 6 1 3 5 7 1 2 3 4 5 6 7
  13. 13 Giải thuật giải là gì? n Ví dụ: Tính tổng các số nguyên lẻ từ 1 n n B1: S=0 n B2: i=1 n B3: Nếu i>n thì sang B7, ngược lại sang B4 n B4: S=S+i n B5: i=i+2 n B6: Quay lại B3 n B7: Tổng cần tìm là S
  14. Giải thuật giải là gì? n Giải thuật (Algorithm): n Các tính chất quan trọng của giải thuật là: က¾ Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. က¾Xác định (definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán. က¾ Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. n Ngoài ra một giải thuật còn phải có đầu vào (input) và đầu ra (output).
  15. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật CTDL + Thuật toán = Chương trình
  16. Đánh giá CTDL và GT 1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu n Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau: n Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong), n Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán, n Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.
  17. Đánh giá CTDL và GT Thời gian thực hiện chương trình. n Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào. n Ví dụ: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số. n Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) 0 n 0. Đơn vị đo thời gian thực hiện. n Đơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng. n Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = cn thì có nghĩa là chương trình ấy cần cn chỉ thị thực thi.
  18. Đánh giá CTDL và GT Tỷ suất tăng n Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số c và n0 sao cho T(n) ≤ c.f(n) với mọi n ≥ n0. n Ví dụ 1-3: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2. Đặt n0 = 1 và c = 4 thì với mọi n ≥ 1 chúng ta dễ dàng chứng minh rằng T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2. n Ví dụ 1-4: Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực vậy, cho n0 = 0 và c = 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3
  19. Đánh giá CTDL và GT Khái niệm độ phức tạp của giải thuật n Độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử c trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có 2 3 n các dạng thường gặp sau: log2n, n, nlog2n, n , n , 2n, n!, n . n Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm khác gọi là hàm đa thức. n Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện, còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật.
  20. 20 Độ phức tạp thuật toán n Để đánh giá hiệu quả của một thuật toán, có thể tính số lượng các phép tính phải thực hiện của thuật toán này: n Phép so sánh n Phép gán n Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào n Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào n Tuy nhiên, không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng n Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm Big-O
  21. 21 Ví dụ Ø Bước 1. Gán Tổng = 0. Gán i = 0. int tong=0, i=0; Ø Bước 2. do{ – Tăng i thêm 1 đơn vị. i++; – Gán Tổng = Tổng + i tong+=i; Ø Bước 3. So sánh i với n }while (i<n); – Nếu i < n, quay lại bước 2. – Ngược lại, dừng thuật toán. • Số phép gán của thuật toán là bao nhiêu? • Số phép so sánh là bao nhiêu? Gán: f(2n + 2), So sánh: f(n) Độ phức tạp: O(n)
  22. Các độ phức tạp thường gặp (GT.53) 22 n Độ phức tạp hằng số: O(1) – thời gian chạy không phụ thuộc vào độ lớn đầu vào n Độ phức tạp tuyến tính: O(n) – thời gian chạy tỉ lệ thuận với độ lớn đầu vào n Độ phức tạp logarit: O(logn) n Độ phức tạp đa thức: O(P(n)), với P là đa thức có bậc từ 2 trở lên n Độ phức tạp hàm mũ: O(2n)
  23. Bảng so sánh các độ phức tạp của 23 thuật toán n Một số lớp thuật toán
  24. Thứ tự độ phức tạp của thuật toán 24
  25. Đánh giá CTDL và GT n Cách tính độ phức tạp Qui tắc cộng: n Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n))) n Ví dụ 1-6: Lệnh gán x=15 tốn một hằng thời gian hay O(1) n Lệnh đọc dữ liệu scanf(“%d”, x) tốn một hằng thời gian hay O(1) n Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)
  26. Đánh giá CTDL và GT n Cách tính độ phức tạp Qui tắc nhân: n Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n))
  27. Đánh giá CTDL và GT Qui tắc tổng quát để phân tích một chương trình: n Thời gian thực hiện của mỗi lệnh gán, Scanf, Printf là O(1) n Thời gian thực hiện của một chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng. Như vậy thời gian này là thời gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh. n Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau IF hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1). n Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.
  28. Đánh giá CTDL và GT Qui tắc tổng quát để phân tích một chương trình: Ví dụ : Tính thời gian thực hiện của đoạn chương trình n void BubleSort(int a[], int N ) { int i, j, temp; {1} for (i = 0 ; i i ; j ) {3} if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ {4} { temp = a[j]; {5} a[j] = a[j-1]; {6} a[j-1] = temp; } Cả ba lệnh đổi chỗ {4} {5} {6} tốn O(1) thời gian, do đó lệnh {3} tốn O(1). } Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1)=O (n-i). Vòng lặp {1} lặp (n-1) lần vậy độ phức tạp của giải thuật là:
  29. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 29
  30. 1. Cấu trúc chương trình C/C++ n Lệnh nhập và xuất dữ liệu n Using scanf, prinf (C standard) n Using cin, cout (Cpp) Ví dụ: Tìm số lớn nhất trong ba số nhập vào từ bàn phím C C++ #include cout >a,b,c; cout <<“max = “<<max;
  31. 1. Cấu trúc chương trình C/C++ 31 n Qui cách viết chương trình n Các dòng trong cùng một khối thẳng cột n Khối con của một khối lùi vào ít nhất một TAB n Ghi chú thích ở những chỗ cần thiết Chương 1: Ôn tập C/C++
  32. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Biến, Hằng, Kiểu dữ liệu và Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 32
  33. 33 2. Biến và Hằng số n Khai báo biến: Kiểu_dữ_liệu tên_biến; n Khai báo và khởi tạo biến: Kiểu_dữ_liệu tên_biến = giá trị; n Khai báo hằng số: const Kiểu_dữ_liệu tên_biến = giá trị; Chương 1: Ôn tập C/C++
  34. 2. Kiểu dữ liệu cơ sở n Kiểu số nguyên: n Có thể có dấu hoặc không có dấu n Các phép toán: O = {+, -, *, /, %, , =, =, } n Kiểu số thực: n Các phép toán: O = {+, -, *, /, , =, =, }
  35. 2. Kiểu dữ liệu n Kiểu ký tự: n Có thể có các kích thước sau: + Kiểu ký tự 1 byte + Kiểu ký tự 2 bytes n Các phép toán: O = {+, -, , =, =, ORD, CHR, } n Kiểu chuỗi ký tự: n Có kích thước tùy thuộc vào từng ngôn ngữ lập trình n Các phép toán: O = {+, &, , =, =, Length, Trunc, } n Kiểu luận lý: n Thường có kích thước 1 byte n Kiểu luận lý thường được thực hiện với các phép toán: O = {NOT, AND, OR, XOR, , =, =, }
  36. 36 2. Các phép toán n Chuyển đổi kiểu: n Trong biểu thức: kiểu thấp hơn sẽ được nâng thành kiểu cao hơn trước khi thực hiện phép toán Ví dụ: 7 + 3.5 n Trong phép gán: Giá trị của biểu thức vế phải được chuyển sang kiểu của biến vế trái Ví dụ: int a=5/2; //a=? float b=5/2; //b=? Chương 1: Ôn tập C/C++
  37. 37 2. Các phép toán n Ép kiểu: n Cú pháp: (Kiểu_dữ _liệu)biểu_thức hoặc Kiểu_dữ _liệu(biểu_thức) n Ví dụ: float b = (float)5/2; Chương 1: Ôn tập C/C++
  38. 38 2. Các cú pháp cơ bản Các toán tử điều khiển: n if n if else n switch case n for n while n do while Chương 1: Ôn tập C/C++
  39. 39 2. Các cú pháp cơ bản Toán tử điều kiện if ( bt_điều_kiện ) if ( bt_điều_kiện_1 ) khối_lệnh; khối_lệnh_1 else if ( bt_điều_kiện_2 ) if ( bt_điều_kiện ) khối_lệnh_2 khối_lệnh_1 else else khối_lệnh_2 khối_lệnh_n Chương 1: Ôn tập C/C++
  40. 40 2. Các cú pháp cơ bản Câu lệnh switch switch (biểu_thức_nguyên) { case hằng_1: các_câu_lệnh_1 [break;] case hằng_2: các_câu_lệnh_2 [break;] [default: các_câu_lệnh] } Chương 1: Ôn tập C/C++
  41. 41 2. Các cú pháp cơ bản Các toán tử điều khiển lặp for (bt_khởi_tạo; bt_kiểm_tra; bt_tăng) khối_lệnh while ( bt_điều_khiển ) do { { câu_lệnh_1; câu_lệnh_2; khối_lệnh }while (bt_điều_khiển); } Chương 1: Ôn tập C/C++
  42. 42 2. Các cú pháp cơ bản n Cấp phát bộ nhớ tĩnh: n Ví dụ: int a, b; n Cấp phát bộ nhớ động: n Bộ nhớ cũng có thể được cấp phát tại thời gian chạy, gọi là Cấp phát động (dynamic allocation) n Dùng toán tử new để cấp phát bộ nhớ động n Ví dụ: int *P; P = new int;
  43. 43 2. Các cú pháp cơ bản
  44. 44 2. Các cú pháp cơ bản n Cấp phát bộ nhớ động:  Heap: vùng bộ nhớ đặc biệt dành riêng cho các biến động. Để tạo một biến động mới, hệ thống cấp phát không gian từ heap. Nếu không còn bộ nhớ, new không thể cấp phát bộ nhớ thì nó trả về giá trị NULL  Trong lập trình, ta nên luôn kiểm tra lỗi này: int *p; p = new int; if (p == NULL) { cout << “Loi cap phat bo nho\n“; exit; }
  45. 45 2. Các cú pháp cơ bản n Hủy bộ nhớ động: n Trả lại vùng bộ nhớ trỏ bởi P, nhưng không sửa giá trị của P n Dùng toán tử delete để hủy bộ nhớ động n Sau khi thực thi delete, giá trị của con trỏ không xác định n Ví dụ: delete P;
  46. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 47 12. Hàm (Function)
  47. 3. Địa chỉ (Address) l Mỗi biến có hai thuộc tính: Địa chỉ (address) và giá trị (value ) Bộ nhớ tại địa chỉ 3: giá trị: 45. Bộ nhớ tại địa chỉ 2: giá trị "Dave" l Biến phải được khai báo trước khi sử dụng Ví dụ: int y=0; char kytu; cout << “Giá trị của 'y' là: " << y << "\n"; cout << “Địa chỉ của 'y' là: " << &y << "\n\n";
  48. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 49
  49. 4. Con trỏ (Pointer) n Là một kiểu dữ liệu đặc biệt, có giá trị là một địa chỉ vùng nhớ của một đối tượng (biến, hàm). n Cho phép truy xuất một đối tượng một cách gián tiếp, nghĩa là tham chiếu 1 đối tượng khác thông qua địa chỉ của nó. n Việc cấp phát động cho mảng được thực hiện thông qua con trỏ. n Tùy theo hệ máy mà kiểu dữ liệu con trỏ có các kích thước khác nhau: + Hệ máy PC: 2 bytes + Hệ máy tính lớn: 4 bytes Ví dụ Int i; giá trị của biến Int *p = &i; //p chứa địa chỉ của i *p = 10 ; //gán i=10
  50. 4. Con trỏ (Pointer) n Khai báo kiểu con trỏ: kiểucơsởT *tênkiểucontrỏ; n Kiểu cơ sở: là kiểu đã định nghiã trước, cũng có thể là kiểu con trỏ. n Kiểu con trỏ void: là kiểu con trỏ có thể chứa địa chỉ của bất kỳ kiểu nào. Nhưng khi sử dụng phải ép về 1 kiểu dữ liệu cụ thể. n Khai báo biến con trỏ: n Mẫu 1: tênkiểucontrỏ tênbiếncontrỏ; n Mẫu 2: kiểucơsởT *tênbiếncontrỏ; n Ví dụ: typedef int *intpointer; Ví dụ intpointer pt; hay int *pt;
  51. 4. Con trỏ (Pointer) Các thao tác trên biến con trỏ 1. Gán 1 địa chỉ cho biến con trỏ: n tênbiếncontrỏ = &tênbiếncầnlấyđịachỉ; n tênbiếncontrỏ = NULL; n Ví dụ: n Chứa địa chỉ của mảng 1 chiều: n int *P , A[10]; > P = A n Chứa địa chỉ của mảng 2 chiều: n float *P, B[3][4]; > P = (float*) B n Chứa địa chỉ của 1 biến cấu trúc: n struct HocSinh *P, hs; > P = &hs
  52. 4. Con trỏ (Pointer) Các thao tác trên biến con trỏ 2. Truy xuất nội dung 1 biến do biến con trỏ trỏ đến: *tênbiếncontrỏ n Lưu ý: Toán tử * và & cùng độ ưu tiên 3. Phép toán số học trên kiểu con trỏ: n Chỉ có ý nghĩa khi thực hiện trên mảng n pt + i ==> Cộng địa chỉ vùng nhớ lưu trong pt với i*sizeof(T) n pt1 – pt2==> số phần tử có kích thước sizeof(T) giữa 2 địa chỉ. n Phép so sánh con trỏ: so sánh địa chỉ lưu trong 2 biến con trỏ: ==, != n Tăng, giảm. n Ví dụ: int *p; p=p+2; // tăng 2 kích thước bộ nhớ int
  53. 54 4. Con trỏ (Pointer) #include #include void main () { int i; int *ia; i = 10; ia = &i; cout<<" The address of i is "<< ia <<"\n"; cout<<" The value at that location is "<< i <<"\n"; cout<<" The value at that location is "<< *ia <<"\n"; *ia = 50; cout<<" The value of i is "<<i; } Chương 1: Ôn tập C/C++
  54. 4. Con trỏ (Pointer) int i; //A int * ia; //B cout<<"The address of i "<< &i << " value="<<i <<endl; cout<<"The address of ia " << &ia << " value = " << ia<< endl; i = 10; //C ia = &i; //D cout<<"after assigning value:"<<endl; cout<<"The address of i "<< &i << " value="<<i <<endl; cout<<"The address of ia " << &ia << " value = " << ia<< " point to: "<< *ia;
  55. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 57
  56. 58 5. Mảng (Array) n Mảng: n Là một cấu trúc dữ liệu n Là danh sách các phần tử có cùng kiểu n Cho phép truy xuất ngẫu nhiên đến các phần tử của nó thông qua chỉ số mảng [0] [1] [2] [3] [4] A 12 2 8 5 1 n Khai báo: Kiểu_dữ_liệu tên_mảng[số_phần_tử]; Ví dụ: int a[100]; Chương 1: Ôn tập C/C++
  57. 59 5. Mảng (Array) n Địa chỉ của mỗi phần tử trong mảng: n Mỗi phần tử trong mảng có một địa chỉ trong bộ nhớ n Ví dụ: void printdetail (int a[]) { for(int i = 0; i<5; i++) { cout<< "value in array "<< a[i] <<" at address: " << &a[i]; } } Chương 1: Ôn tập C/C++
  58. 60 5. Mảng (Array) n Truy cập mảng sử dụng con trỏ: n Có thể truy cập từng phần tử của mảng bằng cách sử dụng con trỏ void print_usingptr(int a[], int n) void print_usingptr(int *a, int n) { { int *b; b=a; cout<<"value in array\n"; cout<<"value in array\n"; for (int i=0; i<n; i++) for (int i=0; i<n; i++) { { cout<<*(a+i)<<" "; cout<<*b<<" "; } b++; } } } Chương 1: Ôn tập C/C++
  59. 5. Mảng (Array) n Trường hợp khác của thao tác một mảng sử dụng con trỏ Mảng giới hạn là một con trỏ hằng nghĩa là không thể thay đổi giá trị của nó trong chương trình. int a[5]; int *b; a=b; //error b=a; //OK Làm việc đúng ngay cả khi dùng a++ ??? Demo
  60. 62 5. Mảng (Array) n Cấp phát động cho mảng và hủy mảng: n Kích thước của mảng động không cần là hằng số mà có thể có giá trị được quyết định tại thời gian chạy n new T[n] : cấp phát một mảng gồm n đối tượng kiểu T và trả về một con trỏ tới đầu mảng n delete [] p : hủy mảng mà p trỏ tới P phải trỏ tới đầu mảng động, nếu không, kết quả của delete sẽ phụ thuộc vào trình biên dịch và loại dữ liệu đang sử dụng. Ta có thể nhận được lỗi runtime error hoặc kết quả sai
  61. 5. Mảng (Array) 63
  62. 5. Mảng (Array) 64
  63. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 65
  64. 6. Mảng con trỏ (Pointer array) n Có thể khai báo mảng con trỏ (tương tự như mảng số) n Trong mảng con trỏ, các phần tử mảng lưu con trỏ Demo
  65. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 67
  66. 68 7. Mảng hai chiều (Two-dimensional array) n Khai báo: Kiểu_dữ_liệu tên_mảng[số_dòng] [số_cột]; n Ví dụ: int a[2][3]; float mang[10][5]; n Không lấy địa chỉ của phần tử mảng hai chiều bằng toán tử & Chương 1: Ôn tập C/C++
  67. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 71
  68. 8. Cấu trúc (Structure) n Kiểu cấu trúc được sử dụng khi bạn muốn xử lý dữ liệu của nhiều kiểu dữ liệu. Nhưng bạn chỉ muốn tham khảo tới dữ liệu như một thực thể đơn n Khai báo structure tencautruc { kieudulieu tenbien1; kieudulieu tenbien2; } n Truy xuất dữ liệu: tencautruc.tenthanhvien
  69. 73 8. Cấu trúc (Structure) n Khai báo biến kiểu cấu trúc (2 cách): Tên_cấu_trúc tên_biến; struct Tên_cấu_trúc tên_biến; n Truy xuất Tên_biến_cấu_trúc.Tên_thành _phần n Ví dụ: Ngay n; hoặc: struct Ngay ng; n Khởi tạo cho một cấu trúc: Ví dụ:struct Ngay d={10,15,2004}; struct Ngay a[]={ {10,15,2004}, {10,16,2004}, {10,17,2004}, {10,18,2004}}; Chương 1: Ôn tập C/C++
  70. 74 9. Con trỏ cấu trúc (Structure pointer) n Giống như các kiểu dữ liệu khác, ta có thể khai báo con trỏ cấu trúc n Ví dụ struct Ngay *p, a[10], *p1, b; p = a; p1 = &b; n Truy nhập thành phần của cấu trúc: tên_con_trỏ->tên_thành_phần hoặc : (*tên_con_trỏ).tên_thành_phần Chương 1: Ôn tập C/C++
  71. 9. Con trỏ cấu trúc (Structure pointer) Ví dụ: Xử lý kiểu cấu trúc sử dụng structure pointer Demo
  72. 76 Bài tập n Viết chương trình tính diện tích, chu vi hình chữ nhật (yêu cầu khai báo cấu trúc hình chữ nhật) n Viết chương trình tính diện tích, chu vi hình tròn (yêu cầu khai báo cấu trúc hình tròn) n Viết chương trình nhập n sinh viên gồm Masv, Hoten, Điểm toán, lý, hóa. In ra Masv, Hoten, Dtb và xếp loại của sinh viên đó Chương 1: Ôn tập C/C++
  73. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 77
  74. 78 10. Chuỗi (String) n Là mảng các ký tự (array of char) n Kết thúc bởi ký tự null “\0” (ending with null char \0) n Chuỗi hằng được tự động thêm “\0” n Ví dụ: char str[]=“Hello”;
  75. 79 10. Chuỗi (String) n Khai báo chuỗi: n char str[] = {‘H’,’e’,’l’,’l’,’o’,’\0’}; n char str[] = “Hello”; n char *str = “Hello”;
  76. 80 10. Chuỗi (String) n Hàm nhập chuỗi: n char *gets(char *s); n Nhận ký tự cho đến khi nhận dấu Enter n Tự động thêm ký tự ‘\0’ n So sánh với cin>>s; //???? n Hàm xuất chuỗi: n int puts(const char *s); n cout<<s;
  77. 10. Chuỗi (String) Một số thao tác thông dụng:(cần #include ) n So sánh 2 chuỗi: strcmp n Sao chép chuỗi: strcpy n Độ dài chuỗi: strlen n Kiểm tra 1 chuỗi nằm trong chuỗi kia: strstr n Cắt 1 từ ra khỏi 1 chuỗi: strtok n Đổi 1 số ra chuỗi: itoa n Đổi 1 chuỗi ra số: atoi, atof, n Nhập một chuỗi: gets n Xuất một chuỗi: puts
  78. 82 10. Chuỗi (String) n Ví dụ: char s1[80], s2[80]; cout << "Input the first string: :"; gets(s1); cout << "Input the second string: "; gets(s2); cout << "Length of s1= " << strlen(s1); cout << "Length of s2= " << strlen(s2); if (!strcmp(s1, s2)) cout << "These strings are equal\n"; strcat(s1, s2); cout << "s1 + s2: " << s1 << endl;; strcpy(s1, "This is a test.\n"); cout << s1; if (strchr(s1, 'e')) cout << "e is in " << s1; if (strstr(s2, "hi")) cout << "found hi in " <<s2;
  79. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 83
  80. 11. Tập tin (File) n Tập tin (File) có thể xem là một kiểu dữ liệu đặc biệt, kích thước tối đa của tập tin tùy thuộc vào không gian đĩa nơi lưu trữ tập tin. n Việc đọc, ghi dữ liệu trực tiếp trên tập tin rất mất thời gian và không bảo đảm an toàn cho dữ liệu trên tập tin đó. n Do vậy, trong thực tế, chúng ta không thao tác trực tiếp dữ liệu trên tập tin mà chúng ta cần chuyển từng phần hoặc toàn bộ nội dung của tập tin vào trong bộ nhớ trong để xử lý. n Có 2 loại tập tin : n File văn bản n File có cấu trúc truy nhập ngẫu nhiên (File nhị phân)
  81. 11. Tập tin (File) n Khai báo biến con trỏ file: FILE *TrỏFile; n Mỗi file đều được đánh dấu kết thúc bởi ký tự có mã 26. Khi sử dụng các hàm để đọc File, nếu gặp cuối File thì hàm sẽ trả về giá trị –1, có tên là EOF. n Mở file: TrỏFile = fopen (char *têntậptin, char *kiểu); n Têntậptin: Bao gồm cả đường dẫn. Nếu có lỗi sẽ cho giá trị NULL. n Kiểu: Kết hợp bởi các mã sau nhằm khai báo kiểu tập tin và cách thức truy xuất tập tin.
  82. 86 11. Tập tin (File) n Cần #include n Mở file hoặc tạo file mới: n FILE *fp; fp = fopen(“d:\\test.txt", "wb"); n Ghi nội dung vào file: n fwrite(&Address, sizeof(TYPE), count, fp); n Đọc nội dung từ file: n fread(&Address, sizeof(TYPE), count, fp); n Đóng file (Lưu file): n fclose(fp);
  83. 11. Tập tin (File) Kiểu Ý nghiã “b” Mở tập tin kiểu nhị phân “t” Mở tập tin kiểu văn bản “r” Mở để đọc. Nếu không có File sẽ báo lỗi “r+” Mở để sửa “w” Mở file mới để ghi. Nếu file đã có sẽ bị xóa “w+” Mở file mới đọc hoặc ghi. “a” Mở file để ghi thêm vào cuối file “a+” Mở file để đọc ghi. Nếu file cũ thì nối thêm,nếu không thì tạo mới
  84. 88 11. Tập tin (File) n Ví dụ: Tạo tập tin nhị phân để lưu 10 số nguyên #include #include void main() { FILE *f; f = fopen("D:\\songuyen.dat", "wb"); if ( f == NULL ) { cout << "Cannot open file.\n"; exit(0); } for( int i=1; i<=10; i++ ) fwrite(&i, sizeof(int), 1, f); fclose(f); }
  85. 11. Tập tin (File) n Ví dụ: Đọc tập tin nhị phân có chứa 10 số nguyên và xuất chúng ra màn hình #include void main() { FILE *f = fopen("D:\\songuyen.dat", "rb"); if (f == NULL) while ( (fread(&i, sizeof(int), 1, f)) != 0) { cout<< i<<" "; } fclose(f); } 89
  86. Kiểu dữ liệu trừu tượng n Một kiểu dữ liệu trừu tượng là một mô hình toán học cùng với một tập hợp các phép toán trên nó. Có thể nói kiểu dữ liệu trừu tượng là một kiểu dữ liệu do chúng ta định nghĩa ở mức khái niệm (conceptual), nó chưa được cài đặt cụ thể bằng một ngôn ngữ lập trình. n Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn ngữ lập trình cụ thể, chúng ta phải thực hiện hai nhiệm vụ: 1. Biểu diễn kiểu dữ liệu trừu tượng bằng một cấu trúc dữ liệu hoặc một kiểu dữ liệu trừu tượng khác đã được cài đặt. 2. Viết các chương trình con thực hiện các phép toán trên kiểu dữ liệu trừu tượng mà ta thường gọi là cài đặt các phép toán.
  87. Kiểu dữ liệu trừu tượng Kiểu DL trừu Đối tượng Phép toán tượng (Object) (Operations) Danh sách (List) Các nút Chèn, xóa, tìm, Đồ thị (Graphs) Đỉnh, cạnh Duyệt, đường đi, Integer - ,-1,0, ,+ +,-,*, Real - ,+ +,-,*, Ngăn xếp Các phần tử Pop, push, IsEmpty, Hàng đợi Các phần tử Enqueue, dequeue Cây nhị phân Các nút Traversal, find
  88. Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++ 2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Mảng con trỏ (Pointer array) 7. Mảng hai chiều (Two-dimensional array) 8. Cấu trúc (Structure) 9. Con trỏ cấu trúc (Structure pointer) 10. Chuỗi (String) 11. Tập tin (File) 12. Hàm (Function) 92
  89. HÀM - FUNCTION n Một hàm là một khối lệnh được đặt tên và có tính chất là nó có thể được thực thi tại nhiều điểm khác nhau trong chương trình khi được gọi. n Các đặc trưng của hàm ü Một chương trình có thể chứa nhiều hàm. ü Được gọi từ chương trình chính (main), từ hàm khác hoặc từ chính nó (đệ quy). ü Không lồng nhau. ü Có 3 cách truyền giá trị: Truyền theo tham trị, tham biến và tham trỏ. ü Các biến cục bộ trong hàm được tạo ra khi hàm được gọi và biến mất khi hàm thực thi xong.
  90. 94 12. Hàm (Function) n Các cú pháp định nghĩa hàm: void Tên_Hàm (kiểu_dữ_liệu tên_biến, ) { // các khai báo biến, // các lệnh } kiểu_dữ_liệu Tên_Hàm (kiểu_dữ_liệu tên_biến, ) { // các khai báo biến, // các lệnh return value; }
  91. 95 12. Hàm (Function) n Cách gọi hàm: n Bước 1: Chuẩn bị các tham số để gởi cho hàm nếu có: n Khai báo biến tương ứng và cho nhập dữ liệu cho biến (nếu cần) n Bước 2: Đối với: a. Hàm không trả về giá trị (void): Tên_Hàm (tham_số_1, tham_số_2, ); b. Hàm có trả về giá trị: n Khai báo một biến có kiểu trùng với kiểu trả về của hàm n Viết lệnh gán: biến = Tên_Hàm (tham_số_1, tham_số_2, ); n Sử dụng biến để xuất, tính toán, gọi hàm khác Chương 1: Ôn tập C/C++
  92. HÀM - FUNCTION n Ví dụ: n Result:?
  93. 97 12. Hàm (Function) #include #include int compute_sum(int n) { int sum=0; for(int i=1; i<=n; i++) sum +=i; return sum; } void main() { int lim = 5, sum; sum = compute_sum(lim); cout<<"The sum of integers from 1 to "<< lim<< " is "<<sum; }
  94. 12. Hàm (Function) n Truyền tham số theo giá trị và theo tham chiếu n Theo giá trị (passing by value ) n Giá trị trước và sau khi truyền không thay đổi. n Theo tham chiếu (passing by reference) n Giá trị bị thay đổi sau khi hàm thực hiện xong. b
  95. 12. Hàm (Function) void f1 (int k) void f1 (int &k) { { k = k + 10; k = k + 10; } } void main( ) void main( ) { { int i; int i; i = 0; i = 0; cout<<“Gia tri i truoc khi goi cout<<"Gia tri i truoc khi goi ham"<< i<<"\n"; ham"<< i<<"\n"; f1(i); f1(i); cout<<"Gia tri i sau khi goi cout<<"Gia tri i sau khi goi ham"<< i<<“\n"; ham"<< i<<“\n"; } }
  96. 100 12. Hàm (Function) n Nguyên mẫu hàm (Prototype) n Nguyên mẫu hàm được sử dụng để khai báo một hàm nhờ đó nó có thể được sử dụng trong chương trình trước khi hàm đó được định nghĩa thực sự n Công dụng: n Giúp chương trình mạch lạc n Giúp tổ chức chương trình n Cho phép sử dụng hàm trước khi định nghĩa Chương 1: Ôn tập C/C++
  97. #include #include int compute_sum(int n); void main() { int lim = 5, sum; sum = compute_sum(lim); cout<<"The sum of integers from 1 to "<< lim<< " is "<<sum; } int compute_sum(int n) { int sum=0; for(int i=1; i<=n; i++) sum +=i; return sum; } 101
  98. Tổng kết Trong chương này, chúng ta cần phải nắm vững các vấn đề sau: 1. Các bước phân tích và lập trình để quyết một bài toán thực tế. 2. 2. Hiểu rõ khái niệm về kiểu dữ liệu, kiểu dữ liệu trừu tượng và cấu trúc dữ liệu. 3. Hàm. 4. Ôn tập (Phần mảng)
  99. Câu hỏi và Bài tập 1. Trình bày tầm quan trọng của Cấu trúc dữ liệu và Giải thuật đối với người lập trình? 2. Các tiêu chuẩn để đánh giá cấu trúc dữ liệu và giải thuật? 3. Khi xây dựng giải thuật có cần thiết phải quan tâm tới cấu trúc dữ liệu hay không? Tại sao? 4. Liệt kê các kiểu dữ liệu cơ sở, các kiểu dữ liệu có cấu trúc trong C, Pascal? 5. Sử dụng các kiểu dữ liệu cơ bản trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ trong (RAM) của máy tính đa thức có bậc tự nhiên n (0 =< n <= 100) trên trường số thực (ai , x R): Với cấu trúc dữ liệu được xây dựng, hãy trình bày thuật toán và cài đặt chương trình để thực hiện các công việc sau: - Nhập, xuất các đa thức. - Tính giá trị của đa thức tại giá trị x0 nào đó. - Tính tổng, tích của hai đa thức.
  100. Câu hỏi và Bài tập 6. Cho bảng giờ tàu đi từ ga Saigon đến các ga như sau (ga cuối là ga Hà nội):
  101. Câu hỏi và Bài tập 6. Sử dụng các kiểu dữ liệu cơ bản, hãy xây dựng cấu trúc dữ liệu thích hợp để lưu trữ bảng giờ tàu trên vào bộ nhớ trong và bộ nhớ ngoài (disk) của máy tính. Với cấu trúc dữ liệu đã được xây dựng ở trên, hãy trình bày thuật toán và cài đặt chương trình để thực hiện các công việc sau: • Xuất ra giờ đến của một tàu T0 nào đó tại một ga G0 nào đó. • Xuất ra giờ đến các ga của một tàu T0 nào đó. • Xuất ra giờ các tàu đến một ga G0 nào đó. • Xuất ra bảng giờ tàu theo mẫu ở trên. Lưu ý: - Các ô trống ghi nhận tại các ga đó, tàu này không đi đến hoặc chỉ đi qua mà không dừng lại. - Dòng “HÀNH TRÌNH” ghi nhận tổng số giờ tàu chạy từ ga Saigon đến ga Hà nội.
  102. Thank you