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

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