CHƯƠNG 1. TỔNG QUAN VỀ CTDL & GT
Trần Minh Thái Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn
1
Mục tiêu
• Giới thiệu vai trò của tổ chức dữ liệu
• Mối quan hệ giữa GT & CTDL
• Các khái niệm và yêu cầu về CTDL
• Nhắc lại các kiểu dữ liệu trong C++
• Tổng quan về đánh giá độ phức tạp GT
2
Suy nghĩ
ạ
ướ
ế
Theo b n: tr
c khi vi
ộ t m t
ể ả
ế
ộ
ươ
ng trình đ gi
i quy t m t bài toán nào
ch
?
ữ
ệ
ả
ầ đó trên máy tính thì c n ph i làm nh ng vi c
gì?
3
Xét đoạn chương trình sau
void main()
{
int n;
cout<<"Nhap vao so nguyen n: ";
cin>>n;
if(n%2==0)
cout<<"La so chan";
else
cout<<"La so le";
4
}
Vai trò của CTDL & GT
Giải thuật
Cấu trúc dữ liệu
Chương trình
5
Các tiêu chuẩn đánh giá CTDL
• Phản ánh đúng thực tế
• Phù hợp với thao tác
• Tiết kiệm tài nguyên hệ thống
6
Khái niệm về kiểu dữ liệu
T =
Ví dụ: Kiểu dữ liệu số nguyên short trong ngôn ngữ C
T = short V = {-32768, 32767} O = {+, -, *, /, %}
7
Khái niệm về kiểu dữ liệu
• Các thuộc tính của một kiểu dữ liệu gồm:
•
•
•
•
Tên Miền giá trị Kích thước lưu trữ Tập các thao tác tác động lên kiểu dữ liệu đó
• Các loại kiểu dữ liệu
•
•
Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản Kiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, …
8
Khái niệm về kiểu dữ liệu
Tĩnh • Được định nghĩa ở thời
điểm biên dịch.
• Được cấp phát ở thời
Động • Được gắn kết với một con trỏ (tại thời điểm biên dịch chưa có). • Phát sinh lúc thực thi.
điểm liên kết.
• Không xác định giá trị
ban đầu.
• Có thể có giá trị ban đầu tùy theo từng ngôn ngữ lập trình.
• Tồn tại đến khi kết thúc
• Được giải phóng khỏi
chương trình.
bộ nhớ khi cần.
9
Nhắc lại các kiểu dữ liệu C++
• Kiểu cơ sở: Số nguyên, số thực và kiểu logic
• Kiểu mảng, chuỗi
• Kiểu có cấu trúc
10
Kiểu số nguyên
Stt
Tên ki uể
Ghi chú
Kích th
cướ
1
char
1 byte 1 byte
2
unsigned char short
1 byte 2 bytes
3 4
unsigned short int
2 bytes 4 bytes
5 6
11
unsigned int long
4 bytes 4 bytes
7 8
Ky t́ ự ́ Sô nguyên ́ Sô nguyên ngươ d ́ Sô nguyên ố S nguyên ngươ d ́ Sô nguyên ́ Sô nguyên ngươ d ́ Sô nguyên ́ Sô nguyên
unsigned long
d
ngươ
4 bytes
Kiểu số thực
Tên ki uể
Ghi chú
Kích th
cướ
Stt 1 2 3
float double long double
4 bytes 8 bytes 8 bytes
ể
ậ
Ki u lu n lý
Tên ki uể
cướ
Stt 1
bool
Ghi chú ồ G m 2 giá tr :
Kích th ị true ho c ặ false
12
Kiểu mảng 1 chiều
5
7
10 … 3
11
2
0
1
2 …
n-2 n-1
Giá trị Vị trí • Khai báo
• Gán giá trị ban đầu
VD: int a[100];
VD1: int a[100] = {0};
VD2: int a[5] = {3, 6, 2, 10, 17};
13
hoặc: int a[] = {3, 6, 2, 10, 17};
Kiểu mảng 1 chiều
- Khởi tạo phát sinh ngẫu nhiên
Phát sinh ngẫu nhiên
- Phát sinh giá trị ngẫu nhiên
srand((unsigned int)time(NULL));
int x = rand()%k;
k: Số nguyên dương x (cid:0) [0..k-1]
VD: Phát sinh 1 số nguyên có giá trị từ 0 đến 50
srand((unsigned int)time(NULL));
14
int x = rand()%51;
Bài tập 1
1.
2.
Cài đặt hàm nhập mảng số nguyên, n phần tử
Cài đặt hàm phát sinh n phần tử ngẫu nhiên cho mảng số
3.
nguyên
Cài đặt hàm phát sinh n phần tử ngẫu nhiên có giá trị tăng
15
dần cho mảng số nguyên
Kiểu chuỗi ký tự
• Khai báo
char
• Xem lại các hàm
- cin.getline, cin.ignore
- strcpy, strcat, strlen
- strcmp, stricmp
- strchr, strstr
16
VD: char hoten[50];
Kiểu mảng – Khai báo kiểu con trỏ
• Mảng 1 chiều
• Chuỗi ký tự
VD: int *a;
char *
17
VD: char *hoten;
Kiểu mảng – Khai báo kiểu con trỏ
Lưu ý khi sử dụng phải cấp phát biến con trỏ bằng lệnh new, hủy bằng lệnh delete
VD:
int *a;
int n = 10;
a = new int[n];
…..
18
delete a;
Bài tập 2
19
Viết lại các hàm trong Bài tập 1 dùng khai báo kiểu con trỏ
Kiểu dữ liệu có cấu trúc
struct tên_struct
{
khai báo các thuộc tính;
};
20
typedef struct tên_struct tên_kiểu;
Ví dụ kiểu dữ liệu có cấu trúc
struct ttDate
{
char thu[9];
unsigned char ngay;
unsigned char thang;
int nam;
};
21
typedef struct ttDate DATE;
Truy cập thành phần có cấu trúc
• Biến cấu trúc kiểu tĩnh
VD:
DATE d;
22
d.nam = 2012;
Bài tập 3
- Mã số
- Họ tên
- Điểm trung bình
23
Viết hàm nhập và hàm xuất thông tin của một sinh viên gồm các thông tin:
Truy cập thành phần có cấu trúc
• Biến cấu trúc kiểu con trỏ
VD:
DATE *d;
24
d->nam = 2012;
Bài tập 4
25
Viết lại các hàm trong Bài tập 3 sử dụng khai báo biến kiểu con trỏ cấu trúc
Các phương pháp mô tả giải thuật
• Lưu đồ
• Mã giả
• Mã tự nhiên
26
Các ký hiệu lưu đồ
Bắt đầu/ kết thúc
Rẽ nhánh
ị ả ề
Giá tr tr v
Điề u kiện
ể
ố Đi m n i
Luồng xử lý
Khối xử lý
27
Nhập/ Xuất
Ký hiệu mã giả
• IF <điều kiện> THEN …ENDIF
• IF <điều kiện> THEN ... ELSE ... ENDIF
• WHILE <điều kiện> DO … ENDWHILE
• DO … UNTIL <điều kiện>
• DISPLAY …
• RETURN …
28
Ví dụ mô tả giải thuật
• Đầu vào: 2 số nguyên dương a và b
• Đầu ra: ước số chung lớn nhất của a và b
29
Tìm ước số chung lớn nhất của 2 số nguyên dương a và b
Mô tả bằng mã tự nhiên
Bước 1: Nếu a = b thì kết luận a là ước số chung lớn nhất, kết
thúc
Bước 2: Nếu a > b thì a = a – b;
Ngược lại thì b = b – a;
30
Bước 3: Quay trở lại Bước 1
Mô tả bằng mã giả
WHILE a ≠ b DO
IF a>b THEN
a=a-b
ELSE
b=b-a
ENDIF
ENDWHILE
31
DISPLAY a
Mô tả bằng lưu đồ
32
Đánh giá độ phức tạp giải thuật
• Phụ thuộc vào ngôn ngữ lập trình
• Phụ thuộc vào người lập trình
• Phụ thuộc vào bộ dữ liệu thử
• Phụ thuộc vào phần cứng
33
Q&A
?
34
