›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Ôn tập

pdf 22 trang phuongnguyen 3740
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 - Ôn tập", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_on_tap.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Ôn tập

  1. Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 2  Con trỏ  Đệ quy  Cấu trúc  Bài tập Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 1
  2. 3  Con trỏ  Đệ quy  Cấu trúc  Bài tập Cấu trúc dữ liệu và giải thuật - HCMUS 2011 4  Địa chỉ trong bộ nhớ: Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 2
  3. 5  Địa chỉ trong bộ nhớ: int X; X = 5; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 6  Khái niệm đặc biệt trong C/C++.  Biến con trỏ: loại biến dùng để chứa địa chỉ.  Khai báo: * ; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 3
  4. 7  Ví dụ: int *a; /*con trỏ đến kiểu int*/ float *b; /*con trỏ đến kiểu float*/ NGAY *pNgay; /*con trỏ đến kiểu NGAY*/ SINHVIEN *pSV; /*con trỏ đến kiểu SINHVIEN*/ Cấu trúc dữ liệu và giải thuật - HCMUS 2011 8  Lưu ý:  Xác định địa chỉ ô nhớ: toán tử &  Xác định giá trị của ô nhớ tại địa chỉ trong biến con trỏ: toán tử *  Con trỏ NULL.  Truy cập thành phần trong cấu trúc: -> Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 4
  5. 9  Cấp phát vùng nhớ động:  Cấp phát: toán tử new.  Hủy: toán tử delete.  Ví dụ: int *p; p = new int; //delete p; p = new int[100]; //delete []p; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 10  Ví dụ: int i; int *p; p = &i; int j; j = *p; int day = pNgay->ngay; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 5
  6. 11 #include int main() { int i,j; int *p; p = &i; *p = 5; j = i; printf("%d %d %d\n", i, j, *p); return 0; } Cấu trúc dữ liệu và giải thuật - HCMUS 2011 12 #include int main() { int i,j; int *p; /* a pointer to an integer */ p = &i; *p=5; j=i; printf("%d %d %d\n", i, j, *p); return 0; } Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 6
  7. 13 #include int main() { int i; int *p; p = &i; *p=5; printf("%d %d %d %d", i, *p, p, &p); return 0; } Cấu trúc dữ liệu và giải thuật - HCMUS 2011 14 #include int main() { int i; int *p; p = &i; *p=5; printf("%d %d %d %d", i, *p, p, &p); return 0; } Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 7
  8. 15  Con trỏ  Đệ quy  Cấu trúc  Bài tập Cấu trúc dữ liệu và giải thuật - HCMUS 2011 16  Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách tường minh hay tiềm ẩn. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 8
  9. 17  Khi viết hàm đệ quy, cần xác định:  Điều kiện dừng  Trường hợp đệ quy Cấu trúc dữ liệu và giải thuật - HCMUS 2011 18  Tính tổng S(n) = 1 + 2 + + n  Ta có:  S(n) = (1 + 2 + + n-1) + n  Trường hợp n>0:  S(n) = S(n-1) + n (điều kiện đệ quy)  Trường hợp n=0  S(0) = 0 (điều kiện dừng) Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 9
  10. 19  Tính tổng S(n) = 1 + 2 + + n int Tong(int n) { if (n == 0)//điều kiện dừng return 0; return Tong(n-1) + n; } Cấu trúc dữ liệu và giải thuật - HCMUS 2011 20  Viết hàm tính n! trong hai trường hợp: không đệ quy và đệ quy. Biết:  n! = 1 x 2 x 3 x x n  0! = 1 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 10
  11. 21  Tính tổng GiaiThua(n) = 1 x 2 x x n  Ta có:  GiaiThua(n) = (1 x 2 x x n-1) x n  Trường hợp n>0:  GiaiThua(n) = GiaiThua(n-1) x n (điều kiện đệ quy)  Trường hợp n=0  GiaiThua(0) = 1 (điều kiện dừng) Cấu trúc dữ liệu và giải thuật - HCMUS 2011 22  Cho mảng một chiều các số nguyên. Viết hàm tính tổng các số nguyên có trong mảng bằng phương pháp đệ quy. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 11
  12. 23  Cho mảng một chiều các số nguyên. Viết hàm tính tổng các số nguyên có trong mảng bằng phương pháp đệ quy.  Input: int[] a, int n  Output: int (Tổng)  Trường hợp đệ quy:  Tong(a, n) = Tong(a,n-1) + a[n-1]  Điều kiện dừng:  Tong(a, 0) = 0 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 24  Cho mảng một chiều các số nguyên. Viết hàm tính tổng các số lẻ có trong mảng bằng phương pháp đệ quy. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 12
  13. 25  Cho mảng một chiều các số nguyên. Viết hàm tính tổng các số lẻ có trong mảng bằng phương pháp đệ quy.  Input: int[] a, int n  Output: int (Tổng)  Trường hợp đệ quy:  Nếu a[n-1] lẻ: Tong(a, n) = Tong(a,n-1) + a[n-1]  Nếu a[n-1] chẳn: Tong(a, n) = Tong(a,n-1)  Điều kiện dừng:  Tong(a, 0) = 0 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 26  Viết hàm đệ quy tính số hạng thứ n của dãy Fibonacci. Biết rằng:  f(0) = f(1) = 1  f(n) = f(n-1) + f(n-2) Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 13
  14. 27  Con trỏ  Đệ quy  Cấu trúc  Bài tập Cấu trúc dữ liệu và giải thuật - HCMUS 2011 28  Cấu trúc là phương pháp/cách thức tập hợp các thông tin dữ liệu khác nhau vào trong một dữ liệu.  Dễ dàng lưu trữ, truy cập, sử dụng.  Định nghĩa thành kiểu dữ liệu riêng  Ví dụ:  NGAY gồm ngay (nguyên), thang (nguyên), nam (nguyên)  SINHVIEN gồm mssv (chuỗi), hoten (chuỗi), ngaysinh (NGAY), quequan (chuỗi) Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 14
  15. 29  Thành phần của cấu trúc:  Kiểu dữ liệu chuẩn.  Kiểu cấu trúc khác.  Sử dụng từ khóa struct.  Sử dụng như một kiểu dữ liệu tự định nghĩa. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 30  Định nghĩa cấu trúc: struct { ; ; ; };  Ví dụ: struct NGAY { int ngay; int thang; int nam; }; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 15
  16. 31  Sử dụng: ;  Ví dụ: NGAY NgayBatDau, NgayKetThuc; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 32  Truy cập thành phần của cấu trúc: NGAY ngaysinh; ngaysinh.ngay = 10; ngaysinh.thang = 1; ngaysinh.nam = 1990; SINHVIEN sv; printf(“Ho ten sinh vien : %s”, sv.hoten); Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 16
  17. 33  Định nghĩa cấu trúc:  Điểm trên hệ tọa độ Oxy.  Đoạn thẳng trên hệ tọa độ Oxy.  Sách trong thư viện Cấu trúc dữ liệu và giải thuật - HCMUS 2011 34  Định nghĩa cấu trúc:  Điểm trên hệ tọa độ Oxy. struct DIEM { float x; float y; }; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 17
  18. 35  Định nghĩa cấu trúc:  Điểm trên hệ tọa độ Oxy. struct DOANTHANG { DIEM BatDau; DIEM KetThuc; }; Cấu trúc dữ liệu và giải thuật - HCMUS 2011 36  Một ví dụ  Nhập vào tọa độ của một điểm và kiểm tra xem điểm này có nằm trên đường thẳng y=2x+1 không? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 18
  19. 37  Một ví dụ  Nhập vào tọa độ của một điểm và kiểm tra xem điểm này có nằm trên đường thẳng y=2x+1 không?  Nhập điểm: DIEM diem; printf("Nhap vao mot diem: \n"); printf("Toa do x: "); scanf("%f", &diem.x); printf("Toa do y: "); scanf("%f", &diem.y); Cấu trúc dữ liệu và giải thuật - HCMUS 2011 38  Một ví dụ  Nhập vào tọa độ của một điểm và kiểm tra xem điểm này có nằm trên đường thẳng y=2x+1 không?  Kiểm tra: if (diem.y == 2 * diem.x +1) printf("Diem (%f, %f) thuoc duong thang\n",diem.x, diem.y); else printf("Diem (%f, %f) khong thuoc duong thang\n",diem.x, diem.y); Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 19
  20. 39  Con trỏ  Đệ quy  Cấu trúc  Bài tập Cấu trúc dữ liệu và giải thuật - HCMUS 2011 40  Cho đoạn code sau đây: int i; int *p, *q, *r; p = &i; q = &i; r = p;  Nếu *r = 5, hỏi *p, *q có giá trị bao nhiêu?  Nếu i = 20 thì *r có giá trị bao nhiêu? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 20
  21. 41  Cho mảng một chiều các số nguyên. Viết hàm đệ quy xuất mảng.  Cho mảng một chiều các số nguyên. Viết hàm đệ quy xuất mảng theo thứ tự ngược (từ phải sang trái). Cấu trúc dữ liệu và giải thuật - HCMUS 2011 42  Cho mảng một chiều các số nguyên. Viết hàm đếm số lượng các phần tử dương có trong mảng.  Cho mảng một chiều các số nguyên. Viết hàm đếm số lượng các phần tử âm có trong mảng. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 21
  22. 43  Cho mảng một chiều các số nguyên. Viết hàm đệ quy kiểm tra mảng có thỏa mãn tính chất ‘toàn giá trị âm’ hay không?  Cho mảng một chiều các số nguyên. Viết hàm đệ quy tìm giá trị lớn nhất có trong mảng.  Cho mảng một chiều các số nguyên. Viết hàm đệ quy tìm vị trí của phần tử có giá trị lớn nhất có trong mảng. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 44 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 22