Tài liệu ôn tập giữa kỳ: Ngăn xếp, Hàng đợi và Thuật toán | Môn Cấu trúc dữ liệu và thuật toán - Trường Đại học Khoa học, Đại học Huế

lOMoAR cPSD| 58702377 I. Ngăn xếp ( Stack ) Vào trước ra sau
Chuyển đổi số nhị phân dùng ngăn xếp
Kiểm tra dấu ngoặc hợp lệ lOMoAR cPSD| 58702377
Phần tử đầu tiên lớn hơn bên phải
Diện tích hình chữ nhật lớn nhất trên biểu đồ II. Hàng đợi ( Queue ) Vào trước ra trước ( Hàng đợi 2 đầu ) lOMoAR cPSD| 58702377
Số lớn nhất của mọi cửa sổ kích thước k III.
Danh sách liên kết #include using namespace std; struct Hocphan{ string mshp; string nameHP; int soTin; float TSQT, TSCK; }; struct HP{ Hocphan a; HP *next; }; struct diemHocphan{ float MSHK; float diemQT, diemCK; string mshp; }; struct diemHP{ diemHocphan h; diemHP *next; }; struct Student{ long mssv; string nameSV; float gpa; diemHP* k; }; struct SV{ Student s; lOMoAR cPSD| 58702377
SV *next; }; typedef struct diemHP* dhp; typedef
struct HP* hp; typedef struct SV* sv; // khoi tao sinh vien
sv makesv(){ Student s; cout << "Nhap thong tin sinh
vien:\n"; cout << "Nhap ma so:"; cin >> s.mssv; cout <<
"Nhap ten sinh vien:"; cin.ignore(); getline(cin, s.nameSV);
cout << "Nhap gpa:"; cin >> s.gpa; int n; cout << "So hoc
phan da hoc:"; cin >> n; dhp head1 = new diemHP(); head1->next = NULL;
for(int i = 0; i < n; i++){ dhp moi = head1; moi->next = head1;
head1 = moi; cout << "Nhap diem hoc phan: \n"; cout << "Hoc
ky:"; cin >> s.k->h.MSHK; cout << "Ma so hoc phan:" ;
cin.ignore(); getline(cin, s.k->h.mshp); cout << "Diem qua
trinh:"; cin >> s.k->h.diemQT ; cout << "Diem cuoi ky:"; cin >>
s.k->h.diemCK; head1->h = s.k->h; } sv tmp = new SV(); tmp->s = s; tmp->next = NULL; }
// kiem tra danh sach rong bool empty(sv a){ return a == NULL; }
// bo sung sinh vien x vao dau danh sach void
insertfirst(sv &a){ sv tmp = makesv(); if(a == NULL){ a =
tmp; } else{ tmp->next = a; a = tmp; } } lOMoAR cPSD| 58702377
// khoi tao hoc phan hp
makehp(){ Hocphan a; cout <<
"Nhap thong tin hoc phan: \n";
cout << "So tin chi hoc phan: ";
cin >> a.soTin; cout << "Ten hoc phan: "; cin.ignore(); getline(cin, a.nameHP); cout << "Ma so hoc phan: "; cin.ignore(); getline(cin,
a.mshp); cout << "Trong so qua
trinh: "; cin >> a.TSQT; cout <<
"Trong so cuoi ki: "; cin >> a.TSCK; hp tmp = new HP();
tmp->a = a; tmp->next = NULL; }
// bo sung hoc phan moi vao dau danh sach void
inserthp(hp &a){ hp tmp = makehp(); if(a == NULL){ a = tmp;
} else{ tmp->next = a; a = tmp; } } // dem so hoc phan int Sizehp(hp a){ int dem = 0; while(a != NULL){ ++dem; a = a->next; } return dem; } lOMoAR cPSD| 58702377
// bo sung hoc phan moi vao sau mon hoc co ma so cho truoc void inserthpmoi(hp
&a, string x){ hp p = a; Hocphan as = p->a; int n = Sizehp(a); for(int i = 0 ; i < n ; i++){
if(as.mshp != x){ p = p->next; } else{ break; } } hp tmp = makehp(); tmp->next = p- >next; p->next = tmp; }
// xoa mon hoc co ma mon cho truoc void
deletehp(hp h, string ms){ int n = Sizehp(h); hp p = h; hp q = NULL;
for(int i = 0 ; i < n ; i++){ if(p- >a.mshp != ms){ q = p; p =
p->next; } else{ q->next = p->next; } } }
// sap xep cac mon hoc theo thu tu tang dan cua so tin chi void sapxep(hp &h){
hp p = h; for(p; p->next = NULL; p = p->next){ hp min = p; for(hp q = p->next; q !=
NULL ; q = q->next){ if(q->a.soTin < min->a.soTin){ min = q; } }
int tmp = min->a.soTin; min->a = p->a; p->a.soTin = tmp; } } // dem so phan tu int Sizesv(sv a){ int dem = 0; while(a != NULL){ lOMoAR cPSD| 58702377 ++dem; a = a->next; } return dem; }
// dem so hoc phan da hoc cua 1 sinh vien int
Sizedhp(Student a){ int dem = 0; dhp tmp = a.k; while(tmp != 0){ ++dem; tmp = tmp->next; } return dem; }
// bo sung sinh vien x vao giua danh sach, truoc phan tu node duoc tro boi p void
insertmiddle1(sv &a, int pos){ int n = Sizesv(a); if(pos <= 0){ cout << "khong hop le"; return; }
else if(pos == 1){ insertfirst(a); return;
} sv q = NULL; sv p = a; for(int i = 1; i <=
pos - 1; i++){ q = p; p=p->next; } sv tmp = makesv(); tmp-
>next = q->next; q->next = tmp; }
// bo sung sinh vien x vao giua danh sach, sau phan tu node duoc tro boi p void insertmiddle2(sv &a, int pos){
int n = Sizesv(a); if(pos <= 0){ cout << "khong hop le"; return; }
else if(pos == 1){ insertfirst(a); return; lOMoAR cPSD| 58702377 }
sv p = a; for(int i = 1; i < pos - 1; i++){ p=p->next; } sv tmp = makesv(); tmp-
>next = p->next; p->next = tmp; }
// bo sung sinh vien vao sau sinh vien co ma so sinh vien cho truoc void insertsv(sv &a, long
x){ sv p = a; Student as = p->s; int n = Sizesv(a); for(int i = 0 ; i < n ; i++){ if(as.mssv != x){ p = p- >next; } else{ break; } } sv tmp = makesv(); tmp->next = p- >next; p->next = tmp; }
// xoa sinh vien duoc tro boi con tro p void deletesv(sv &a, int pos){
if( pos <= 0 || pos > Sizesv(a)) return; sv q =
NULL, p = a; for(int i = 1; i < pos ; i++){ q = p; p = p->next; } if(q = NULL){ a = a- >next; }
else { q->next = p->next; } }
// xoa sinh vien o truoc sinh vien duoc tro boi p void
deletesvtruoc(sv&a, int pos){ if( pos <= 0 || pos > Sizesv(a))
return; sv r = NULL, q = NULL, p = a; for(int i = 1; i < pos ; i++){ r = q; q = p; p = p->next; } lOMoAR cPSD| 58702377 if(r = NULL){ a = a- >next; }
else { r->next = q->next; } }
// xoa sinh vien o sau sinh vien duoc tro boi p void deletesvsau(sv&a, int pos){
if( pos <= 0 || pos > Sizesv(a)) return; sv q =
NULL, p = a; for(int i = 1; i < pos ; i++){ p = p-
>next; } q = p->next; if(p = NULL){ a = a->next; }
else { p->next = q->next; } } // in 1 mon hoc void inhp(Hocphan a){
cout << "MSHP: " << a.mshp << endl; cout << "Ten hoc phan: "
<< a.nameHP << endl; cout << "So tin hoc phan: " << a.soTin <<
endl; cout << "Trong so qua trinh: " << a.TSQT << endl; cout <<
"Trong so cuoi ki: " << a.TSCK << endl; } // in 1 sinh vien void insv(Student s, int n){
cout << "MSSV: " << s.mssv << endl; cout << "Ho Ten:
" << s.nameSV << endl; cout << "GPA: " << s.gpa << endl;
cout << "Danh sach hoc phan: \n"; for(int i = 0; i < n ; i++){ cout << "Ma so hoc
ky: " << s.k->h.MSHK << endl; cout << "Ma so hoc phan: " << s.k->h.mshp <<
endl; cout << "Diem qua trinh: " << s.k->h.diemQT << endl; cout << "Diem
cuoi ki: " << s.k->h.diemCK << endl; s.k = s.k->next; lOMoAR cPSD| 58702377 } }
// in danh sach sinh vien void
inds(sv a){ int n = Sizesv(a); int f =
Sizedhp(a->s); for(int i = 0; i < n;
i++){ insv(a->s,f); a = a->next; } cout << endl; }
// tim kiem sinh vien o truoc sinh vien duoc tro boi p va in sinh vien do ra man hinh
void findsvq(sv a, int pos){ sv q =
NULL, p = a; for(int i = 1; i < pos ; i++){ q = p; p = p->next; } Student as = q->s; int f =
Sizedhp(a->s); insv(q->s,f); }
// tim kiem sinh vien bang mssv cho truoc va in sinh vien do ra man hinh
void findsv(sv a, long x){ sv p = a; Student as = p->s; int n =
Sizesv(a); for(int i = 0 ; i < n ; i++){ if(as.mssv != x){ p = p- >next; } else{ int f = Sizedhp(p-
>s); insv(p->s,f); break; } } } lOMoAR cPSD| 58702377
// tim mon hoc co ma so mon hoc cho truoc va in ra man hinh void findhp(hp a,
string x){ hp p = a; Hocphan as = p->a; int n = Sizehp(a); for(int i = 0 ; i < n ; i++){
if(as.mshp != x){ p = p->next; } else{ inhp(p->a); break; } } IV. Đệ quy
// tong cua n so tu nhien dau day so tu nhien long long dqsumstn(int n){ if(n == 1) return 1; return dqsumstn(n - 1) + n; } lOMoAR cPSD| 58702377 long long sumstn(int n){
long long sum = 0; for(int i = 1; i
<= n; i++){ sum = sum + i; } return sum; }
// to hop chap k cua n long long dqtohop( int n, int k){
if(k == 0) return 1; return ((n- k+1)/k)*dqtohop(n,k-1); }
long long tohop( int n, int k){ if(k == 0 |
k == n) return 1; long long n1 = sumstn(n); long long k1 = sumstn(k); long long ntk= sumstn(n-k); long long th = n1/k1/ntk; return th; }
// tim uoc chung lon nhat cua 2 so nguyen a va b int dqucln(int a,
int b){ if(a == 0 | b == 0) return a + b; if(a == b) return a; if(a>b){ return dqucln(a-b,b); } else{ if(a} }
int ucln(int a, int b){ int uc; int c =
(ai++){ if(a%i == 0 && b%i == 0){ uc = i; lOMoAR cPSD| 58702377 } } return uc; } V. Thuật toán sắp xếp #include #include
using namespace std; // sap xep chon
void selectionsort(int a[], int n){
for(int i = 0; i < n-1; i++){ int min = i;
for(int j = i+1; j < n; j++){ if(a[j] < a[min]){ min = j; } } swap(a[i],a[min]); } } // sap xep noi bot lOMoAR cPSD| 58702377
void bubblesort(int a[],int n){
for(int i = 0; i < n-1; i++){ for(int j = n-1; j > i; j-
-){ if(a[j] < a[j-1]){ swap(a[j], a[j-1]); } } } }
// sap xep noi bot cai tien void bubblesort1(int a[], int n){
int i = 0; bool sorted = false; while(!sorted
&& i < n-1){ sorted = true; for(int j = n -2; j
>= i; j--){ if(a[j] > a[j+1]){ sorted = false; } } i++; } } // sap xep chen lOMoAR cPSD| 58702377
void insertionsort(int a[], int n){
for(int i = 1; i < n; i++){ int x = a[i]; int pos = i - 1;
while(pos >= 0 && x < a[pos]){ a[pos + 1] = a[pos]; --pos; } a[pos + 1] = x; } }
int main(){ int a[1000], n; cin >> n;
for(int i = 0; i < n; i++){ cin >> a[i]; }
selectionsort(a,n); for(int i = 0;
i < n; i++){ cout << a[i] << " "; } return 0; } VI. Cây nhị phân #include using namespace std; lOMoAR cPSD| 58702377 struct node{ int data; }; struct tree{ node a; tree *LP, *RP; }; typedef struct tree* tr; // khoi tao cay void
maketree(tr &T){ T = NULL; } // bo sung 1 phan tu void
inserttree(tr &T, int x){ if(T ==
NULL){ tr p = new tree(); p->a.data = x; p->LP = NULL; p->RP = NULL; T = p; }
else { if(T->a.data > x){ inserttree(T- >LP,x); }
else if(T->a.data < x){ inserttree(T->RP,x); } } }
// hien thi cac khoa tren cay (NLR) void duyettree(tr T){ lOMoAR cPSD| 58702377
if(T != NULL){ cout << T->a.data << endl;
duyettree(T->LP); duyettree(T- >RP); } } // dem so phan tu cua cay int demtree(tr T){ int dem = 0; while(T != NULL){ ++dem; demtree(T->LP); ++dem; demtree(T->RP); } return dem; }
// tong cac khoa tren cay long sumtree(tr
T){ long sum = T->a.data; int n =
demtree(T); for(int i = 1; i <= n ; i++){
sumtree(T->LP); sum = sum + T->a.data;
sumtree(T->RP); sum = sum + T->a.data; } return sum; } lOMoAR cPSD| 58702377 lOMoAR cPSD| 58702377 lOMoAR cPSD| 58702377