�ݺ�ߣ

©FIT-HCMUS 1
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 2011
2
 Con trỏ
 Đệ quy
 Cấu trúc
 Bài tập

©FIT-HCMUS 2
3
 Con trỏ
 Đệ quy
 Cấu trúc
 Bài tập
4
 Địa chỉ trong bộ nhớ:

©FIT-HCMUS 3
5
 Địa chỉ trong bộ nhớ:
int X;
X = 5;
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:
<KieuDuLieu> *<TenBien>;

©FIT-HCMUS 4
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*/
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: ->

©FIT-HCMUS 5
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;
10
 Ví dụ:
int i;
int *p;
p = &i;
int j;
j = *p;
int day = pNgay->ngay;

©FIT-HCMUS 6
11
#include <stdio.h>
int main()
{
int i,j;
int *p;
p = &i;
*p = 5;
j = i;
printf("%d %d %dn", i, j, *p);
return 0;
}
12
#include <stdio.h>
int main()
{
int i,j;
int *p; /* a pointer to an integer */
p = &i;
*p=5;
j=i;
printf("%d %d %dn", i, j, *p);
return 0;
}

©FIT-HCMUS 7
13
#include <stdio.h>
int main()
{
int i;
int *p;
p = &i;
*p=5;
printf("%d %d %d %d", i, *p, p, &p);
return 0;
}
14
#include <stdio.h>
int main()
{
int i;
int *p;
p = &i;
*p=5;
printf("%d %d %d %d", i, *p, p, &p);
return 0;
}

©FIT-HCMUS 8
15
 Con trỏ
 Đệ quy
 Cấu trúc
 Bài tập
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.

©FIT-HCMUS 9
17
 Khi viết hàm đệ quy, cần xác định:
 Điều kiện dừng
 Trường hợp đệ quy
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)

©FIT-HCMUS 10
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;
}
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

©FIT-HCMUS 11
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)
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.

©FIT-HCMUS 12
23
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
24
tính tổng các số lẻ có trong mảng bằng phương
pháp đệ quy.

©FIT-HCMUS 13
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)
 Điều kiện dừng:
 Tong(a, 0) = 0
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)

©FIT-HCMUS 14
27
 Con trỏ
 Đệ quy
 Cấu trúc
 Bài tập
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)

©FIT-HCMUS 15
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.
30
 Định nghĩa cấu trúc:
struct <TenCauTruc>{
<KieuDuLieu> <ThanhPhan1>;
<KieuDuLieu> <ThanhPhan2>;
…
<KieuDuLieu> <ThanhPhanN>;
};
 Ví dụ:
struct NGAY {
int ngay;
int thang;
int nam;
};

©FIT-HCMUS 16
31
 Sử dụng:
<TenCauTruc> <BienCauTruc>;
 Ví dụ:
NGAY NgayBatDau, NgayKetThuc;
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);

©FIT-HCMUS 17
33
 Điểm trên hệ tọa độ Oxy.
 Đoạn thẳng trên hệ tọa độ Oxy.
 Sách trong thư viện
34
struct DIEM {
float x;
float y;
};

©FIT-HCMUS 18
35
struct DOANTHANG {
DIEM BatDau;
DIEM KetThuc;
};
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?

©FIT-HCMUS 19
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);
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
thangn",diem.x, diem.y);
else
printf("Diem (%f, %f) khong thuoc duong
thangn",diem.x, diem.y);

©FIT-HCMUS 20
39
 Con trỏ
 Đệ quy
 Cấu trúc
 Bài tập
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?

©FIT-HCMUS 21
41
đệ quy xuất mảng.
đệ quy xuất mảng theo thứ tự ngược (từ phải
sang trái).
42
đếm số lượng các phần tử dương có trong
mảng.
đếm số lượng các phần tử âm có trong mảng.

©FIT-HCMUS 22
43
đệ quy kiểm tra mảng có thỏa mãn tính chất
‘toàn giá trị âm’ hay không?
đệ quy tìm giá trị lớn nhất có trong mảng.
đệ quy tìm vị trí của phần tử có giá trị lớn nhất
có trong mảng.
44

�ݺ�ߣ

Cấu trúc dữ liệu cơ bản - Ôn tập

More Related Content

Cấu trúc dữ liệu cơ bản - Ôn tập