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
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<=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 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;
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.
}

ThemDau(DS,int(str[i-1])-48);
}
void Xuat(DanhSach DS)
{
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 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.
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.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<<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

}
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;
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.
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 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[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)
{

void Delete(List &L)
{
Node *N,*tam;
N=L.First;
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 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.
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++)
{

case 2:so[2]++;break;
case 3:so[3]++;break;
case 4:so[4]++;break;
case 5:so[5]++;break;
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.
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 ;
}

{
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&&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;

}
// 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 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.
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 ;

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.
// 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)=a
n
X
n
+ a
n-1
+…+a
1
x+a
0
đượ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)

DisplayEx(ch);
cout<<"\n";
for(i=ch;i>=0;i )
{
cout<<"a"<<i<<"= ";cin>>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

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 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.
{
cout<<N->Info;
N=N->Right;
}
}
//vao sau ra truoc (them vao dau danh sach)
void Push(Stack &S,int phantu)

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 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.
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<<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=='/')

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<<N->Info;
N=N->Right;
}
}

while(!Emty(K))
{c=Pop(K);Push(S,c);}
}
void XoaPTn(Stack &S,int n)
{
if(n<=0||n>S.n)
{
cout<<"\nn<0 hoac n lon hon so phan tu cua ngan xep";
getch();return;
}
//lay noi dung cua phan tu thu n
Stack K;Create(K);int kt=n;char c,tmp;
while(kt!=0)
{
c=Pop(S);
SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 22
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.
Push(K,c);
kt ;
}
cout<<"\nPhan tu thu "<<n<<"= "<<c;
cout<<"\nban co muon xoa phan tu nay khong (y,n):";tmp=getch();
if(tmp=='y')
{
c=Pop(K);//bo di phan tu thu n
//tra lai ngan xep sau khi xoa
while(!Emty(K))
{c=Pop(K);Push(S,c);}
}
else

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 Emty(Queue &Q)
{
return(Q.First->Right==Q.Last);
}
//hien thi ngan xep
void Display(Queue &Q)
{
cout<<"\n\n";
Node *N;
N=Q.First->Right;
for(int i=1;i<=Q.n;i++)
{
cout<<N->Info;
N=N->Right;
}
}
//vao sau ra truoc (them vao dau danh sach)
void Push(Queue &Q,char phantu)
{
Node *N=new Node;
N->Info=phantu;
N->Right=Q.Last;
N->Left=Q.Last->Left;
Q.Last->Left->Right=N;
Q.Last->Left=N;
Q.n++;
}
//lay mot phan tu o dinh hang doi
char Pop(Queue &Q)

while(!Emty(K)) //Tra lai hang doi nhu ban dau
{
c=Pop(K);
Push(Q,c);
}
return check;
}
void XemPTn(Queue &Q,int n)
{
if(n<=0||n>Q.n)
{
cout<<"\nn<0 hoac n lon hon so phan tu cua hang doi";
getch();return;
}
//lay noi dung cua phan tu thu n
Queue K;Create(K);int kt=0;char c,tam;
while(!Emty(Q))
{c=Pop(Q); Push(K,c); kt++;if(kt==n)tam=c;}
cout<<"Phan tu thu "<<n<<"= "<<tam;getch();
//tra lai ngan xep ban dau
while(!Emty(K))
{c=Pop(K);Push(Q,c);}
}
void XoaPTn(Queue &Q,int n)
{
if(n<=0||n>Q.n)
{
cout<<"\nn<0 hoac n lon hon so phan tu cua hang doi";
SVTH: Tống Văn Chình – Lớp 06I Trường CĐ Công Nghệ Thông Tin- ĐH ĐN. Page 25