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

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

72
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 1 8/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 4 8/21/2015 Data structure & Algorithm
NỘI DUNG 3 3 Con trỏ 2 2 Cấu trúc 1 1 Đệ quy 8/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 đệ 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:  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 & Algorithm 17
CON TRỎ (POINTER)  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