intTypePromotion=3

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

Chia sẻ: Hoàng Huy | Ngày: | Loại File: DOC | Số trang:31

0
261
lượt xem
87
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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....

Chủ đề:
Lưu

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à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 SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 1
  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. 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
  3. 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. int fibonaci(int n) { if(nb) return UCLN(a-b,b); else return UCLN(a,b-a); } float HaiMuN(int n) { if(n
  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. 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
  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. 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
  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. 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
  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. void SapXepTang(DanhSach DS) { int tam; for(int i=1;iRight->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
  8. 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->PhanTuRight->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 8
  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. //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
  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. //xoa phan tu tai vi tri K void XoaK(DanhSach &DS,int k) { cout
  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 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
  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. 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
  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 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= 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
  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. { 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;iRight!=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 14
  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. 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;iRight!=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
  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. 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 < 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 16
  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. //nhap da thuc void AddDT(List &L) { int ch,i,n; coutch; DisplayEx(ch); coutInfo+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) { SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 17
  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. 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
  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. N=S.First->Right; for(int i=1;iInfo=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.nRight; 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
  20. 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

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản