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

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); } } int fibonaci(int n) { if(n<=2)return 1; else return fibonaci(n-1)+fibonaci(n-2); } int UCLN(int a,int b) { if(a==b) return a; else if(a>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; } //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(); } 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<<"\n\n"; Node *N=new Node; N=L.First->Right; for(int i=1;i<=L.n;i++) { coutInfo; N=N->Right; } } //vao sau ra truoc (them vao dau danh sach) void Add_LIFO(List &L,int phantu) { 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<<"Ban muon sap xep day so theo thu tu nao ?"; cout>sx; cout<<"Nhap vao mot day so nguyen: "; while(int(ch)>=48 && int(ch)<= 57) { ch=getch();cout<<ch; if(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) void SapXepTang(DanhSach DS) { int tam; for(int i=1;i<DS.n;i++) for(int j=i+1;j<=DS.n;j++) if(DS.PhanTu[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.n;i++) for(int j=i+1;j<=DS.n;j++) if(DS.PhanTu[i]>DS.PhanTu[j]) { swap(DS.PhanTu[i],DS.PhanTu[j]); } } void ThemPhanTu(List &L,int pt) { Node *tam=new Node; tam=L.First; while(tam->Right!=L.Last&&tam->PhanTu < pt) //chay tu Node dau tien cho den Node cuoi { //Dieu kien dung la pt lon hon PhanTu tai Node tam tam=tam->Right; //tim vi tri thich hop if(tam->PhanTu>=pt && tam->Right->PhanTu<=pt) { //chen vao vi tri vua tim duoc tam->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 < pt) //chay tu Node dau tien cho den Node cuoi { //Dieu kien dung la pt lon hon PhanTu tai Node tam tam=tam->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ỏ. //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[1]) ThemDau(DS,phantu); else if(phantu>=DS.PhanTu[DS.n]) ThemCuoi(DS,phantu); else for(int i=1;i<=DS.n-1;i++) if(DS.PhanTu[i]=phantu) { ThemK(DS,phantu,i);i=DS.n;cout<<DS.PhanTu[DS.n];getch();//ket thuc vong lap(chi them 1 lan) } } //------ Doi voi danh sach duoc luu tru dac ------ void NhapVaSapXep(DanhSach &DS) { char ch='1'; int i=0; cout<<"Nhap vao mot day so nguyen: "; while(int(ch)>=48 && int(ch)<= 57) { if(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ỏ. //xoa phan tu tai vi tri K void XoaK(DanhSach &DS,int k) { cout<<"\n\t\txoa phan tu tai vi tri "<<k<<" co gia tri= "<<DS.PhanTu[k]; for(int i=k;i<=DS.n;i++) DS.PhanTu[i]=DS.PhanTu[i+1]; DS.n--;Xuat(DS); } //xoa nhung phan tu trung nhau trong danh sach void XoaPTTrung(DanhSach &DS) { for(int i=1;i<=DS.n-1;i++) { if(DS.PhanTu[i]==DS.PhanTu[i+1]) {XoaK(DS,i+1);i--;} } } //------ doi voi danh sach luu tru bang con tro ------- void Delete(List &L) { Node *N,*tam; N=L.First; while(N->Right!=L.Last) { if(N->Info==N->Right->Info) { coutInfo= "Info; coutInfo= "Right->Info; coutRight->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; } } 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<=10;i++)so[i]=0; for(i=1;i<=DS.n;i++) { switch (DS.PhanTu[i]) {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; 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<10;i++) { cout<<"\nSo "<<i<<" Xuat hien "<<so[i]<<" lan."; } } //------ doi voi danh sach luu tru bang con tro ------- void Count(List &L) { int i,so[10]; for(i=0;i<=10;i++)so[i]=0; Node *N; N=L.First; for(i=1;i<=L.n;i++) { N=N->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; 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<10;i++) { cout<<"\nSo "<<i<<" Xuat hien "<<so[i]<<" lan."; } } Bài 10. Viết chương trinhf con đảo ngược 1 danh sách trong cả 2 trường hợp là lưu bằng mảng và lưu bằng con trỏ. void DaoNguoc(DanhSach &DS) { int i=0,j=DS.n; for(i=1;i<=DS.n/2;i++) { DS.PhanTu[0]=DS.PhanTu[i];//phan tu 0 lam trung gian DS.PhanTu[i]=DS.PhanTu[j]; DS.PhanTu[j]=DS.PhanTu[0]; j--; } } //------ doi voi danh sach luu tru bang con tro ------- void Change(List &L) { Node*N=L.First->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); } } 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<=j;i++) //dich chuyen cac phan tu sau vi tri k lui 1 { DS.PhanTu[n+1]=DS.PhanTu[n]; n--; } //them vao vi tri k 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) ThemDau(DS,phantu); else if(phantu<DS.PhanTu[1]) ThemDau(DS,phantu); else if(phantu>DS.PhanTu[DS.n]) ThemCuoi(DS,phantu); else for(int i=1;i<=DS.n-1;i++) if(DS.PhanTu[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<=L.n-1;i++) { N=N->Right; 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<=A.n;i++) Them(C,A.PhanTu[i]); for(i=1;i<=B.n;i++) Them(C,B.PhanTu[i]); } //------ doi voi danh sach luu tru bang con tro ------- void Combine(List &A,List &B,List &C) { Node*N=A.First->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; } } 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<=DS.n;i++) { if(DS.PhanTu[i]%2==1) { for(int j=i;j<=DS.n-1;j++) DS.PhanTu[j]=DS.PhanTu[j+1]; DS.n--; i--; } } } //------ doi voi danh sach luu tru bang con tro ------- void Del_(List &L) { Node *N=L.First->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]); } //------ 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; } } Bài 15. Đa thức P(x)=anXn + 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(hsLeft->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; } //nhap da thuc void AddDT(List &L) { int ch,i,n; cout>ch; DisplayEx(ch); cout<<"\n"; for(i=ch;i>=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; 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<<"\n\n"; Node *N=new Node; N=S.First->Right; for(int i=1;i<=S.n;i++) { coutInfo; 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<=0) {cout<<"Ngan xep rong";getch();return 0;} int n=S.First->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; } } void main() { clrscr(); cout<<"\n\n\nDoi voi danh sach luu tru bang con tro, DSLK doi"; Stack B;long n; Create(B); cout>n; Thap2NhiPhan(B,n); cout<<n<<" duoc doi thanh so nhi phan:\n"; Display(B); getch(); } Bài 19. vctc kiểm tra 1 chuỗi dấu ngoặc đúng (chuỗi dấu ngoặc đúng là chuỗi dấu mở đóng khớp nhau như trong biểu thức toán học) Bài 20. vctc kiểm tra 1 biểu thức được cho dưới dạng hậu tố có chuẩn không? (thông báo lỗi nếu không chuẩn ) giả sử mỗi toán hạng là 1 ký tự. //nhap vao chuoi hau to void Add_And_Insert(Stack &S) { char ch='1'; cout<<"\nNhap vao chuoi hau to dung (vd: 12+ ): "; while(int(ch)!=13) { ch=getch();cout<<ch; if((int(ch)>=48 && int(ch)<= 57)||ch=='+'||ch=='-'||ch=='*'||ch=='/') Push(S,ch); } } //kiem tra chuoi hau to void Check(Stack &S,Stack &K) { char c;int i; while(!Emty(S)) //chuyen chuoi hau to ve dang 1,0 { //toan hang(0,1,...,9) =1, toang tu(+-*/)=0 c=Pop(S); if(int(c) >= 48 && int(c)<= 57) Push(K,'1'); else Push(K,'0'); } cout<<"\n\nChuoi hau to duoc chuyen ve dang 0,1"; cout<<"\ntoan hang(0,1,...,9) =1, toang tu(+-*/)=0"; Display(K); //kiem tra Node N,N+1,N+2 co dang 110 hay ko? //neu co thi xoa N+1va N+2 i=K.n;Node *N; while(!Emty(K)&&i>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<<"\nChuoi hau to nhap vao la dung"; else cout<<"\nChuoi hau to vua nhap vao sai";getch(); } Bài 21. Cho 1 Stack S . Hãy viets chương trình con thực hiện các công việc sau: - Đếm số phần tử của Stack S - Xuất nội dung phần tử thứ n của Stack S - Xuất nội dung của Stack S - Loại Phần tử thứ n của Stack S. Trong các chương trình con trên yêu cầu bảo toàn thứ tứ các phần tử của Stack S. //hien thi ngan xep void Display(Stack &S) {cout<<"\n\n"; Node *N; N=S.First->Right; for(int i=1;i<=S.n;i++) { coutInfo; N=N->Right; } } 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(nS.n)