Bài giảng Cấu trúc dữ liệu và giải thuật: Ôn tập - Lê Thị Ngọc Hạnh

Bài giảng này nhắc lại những kiến thức cơ bản về cấu trúc dữ liệu và giải thuật. Trong chương này người học sẽ ôn tập lại các kiến thức về đệ qui, cấu trúc và con trỏ. Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Ôn tập - Lê Thị Ngọc Hạnh CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT GV: LÊ THỊ NGỌC HẠNH 18/21/2015 Data structure & Algorithm ĐÁ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 ÔN TẬP GV: LÊ THỊ NGỌC HẠNH 48/21/2015 Data structure & Algorithm NỘI DUNG 3 3 Con trỏ 2 2 Cấu trúc 1 1 Đệ quy8/21/2015 Data structure & Algorithm 5 ĐỆ 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 đệ quy8/21/2015 Data structure & Algorithm 6 ĐỆ QUY – VÍ DỤTính tổng S(n) = 1 + 2 + … + nTa 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 + … + nint 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ẬP1. 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ếthàm tính tổng các số lẻ có trong mảng bằngphương pháp đệ quy8/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:  Cách 2:struct struct { { ; ; … … ; ;} , ; };Ví dụ: struct ;struct DIEM Ví dụ:{ struct DIEM int x; { int y; int x, y;} diem1, diem2; }; DIEM diem1, diem2; 8/21/2015 Data structure & Algorithm 12 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 & Algori ...