Báo cáo bài tập thực hành môn Cấu trúc dữ liệu & giải thuật

Nội dung text: Báo cáo bài tập thực hành môn Cấu trúc dữ liệu & giải thuật

1. BÁO CÁO BÀI TẬP THỰC HÀNH MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
2. BÁO CÁO BÀI TẬP THỰC HÀNH MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT Bài 1. Viết chương trình con bằng gaiir thuật đệ qui để thực hiện các công việc sau: - Tính n! - Tính S=1+2+3+ +n - Tính s=1+3+5+ +(2k+1) với 2k+1<=n - Đổi số nguyên n hệ 10 sang hệ 2 - Đảo ngược double giaithua(int n) { if(n<0) return 0; else if(n<=1) return 1; else return n*giaithua(n-1); } double S1(int n) { if(n<=0) return 0; else return n+S1(n-1); } double S2(int n) { if(n<=0) return 0; else if(n%2==0) return S2(n-1); else return n+S2(n-2); } void he10to2(long n) { if(n==0) return; he10to2(n/2); if(n%2==0) cout<<"0"; else cout<<"1"; } void DaoNguoc(long n) { if(n==0)return; else { cout<<n%10; DaoNguoc(n/10); } }
3. int fibonaci(int n) { if(n b) return UCLN(a-b,b); else return UCLN(a,b-a); } float HaiMuN(int n) { if(n<0) return 1/HaiMuN(-n); if(n==0)return 1; else return 2*HaiMuN(n-1); } float XmuY(int x,int y) { if(y<0) return 1/XmuY(x,-y); if(x==0)return 0; else if(y==0)return 1; else return x*XmuY(x,y-1); } Bài 2. Viết hàm khai báo cac chương trình con cài đặt danh sách mảng. Dùng các chương trình con này để: - Chương trình con nhận một dãy các số nguyên nhập từ bàn phím, lưu trữ nó trong danh sách theo thứ tự nhập vào. - Chương trình con nhận một dãy các số nguyên nhập từ bàn phím, lưu trữ nó trong danh sách thứ tự ngược với thú tự nhập vào. - Viết chương trình con in ra màn hình các phần tử trong danh sách theo thứ tự của nó trong danh sách. struct DanhSach { int PhanTu[100]; int n; //so phan tu cua danh sach }; void TaoRong(DanhSach &DS) { DS.n=0;
4. } //them vao dau sanh sach void ThemDau(DanhSach &DS,int phantu) { for(int i=DS.n;i>=1;i ) DS.PhanTu[i+1]=DS.PhanTu[i]; DS.PhanTu[1]=phantu; DS.n++; } //them vao cuoi danh sach void ThemCuoi(DanhSach &DS,int phantu) { DS.n++; DS.PhanTu[DS.n]=phantu; } //nhap va luu tru theo thu tu void Nhap(DanhSach &DS) { char str[99]; cout<<"\nNhap vao mot day so nguyen"; gets(str); for(int i=1;i<=strlen(str);i++) ThemCuoi(DS,int(str[i-1])-48); } //nhap va luu tru nguoc voi thu tu nhap void NhapNguoc(DanhSach &DS) { char str[99]; cout<<"\nNhap vao mot day so nguyen"; gets(str); for(int i=1;i<=strlen(str);i++) ThemDau(DS,int(str[i-1])-48); } void Xuat(DanhSach DS) { for(int i=1;i<=DS.n;i++) cout<<DS.PhanTu[i]; getch(); }
5. Bài 3. Tương tự bài tập 1, nhưng cài đặt bằng con trỏ. struct Node { int Info; Node *Left; Node *Right; }; struct List { Node *First; Node *Last; int n; }; void Create(List &L) { L.First=new Node; L.Last= new Node; L.First->Left=NULL; L.First->Right=L.Last; L.Last->Left=L.First; L.Last->Right=NULL; L.n=0; } int Emty(List &L) { return(L.First->Right==L.Last); } //hien thi danh sach void Display(List &L) { cout Right; for(int i=1;i Info; N=N->Right; } } //vao sau ra truoc (them vao dau danh sach) void Add_LIFO(List &L,int phantu)
6. { Node *N=new Node; N->Info=phantu; N->Left=L.First; N->Right=L.First->Right; L.First->Right->Left=N; L.First->Right=N; L.n++; } //vao truoc ra sau (them vao cuoi danh sach) void Add_FILO(List &L,int phantu) { Node *N=new Node; N->Info=phantu; N->Right=L.Last; N->Left=L.Last->Left; L.Last->Left->Right=N; L.Last->Left=N; L.n++; } //nhap va luu tru theo thu tu nhap vao hoac nguoc lai void Add_And_Insert(List &L) { char ch='1';int sx=0; cout >sx; cout =48 && int(ch) = 48 && int(ch) <= 57) if(sx==1) Add_FILO(L,int(ch)-48); else Add_LIFO(L,int(ch)-48); } } Bài 4. Viết chương trình con sắp xếp một danh sách chứa các số nguyên, trong các trường hợp: - Danh sách được cài đặt bằng mảng(DS đặc) - Danh sách được cài đặt bằng con trỏ(DS liên kết)
7. void SapXepTang(DanhSach DS) { int tam; for(int i=1;i DS.PhanTu[j]) { swap(DS.PhanTu[i],DS.PhanTu[j]); } } void SapXepTang(List &L) { Node *tam1=new Node; Node *tam2=new Node; tam1=L.First; while(tam1->Right->Right!=L.Last) //chay tu Node dau tien cho den Node ke cuoi { tam1=tam1->Right; while(tam2->Right!=L.Last) //chay tu Node tam den Node cuoi { tam2=tam1->Right; if(tam1->PhanTu > tam2->PhanTu) swap(tam1,tam2); } } } Bài 5. Viết chương trình con thêm 1 phần tử trong danh sách liên kết đã có thứ tự sao cho ta vẫn có 1 danh sách có thứ tự. void SapXepTang(DanhSach DS) { int tam; for(int i=1;i DS.PhanTu[j]) { swap(DS.PhanTu[i],DS.PhanTu[j]); } } void ThemPhanTu(List &L,int pt) { Node *tam=new Node;
8. tam=L.First; while(tam->Right!=L.Last&&tam->PhanTu Right; //tim vi tri thich hop if(tam->PhanTu>=pt && tam->Right->PhanTu Right->Left=tam; tam->Left->Right=tam; tam->Left=tam->Left->Right; } } } Bài 6. Viết chương trình con tìm kiếm và xóa 1 phần tử trong danh sách liên kết có thứ tự. void XoaPhanTu(List &L,int pt) { Node *tam=new Node; tam=L.First; while(tam->Right!=L.Last&&tam->PhanTu Right; //tim vi tri thich hop if(tam->PhanTu==pt) { //xoa phan tu tai vi tri vua tim duoc delete tam->Left->Right; tam->Right->Left=tam->Left; tam->Left->Right=tam->Right; delete tam; } } } Bài 7.Viết chương trình con nhập vào từ bàn phím 1 dãy số nguyên, lưu trữ nó trong một danh sách có thứ tự không giảm, theo cách sau: Với mỗi phần tử được nhập vào chương trình con phải tìm vị trí thích hợp để xen nó vào danh sách cho đúng thứ tự. vctc trên cho trường hợp danh sách được cài đặt bằng mảng và cài đặt bằng con trỏ.
9. //them vao vi tri k trong sanh sach void ThemK(DanhSach &DS,int phantu,int k) { for(int i=DS.n;i>=k;i ) DS.PhanTu[i+1]=DS.PhanTu[i]; DS.PhanTu[k]=phantu; DS.n++; } //tim vi tri thich hop va them vao sanh sach void Them(DanhSach &DS,int phantu) { if(DS.n==0||phantu =DS.PhanTu[DS.n]) ThemCuoi(DS,phantu); else for(int i=1;i =phantu) { ThemK(DS,phantu,i);i=DS.n;cout =48 && int(ch) 57) { i++; ch=getch();cout<<ch; Them(DS,int(ch)-48); } } } Bài 8. Viết chương trình con loại bỏ các phần tử trùng nhau(giứ lại duy nhất 1 phần tử) trong 1 danh sách có thứ tự không giảm trong 2 trường hợp: Cài đặt bằng mảng và cài đặt bằng con trỏ.
10. //xoa phan tu tai vi tri K void XoaK(DanhSach &DS,int k) { cout Right!=L.Last) { if(N->Info==N->Right->Info) { cout Info= " Info; cout Info= " Right->Info; cout Right->Info;getch(); tam=N->Right; N->Right->Right->Left=N; N->Right=N->Right->Right; delete tam; L.n ; Display(L);//kiem tra } else N=N->Right; } }
11. Bài 9. Viết chương trình con đếm số lần xuất hiện của mỗi ký tự trong 1 chuỗi ký tự. void Dem(DanhSach &DS) { int i,so[10]; for(i=0;i Right; switch (N->Info) {case 1:so[1]++;break; case 2:so[2]++;break; case 3:so[3]++;break; case 4:so[4]++;break; case 5:so[5]++;break;
12. case 6:so[6]++;break; case 7:so[7]++;break; case 8:so[8]++;break; case 9:so[9]++;break; case 0:so[0]++;break; } } for(i=0;i Right->Right;//bat dau tu phan tu so 2 int tam; while(N->Right!=NULL) { Node*tmp=N;tam=N->Info; //xoa Node N->Left->Right=N->Right; N->Right->Left=N->Left; N=N->Right; delete tmp;L.n ; //them Node vua xoa vao dau danh sach Add_LIFO(L,tam); } }
13. Bài 11. vctc nhận vào từ bàn phím 1 dãy số nguyên, lưu trữ nó trong 1 danh sách có thứ tự tăng không có 2 phần tử trùng nhau, theo cách sau: Với mỗi phần tử được nhập vào chương trình con phải tìm kiếm xem nó có trong danh sách chưa? Nếu chưa có thì xen nó vào danh sách cho đúng thứ tự. vctc trên trường hợp danh sách được cài đặt bằng mảng và cài đặt bằng con trỏ. //them vao vi tri k trong sanh sach void ThemK(DanhSach &DS,int phantu,int k) { int i,n=DS.n,j=DS.n-k+1; for(i=1;i DS.PhanTu[DS.n]) ThemCuoi(DS,phantu); else for(int i=1;i phantu) { ThemK(DS,phantu,i+1);i=DS.n;//ket thuc vong lap(chi them 1 lan) } } //them vao vi tri thich hop trong danh sach void Add(List &L,int phantu) { if(Emty(L)) Add_LIFO(L,phantu); else if(phantu Right->Info) Add_LIFO(L,phantu);//them dau else if(phantu >= L.Last->Left->Info) Add_FILO(L,phantu); //them cuoi else { Node *N;Node *M; N=L.First; M=L.First->Right; for(int i=1;i Right;
14. M=M->Right; if(N->Info Info > phantu) { Node *K=new Node; K->Info=phantu; K->Left=N; K->Right=M; N->Right=K; M->Left=K; L.n++;return;//dung vong lap, chi them 1 Node } } delete N,M; } } Bài 12. Viết chương trình con trộn 2 danh sách liên kết chứa các số nguyên theo thứ tự tăng để được 1 danh sách cũng có thứ tự void TronDS(DanhSach &A,DanhSach &B,DanhSach &C) { int i; for(i=1;i Right; while(N->Right!=NULL) { Add(C,N->Info); N=N->Right; } N=B.First->Right; while(N->Right!=NULL) { Add(C,N->Info); N=N->Right; } }
15. Bài 13. Viết chương trình con xóa khỏi danh sách lưu trữ cá số nguyên các phần tử là là số nguyên lẻ,cũng trong 2 trường hợp là cài đặt bằng mảng và con trỏ. void XoaLe(DanhSach &DS) { for(int i=1;i Right; while(N->Right!=NULL) { if(N->Info%2==1) { Node *tmp=N; N->Left->Right=N->Right; N->Right->Left=N->Left; delete tmp; L.n ; } N=N->Right; } } Bài 14.Viết chương trình con tách 1 danh sách chứa các số nguyên các phần tử thành 2 danh sách : 1 danh sách gồm các số chẵn còn danh sách kia gồm các số lẻ. void Tach(DanhSach &A,DanhSach &B,DanhSach &C) { for(int i=1;i<=A.n;i++) if(A.PhanTu[i]%2==0) Them(B,A.PhanTu[i]); else Them(C,A.PhanTu[i]); }
16. // doi voi danh sach luu tru bang con tro void Tach2(List &P,List &Q,List &R) { Node *N=P.First->Right; while(N->Right!=NULL) { if(N->Info%2==0) Add(Q,N->Info); else Add(R,N->Info); N=N->Right; } } n Bài 15. Đa thức P(x)=anX + an-1+ +a1x+a0 được lưu trx trong máy tính dưới dạng 1 danh sách liên kết mà mỗi phần tử của danh sách là một bản ghi có 3 trường lưu giữ hệ số, số mũ và trường con trỏ để trỏ đén phần tử kế tiếp. Chú ý cách lưu trữ đảm bảo thứ tự giảm dần theo số mũ của từng hạng tử của đa thức. //them vao vi tri thich hop trong danh sach void Add(List &L,int hs,int sm) { if(hs>L.First->Right->HeSo) {Add_LIFO(L,hs,sm);return;} if(hs Left->HeSo) {Add_FILO(L,hs,sm);return;} Node *N; N=L.First->Right; while(N->Right!=NULL) if(N->SoMu==sm) {N->HeSo=N->HeSo+hs;return;} else N=N->Right; N=L.First->Right; while(N->Right!=NULL) if(N->SoMu N->Right->SoMu) { Node *K=new Node; K->HeSo=hs; K->SoMu=sm; K->Left=N; K->Right=N->Right; N->Right->Left=K; N->Right=K; L.n++;return; } else N=N->Right; }
17. //nhap da thuc void AddDT(List &L) { int ch,i,n; cout >ch; DisplayEx(ch); cout =0;i ) { cout >n; if(n!=0)Add_FILO(L,n,i); } } Bài 16. Để lưu trữ 1 số nguyên lớn ta có thể dùng danh sách liên kết chứa các chữ số của nó. Hãy tìm cách lưu trữ các chũa só của 1 số nguyên lớn theo ý tưởng trên sap cho viêc cộng 2 số nguyên lớn là dễ dàng thực hiện. Viết chương trình con cộng 2 số nguyên lớn. //cong hai so nguyen lon void Cong(List &A,List &B,List &C) { Node *N,*M; if(A.n>=B.n) { C=A;Display(C);getch(); N=B.Last->Left; M=C.Last->Left; while(N->Left!=NULL) { if(M->Info+N->Info>1000)M->Left->Info+=1; M->Info=(M->Info+N->Info)%1000; N=N->Left; M=M->Left; } } else { C=B;C.First->Info=0; N=A.Last->Left; M=C.Last->Left; while(N->Left!=NULL) { if(M->Info+N->Info>1000)M->Left->Info+=1; M->Info=(M->Info+N->Info)%1000;
18. N=N->Left; M=M->Left; } } if(C.First->Info==1) Add_LIFO(C,1); } Bài 17. HÃy cài đặt 1 ngăn xếp theo cách dùng con trỏ. struct Node { int Info; Node *Left; Node *Right; }; struct Stack { Node *First; Node *Last; int n; }; void Create(Stack &S) { S.First=new Node; S.Last= new Node; S.First->Left=NULL; S.First->Right=S.Last; S.Last->Left=S.First; S.Last->Right=NULL; S.n=0; } int Emty(Stack &S) { return(S.First->Right==S.Last); } //hien thi ngan xep void Display(Stack &S) { cout Right; for(int i=1;i<=S.n;i++)
19. { cout Info; N=N->Right; } } //vao sau ra truoc (them vao dau danh sach) void Push(Stack &S,int phantu) { Node *N=new Node; N->Info=phantu; N->Left=S.First; N->Right=S.First->Right; S.First->Right->Left=N; S.First->Right=N; S.n++; } //lay mot phan tu o dinh ngan xep int Pop(Stack &S) { if(S.n Right->Info; Node*N=S.First->Right; S.First->Right->Right->Left=S.First; S.First->Right=S.First->Right->Right; delete N;S.n ; return n; } Bài 18. Dùng ngăn xếp để viết chương trình con đổi 1 số thập phân sang số nhị phân. //doi 1 so thap phan sang nhi phan void Thap2NhiPhan(Stack &S,long n) { //int check=0; if(n<0) n=n*-1;//check=1;} while(n!=0) { Push(S,n%2); n=n/2; } }
20. void main() { clrscr(); cout >n; Thap2NhiPhan(B,n); cout =48 && int(ch) = 48 && int(c)<= 57) Push(K,'1'); else Push(K,'0'); } cout<<"\n\nChuoi hau to duoc chuyen ve dang 0,1";
21. cout 0) { N=K.First->Right; while(N->Right!=NULL) { if(N->Info=='1'&&N->Right->Info=='1'&&N->Right->Right->Info=='0') { //xoa 2 Node sau N Node *t1=N->Right,*t2=N->Right->Right; N->Right->Right->Right->Left=N; N->Right=N->Right->Right->Right; delete t1,t2;K.n-=2; } N=N->Right; } i ; } if(K.n==1&&K.First->Right->Info=='1') cout Right; for(int i=1;i Info; N=N->Right; } }
22. int Count(Stack &S) { Stack K;Create(K);char c;int check=0; while(!Emty(S)) //dem so phan tu cua ngan xep { c=Pop(S);check++; Push(K,c); } while(!Emty(K)) //Tra lai ngan xep nhu ban dau { c=Pop(K); Push(S,c); } return check; } void XemPTn(Stack &S,int n) { if(n S.n) { cout S.n) { cout<<"\nn<0 hoac n lon hon so phan tu cua ngan xep"; getch();return; } //lay noi dung cua phan tu thu n Stack K;Create(K);int kt=n;char c,tmp; while(kt!=0) { c=Pop(S);
23. Push(K,c); kt ; } cout Left=NULL; Q.First->Right=Q.Last; Q.Last->Left=Q.First; Q.Last->Right=NULL; Q.n=0; }
24. int Emty(Queue &Q) { return(Q.First->Right==Q.Last); } //hien thi ngan xep void Display(Queue &Q) { cout Right; for(int i=1;i Info; N=N->Right; } } //vao sau ra truoc (them vao dau danh sach) void Push(Queue &Q,char phantu) { Node *N=new Node; N->Info=phantu; N->Right=Q.Last; N->Left=Q.Last->Left; Q.Last->Left->Right=N; Q.Last->Left=N; Q.n++; } //lay mot phan tu o dinh hang doi char Pop(Queue &Q) { if(Q.n Right->Info; Node*N=Q.First->Right; Q.First->Right->Right->Left=Q.First; Q.First->Right=Q.First->Right->Right; delete N;Q.n ; return n; } //nhap vao cac phan tu cua ngan xep void Add(Queue &Q) { char ch='1';
25. cout Q.n) { cout Q.n) { cout<<"\nn<0 hoac n lon hon so phan tu cua hang doi";
26. getch();return; } //lay noi dung cua phan tu thu n Queue K;Create(K);int kt=n-1;char c,tmp; while(kt!=0) { c=Pop(Q); Push(K,c); kt ; } tmp=Pop(Q); cout >n; XemPTn(B,n);
27. Display(B); cout >n; XoaPTn(B,n); Display(B); getch(); } Bài 23. Viết chương trình con đảo ngược 1 stack. //dao nguoc mot stack void DaoNguoc(Stack &S) { Stack S1,S2;char c; Create(S1);Create(S2); while(!Emty(S)) { c=Pop(S); Push(S1,c); } while(!Emty(S1)) { c=Pop(S1); Push(S2,c); } while(!Emty(S2)) { c=Pop(S2); Push(S,c); } } void main() { clrscr();int n; cout<<"\n\n\nDoi voi danh sach luu tru bang con tro, DSLK doi"; Stack B; Create(B); Add(B); cout<<"\nNgan xep sau khi nhap:"; Display(B); cout<<"\nNgan xep sau khi dao nguoc:"; DaoNguoc(B); Display(B); getch();
28. } Bài 24. Viết chương trình con đảo ngược 1 Queue. Bài 25. Dùng Stack và Queue để kiểm tra 1 chuỗi kí tự có đới xứng không? Bài 26. Ta có thể cài đặt ngăn xếp trong cùng 1 mảng, gọi là ngăn xếp 2 đầu hoạt động của 2 ngăn xếp này theo sơ đồ sau: Đáy ngăn xếp 1 Đỉnh(TOP) ngăn xếp 1 Phần mảng còn trống Đỉnh(TOP) ngăn xếp 2 Đáy ngăn xếp 2 Hãy viết chương trình con cần thiết đẻ cài đặt ngăn xếp 2 đầu. Câu 35: Tất cả các thao tác searchNode, insertNode, delNode trên CNPTK đều có độ phức tạp trung bình O(h), với h là chiều cao của cây Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự. Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK (khi mà mỗi nút đều chỉ có 1 con trừ nút lá). Lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n).
29. Câu36 54 31 65 29 43 59 78 10 20 36 Câu37 Xen thêm nút 15 54 31 65 29 43 59 78 10 20 36 15
30. Xen thêm nút 45 54 31 65 29 43 59 78 10 20 36 45 15 Xen thêm nút 55 54 31 65 29 43 59 78 10 20 36 45 55 15
31. Câu38: Vẽ lại cây tìm kiếm nhị phân khi lần lượt Xóa nút 10 54 31 65 29 43 59 78 20 36 Xóa nút 20 54 31 65 29 43 59 78 36 Xóa nút 65 54 31 78 29 43 59 36
32. Xóa nút 54 59 31 78 29 43 36 Bài 39 Dựng cây tìm kiếm nhị phân ứng với dãy khóa : HAIPHONG, CANTHO, NHATRANG, DALAT, HANOI, ANGIANG, MINHHAI, HUE, SAIGON, VINHLONG Đường đi trên cây khi tìm kiếm khóa: DONGTHAP Đường đi là những mũi tên đậm HAIPHONG CANTHO NHATRANG ANGIANG DALAT HANOI SAIGON MINHHAI VINHLONG NULL HUE