Bài giảng Cấu trúc dữ liệu và thư viện - Các kiểu dữ liệu cơ bản - Đỗ Phan Thuận
Cấu trúc dữ liệu và Thư viện
THUẬT TOÁN ỨNG DỤNG
Đỗ Phan Thuận
Bộ môn Khoa Học Máy Tính, Viện CNTT & TT,
Trường Đại Học Bách Khoa Hà Nội.
Ngày 15 tháng 10 năm 2019
1 / 42
1
2
3
Các kiểu dữ liệu cơ bản
Số nguyên lớn
Thư viện CTDL và Thuật toán
Dequeue
Sắp xếp và tìm kiếm
4
5
6
7
Biểu diễn tập hợp bằng Bitmask
Một số ứng dụng của CTDL
Cấu trúc dữ liệu mở
Biểu diễn đồ thị
2 / 42
1
2
3
Các kiểu dữ liệu cơ bản
Số nguyên lớn
Thư viện CTDL và Thuật toán
Dequeue
Sắp xếp và tìm kiếm
4
5
6
7
Biểu diễn tập hợp bằng Bitmask
Một số ứng dụng của CTDL
Cấu trúc dữ liệu mở
Biểu diễn đồ thị
3 / 42
Các kiểu dữ liệu cơ bản
Các kiểu dữ liệu phải biết:
I
bool: biến bun (boolean) (true/false)
I
char: biến nguyên 8-bit (thường được sử dụng để biểu diễn các ký tự
ASCII)
I
I
I
short: biến nguyên 16-bit
int: biến nguyên 32-bit
long long: biến nguyên 64-bit
I
I
I
float: biến thực 32-bit
double: biến thực 64-bit
long double: biến thực 128-bit
I
string: biến xâu ký tự
3 / 42
Các kiểu dữ liệu cơ bản
Loại
Số Byte
Giá trị nhỏ nhất
Giá trị lớn nhất
bool
1
1
2
4
8
n
char
-128
127
short
-32768
32767
int/long
long long
-2148364748
-9223372036854775808
−28n−1
2147483647
9223372036854775807
28n−1 − 1
Loại
Số Byte
Giá trị nhỏ nhất Giá trị lớn nhất
unsigned char
unsigned short
unsigned int
1
0
0
0
0
0
255
2
4
8
n
65535
4294967295
18446744073709551615
28n − 1
unsigned long long
Loại
Số Byte
Giá trị nhỏ nhất
≈ −3.4 × 10−38
≈ −1.7 × 10−308
Giá trị lớn nhất
float
4
8
≈ 3.4 × 10−38
≈ 7 chữ số
double
≈ 1.7 × 10−308
≈ 14 chữ số
4 / 42
1
2
3
Các kiểu dữ liệu cơ bản
Số nguyên lớn
Thư viện CTDL và Thuật toán
Dequeue
Sắp xếp và tìm kiếm
4
5
6
7
Biểu diễn tập hợp bằng Bitmask
Một số ứng dụng của CTDL
Cấu trúc dữ liệu mở
Biểu diễn đồ thị
5 / 42
Số nguyên lớn
Làm thế nào để tính toán với số nguyên cực lớn, nghĩa là không thể
lưu trữ bằng kiểu long long
Ý tưởng đơn giản: Lưu số nguyên dưới dạng string
Tuy nhiên làm thế nào để tính toán số học giữa hai số nguyên?
Có thể dùng thuật toán giống như phương pháp tính bậc tiểu học:
tính từng chữ số, từng phần, có lưu phần nhớ
6 / 42
1
2
3
Các kiểu dữ liệu cơ bản
Số nguyên lớn
Thư viện CTDL và Thuật toán
Dequeue
Sắp xếp và tìm kiếm
4
5
6
7
Biểu diễn tập hợp bằng Bitmask
Một số ứng dụng của CTDL
Cấu trúc dữ liệu mở
Biểu diễn đồ thị
8 / 42
Tầm quan trọng của cấu trúc dữ liệu
Nhiều khi dữ liệu cần được biểu diễn theo cách thuận lợi cho
I
I
I
I
Truy vấn hiệu quả
Chèn hiệu quả
Xóa hiệu quả
Cập nhật hiệu quả
Nhiều khi dữ liệu cần được biểu diễn theo cách tốt hơn nữa
I
Làm thế nào để biểu diễn số nguyên lớn?
Làm thế nào để biểu diễn đồ thị?
I
Các cấu trúc dữ liệu giúp chúng ta thực hiện được những điều này
9 / 42
Các cấu trúc dữ liệu thông dụng
Mảng tĩnh
Mảng động
Danh sách liên kết
Ngăn xếp
Hàng đợi
Hàng đợi ưu tiên
Hàng đợi hai đầu
Tập hợp
Ánh xạ
10 / 42
Các cấu trúc dữ liệu thông dụng
Mảng tĩnh - int arr[10]
Mảng động - vector<int>
Danh sách liên kết - list<int>
Ngăn xếp - stack<int>
Hàng đợi - queue<int>
Hàng đợi ưu tiên - priority_queue<int>
Hàng đợi hai đầu - deque<int>
Tập hợp - set<int>
Ánh xạ - map<int, int>, sử dụng cây cân bằng đỏ đen
10 / 42
Các cấu trúc dữ liệu thông dụng
Mảng tĩnh - int arr[10]
Mảng động - vector<int>
Danh sách liên kết - list<int>
Ngăn xếp - stack<int>
Hàng đợi - queue<int>
Hàng đợi ưu tiên - priority_queue<int>
Hàng đợi hai đầu - deque<int>
Tập hợp - set<int>
Ánh xạ - map<int, int>, sử dụng cây cân bằng đỏ đen
Thông thường nên sử dụng thư viện chuẩn
I
I
Gần như chắc chắn chạy nhanh và không lỗi
Giảm bớt việc viết code
Nhiều khi vẫn cần tự viết code thay vì dùng thư viện chuẩn
I
Khi muốn kiểm soát linh hoạt
I
Khi muốn tùy biến/hiệu chỉnh cấu trúc dữ liệu
10 / 42
Deque - Hàng đợi hai đầu
Deque=Double-Ended Queue: là CTDL có tính chất của cả Stack và
Queue, nghĩa là cho phép thêm và xóa ở cả hai đầu
#include <deque >
deque <string > myDeque;
hỗ trợ tất cả các phương thức của kiểu vector và list bao gồm cả chỉ
số và con trỏ (iterator)
I
I
I
I
I
I
I
size() trả về kích thước của deque
front() trả về phần tử đầu tiên của deque
back() trả về phần tử cuối cùng của deque
push_front() thêm phần tử mới vào đầu của deque
push_end() thêm phần tử mới vào cuối của deque
pop_front() xóa phần tử đầu của deque
pop_end() xóa phần tử cuối của deque
11 / 42
Deque - Kiểm tra chuỗi Palindrome
12 / 42
Tùy biến kiểu priority_queue<int>
Trong nhiều trường hợp không thể dùng trực tiếp kiểu priority_queue mà
cần tùy biến lại để cài đặt thuật toán. Ví dụ:
class Plane{ // tuy bien priority queue min
public: int fuel
public: Plane(int vQ ){(* this ). fuel=fuel ;}
friend ostream& operator <<( ostream& os , const Plane& p){
os <<p.fuel <<endl;return os;
}
bool operator >( const LabVer& p) const{
return fuel >p. fuel;
}
};
typedef priority_queue <Plane ,vector <Plane >,greater <Plane >
PQPlane PQ;
>
PQPlane;
int main (){
vector <Plane > vP;
vP. push_back(Plane (4)); vP. push_back(Plane (7));
vP. push_back(Plane (3)); vP. push_back(Plane (9));
PQPlane PQ(vP. begin (),vP.end ());
while (!PQ. empty ()){ cout <<PQ.top (); PQ.pop ();}
return 0;
}
13 / 42
Sắp xếp và Tìm kiếm
Các toán tử thông dụng nhất:
I
I
I
Sắp xếp một mảng - sort(arr.begin(), arr.end())
Tìm kiếm trên một mảng chưa sắp xếp - find(arr.begin(), arr.end(), x)
Tìm kiếm trên một mảng đã sắp xếp - lower_bound(arr.begin(),
arr.end(), x)
Thông thường nên sử dụng thư viện chuẩn
Có lúc cần phiên bản khác của tìm kiếm nhị phân nhưng bình thường
lower_bound là đủ
hơn 90% sinh viên tự lập trình sai tìm kiếm nhị phân
14 / 42
1
2
3
Các kiểu dữ liệu cơ bản
Số nguyên lớn
Thư viện CTDL và Thuật toán
Dequeue
Sắp xếp và tìm kiếm
4
5
6
7
Biểu diễn tập hợp bằng Bitmask
Một số ứng dụng của CTDL
Cấu trúc dữ liệu mở
Biểu diễn đồ thị
15 / 42
Biểu diễn tập hợp
Cho một số lượng nhỏ (n ≤ 30) phần tử
Gán nhãn bởi các số nguyên 0, 1, . . . , n − 1
Biểu diễn tập hợp các phần tử này bởi một biến nguyên 32-bit
Phần thử thứ i trong tập được biểu diễn bởi số nguyên x nếu bit thứ
i của x là 1
Ví dụ:
I
Cho tập hợp {0, 3, 4}
int x = (1<<0) | (1<<3) | (1<<4);
I
16 / 42
Biểu diễn tập hợp
Tập rỗng:
0
Tập có một phần tử:
1<<i
Tập vũ trụ (nghĩa là tất cả các phần tử):
(1<<n)-1
Hợp hai tập:
x|y
Giao hai tập:
x&y
Phần bù một tập:
~x & ((1<<n)-1)
17 / 42
Tải về để xem bản đầy đủ
45 trang
26/04/2022
6600
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thư viện - Các kiểu dữ liệu cơ bản - Đỗ Phan Thuận", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thu_vien_cac_kieu_du_lieu_co_b.pdf
