Tài liệu ôn tập môn Cấu trúc dữ liệu - Giải thuật | Học viện Công Nghệ Bưu Chính Viễn Thông

lOMoAR cPSD| 58457166
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1. Tham chiếu/ tham trị:
- Khi muốn thay đổi giá trị của đối số sau khi kết thúc 1 hàm, ta sẽ truyền tham chiếu: &a ( a là biến
trong hàm ) => thì giá trị sẽ được thay đổi sau khi kết thúc hàm
2. Func 琀椀 on Overloading (Nạp chồng hàm):
- Tạo nhiều hàm cùng tên nhưng khác giá trị đầu ra, đầu vào 3. Mảng 1 chiều:
- Sử dụng FOR EACH để nhập, gán giá trị …. Cho các phần tử của mảng:
+ Nếu muốn nhập phần tử cho mảng thì phải thêm & để truyền tham chiếu thay đổi giá trị các
phần tử trong mảng, chỉ sử dụng đối với mảng được khai báo chính xác sô lượng phần tử trong mảng Int a[n]; For( int &x : a ){ Cin >> x; }
4.(DẠNG BÀI TẬP) Mảng cộng dồn trên mảng 1 chiều và 2 chiều: - Mảng 1 chiều:
(Tạo mảng có kích thước n+1 để gán giá trị mảng từ vị trí thứ 1 đến n)
+ Nhập các giá trị mảng như thông thường
+ Tạo một mảng pre 昀椀 x: pre[i] = pre[i-1] + a[i]
+ Nhập số lượng truy vấn và lần lượt các giá trị l và r để 琀 nh + kq = pre[r] – pre[l-1] 5. STRING
- Độ dài của xâu: s.size();
- Chỉ số kí tự trong xâu được đánh từ 0, 1, 2,…….
- Nối hai hay nhiều xâu bằng: s1 + s2 (xâu 2 được nối ngay sau xâu 1)
- So sánh 2 xâu theo thứ tự từ điển:
+ Sử dụng toán tử so sánh: >, <, ==
+ Sử dụng hàm compare: res = a.compare(b) lOMoAR cPSD| 58457166
• Nếu a > b thì res = 1
• Nếu a < b thì res = - 1 • Nếu a == b thì res = 0
- Cắt xâu a tại kí tự thứ i với n kí tự : b = a.substr(i, n) a = “abcdef” b = a.substr( 3, 3 ) => b = “def”
- Chuyển xâu s thành số: stoi(s), stoll(s)
- Chuyển số n thành xâu: to_string(n)
- Tách từ trong xâu s: stringstream ss(s)
+ Sử dụng biến string tmp để lưu từ vừa tách String tmp; While( ss >> tmp ){} 6.VECTOR:
- Cú pháp: vector tên vector;
- Khai báo vector v có n phần tử: vector v(n);
+ Nếu muốn tạo vector v có n phần tử, mỗi phần tử có giá trị x: vector v(n,x);
- Khai báo có n vector: vector v[n];
- Đẩy giá trị x vào trong vector v: v.push_back(x);
- Kích thước vector: v.size();
- Các phần tử trong vector được đánh chỉ số từ 0, 1, 2,….. (v[0],….)
- Phần tử cuối cùng trong vector: v.size() – 1 hoặc v.back() 7. PAIR:
- Cú pháp: pair< datatype1, datatype2 > p;
- Truy cập phần tử trong pair: p.昀椀 rst hoặc p.second
- Gán giá trị cho các phần tử trong pair: pair< int, int > p = {100, 200};
8. SET: Lưu các phần tử riêng biệt không trùng nhau - Cú pháp: set tên set;
- Các phần tử trong set sẽ được tự động sắp xếp từ nhỏ đến lớn
- Thêm phần tử vào trong set: s.insert(value);
- Kích thước của set: s.size(); lOMoAR cPSD| 58457166
- Tìm kiếm phần tử n trong set s: res = s.count(n):
+ Nếu res != 0 thì phần tử n có trong set
+ Nếu res == 0 thì phần tử không có trong set
- Xóa phần tử n trong set s: s.erase(n)
9.(DẠNG BT) Max/min sliding window:
- Nhập n phần tử, k kích thước của sổ và phần tử của mảng.
- Duyệt vòng for từ 0, …, n-k
- Mỗi lần duyệt sẽ tạo một set rồi thêm k phần tử bắt đầu từ vị trí i trong mảng
For( int i = 0; i <= n – k; i ++ ){ Set s;
For( int j = i; j < i+k; j++ ) s.insert(a[j]);
Cout << min( *s.begin() ) or max ( *s.rbegin() ) của set }
10. MAP: Lưu các cặp key, value hay chính là lưu các pair - Cú pháp map mp;
- Map sẽ tự sắp xếp các key theo thứ tự tăng dần
- Các key không được trùng nhau
- Thêm giá trị vào trong map:
+ mp[100] = 200 ( 100 là key, 200 là value )
+ mp.insert( {100, 200} ) ( 100 là key, 200 là value )
- Số lượng phần tử trong map: mp.size();
- Duyệt các phần tử trong map: for( pair x : mp ) { x.昀椀 rst… x.second….. }
- Tìm kiếm key trong map: Res = mp.count(key)
+ res = 0 thì key không có trong map lOMoAR cPSD| 58457166
+ res != 0 thì có key trong map
- Xóa cặp key – value trong map thông qua key: mp.erase(key)
11. Sử dụng typedef và de 昀椀 ne
- TYPEDEF: Định nghĩa các kiểu dữ liệu đã có sẵn Typedef long long ll; Typedef int i;
- DEFINE: Định nghĩa kiểu dữ liệu có sẵn và các giá trị đặc biệt #de 昀椀 ne ll long long #de 昀椀 ne sn int #de 昀椀 ne PI 3.14
#de 昀椀 ne for(i,a,b) for( int i = (a); i < (b); i ++ )
12. Thuật toán 琀 m kiếm nhị phân ( Các phần tử trong mảng phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần ) C1: Tạo hàm
* Với mảng được xếp tăng dần
- Gán giá trị l (le 昀琀) = 0 và r (right) = n – 1
- Tạo vòng lặp while( l < r ) - Tạo biến m = ( l + r ) / 2;
- Nếu a[m] > x => r = m – 1
- Nếu a[m] < x => l = m + 1
- Nếu a[m] == x thì return 琀 m thấy
- Nếu kết thúc vòng lặp mà chưa return thì trả lại kết quả không 琀 m thấy
* Với mảng sắp xếp giảm dần thì ngược lại
C2: Sử dụng hàm có sẵn binary_search( a, a+n, x ) Tìm kiếm x trong đoạn từ a[0] đến a[n-1] đã được sắp xếp tăng dần.
* Sử dụng hàm có sẵn chỉ trả lại kết quả 1 or 0, không trả lại vị trí 琀 m thấy phần tử trong mảng Với:
a: phần tử bắt đầu a+n: phần tử
sau phần tử cuối cùng x: phần tử cần 琀 m lOMoAR cPSD| 58457166
13. Lower_bound và Upper_bound
*Sử dụng cho mảng đã được sắp xếp, giá trị trả về của hai hàm này sẽ là CON TRỎ VD: 1 2 2 2 3 4 5
- Lower_bound( iter1, iter2, key ): Tìm về vị trí của phần tử đầu 琀椀 ên >= key
Auto it = lower_bound( a, a+n, 2 )
Khi đó it sẽ có giá trị là con trỏ vị trí có màu vàng
- upper_bound( iter1, iter2, key ): Tìm về vị trí của phần tử đầu 琀椀 ên > key
Auto it = upper_bound( a, a+n, 2 )
Khi đó it sẽ có giá trị là con trỏ vị trí có màu xanh
+ Nếu muốn trả về vị trí trong mảng: it – a
+ Nếu trả lại giá trị của vị trí mà con trỏ it đang trỏ đến: *it 14. Sắp xếp:
- Sắp xếp tăng dần: sort( a, a+n )
- Sắp xếp giảm dần: sort( a, a+n, greater() )
15. Thuật toán sắp xếp chọn: - Độ phức tạp: 0(n^2)
- Tạo một vòng for với i = 0 đến n – 2
- Tạo biến min_idx là vị trí thứ i là nhỏ/lớn nhất
- Tạo một vòng for với j = i + 1 đến n – 1
- Nếu phần tử thứ j lớn hơn/ nhỏ hơn phần tử min_idx thì min_idx = a[j]
- Kết thúc vòng lặp của j, ta sẽ swap a[i] với a[min_idx]
16. Sắp xếp nổi bọt: - Độ phức tạp: O(n^2)
- Tạo vòng for của i từ 0 => n-1
- Tạo vòng for của j từ 0 => n-1-i
- Nếu phần tử a[j] lớn/nhỏ hơn a[j+1] thì swap 17. Sắp xếp chèn:
- Tạo vòng for i từ 1 => n – 1 lOMoAR cPSD| 58457166
- Gán gt = a[i] (Giá trị đang xét) và pos = i – 1 (vị trí có khả năng chèn)
- Tạo vòng lặp while với pos >= 0 (giá trị nằm trong mảng) và gt < a[pos] (giá trị đang xét nhỏ hơn phần tử đứng trước nó)
- Gán a[pos+1] = a[pos] (Dịch phần tử sang phải) và pos -- ( Giảm giá trị pos để 琀 m xem còn vị trí thỏa mãn hơn không )
- Khi kết thúc vòng lặp => 琀 m được vị trí để chèn gt vào tức a[pos+1] = gt;
18. Thuật toán sắp xếp trộn ( Merge Sort ):
void merge( int a[], int l, int m, int r ){
vector x( a + l, a + m + 1 ); // tạo vector x copy phần tử từ vị trí l đến m của mảng a
vector y( a + m + 1, a + r + 1 ); // tạo vector y copy phần tử từ vị trí m+1 đến r của mảng a
int i = 0, j = 0; // i là index của vector x và j là index của vector y while( i < x.size() && j < y.size() ){
// thằng nào nhỏ hơn thì được gán vào a[l] rồi tăng l++ và index của vector đó lên 1 if( x[i] < y[j] ){ a[l] = x[i]; l++; i++; } else{ a[l] = y[j]; l++; j++; } }
// vì kích thước của vector x và y khác nhau nên sau khi kết thúc vòng lặp có thể còn xót lại một
vector chưa được xếp vào mảng nên dùng vòng lặp while để xếp nốt while( i < x.size() ){ a[l] = x[i]; l++; i++; } while( j < y. size() ){ a[l] = y[j]; l++; j++; } lOMoAR cPSD| 58457166 }
void merge_sort( int a[], int l, int r ){ // Sử dụng phương pháp chia để trị, đến khi nào mảng a còn 1 phần
tử thì dừng việc chia rồi sau đó 琀椀 ến hành trộn
if( l >= r ) return; int m = ( r + l ) / 2; merge_sort( a, l, m ); merge_sort( a, m + 1, r ); merge( a, l, m, r ); }
19. Sắp xếp vun đồng (Heap Sort):
void heapify( int a[], int n, int i ){
int l = 2 * i + 1; // lá bên trái của nút gốc i int r = 2 * i + 2;
// lá bên phải nút gốc i int lar = i; // Gán vị trí của phần
tử có giá trị lớn nhất tại i
if( l < n && a[l] > a[lar] ) lar = l; // nếu l nằm trong khoảng của n và lá trái lớn hơn gốc thì cập
nhật vị trí lớn nhất là l
if( r < n && a[r] > a[lar] ) lar = r; // nếu r nằm trong khoảng của n và lá phải lớn hơn gốc thì cập
nhật vị trí lớn nhất là r
// sau khi 琀 m được vị trí lớn nhất trong 3 thằng, t quay lại kiểm tra nếu thằng lớn nhất không
nằm ở gốc thì swap và 琀椀 ếp tục heapify vị trí của thằng lớn nhất vừa 琀 m được if( lar != i ){ swap( a[i], a[lar] ); heapify( a, n, lar ); } } void heapSort( int a[], int n ){
// Bước đầu để 琀 m ra được thằng lớn nhất và đưa nó về nút gốc 0
for( int i = n / 2 - 1; i >= 0; i -- ){ heapify( a, n, i ); } lOMoAR cPSD| 58457166
// Sau khi 琀 m được t hoán vị thằng đầu cho thằng cuối cùng và bỏ lá cuối để không xét đến
nữa là sẽ heapify các thằng còn lại bắt đầu từ nút gốc 0 với i phần tử
for( int i = n - 1; i >= 0; i -- ){ swap( a[i], a[0] ); heapify( a, i, 0 ); } }
20. Sắp xếp nhanh (Quick Sort): - Phân hoạch Lomuto:
// Chọn chốt là phần tử cuối cùng.
// Phân hoạch bài toán để 琀 m vị trí phù hợp cho chốt
int par 琀椀琀椀 on( int a[], int l, int r ){ int pivot = a[r]; // Chọn phần tử chốt là phần tử
cuối cùng của đoạn int i = l - 1; // i là vị trí để hoán vị các phần tử nhỏ hơn pivot
sang bên trái của đoạn for( int j = l; j < r; j ++ ){ // Dùng vòng for từ l đến r – 1 tức không xét phần tử pivot
if( a[j] < pivot ){ // nếu phần tử a[j] < pivot thì ta tăng giá trị i và swap i++; swap( a[i], a[j] ); } }
// Sau khi kết thúc vòng lặp trên ta đã có các phần tử nhỏ hơn pivot nằm một phía và lớn hơn
nằm một phía. Ta chỉ cần tăng i lên để hoán vị thằng đầu 琀椀 ên lớn hơn pivot với vị trí cuối cùng thì ta
đã phân hoạch được mảng a thành hai đoạn rồi return lại vị trí i i++; swap( a[i], a[r] ); return i;
} void quickSort( int a[], int l, int r ){
if( l >= r ) return; // Hàm sẽ dừng lại khi l > r hay mảng chỉ còn 1 phần tử l ==
r int p = par 琀椀琀椀 on( a, l, r ); // vị trí phân hoạch quickSort( a, l, p - 1 ); lOMoAR cPSD| 58457166
// thực hiện phân hoạch đoạn bên trái của p quickSort( a, p + 1, r ); } // thực
hiện phân hoạch đoạn bên phải của p - Phân hoạch Hoare:
int par 琀椀琀椀 on( int a[], int l, int r ){
int pivot = a[l]; // xét vị trí chốt là phần tử nằm ngoài cùng bên trái của mảng
int i = l, j = r; // Tạo hai biến chạy để xét phần tử lớn/nhỏ hơn pivot while( 1 ){
while( a[i] < pivot ){ // nếu phần tử nằm bên trái nhỏ hơn pivot tức đã nằm đúng vị trí
thì tăng i lên để kiểm tra phần tử 琀椀 ếp theo i++; }
while( a[j] > pivot ){ // nếu phần tử nằm bên phải lớn hơn pivot tức đã nằm đúng vị trí
thì giảm j đi để kiểm tra phần tử 琀椀 ếp theo j--; }
if( i < j ){ // nếu kết thúc hai vòng lặp trên mà 琀 m được một cặp nghịch thế tức phần tử
bên trái thì lớn hơn pivot còn phần tử bên phải nhỏ hơn pivot thì chúng đang nằm sai vị trí thì 琀椀 ến
hành swap hai phần tử và tăng i, giảm j để 琀 m phần tử 琀椀 ếp theo swap( a[i], a[j] ); i++; j--; }
else return j; // Nếu i > j tức các phần tử đã nằm đúng vị trí thì trả lại giá trị j là vị trí
phần tử cuối cùng 琀 nh từ bên trái sang phải có giá trị nhỏ hơn pivot } } void quickSort( int a[], int l, int r ){
if( l >= r ) return; int p = par 琀椀琀椀 on( a, l, r ); // phần hoạch
thành công đoạn trên quickSort( a, l, p ); // 琀椀 ến hành phân hoạch đoạn lOMoAR cPSD| 58457166
có giá trị < pivot quickSort( a, p + 1, r ); 琀椀 ến hành phần hoạch đoạn có giá trị >= pivot }
21. Các hàm trong C++ 21.1 Min/Max: Min({1, 2,3,4,5}); Max(10,20);
21.2 Min/max_element: Tìm giá trị min/ max trong mảng, vector:
- Kết quả trả về sẽ là 1 con trỏ đến vị trí min max
- 琀 m phần tử min trong mảng a có n phần tử: *min_element( a, a + n );
- 琀 m phần tử min trong vector v: *min_element( v.begin(), b.end() );
21.3 Tính tổng các phần tử trong mảng/vector bằng accumulate:
- Tổng các phần tử trong mảng a có n phần tử với giá trị khởi tạo bằng 0: res = accumulate( a, a+n, 0 );
- Tổng các phần tử trong vector v với giá trị khởi tạo bằng 0: res = accumulate( v.begin(), v.end(), 0 );
21.4 Find: Tìm kiếm phần tử n trong mảng/vector
- Kết quả trả về là con trỏ trỏ tới vị trí
- Tìm n trong mảng a có 5 phần tử: auto it = 昀椀 nd( a, a+5, n )
+ Nếu 琀 m thấy thì it sẽ trỏ đến vị trí của n trong mảng
+ Nếu không thấy thì con trỏ it sẽ trỏ đến vị trí a+5
* Nếu muốn trả lại vị trí trong mảng/vector: it – v.begin() hoặc it – a
21.5 Merge: Trộn hai mảng/vector
- Chỉ áp dụng cho mảng tăng dần
- Trộn mảng a có n phần tử với mảng b có m phần tử vào mảng res: merge( a, a+n, b, b+m, res )
- Trộn vector a với vector b vào vector res:
Merge( a.begin(), a.end(), b.begin(), b.end(), res.begin() )
*Cần khai báo mảng/vector res có kích thước vừa đủ để trộn 2 mảng/vector
21.6 Reverse: Đảo mảng/vector lOMoAR cPSD| 58457166
Đảo mảng có n phần tử: reverse( a, a +n );
Đảo vector v : reverse( v.begin(), v.end() );
22. Sàng số nguyên tố:
- Tạo một mảng có n + 1 phần tử ( Giới hạn < 10^7 )
- Gán tất cả các phần tử của mảng bằng 1
- Vì 0 và 1 không phải số nguyên tố nên cho phần tử 0 và 1 bằng 0
- Duyệt vòng for i từ 2 => sqrt(n)
- Nếu là số nguyên tố ( tức phần tử của mảng tại i bằng 1 ) thì tạo vòng for j từ i*i đến n với bước nhảy
làj += i và tất cả phần tử tại a[j] đó sẽ gán cho giá trị bằng 0
23. Phân 琀 ch thừa số nguyên tố:
- Duyệt vòng for i từ 2 đến sqrt(n) để 琀 nh thừa số nguyên tố của n
24. Đếm ước của 1 số: - Tạo biến đếm cnt = 0
- Duyệt vòng for i từ 1 => sqrt(n) - Nếu n % i == 0 với
+ Nếu i*i != n thì cnt += 2
+ Nếu i*i == n thì cnt += 1
25. Kiểm tra hai số nguyên tố cùng nhaulong long gcd( long long a, long long b ){ if( b == 0 ) return a; return gcd( b, a % b ); }
26. Ước chung lớn nhất, bội chung nhỏ nhất: - Ước chung lớn nhất: ll gcd( ll a, ll b ){ if( b == 0 ) return a; return gcd( b, a % b ); }- Bội chung nhỏ nhất: Res = a * b / gcd( a, b ) lOMoAR cPSD| 58457166 27. Modular
- ( a + b ) mod m = ( a mod m + b mod m ) mod m
- ( a – b ) mod m = ( a mod m – b mod m ) mod m
- ( a * b ) mod m = ( ( a mod m ) * ( b mod m ) ) mod m
- a^b mod m = ( a mod m ) ^ b mod m 28. Đệ quy
- Tìm ra kết quả của bài toán nhỏ nhất để làm điểm dừng
- Công thức truy hồi của bài toán 29. Thuật toán sinh
- Cấu hình đầu 琀椀 ên - Cấu hình cuối cùng - Phương pháp sinh - Các bước:
+ Khởi tạo cấu hình đầu 琀椀 ên
+ While ( Khi chưa phải cấu hình cuối cùng ) {
+ In ra cấu hình hiện tại
+ Sinh ra cấu hình kế 琀椀 ếp }