thi tn
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<<n%10;
DaoNguoc(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[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<<"
Nhap 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<<"
Nhap 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[i];
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<<"
";
Node *N=new Node;
N=L.First->Right;
for(int i=1;i<=L.n;i++)
{
cout<<N->Info;
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<<"
Nhan phim '1' neu theo thu tu nhap
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)
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 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[i]>DS.PhanTu[j])
{
swap(DS.PhanTu[i],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[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;
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<<"
\t\txoa phan tu tai vi tri "<<k<<" co gia tri= "<<DS.PhanTu[k];
for(int i=k;i<=DS.n;i++)
DS.PhanTu[i]=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[i]==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)
{
cout<<"
\t\tN->Info= "<<N->Info;
cout<<"\tM->Info= "<<N->Right->Info;
cout<<"\tXoaMsoNormal"> 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[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<<"
So "<<i<<" Xuat hien "<<so[i]<<" lan.";
}
}
//------ doi voi danh sach luu tru bang con tro -------
void Count(List &L)
{
int i,so[10];
for(i=0;i<=10;i++)so[i]=0;
Node *N;
N=L.First;
for(i=1;i<=L.n;i++)
{
N=N->Right;
switch (N->Info)
{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<<"
So "<<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)
{
Node*N=L.First->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);
}
}
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(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;
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;
}
}
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]);
}
//------ 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(hs<L.Last->Left->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;
}
//nhap da thuc
void AddDT(List &L)
{
int ch,i,n;
cout<<"
Nhap vao bac cua da thuc: ";cin>>ch;
DisplayEx(ch);
cout<<"
";
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
{
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;
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<<"
";
Node *N=new Node;
N=S.First->Right;
for(int i=1;i<=S.n;i++)
{
cout<<N->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;
}
}
void main()
{
clrscr();
cout<<"
Doi voi danh sach luu tru bang con tro, DSLK doi";
Stack B;long n;
Create(B);
cout<<"
Nhap mot so thap phan: "; cin>>n;
Thap2NhiPhan(B,n);
cout<<n<<" duoc doi thanh so nhi phan:
";
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<<"
Nhap 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=='/')
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<<"
Chuoi hau to duoc chuyen ve dang 0,1";
cout<<"
toan 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<<"
Chuoi hau to nhap vao la dung";
else cout<<"
Chuoi 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<<"
";
Node *N;
N=S.First->Right;
for(int i=1;i<=S.n;i++)
{
cout<<N->Info;
N=N->Right;
}
}
int Count(Stack &S)
{
Stack K;Create(K);char c;int check=0;
while(!Emty(S)) //dem so phan tu cua ngan xep
{
c=Pop(S);check++;
Push(K,c);
}
while(!Emty(K)) //Tra lai ngan xep nhu ban dau
{
c=Pop(K);
Push(S,c);
}
return check;
}
void XemPTn(Stack &S,int n)
{
if(n<=0||n>S.n)
{
cout<<"
n<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;
while(kt!=0)
{c=Pop(S); Push(K,c); kt--;}
cout<<"Phan tu thu "<<n<<"= "<<c;getch();
//tra lai ngan xep ban dau
while(!Emty(K))
{c=Pop(K);Push(S,c);}
}
void XoaPTn(Stack &S,int n)
{
if(n<=0||n>S.n)
{
cout<<"
n<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);
Push(K,c);
kt--;
}
cout<<"
Phan tu thu "<<n<<"= "<<c;
cout<<"
ban 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
{
//tra lai ngan xep nhu ban dau
while(!Emty(K))
{c=Pop(K);Push(S,c);}
}
}
Bài 22. Cũng với nội dung câu 21 nhưng với kiểu dữ liệu Queue.
struct Node
{
char Info;
Node *Left;
Node *Right;
};
struct Queue
{
Node *First;
Node *Last;
int n;
};
void Create(Queue &Q)
{
Q.First=new Node;
Q.Last= new Node;
Q.First->Left=NULL;
Q.First->Right=Q.Last;
Q.Last->Left=Q.First;
Q.Last->Right=NULL;
Q.n=0;
}
int Emty(Queue &Q)
{
return(Q.First->Right==Q.Last);
}
//hien thi ngan xep
void Display(Queue &Q)
{
cout<<"
";
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)
{
if(Q.n<=0) {cout<<"Hang doi rong";getch();return 0;}
char n=Q.First->Right->Info;
Node*N=Q.First->Right;
Q.First->Right->Right->Left=Q.First;
Q.First->Right=Q.First->Right->Right;
delete N;Q.n--;
return n;
}
//nhap vao cac phan tu cua ngan xep
void Add(Queue &Q)
{
char ch='1';
cout<<"
Nhap vao cac phan tu cua hang doi, nhan ENTER de ket thuc
\t: ";
while(int(ch)!=13)
{
ch=getch();cout<<ch;
if(int(ch)!=13)Push(Q,ch);
}
}
int Count(Queue &Q)
{
Queue K;Create(K);char c;int check=0;
while(!Emty(Q)) //dem so phan tu cua hang doi
{
c=Pop(Q);check++;
Push(K,c);
}
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<<"
n<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<<"
n<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=n-1;char c,tmp;
while(kt!=0)
{
c=Pop(Q);
Push(K,c);
kt--;
}
tmp=Pop(Q);
cout<<"
Phan tu thu "<<n<<"= "<<tmp;
cout<<"
ban co muon xoa phan tu nay khong (y,n):";c=getch();
if(c=='y')
{
//chuyen toan bo nhung phan tu con lai trong Q sang K
while(!Emty(Q))
{c=Pop(Q);Push(K,c);}
}
else
{
//chuyen ky tu vao K va chuyen toan bo PT con lai trong Q sang K
Push(K,tmp);
while(!Emty(Q))
{c=Pop(Q);Push(K,c);}
}
//tra lai Hang doi Q
while(!Emty(K))
{c=Pop(K);Push(Q,c);}
}
void main()
{
clrscr();int n;
cout<<"
Doi voi danh sach luu tru bang con tro, DSLK doi";
Queue B;
Create(B);
Add(B);
cout<<"
Hang Doi sau khi nhap:";
Display(B);
cout<<"
So phan tu cua Hang Doi= "<<Count(B);
Display(B);
cout<<"
Nhap so thu tu cua phan tu can xem: n= ";cin>>n;
XemPTn(B,n);
Display(B);
cout<<"
Nhap so thu tu cua phan tu can xoa: n= ";cin>>n;
XoaPTn(B,n);
Display(B);
getch();
}
Bài 23. Viết chương trình con đảo ngược 1 stack.
//dao nguoc mot stack
void DaoNguoc(Stack &S)
{
Stack S1,S2;char c;
Create(S1);Create(S2);
while(!Emty(S))
{
c=Pop(S);
Push(S1,c);
}
while(!Emty(S1))
{
c=Pop(S1);
Push(S2,c);
}
while(!Emty(S2))
{
c=Pop(S2);
Push(S,c);
}
}
void main()
{
clrscr();int n;
cout<<"
Doi voi danh sach luu tru bang con tro, DSLK doi";
Stack B;
Create(B);
Add(B);
cout<<"
Ngan xep sau khi nhap:";
Display(B);
cout<<"
Ngan xep sau khi dao nguoc:";
DaoNguoc(B);
Display(B);
getch();
}
Bài 24. Viết chương trình con đảo ngược 1 Queue.
Bài 25. Dùng Stack và Queue để kiểm tra 1 chuỗi kí tự có đới xứng không?
Bài 26. Ta có thể cài đặt ngăn xếp trong cùng 1 mảng, gọi là ngăn xếp 2 đầu hoạt động của 2 ngăn xếp này theo sơ đồ sau:
Đáy ngăn xếp 1
Đỉnh(TOP) ngăn xếp 1
Phần mảng còn trống
Đỉnh(TOP) ngăn xếp 2
Đáy ngăn xếp 2
Hãy viết chương trình con cần thiết đẻ cài đặt ngăn xếp 2 đầu.
Câu 35:
Tất cả các thao tác searchNode, insertNode, delNode trên CNPTK đều có độ phức tạp trung bình O(h), với h là chiều cao của cây
Trong trong trường hợp tốt nhất, CNPTK có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự.
Tuy nhiên, trong trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK (khi mà mỗi nút đều chỉ có 1 con trừ nút lá). Lúc đó các thao tác trên sẽ có độ phức tạp O(n). Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n).
Câu36
54
65
78
59
31
29
10
20
43
36
Câu37
Xen thêm nút 15
54
65
78
59
31
29
10
20
43
36
15
Xen thêm nút 45
54
65
78
59
31
29
10
20
43
36
15
45
Xen thêm nút 55
54
31
29
10
20
43
36
15
45
65
78
59
55
Câu38: Vẽ lại cây tìm kiếm nhị phân khi lần lượt
54
65
78
59
31
29
20
43
36
Xóa nút 10
54
65
78
59
31
29
43
36
Xóa nút 20
54
78
59
31
29
43
36
Xóa nút 65
Xóa nút 54
59
78
31
29
43
36
Bài 39
Dựng cây tìm kiếm nhị phân ứng với dãy khóa : HAIPHONG, CANTHO, NHATRANG, DALAT, HANOI, ANGIANG, MINHHAI, HUE, SAIGON, VINHLONG
Đường đi trên cây khi tìm kiếm khóa: DONGTHAP
Đường đi là những mũi tên đậm
HAIPHONG
CANTHO
DALAT
ANGIANG
NHATRANG
HANOI
MINHHAI
HUE
SAIGON
VINHLONG
NULL
Bạn đang đọc truyện trên: Truyen247.Pro