Download miễn phí 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à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.
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-07-bao_cao_bai_tap_thuc_hanh_mon_cau_truc_du_lieu_va.SIHnACBZ2X.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53940/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
guoc(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
;
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;
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>DS.PhanTu[j])
{
swap(DS.PhanTu,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>DS.PhanTu[j])
{
swap(DS.PhanTu,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;
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=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=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==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=0;
for(i=1;i<=DS.n;i++)
{
switch (DS.PhanTu)
{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<<" lan.";
}
}
//------ doi voi danh sach luu tru bang con tro -------
void Count(List &L)
{
int i,so[10];
for(i=0;i&...
