Giáo trình môn học Cấu trúc dữ liệu và giải thuật

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. Chú ý: Khi viết hàm đệ quy, cần xác định: • Điều kiện dừng • Trường hợp đệ quy

pdf28 trang | Chia sẻ: thuychi16 | Lượt xem: 756 | Lượt tải: 2download
Bạn đang xem trước 20 trang tài liệu Giáo trình môn học Cấu trúc dữ liệu và giải thuật, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
G V : L Ê T H Ị N GỌC HẠN H CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 8/21/2015 Data structure & Algorithm 1 ĐÁNH GIÁ MÔN HỌC Thang điểm: 10 Tỉ lệ điểm thành phần: Chuyên cần : giữa kỳ : cuối kỳ (1:3:6) Đồ án miễn thi cuối kỳ: gồm 5 đồ án, mỗi nhóm tối đa 2 thành viên. Nộp trước ngày 30/10/2014. 8/21/2015 Data structure & Algorithm 2 TÀI LIÊU THAM KHẢO Giáo trình “Cấu trúc dữ liệu và giải thuật”, Trần Hạnh Nhi, Dương Anh Đức, Nxb ĐHQG TP. HCM. Data Structures And Problem Solving Using C++ , Mark Weiss, Florida International University. 8/21/2015 Data structure & Algorithm 3 G V : L Ê T H Ị N GỌC HẠN H ÔN TẬP 8/21/2015 Data structure & Algorithm 4 NỘI DUNG 8/21/2015 Data structure & Algorithm 5 Cấu trúc Con trỏ Đệ quy 1 2 3 1 2 3 ĐỆ QUY 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. Chú ý: Khi viết hàm đệ quy, cần xác định: • Điều kiện dừng • Trường hợp đệ quy 8/21/2015 Data structure & Algorithm 6 ĐỆ QUY – VÍ DỤ 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) 8/21/2015 Data structure & Algorithm 7 ĐỆ QUY – VÍ DỤ 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; } 8/21/2015 Data structure & Algorithm 8 ĐỆ QUY – BÀI TẬP 1. Với a > 0, cho dãy số thực được cho theo công thức truy hồi sau: 𝒙𝟎 = 1; 𝒙𝒏= 𝒙𝒏−𝟏 𝟐 + 𝒂 𝟐𝒙𝒏−𝟏 nếu n ≥ 1 2. 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 8/21/2015 Data structure & Algorithm 9 CẤU TRÚC (STRUCT) 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) 8/21/2015 Data structure & Algorithm 10 CẤU TRÚC (STRUCT) 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. 8/21/2015 Data structure & Algorithm 11 STRUCT– KHAI BÁO  Cách 1: struct { ; ; } , ; Ví dụ: struct DIEM { int x; int y; } diem1, diem2; 8/21/2015 Data structure & Algorithm 12  Cách 2: struct { ; ; }; struct ; Ví dụ: struct DIEM { int x, y; }; DIEM diem1, diem2; STRUCT Sử dụng: ; Ví dụ: NGAY NgayBatDau, NgayKetThuc; 8/21/2015 Data structure & Algorithm 13 STRUCT 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); 8/21/2015 Data structure & Algorithm 14 BÀI TẬP  Định nghĩa kiểu dữ liệu thí sinh (THISINH) gồm các thông tin: số báo danh (sbd), ngày sinh (ngaysinh), họ tên (hoten), khối thi (khoithi), điểm môn thi 1 (mon1), điểm môn thi 2 (mon2), điểm môn thi 3 (mon3), tổng điểm thi (tongdiem).  Viết hàm nhập các thông tin của thí sinh.  Hàm xuất các thông tin của thí sinh.  Viết hàm tính tổng điểm thi của thí sinh.  Hàm xử lý: nếu tổng điểm thi trên 15 điểm và không có điểm khống chế (2 điểm) thì thí sinh đó trúng tuyển, ngược lại là không trúng tuyển.  Hàm main, xuất các thông tin của thí sinh đã nhập và kết quả thi của thí sinh. 8/21/2015 Data structure & Algorithm 15 CON TRỎ (POINTER) Địa chỉ trong bộ nhớ: 8/21/2015 Data structure & Algorithm 16 CON TRỎ (POINTER) Địa chỉ trong bộ nhớ: int X = 5; 8/21/2015 Data structure & Algorithm 17 Biến con trỏ: loại biến dùng để chứa địa chỉ. Khai báo: *; 8/21/2015 Data structure & Algorithm 18 CON TRỎ (POINTER) 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*/ 8/21/2015 Data structure & Algorithm 19 CON TRỎ (POINTER) 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ử * • Truy cập thành phần trong cấu trúc:  8/21/2015 Data structure & Algorithm 20 CON TRỎ (POINTER) Ví dụ: int i; int *p; p = &i; int j; j = *p; int day = pNgay->ngay; 8/21/2015 Data structure & Algorithm 21 CON TRỎ - VÍ DỤ CON TRỎ - VÍ DỤ #include int main() { int i,j; int *p; p = &i; *p = 5; j = i; printf("%d %d %d\n", i, j, *p); return 0; } 8/21/2015 Data structure & Algorithm 22 CÁC CẤU TRÚC ĐIỀU KHIỂN Cấu trúc lựa chọn thực hiện lệnh theo tình huống: If; if else; switch . 8/21/2015 Windows Programming 23 CÁC CẤU TRÚC ĐIỀU KHIỂN 8/21/2015 Windows Programming 24 CÁC CẤU TRÚC ĐIỀU KHIỂN Viết chương trình nhập vào năm dương lịch (từ 1975 trở đi) và in ra các giải thể thao lớn được tổ chức trong năm đó. Biết rằng: Các năm chia hết cho 4 có tổ chức Olympic và các giải bóng Châu Âu Các năm chia 4 dư 2 có tổ chức WorldCup Các năm lẻ và cũng là các năm chia 4 dư 1 hoặc dư 3 thì tổ chức Sea Games 8/21/2015 Windows Programming 25 CÁC CẤU TRÚC ĐIỀU KHIỂN TRONG C# Các cấu trúc lặp để thực thi lệnh theo chu kỳ: For ; dowhile; while 8/21/2015 Windows Programming 26 CÁC CẤU TRÚC ĐIỀU KHIỂN 8/21/2015 Windows Programming 27 BÀI TẬP  Định nghĩa kiểu dữ liệu thí sinh (THISINH) gồm các thông tin: số báo danh (sbd), ngày sinh (ngaysinh), họ tên (hoten), khối thi (khoithi), điểm môn thi 1 (mon1), điểm môn thi 2 (mon2), điểm môn thi 3 (mon3), tổng điểm thi (tongdiem).  Viết hàm nhập các thông tin của thí sinh.  Hàm xuất các thông tin của thí sinh.  Viết hàm tính tổng điểm thi của thí sinh.  Hàm xử lý: nếu tổng điểm thi trên 15 điểm và không có điểm khống chế (2 điểm) thì thí sinh đó trúng tuyển, ngược lại là không trúng tuyển.  Hàm main, xuất các thông tin của thí sinh đã nhập và kết quả thi của thí sinh. 8/21/2015 Data structure & Algorithm 28
Tài liệu liên quan