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

Giảng viên: 
Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
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 2013 
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 2013 
4 
 Địa chỉ trong bộ nhớ: 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
5 
 Địa chỉ trong bộ nhớ: 
int X; 
X = 5; 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
31 
 Sử dụng: 
 ; 
 Ví dụ: 
NGAY NgayBatDau, NgayKetThuc; 
Cấu trúc dữ liệu và giải thuật - HCMUS 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
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 2013 
44