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

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[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<<"\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[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<<"\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[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) { 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[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) { 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[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<<"\nSo "<<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<<"\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) { 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) { 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 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 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(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 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>ch; DisplayEx(ch); cout<<"\n"; for(i=ch;i>=0;i--) { cout>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<<"\n\n"; Node *N=new Node; N=S.First->Right; for(int i=1;i<=S.n;i++) { coutInfo; 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<<"\n\n\nDoi voi danh sach luu tru bang con tro, DSLK doi"; Stack B;long n; Create(B); cout>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=='/') 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<<"\n\nChuoi hau to duoc chuyen ve dang 0,1"; cout<<"\ntoan 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<<"\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++) { coutInfo; 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(nS.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; 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(nS.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); 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 { //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<<"\n\n"; Node *N; N=Q.First->Right; for(int i=1;i<=Q.n;i++) { coutInfo; 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<<"\nNhap vao cac phan tu cua hang doi, nhan ENTER de ket thuc\n\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(nQ.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(nQ.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=n-1;char c,tmp; while(kt!=0) { c=Pop(Q); Push(K,c); kt--; } tmp=Pop(Q); cout<<"\nPhan tu thu "<<n<<"= "<<tmp; cout<<"\nban 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<<"\n\n\nDoi voi danh sach luu tru bang con tro, DSLK doi"; Queue B; Create(B); Add(B); cout<<"\nHang Doi sau khi nhap:"; Display(B); cout<<"\nSo phan tu cua Hang Doi= "<<Count(B); Display(B); cout>n; XemPTn(B,n); Display(B); cout>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<<"\n\n\nDoi voi danh sach luu tru bang con tro, DSLK doi"; Stack B; Create(B); Add(B); cout<<"\nNgan xep sau khi nhap:"; Display(B); cout<<"\nNgan 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 5