Tài liệu 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 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Á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<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) { SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 2 Bài 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. 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<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++) { cout<Info; N=N->Right; } } //vao sau ra truoc (them vao dau danh sach) SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 4 Bài 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. 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<<"\n Nhan phim '1' neu theo thu tu nhap\n Nhan phim bat ky neu nguoc lai";cin>>sx; cout<<"Nhap vao mot day so nguyen: "; while(int(ch)>=48 && int(ch)<= 57) { ch=getch();cout<= 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) SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 5 Bài 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. void SapXepTang(DanhSach DS) { int tam; for(int i=1;iDS.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;iDS.PhanTu[j]) { swap(DS.PhanTu[i],DS.PhanTu[j]); } } void ThemPhanTu(List &L,int pt) { SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 6 Bài 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. 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ỏ. SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 7 Bài 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. //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<=DS.n-1;i++) if(DS.PhanTu[i]<=phantu&&DS.PhanTu[i+1]>=phantu) { ThemK(DS,phantu,i);i=DS.n;cout<=48 && int(ch)<= 57) { if(int(ch)<48&&int(ch)>57) { i++; ch=getch();cout<Info= "<Info; cout<<"\tM->Info= "<Right->Info; cout<<"\tXoa M="<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; } } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 9 Bài 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 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 "<Right; switch (N->Info) {case 1:so[1]++;break; case 2:so[2]++;break; case 3:so[3]++;break; case 4:so[4]++;break; SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 10 Bài 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. 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 "<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); } } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 11 Bài 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 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(phantuDS.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 <= L.First->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++) { SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 12 Bài 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=N->Right; M=M->Right; if(N->Info <= phantu && M->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; } } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 13 Bài 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 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]); } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 14 Bài 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. //------ 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 < sm && sm>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; } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 15 Bài 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. //nhap da thuc void AddDT(List &L) { int ch,i,n; cout<<"\nNhap vao bac cua da thuc: ";cin>>ch; DisplayEx(ch); cout<<"\n"; for(i=ch;i>=0;i--) { cout<<"a"<>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; SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 16 Bài 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=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++) SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 17 Bài 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. { 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<=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; } } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 18 Bài 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. void main() { clrscr(); cout<<"\n\n\nDoi voi danh sach luu tru bang con tro, DSLK doi"; Stack B;long n; Create(B); cout<<"\nNhap mot so thap phan: "; cin>>n; Thap2NhiPhan(B,n); cout<=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"; SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 19 Bài 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. 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++) { cout<Info; N=N->Right; } } SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 20