Bài giảng Giới thiệu về cấu trúc dữ liệu và giải thuật - Bài 1 - Lê Sỹ Vinh giúp bạn nắm bắt cấu trúc dữ liệu, thuật toán, dữ liệu, kiểu dữ liệu cơ bản, kiểu dữ liệu có cấu trúc, trừu tượng hóa dữ liệu.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Giới thiệu về cấu trúc dữ liệu và giải thuật - Bài 1 - Lê Sỹ Vinh
- Bài 1: Giới thiệu về cấu trúc dữ liệu
và giải thuật
(Introduction to data structures and algorithms)
Lê Sỹ Vinh
Bộ Môn Khoa Học Máy Tính – Khoa CNTT
Đại Học Công Nghe - ĐHQGHN
Email: vinhioi@yahoo.com
- C u trúc d li u (data structure)
- C u trúc d li u là gì?
C u trúc d li u là cách t ch c lưu gi d li u trong sao cho hi u qu nh t
- Th nào là hi u qu ?
1. “Chính xác”
2. Dùng ít b nh
3. Kh năng tìm ki m/truy xu t
4.
4. Kh năng c p nh t, thêm b t (modification, insertion / deletion)
5. ðơn gi n, d hi u
- Các ki u c u trúc d li u cơ b n
• B n ghi (struct)
• Danh sách (array)
• Danh sách liên k t (list)
• Cây (tree)
• B ng băm (hash table)
- Thu t toán (algorithm)
• Thu t toán là gì?
Thu t toán là m t phương pháp bao g m m t dãy các bư c tính toán ñ
gi i quy t m t bài toán. Thu t toán có th ñư c di n t dư i d ng ngôn
ng t nhiên (ti ng Vi t, ti ng Anh…) hay ngôn ng l p trình (C++,
Java…)
• Th nào là m t thu t toán t t?
1. “ðúng ñ n”
2. Nhanh
3. Ít b nh
4. ðơn gi n, d hi u
- Ví d 1: S p x p danh sách tuy n sinh
Năm 2008, ð i h c Công Ngh có N thí sinh tham gia tuy n sinh, hãy vi t
chương trình s p x p các thí sinh theo th t gi m d n c a t ng ñi m thi ba
môn
Ví d :
Stt H tên Toán Lý Hóa T ng
1 Tr n Anh Tu n 7 8 7 22
2 Bùi Ng c Thăng 10 10 9 29
3 Lê S Vinh 10 8 8 26
4 Nguy n Th Ánh 8 10 9 27
- S p x p n i b t (bubble sort)
Ý tư ng: L n lư t duy t qua danh sách thí sinh, n u hai thí sinh không ñúng
th t , ñ i ch hai thí sinh. L p l i quá trình trên cho ñ n khi danh sách
ñư c s p x p
Step 0 Step 1 Step 3
1. (Tu n, 22) 1. (Thăng, 29) 1. (Thăng, 29)
2. (Thăng , 29) 2. (Tu n, 22) 2. (Vinh, 26)
3. (Vinh, 26) 3. (Vinh, 26) 3. (Tu n, 22)
4. (Ánh , 27) 4. (Ánh, 27) 4. (Ánh, 27)
Step 4 Step 5
1. (Thăng, 29) 1. (Thăng, 29)
2. (Vinh, 26) 2. (Ánh, 27)
3. (Ánh, 27) 3. (Vinh, 26)
4. (Tu n, 22) 4. (Tu n, 22)
- S p x p n i b t (bubble sort)
Function bubbleSort (A : danh sách thí sinh) {
swapped := false;
do
swapped := false;
for each i = 1 to N – 1 do
if A[i].diem < A[i + 1]. diem then {
swap (A[i], A[i+1]);
swapped := true;
}
done;
while (swapped = true)
}
- Ví d 1’: S p x p danh sách website (google search)
Google có danh sách N website. Website x có m t ñ ưu tiên là
f(x). Hãy s p x p các website trên theo ñ ưu tiên gi m d n
Câu h i: Có th dùng bubble sort không?
Tr l i: ðư c, nhưng không hi u qu
- Ví d 2: Danh b ñi n tho i
Vi t m t chương trình qu n lý danh b ñi n tho i c a toàn b thành ph Hà
N i, sao cho các thao tác sau ñư c hi u qu nh t:
1. Ki m tra m t s ñi n tho i
2. Thêm m t s ñi n tho i
3. Xóa m t s ñi n tho i
- Ví d 3: Tìm ñư ng ñi t t nh t
• Xây d ng h th ng ph n m m ch ñư ng ñi t t nh t cho ngư i dùng
1. ðư ng ñi ng n nh t
2. ðư ng ñi qua ít ñèn xanh – ñèn ñ nh t
3. ðư ng ñi ít t c nh t
- Ví d 3: Tìm ñư ng ñi t t nh t (google map)
- Ví d 3: Tìm ñư ng ñi t t nh t (google map)
- Ví d 4: Xây d ng h th ng t ñi n
Vi t chương trình t ñi n Anh – Vi t, cho phép th c hi n các thao tác sau:
1. Tìm m t t
2. Thêm m t t
3. Xóa m t t
4. S a m t t
5. Tìm t ñ ng nghĩa
- Ví d 5: Ngư i bán hàng
traveling salesman problem (TSP)
M t ngư i bán hàng c n ñ n thăm N khách hàng N ñ a ñi m khác nhau. Tìm
m t hành trình cho ngư i bán hàng trên sao cho:
1. M i ñ a ñi m thăm ñúng 1 l n, sau ñó quay v ñi m xu t phát
2. T ng chi phí ñi l i là ít nh t
- Ngư i bán hàng
Thu t toán: Thăm ñ a ñi m g n nh t (nearest neighbor tour)
T ñi m xu t phát, l n lư t ñi thăm các ñi m theo quy t c: “ð n thăm ñi m
chưa ñư c thăm g n v i ñi m hi n t i nh t”
- Ngư i bán hàng
Nearest neighbor tour: 1 → 2 → 3 → X → 7 → 8 → 6 → 5 → 4 → 9 → 1
ðương ñi t i ưu: 1→2 →3→4 →5 →6 →8→7→X→9→1
- Các ví d khác (10’)
- Th nào là m t chương trình t t?
1. ðúng ñ n
2. Hi u qu
3. D hi u
4. D tìm l i
5. D thay ñ i và nâng c p
“Thu t toán + C u trúc d li u = Chương trình”
N. Wirth
- D li u
• D li u là nh ng thông tin mà máy tính có th x lý: s nguyên, s th c,
xâu kí t , và các d li u ph c t p ñư c t o t nhi u thành ph n
• Trong b nh máy tính, d li u ñư c bi u di n dư i d ng nh phân (dãy các
kí t 0, 1)
• Trong các ngôn ng l p trình b c cao (C++, Java..), d li u ñư c bi u di n
dư i d ng tr u tư ng, xu t phát t bi u di n toán h c và d hi u cho con
ngư i:
– int age
– double weight
- Ki u d li u cơ b n
Ki u d li u ñư c xác ñ nh b i:
1. Ph m vi giá tr
2. Các phép toán
Ví d trong C++
ki u ph m vi phép toán thư ng dùng
bool true / false and, or, not
char -127 -> 127 ‘’, ‘=’
int -32,767 -> 32,767 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’
float ~1E-37 -> ~1E+37 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’
double ~1.7E-308 -> ~1.7E+308 ‘’, ‘=’, ‘+’, ‘-’, ‘*’, ‘/’
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
