ữ ệ
ấ
ả
C u trúc d li u và gi
ậ i thu t
Ôn tập
Giảng viên: Văn Chí Nam
Nội dung trình bày
Con trỏ
Đệ quy
Cấu trúc
Bài tập
2
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Nội dung trình bày
Con trỏ
Đệ quy
Cấu trúc
Bài tập
3
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Con trỏ
Địa chỉ trong bộ nhớ:
4
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Con trỏ
Địa chỉ trong bộ nhớ:
int X;
X = 5;
5
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Con trỏ
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:
6
*;
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Con trỏ
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*/
7
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Con trỏ
Lưu ý:
ớ
ị
ị
ỉ
Xác đ nh đ a ch ô nh : toán t
ử &
ị
ị ủ
ớ ạ ị
ế
ỉ
i đ a ch trong bi n con
ử
ỏ
Xác đ nh giá tr c a ô nh t *
tr : toán t
ỏ Con tr NULL.
ậ
ấ
8
ầ Truy c p thành ph n trong c u trúc: > i thu t HCMUS 2011
ữ ệ ậ ấ ả C u trúc d li u và gi
Con trỏ
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;
//delete []p;
9
p = new int[100]; ậ C u trúc d li u và gi
ữ ệ ấ ả i thu t HCMUS 2011
Con trỏ
Ví dụ:
int i;
int *p;
p = &i;
int j;
j = *p;
10
int day = pNgay->ngay; C u trúc d li u và gi
ữ ệ ậ ấ ả i thu t HCMUS 2011
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);
11
return 0; C u trúc d li u và gi }
ấ ữ ệ ả ậ i thu t HCMUS 2011
Con trỏ - Ví dụ
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 2011
Con trỏ - Ví dụ
#include
int main()
{
int i;
int *p;
p = &i;
*p=5;
printf("%d %d %d %d", i, *p, p, &p);
return 0;
13
} C u trúc d li u và gi
ữ ệ ấ ả ậ i thu t HCMUS 2011
Con trỏ - Ví dụ
#include
int main()
{
int i;
int *p;
p = &i;
*p=5;
printf("%d %d %d %d", i, *p, p, &p);
return 0;
14
} C u trúc d li u và gi
ữ ệ ấ ả ậ i thu t HCMUS 2011
Nội dung trình bày
Con trỏ
Đệ quy
Cấu trúc
Bài tập
15
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Khái niệm
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.
16
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Chú ý
Khi viết hàm đệ quy, cần xác định:
ệ ừ
ề
Đi u ki n d ng
ườ
ệ
ợ
Tr
ng h p đ quy
17
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Ví dụ
Tính tổng S(n) = 1 + 2 + … + n
Ta có:
S(n) = (1 + 2 + …+ n1) + 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)
18
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
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;
}
19
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Ví dụ
Viết hàm tính n! trong hai trường hợp: không đệ
20
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 2011
Ví dụ
Tính tổng GiaiThua(n) = 1 x 2 x … x n
Ta có:
GiaiThua(n) = (1 x 2 x …x n1) 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)
21
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Ví dụ
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.
22
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Ví dụ
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 ậ
23
ữ ệ ấ ả C u trúc d li u và gi i thu t HCMUS 2011
Ví dụ
Cho mảng một chiều các số nguyên. Viết hàm
24
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 2011
Ví dụ
Cho mảng một chiều các số nguyên. Viết hàm
25
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)
ệ ừ ả
ề ữ ệ C u trúc d li u và gi
Đi u ki n d ng: ậ Tong(a, 0) = 0
ấ i thu t HCMUS 2011
Ví dụ
Viết hàm đệ quy tính số hạng thứ n của dãy
26
Fibonacci. Biết rằng:
f(0) = f(1) = 1
f(n) = f(n1) + f(n2)
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Nội dung trình bày
Con trỏ
Đệ quy
Cấu trúc
Bài tập
27
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
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) ữ ệ
28
ỗ
ỗ
ấ ả C u trúc d li u và gi i thu t HCMUS 2011
SINHVIEN g m mssv (chu i), hoten (chu i),
ngaysinh (NGAY), quequan (chu i)ỗ
ậ ồ
Cấu trúc
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.
29
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
Định nghĩa cấu trúc:
30
struct {
;
;
…
;
ữ ệ ả ậ
}; ấ C u trúc d li u và gi
Ví dụ:
i thu t HCMUS 2011
struct NGAY {
int ngay;
int thang;
int nam;
};
Cấu trúc
Sử dụng:
31
;
Ví dụ:
NGAY NgayBatDau, NgayKetThuc;
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
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;
…
32
ữ ệ ả i thu t HCMUS 2011 ậ ấ C u trúc d li u và gi printf(“Ho ten sinh vien : %s”, sv.hoten);
Cấu trúc
Đị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
33
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
Định nghĩa cấu trúc:
ệ ọ ộ
ể
Đi m trên h t a đ Oxy.
34
struct DIEM {
float x;
float y;
};
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
Định nghĩa cấu trúc:
ệ ọ ộ
ể
Đi m trên h t a đ Oxy.
35
struct DOANTHANG {
DIEM BatDau;
DIEM KetThuc;
};
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
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?
36
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Cấu trúc
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");
37
printf("Toa do x: "); ả ấ C u trúc d li u và gi
scanf("%f", &diem.x);
printf("Toa do y: ");
scanf("%f", &diem.y);
ữ ệ ậ i thu t HCMUS 2011
Cấu trúc
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
38
thang\n",diem.x, diem.y); ấ ả C u trúc d li u và gi else
printf("Diem (%f, %f) khong thuoc duong
thang\n",diem.x, diem.y);
ữ ệ ậ i thu t HCMUS 2011
Nội dung trình bày
Con trỏ
Đệ quy
Cấu trúc
Bài tập
39
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Bài tập
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?
40
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Bài tập
Cho mảng một chiều các số nguyên. Viết hàm
41
đệ 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 2011
Bài tập
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.
42
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
Bài tập
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
43
đệ 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. ậ
ữ ệ ấ ả i thu t HCMUS 2011 C u trúc d li u và gi
44
Hỏi và đáp
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t HCMUS 2011
