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";

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;
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.
}
//them vao dau sanh sach
void ThemDau(DanhSach &DS,int phantu)
{
for(int i=DS.n;i>=1;i--)

for(int i=1;i<=DS.n;i++)
cout<<DS.PhanTu[i];
getch();
}
SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 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.
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)

{
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<<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)
SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 5

{
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;
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.
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ó

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&&DS.PhanTu[i+1]>=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)<48&&int(ch)>57)
{
i++;
ch=getch();cout<<ch;

while(N->Right!=L.Last)
{
if(N->Info==N->Right->Info)
{
cout<<"\n\t\tN->Info= "<<N->Info;
cout<<"\tM->Info= "<<N->Right->Info;
cout<<"\tXoa M="<<N->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;

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 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)
{

//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&&DS.PhanTu[i+1]>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++)
{
N=N->Right;