Cau Truc Du Lieu
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Cau Truc Du Lieu as PDF for free.
More details
- Words: 6,588
- Pages: 34
Trang 1
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 1 DANH SÁCH LIÊN KẾT ĐƠN #include #include #include<stdlib.h> typedef struct Node { };
Phần định nghĩa danh sách liên kết đơn. Danh sách lưu các số nguyên. Nếu muốn lưu dữ liệu khác thì ta định nghĩa lại. Ví dụ muốn thông tin về sinh viên thì ta định nghĩa như sau: typedef struct Node {
int data; Node *next;
char ten[50]; char que[20]; float diemTB; Node *next;
}; void themdau(Node *&L, int x) { //buoc 1 Node *p=new Node; Thêm 1 phần tử giá trị x vào đầu danh sách L. p->data=x; p->next=L; 1. Tạo node mới p và gán dữ liệu x vào p và gắn L vào sau p // buoc 2 2. Cho L trỏ đến p L=p; } void duyet(Node *L) In nội dung danh sách được trỏ bởi L { Cho P trỏ đến L. Node *p=L; Trong khi P khác rỗng thì { in nội dung của P và cho P trỏ đến nốt sau P }. cout<<"--->"; Lưu ý : Lệnh cout dùng để in, tương tự như lệnh printf while (p!=NULL) { cout<data<<"--> "; // nhớ có lệnh #include p=p->next; } cout<<" NULL"; } // tao danh sach lien ket gom co n node void taods(Node *&L, int n) Đoạn lệnh bên thực hiện việc tạo ra danh sách { gồm có n nốt. Hàm nhận đối số n là số nốt cần L=NULL; tạo, sau đó sẽ yêu cầu nhập n số để chèn vào. for(int i=1; i<=n; i++) Các nốt được chèn vào danh sách theo thứ theo { int x; thứ tự ngược, nghĩa là phần tử nào chèn vào cout<<"nhap so can them:"; cin>>x; trước sẽ ở cuối danh sách. themdau(L,x); } } void tao(Node *&L) { Đoạn lệnh bên thực hiện việc tạo ra danh sách L=NULL; int x; gồm các nốt khác 0. Khi nhập số 0 sẽ kết thúc do việc chèn. { cout<<"nhap so can them:"; cin>>x; if (x!=0)themdau(L,x); } while(x!=0); Hàm bên tính tổng giá trị các nốt trong danh } int tong(Node *L) sách liên kết. { Thuật toán int t=0; Node *p=L; 1. Cho t=0 và con trỏ P trỏ đầu danh sách while (p!=NULL) { 2. Trong khi p khác rỗng thì cộng giá trị hiện tại t=t+p->data; p=p->next; của P vào t và cho p trỏ đến nốt kế tiếp } return t; 3. Trả về giá trị của t } [email protected]
Trang 2
Bài tập Cấu trúc dữ liệu và thuật toán
void main() // hàm main gọi lại các hàm đã định nghĩa ở trên. { Node *L=NULL; //int n; cout<<"\n nhap so not can tao:"; cin>>n; Có thể gọi hàm tạo n nốt hoặc //taods(L,n); gọi hàm tạo như bên. tao(L); cout<<"\n Noi dung danh sach:\n"; duyet(L); cout<<"\n tong cac so="<
!!! Mỗi dòng include viết trên 1 dòng như bài 1
Ví dụ 2
#include #include #include<stdio.h> #include<stdlib.h> typedef struct Node { int data; Node *next; }; Node *L; void themdau(Node *&L, int x) { Node *p=new Node; p->data=x; p->next=L; L=p; } void duyet(Node *L) { Node *p=L; cout<<"--->"; while (p!=NULL) { cout<data<<"--> "; p=p->next; } cout<<" NULL"; Thuật toán chèn nút có giá trị x vào vị trí k trong danh } sách Các trường hợp có thể xảy ra: void tao(Node *&L) Nếu k< 1 thì không chèn được { Nếu như k=1 thì tương ứng với chèn nút x vào đầu danh L=NULL; sách int x; Nếu k lớn hơn 1 thì cho con trỏ p trỏ đến nút k -1 do Nếu p rỗng thì báo là ko chèn được { Ngược lại thì tạo một nút mới và gắn liền sau p. cout<<"nhap so can them:"; cin>>x; if (x!=0) themdau(L,x); } while(x!=0);
} void chenthuk(Node *&L, int x, int k) { if (k<1) printf("\n vi tri chen ko hop le!"); else if (k==1){ Node *t=new Node; t->data=x; t->next=L; L=t; } else // k>1 { int vt=1; Node *p=L; while (p!=NULL && vtnext;} if (p==NULL) printf("\n Vi tri chen khong hop le!"); else // chen not t sau p { Node *t=new Node; t->data=x; t->next= p->next; p->next=t; } } }
[email protected]
Trang 3
Bài tập Cấu trúc dữ liệu và thuật toán
void inthuk(Node *L, int k) { Thuật toán in nút thứ k (k>0). int vt=1; Cho con trỏ p trỏ đầu danh sách và vt=1; Node *p=L; Nhảy đến nốt thứ k trong danh sách while (p!=NULL && vtnext; } if (p==NULL || vt!=k) printf("\n Vi tri in khong hop le!"); else printf("\n Not thu %d co gia tri la:%d",k,p->data); } void xoathuk(Node *&L,int k) Thuật toán xóa nốt thứ k { Nếu k <1 hoặc danh sách rỗng if (k<1|| L==NULL) thì không xóa được do vị trí xóa printf("\n vi tri xoa ko hop le!"); không hợp lệ else Nếu k=1 thì xóa phần tử đầu if (k==1) tiên { Nếu k>1 thì cho p trỏ đến nút Node *q=L; L=L->next; delete q; thứ k -1. Nếu như p rỗng hoặc } nút sau p (nút thứ k) rỗng thì else // k>1 báo không xóa được ngược lại { thì xóa nút sau p. int vt=1; Node *p=L; while (p!=NULL && vtnext; } if (p==NULL|| p->next==NULL) printf("\n Vi tri xoa khong hop le!"); else { Node *q= p->next; p->next=q->next; delete q; } } } void main() { clrscr(); L=NULL; tao(L); cout<<"\n Noi dung danh sach:\n"; duyet(L); int k; printf("\nhap vi tri not can in:"); scanf("%d", &k); inthuk(L,k); chenthuk(L,100,4); cout<<"\n Noi dung danh sach sau khi chen 100 vao vt thu 4:\n"; duyet(L); xoathuk(L,3); cout<<"\n Noi dung danh sach sau khi xoa pt thu 3:\n"; duyet(L); getch(); }
[email protected]
Trang 4
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 3 #include #include #include<stdio.h> #include<stdlib.h> typedef struct Node { int data; Node *next; }; // khai bao L la danh sach lien ket Node *L; void duyet(Node *L) { Node *p=L; cout<<"--->"; while (p!=NULL) { cout<data<<"--> "; p=p->next; } cout<<" NULL"; Thuật toán tạo danh sách liên kết đơn, thứ tự các nút trong } danh sách đúng với thứ tự nhập vào. void tao1(Node *&L) Danh sách được quản lý bởi hai con trỏ đầu và cuối. Ban đầu { khi thêm một phần tử vào danh sách, con trỏ đầu và cuối đều Node *dau=NULL,*cuoi=NULL; trỏ đến nút vừa được tạo. Các phần tử được thêm vào sau đều int x; được thêm vào sau con trỏ cuối. Sau cùng gán L= con trỏ đầu do { cout<<"nhap so can them:"; cin>>x; if (x!=0) { Node *p=new Node; p->data=x; p->next=NULL; if (dau==NULL) dau=cuoi=p; else {cuoi->next=p; cuoi=p;} } } while(x!=0); L=dau; } Sắp xếp các giá trị trong danh sách theo thứ tự tăng dần. void sapxep(Node *&L) Vị trí các nút không thay đổi nhưng thay đổi giá trị trong các nút { Node *p=L; while (p!=NULL) { Node *q=p->next; while (q!=NULL) { if (p->data>q->data) { int t=p->data; p->data= q->data ; q->data=t;} q=q->next; } Cho trước danh sách L đã có thứ tự tăng dần. Chèn nốt có giá trị x p=p->next; vào danh sách sao cho danh sách cũng tăng dần. } Nếu danh sách rỗng hoặc phần tử đầu tiên trong danh sách có giá } trị > x thì chèn vào đầu danh sách, ngược lại thì cho con trỏ p trỏ đến nốt mà nốt sau nó (q) có giá trị > x hoặc q = NULL và chèn void chentang(Node *&L, int x) nốt t vào giữa vị trí p và q { Node *t, *p,*q; if (L==NULL|| L->data>=x) { t=new Node; t->data=x; t->next=L; L=t;} else { p=L; q=p->next; while (q!=NULL && q->data<x) { p=q; q=q->next;} t=new Node; t->data=x; t->next=q; p->next=t; } }
[email protected]
Trang 5
Bài tập Cấu trúc dữ liệu và thuật toán
void main() { clrscr(); L=NULL; tao1(L); cout<<"\n Noi dung danh sach:\n"; duyet(L); sapxep(L); cout<<"\n Noi dung danh sach sau khi sap xep:\n"; duyet(L); int x; cout<<"\nnhap gia x can chen:"; cin>>x; chentang(L,x); cout<<"\n Noi dung danh sach sau khi chen gia tri x:\n"; duyet(L); getch(); }
Ví dụ 4 #include #include #include<stdio.h> #include<stdlib.h> typedef struct Node { int data; Node *next; }; void chentangkotrung(Node *&L, int x) { Node *t=new Node; t->data=x; t->next=NULL; if (L==NULL) L=t; else if (L->data>x) { t->next=L; L=t; } else if (L->data==x) cout<<" Da co trong danh sach \n"; else { Node *p=L, *q=L->next; while (q!=NULL && q->data<x) { p=q; q=q->next;} if (q!=NULL && q->data==x) cout<<"\n Da co trong danh sach\n"; else { t->next=q; p->next=t; } } } void chentangdq(Node *&L, int x) { if (L==NULL|| L->data>=x) { Node *t=new Node; t->data=x; t->next=L; L=t;} else chentangdq(L->next,x); } void chentangkotrungdq(Node *&L, int x) { if (L==NULL|| L->data>x) { Node *t=new Node; t->data=x; t->next=L; L=t;} else if (L->data==x) cout<<"\n da co gia tri "<<x<<" trong danh sach"; else chentangdq(L->next,x); }
[email protected]
Trang 6
Bài tập Cấu trúc dữ liệu và thuật toán void taotangkotrung(Node *&L) { L=NULL; int x; do { cout<<"nhap so can them:"; cin>>x; if (x!=0) chentangkotrung(L,x); } while(x!=0); /* int i,n,x; cout<<"nhap so phan tu can them:"; cin>>n; for(i=1; i<=n; i++) { cout<<" nhap so thu "<<<":"; cin>>x; chentangkotrung(L,x); } */ } void inds(Node *L) { Node *p=L; cout<<"------>"; while (p!=NULL) { cout<< p->data <<"--> "; p=p->next; cout<<" NULL"; } void tron(Node *&L, Node *L1, Node *L2) // trộn 2 danh sách L1 và L2, kết quả được đưa vào L { Node *p=L1, *q=L2; L=NULL; while(p!=NULL) { chentangdq(L, p->data); p=p->next;} while(q!=NULL) { chentangdq(L, q->data); q=q->next;} } void main() { clrscr(); Node *L1=NULL; cout<<"\n Tao danh cout<<"\n Noi dung inds(L1); Node *L2=NULL; cout<<"\n Tao danh cout<<"\n Noi dung inds(L2); Node *L=NULL; tron(L,L1,L2); cout<<"\n Noi dung inds(L); getch();
sach L1:\n"; taotangkotrung(L1); danh sach L1:\n"; sach L2:\n"; taotangkotrung(L2); danh sach L2:\n";
danh sach L = L1 + L2:\n";
}
[email protected]
}
Trang 7
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 5
MỘT SỐ THAO TÁC XỬ LÝ TRÊN DANH SÁCH LIÊN KẾT ĐƠN
#include<stdio.h> #include<stdlib.h> #include #include<math.h> #include<string.h> //dinh nghia mot phan tu trong danh sach lien ket don. typedef struct Node { int data; Node *next; }; // nhap du lieu cho danh sach, viec nhap dung khi nhap so =0 void nhap_ds(Node *&L) { int x; Node *t,*cuoi; cuoi=L=NULL; int dung=0; while(dung==0) { printf("nhap vao mot so:");scanf("%d",&x); if(x==0) dung=1; // neu nhap so 0 thi ket thuc else // neu so khac 0 thi them vao danh sach { t=new Node; // tao not moi de chua so vua nhap t->data=x; t->next=NULL; if(L==NULL) // neu ds chua co pt nao thi them vao dau { L=t; cuoi=t; } else // neu co roi thi them vao cuoi { cuoi->next=t; cuoi=t;} } } } void taotang(Node *&L) // TẠO DANH SÁCH CHỨA CÁC GIÁ TRỊ TĂNG(TRÙNG HOẶC KHÔNG) L=NULL; int x; do { cout<<"nhap so can them:"; cin>>x; if (x!=0) { Node *t=new Node; t->data=x; t->next=NULL; if (L==NULL) L=t; else if (xdata) { t->next=L; L=t;} else { Node *p=L; Node *q=p->next; while (q!=NULL && q->data<x) { p=q; q=q->next;} //if (q==NULL||q->data!=x) // co dong nay thi ko trung { p->next=t; t->next=q; } } } } while(x!=0); }
[email protected]
Trang 8
Bài tập Cấu trúc dữ liệu và thuật toán // thu tuc hien thi noi dung danh sach void in_ds(Node *L) { Node *p=L; if (p==NULL) printf("\n Day la danh sach rong!!!"); else { printf("\nNoi dung danh sach:\n"); printf("===>"); while(p!=NULL) { printf("%d--->",p->data); p=p->next; } printf("NULL"); } } // dat cac gia tri Âm trong danh sach vỀ gia tri 99 void dat_99(Node *&L) { Node *p=L; while(p!=NULL) { if (p->data<0) p->data=99; p=p->next; } printf("\n Da thu hien xong!!!"); } // dem so phan tu cua danh sach L int dem_pt(Node *L) { int dem=0; Node *p=L; while(p!=NULL) { dem++; p=p->next; } return dem; } // dem so phan tu trong danh sach lien ket theo phuong an de qui int dem_ptdq(Node *&L) { if (L==NULL) return 0; else return 1 + dem_ptdq(L->next); }
// dem so phan tu co gia tri x trong danh sach int dem_pt_x(Node *L,int &x) { int dem=0; Node *p=L; while(p!=NULL) { if(p->data==x) dem++; p=p->next; } return dem; } // dem so phan tu co gia tri x trong danh sach theo phuong an de qui
[email protected]
Trang 9
Bài tập Cấu trúc dữ liệu và thuật toán
int dem_pt_xdq(Node *L,int &x) { if (L==NULL) return 0; else if (L->data==x) return 1+ dem_pt_xdq(L->next,x); else return dem_pt_xdq(L->next,x); } //tinh tong cac node co gia tri la boi cua x trong danh sach int tong_boi_x(Node *L,int &x) { Node *p=L; int tong=0; if (x==0) printf("Khong tinh duoc boi cua 0!!!"); else while(p!=NULL) { if(p->data%x==0) tong=tong+p->data; p=p->next; } return tong; } // tinh tong cac not co gia tri la boi cua x theo phuong an de qui int tong_boi_xdq(Node *L,int &x) { if (x==0) { printf("Khong tinh duoc boi cua 0!!!"); return 0; } else if (L==NULL) return 0; else if (L->data%x==0) return L->data+tong_boi_xdq(L->next,x); else return tong_boi_xdq(L->next,x); } //kiem tra trong danh sach co phan tu x hay khong int kiem_tra_x(Node *L,int &x) { Node *p=L; int yes=0; while(p!=NULL && yes==0) if(p->data==x) yes=1; else p=p->next; return yes; } //kiem tra trong danh sach co phan tu x hay khong theo phuong an de qui int kiem_tra_xdq(Node *L,int &x) { if (L==NULL) return 0; else if (L->data==x) return 1; else return kiem_tra_xdq(L->next,x); } //tim phan phu x co trong danh sach hay khong, neu co thi in vi tri cua x void tim_x(Node *L,int &x) { Node *p=L; int yes=0,vt=0; while(p!=NULL && yes==0) { vt++; if(p->data==x) yes=1; else p=p->next;
[email protected]
Trang 10
Bài tập Cấu trúc dữ liệu và thuật toán
} if(yes==1) printf("\n Co gia tri %d trong danh sach o vi tri %d!!!",x,vt); else printf("\n Khong co gia tri %d trong danh sach!!!",x); } // tim phan phu x co trong danh sach hay khong, neu co thi in vi tri cua x void tim_xdq(Node *L,int x, int &vt) { if (L==NULL) printf("\n Khong co gia tri %d trong danh sach!!!",x); else if (L->data==x) printf("\n Co gia tri %d trong danh sach o vi tri %d!!!",x,vt); else { vt++; tim_xdq(L->next,x,vt);} } // cho con tro p tro den phan tu thu k trong danh sach void nhayden_k(Node *&L, int k,Node *&p) { p=NULL; if(k<1) printf("Khong the nhay den vi tri <1 ?!"); else if (L==NULL) printf("Danh sach rong, khong the nhay !!!"); else { int vt=1; p=L; while (p!=NULL && vtnext; vt++; } if (p==NULL) printf("\n Danh sach khong du %d phan tu !!!",k); else printf("\n Gia tri phan tu thu %d = %d",k,p->data); } } // xoa phan tu dau danh sach void xoapt_dau(Node *&L) { if (L==NULL) printf("\n Danh sach rong, khong the xoa!!!"); else L=L->next; } // xoa phan tu cuoi danh sach void xoapt_cuoi(Node *&L) { if (L==NULL) printf("\n Danh sach rong, khong the xoa!!!"); else if( L->next==NULL) L=NULL; else { Node *q=L,*p=q->next; while(p->next!=NULL) { q=p; p=p->next; } q->next=NULL; } } // xoa phan tu cuoi danh sach theo phuong an de qui void xoapt_cuoidq(Node *&L) { if (L==NULL) printf("\n Danh sach rong, khong the xoa!!!"); else if( L->next==NULL) L=NULL; else xoapt_cuoidq(L->next); }
[email protected]
Trang 11
Bài tập Cấu trúc dữ liệu và thuật toán
//xoa phan tu sau con tro P trong danh sach void xoapt_s_p(Node *&L,Node *p) { if (L==NULL) printf("\nDanh sach rong, khong the xoa!!!"); else if(p->next==NULL) printf("\nKhong the xoa phan tu NULL"); else { Node *q=L; while(q!=NULL && q!=p) q=q->next; if (q==NULL) printf("\n Khong ton tai con tro p trong danh sach"); else { q=p->next; p->next=q->next; } } } //xoa phan tu truoc con tro P trong danh sach void xoapt_t_p(Node *&L,Node *p) { if (L==NULL) printf("\nDanh sach rong, khong the xoa!!!"); else if (p==L) printf("Khong co phan tu truoc de xoa!!!"); else if (L->next==p) L=L->next; else { Node *q=L; while(q!=NULL && q->next!=p) q=q->next; if (q==NULL) printf("\nkhong ton tai con tro p trong danh sach"); else { Node *w=L; while(w->next!=q) w=w->next; w->next=p; } } } // xoa phan tu co gia tri x trong danh sach void xoadq(Node *&L,int x) { if (L==NULL) printf("\n khong co gia tri % trong danh sach!",x); else if (L->data==x) { // Node *p=L; L=L->next; delete p; L=L->next; } else xoadq(L->next,x); } // xoa tat ca cac phan tu co gia tri x trong danh sach void xoahetdq(Node *&L,int x) { if (L!=NULL) { if (L->data==x) { L=L->next; xoahetdq(L,x); } // { Node *p=L; L=L->next; delete p; } else xoahetdq(L->next,x); } }
[email protected]
Trang 12
Bài tập Cấu trúc dữ liệu và thuật toán
// kiem tra danh sach co tang dan hay khong int tangdan(Node *&L) { Node *p=L; if(p==NULL||p->next==NULL) return 1; else { Node *q=p->next; int yes=1; while(q!=NULL && yes==1) if(p->data> q->data) yes=0; else { p=q; q=q->next;} return yes; } } // sap xep danh sach tang dan void sapxep(Node *&L) { Node *p,*q; p=L; while (p!=NULL) { q=p->next; while(q!=NULL) { if(p->data>q->data) { int t=q->data; q->data=p->data; p->data=t; } q=q->next; } p=p->next; } } // chen not co gia tri x vao danh sach tang dan o vi tri thich hop void chentang(Node *&L,int x) { Node *t=new Node; t->data=x; t->next=NULL; if (L==NULL) L=t; else if (L->data>=x) { t->next=L; L=t;} else { Node *P=L; while (P!=NULL && P->data<x) P=P->next; Node *Q=L; while (Q->next!=P) Q=Q->next; Q->next=t; t->next=P; } } // tao danh sach lien ket vong TỪ DANH SÁCH LIÊN KẾT ĐƠN void taovong(Node *&L) { Node *P=L; if (P==NULL) printf("\Khong the tao vong danh sach lien ket rong!"); else while (P->next!=NULL) P=P->next; P->next=L; } // noi danh sach L2 vao sau L1
[email protected]
Trang 13
Bài tập Cấu trúc dữ liệu và thuật toán void noi2danhsach(Node *&L1, Node *&L2) // NỐI L2 VÀO SAU L1 { Node *P=L1; if (L1==NULL) L1=L2; else { while (P->next!=NULL) P=P->next; P->next=L2; } } // in cac gia tri trong L1 nhung khong co trong L2 void inkhongtrung(Node *&L1, Node *&L2) { Node *P=L1; while(P!=NULL) { Node *Q=L2; int yes=1; while (Q!=NULL && yes==1) if (P->data=Q->data) yes=0; else Q=Q->next; if( yes==1) printf("%5d", P->data) ; P=P->next; } } void main() { int x; Node *l,*l1,*l2,*p,*q; // clrscr(); nhap_ds(l); in_ds(l); if (tangdan(l)==1) printf("\nDanh sach tang dan!"); else printf("\nDanh sach khong tang dan!"); /* sapxep(l); printf("\nNoi dung danh sach sau khi sap xep:"); in_ds(l); if (tangdan(l)==1) printf("\nDanh sach tang dan!"); else printf("\nDanh sach khong tang dan!"); nhayden_k(l,2,p); xoapt_s_p(l,p); in_ds(l); */ printf("\n nhap gia tri x:"); scanf("%d",&x); xoahetdq(l,x); printf("\nNoi dung danh sach sau xoa phan tu x:"); in_ds(l); getch(); }
[email protected]
Trang 14
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 6
DANH SÁCH LIÊN KẾT VÒNG
#include #include #include<stdio.h> #include<stdlib.h> typedef struct CNode { int data; CNode *next; }; // khai báo L la danh sách liên kết vòng CNode *L; // tao danh sach lien ket vong void taodsv(CNode *&L) { // buoc 1 CNode *dau=NULL,*cuoi=NULL; int x; do { cout<<"nhap so can them:"; cin>>x; if (x!=0) { CNode *p=new CNode; p->data=x; p->next=NULL; if (dau==NULL) dau=cuoi=p; else {cuoi->next=p; cuoi=p;} } } while(x!=0); L=dau; // buoc 2 cuoi->next=L; } void duyetv(CNode *L) // hiển thị nội dung danh sách liên kết vòng { CNode *p=L; cout<<"--->"; if(L==NULL) cout<<"\n danh sach rong!"; else do { cout<data<<"--> "; p=p->next; } while (p!=L); } int timxv(CNode *L, int x) //kiểm tra giá trị x có trong danh sách { if(L==NULL) return 0; else { CNode *p=L; int yes=0; do { if (p->data==x) {yes=1; break;} else p=p->next; } while (p!=L); return yes; } }
[email protected]
Trang 15
Bài tập Cấu trúc dữ liệu và thuật toán void main() { L=NULL; int x; taodsv(L); cout<<"\n Noi dung danh sach:\n"; duyetv(L); cout<<"\n nhap gia tri can tim:"; cin>>x; if (timxv(L,x)==1) cout<<"\n Co gia tri x trong danh sach"; else cout<<"\n Khong co gia tri x trong danh sach"; getch(); }
Ví dụ 7
THÁP HÀ NỘI VÀ DÃY FIBONANCY
#include #include #include<stdlib.h> void thaphn1(int n, char a, char b, char c) { if(n==1) cout<<"\n chuyen 1 dia tu cot "<>n; thaphn1(n,'A','B','C'); getch(); } #include #include long fib(int n) { if(n==0||n==1) return 1; else return fib(n-1)+fib(n-2); } void lietkefib(int n) { long f0=1,f1=1,f; for(int i=0; i<=n; i++) { cout<
#include<stdlib.h>
} void main() { int n; clrscr(); cout<<"\n nhap n:"; cin>>n; //cout<<"\n phan tu thu n ( 0-->n) cua day la:"<
[email protected]
Trang 16
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 8
DANH SÁCH LIÊN KẾT ĐÔI
#include #include #include<stdlib.h> typedef struct DNode { int data; DNode *next, *prev;}; void taodsd(DNode *&L) { int x; DNode *t,*dau,*cuoi; L=NULL; dau=cuoi=NULL; do { cout<<"nhap mot so:"; cin>>x; if (x!=0) { t=new DNode; t->data=x; t->next=t->prev=NULL; if (dau==NULL) dau=cuoi=t; else { cuoi->next=t; t->prev=cuoi; cuoi=t;} } } while (x!=0); L=dau; } void indsd(DNode *L) { DNode *p=L; while(p!=NULL) { cout<<" "<< p->data; p=p->next;} } int timxdsd(DNode *L, int x) { int yes=0; DNode *p=L; while (p!=NULL&& yes==0) if (p->data==x) yes=1; else p=p->next; return yes; } int timx1dsd(DNode *L, int x) { DNode *p=L; int vt=1; while (p!=NULL&& p->data!=x) if (p==NULL) return 0; else return vt; }
{ p=p->next; vt++; }
int demx1dsd(DNode *L, int x) { DNode *p=L; int dem=0, vt=1;; while (p!=NULL) { if (p->data==x) { dem++; cout<<"\n co gia tri x tai vi tri "<next; vt++; } return dem; } [email protected]
Trang 17
Bài tập Cấu trúc dữ liệu và thuật toán
void main() { DNode *L; clrscr(); taodsd(L); indsd(L); int x; cout<<"\n nhap gia tri x can tim:"; cin>>x; int k= timx1dsd(L,x); if (k==0) cout<<"\n khong co gia tri "<<x<<" trong danh sach"; else cout<<"\n co gia tri "<<x<<" trong danh sach o vi tri "<
Ví dụ 9
CHÈN XÓA CÁC NỐT TRÊN DANH SÁCH LIÊN KẾT ĐÔI
#include #include #include<stdlib.h> typedef struct DNode { int data; DNode *next, *prev;}; void chenkdsd(DNode *&L,int k, int x) { if(k<1) cout<<"\n khong chen duoc"; else { if (k==1) // xoa phan tu dau tien { DNode *t= new DNode; t->data=x; t->next=t->prev=NULL; if (L==NULL) L=t; else { t->next=L; L->prev=t; L=t; } } else // k> 1 { // cho p tro den not thu k-1 int vt=1; DNode *p=L; while(p!=NULL && vtnext; vt++; } if(p==NULL) cout<<" \n Khong chen duoc"; else // chen sau p { DNode *t= new DNode; t->data=x; t->next=t->prev=NULL; t->next=p->next; if (p->next!=NULL) p->next->prev=t; p->next=t; t->prev=p; } } } } void indsd(DNode *L) { DNode *p=L; while(p!=NULL) { cout<<" }
"<< p->data;
[email protected]
p=p->next; }
Trang 18
Bài tập Cấu trúc dữ liệu và thuật toán void xoakdsd(DNode *&L,int k) { if(k<1|| L==NULL) cout<<"\n khong xoa duoc"; else { if (k==1) // xoa phan tu dau tien { DNode *q=L; L=L->next; if (L!=NULL) L->prev=NULL; delete q; } else // k> 1 va L<>NULL { // cho p tro den not thu k int vt=1; DNode *p=L; while(p!=NULL && vtnext; vt++; }
}
if(p==NULL) cout<<" \n Danh sach khong du k phan tu"; else // xoa phan tu duoc tro boi p { p->prev->next=p->next; if (p->next!=NULL) p->next->prev= p->prev; delete p; }
}
} void taodsd(DNode *&L) { int x; DNode *t,*dau,*cuoi; L=NULL; dau=cuoi=NULL; do { cout<<"nhap mot so:"; cin>>x; if (x!=0) { t=new DNode; t->data=x; t->next=t->prev=NULL; if (dau==NULL) dau=cuoi=t; else { cuoi->next=t; t->prev=cuoi; cuoi=t;} } } while (x!=0); L=dau; } void main() { DNode *L; clrscr(); taodsd(L); cout<<"\n danh sach vua nhap:\n"; indsd(L); int k; cout<<"\n nhap vi tri can chen:"; cin>>k; chenkdsd(L, k,100); cout<<"\n danh sach sau khi chen 100 vao vi tri k:\n"; indsd(L); getch(); }
[email protected]
Trang 19
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 10
CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
#include #include #include<stdlib.h> #define MAXSIZE 1000 typedef struct Stack1 {
int a[MAXSIZE+1]; int top;
}; void CreateS(Stack1 &S) { S.top=0; } int EmptyS(Stack1 S) { if (S.top==0) return 1; else return 0; } void PushS(Stack1 &S,int x) { S.top=S.top+1; S.a[S.top]=x; } void PopS(Stack1 &S,int &x) { if (S.top>0) {x=S.a[S.top]; S.top=S.top-1;} else cout<<"\Danh sach rong,khong lay duoc!"; } int TopS(Stack1 S) { if (S.top>0) return S.a[S.top]; else {cout<<"\n ngan xep rong"; return 0;} } void main() { Stack1 S; CreateS(S); int i,x; for(i=1; i<=5; i++) { cout<<"nhap so thu "<<<":"; cin>>x; PushS(S,x); } cout<<"\n Cac so vua them vao ngan xep: "; while (!EmptyS(S)) { PopS(S,x); cout<<x<<" "; } getch(); }
[email protected]
Trang 20
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 11
ỨNG DỤNG NGĂN XẾP
PHÂN TÍCH SỐ N SANG HỆ NHỊ PHÂN và IN ĐẢO
#include #include #include<stdlib.h> #define MAXSIZE 1000 typedef struct Stack1 { int a[MAXSIZE+1]; int top; }; void CreateS(Stack1 &S) { S.top=0; } int EmptyS(Stack1 S) { if (S.top==0) return 1; else return 0; } void PushS(Stack1 &S,int x) { S.top=S.top+1; S.a[S.top]=x; } void PopS(Stack1 &S,int &x) { if (S.top>0) {x=S.a[S.top]; S.top=S.top-1;} else cout<<"\Danh sach rong,khong lay duoc!"; } void bieudiennhiphan(int n) { Stack1 S; CreateS(S); int x; while(n>0) { x=n%2; PushS(S,x); n=n/2; } while (!EmptyS(S)) { PopS(S,x); cout<<x<<" "; } } void dao(int n) { Stack1 S; CreateS(S); int x; while(n>0) { x=n%10; PushS(S,x); n=n/10; Stack1 t; CreateS(t); // bo vao ngan xep tam while (!EmptyS(S)) { PopS(S,x); PushS(t,x); } // lay ra tu ngan xep tam de in while (!EmptyS(t)) { PopS(t,x); cout<<x; } }
}
void main() { int n; cout<<"\nnhap so nguyen can bieu dien sang nhi phan:"; cin>>n; bieudiennhiphan(n); cout<<"\n So n in theo chieu nguoc la:”; dao(n); getch(); }
[email protected]
Trang 21
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 12
CÀI ĐẶT NGĂN XẾP BẰNG CON TRỎ, IN ĐẢO SỐ NGUYÊN N
#include typedef struct Stack
#include {
#include<stdlib.h>
int data; Stack *next;
}; void CreateS(Stack *&S) { S=NULL; } int EmptyS(Stack *S) { if (S==NULL) return 1; else return 0; } void PushS(Stack *&S,int x) { Stack *t=new Stack; t->data=x; t->next=S; S=t; } void PopS(Stack *&S,int &x) { if (S==NULL) cout<<"\Ngan xep rong,khong lay duoc!"; else { x=S->data; Stack *q=S; S=S->next; delete q; } } int TopS(Stack *S) { if (S==NULL) {cout<<" \n Ngan xep rong"; return 0; } else return S->data; } void dao(int n) { Stack *S; CreateS(S); int x; while(n>0) { x=n%10; PushS(S,x); n=n/10; } Stack *t; CreateS(t); // bo vao ngan xep tam while (!EmptyS(S)) { PopS(S,x); PushS(t,x); } while (!EmptyS(t)) { PopS(t,x); cout<<x; } } void main() { int n; cout<<"\nnhap so nguyen can dao:"; cin>>n; dao(n); getch(); } [email protected]
Trang 22
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 13
IN PHẦN TỬ THỨ K CỦA NGĂN XẾP
#include #include #include<stdlib.h> typedef struct Stack { int data; Stack *next; }; void CreateS(Stack *&S) { S=NULL; } int EmptyS(Stack *S) { if (S==NULL) return 1; else return 0; } void PushS(Stack *&S,int x) { Stack *t=new Stack; //data info || next link t->data=x; t->next=S; S=t; } void PopS(Stack *&S,int &x) { if (S==NULL) cout<<"\Ngan xep rong,khong lay duoc!"; else { x=S->data; Stack *q=S; S=S->next; delete q; } } int TopS(Stack *S) { if (S==NULL) {cout<<" \n Ngan xep rong"; return 0; } else return S->data; } void inthuk(Stack *S, int k) { //1 Stack *T=NULL; int x, vt=0; while ((!EmptyS(S))&& vt>k; inthuk(S,k); getch(); } [email protected]
Trang 23
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 14
ỨNG DỤNG NGĂN XẾP KIỂM TRA CHUỖI () CHUẨN
#include #include #include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Stack { char data; Stack *next; Tham khảo ví dụ 19 }; void CreateS(Stack *&S) (không dùng stack) { S=NULL; } int EmptyS(Stack *S) { if (S==NULL) return 1; else return 0; } void PushS(Stack *&S,char x) { Stack *t=new Stack; //data info || next link t->data=x; t->next=S; S=t; } void PopS(Stack *&S,char &x) { if (S==NULL) cout<<"\Ngan xep rong,khong lay duoc!"; else { x=S->data; Stack *q=S; S=S->next; delete q; } } int kiemtrachuan(char *st) { // b1 Stack *S=NULL; char x; // b2 for(int i=0; i<strlen(st); i++) { if (st[i]=='(') PushS(S,st[i]); else if (st[i]==')') if (EmptyS(S)) return 0; else PopS(S,x); else return 0; // cac ky tu khac {'(', ')'} } // b3 if (EmptyS(S)) return 1; else return 0; } void main() { char st[100]; clrscr(); cout<<"\n nhap chuoi can kiem tra:"; gets(st); if(kiemtrachuan(st)==1) cout<<"\n day la chuan"; else cout<<"\n khong phai chuoi chuan"; getch(); } [email protected]
Trang 24
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 15
CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
#include #include #include<stdlib.h> #define MAXSIZE 1000 typedef struct Queue {
int a[MAXSIZE+1]; int head,tail;
}; void CreateQ(Queue &Q) { Q.head=0; Q.tail=0; } int EmptyQ(Queue Q) { if (Q.head==0 && Q.tail==0) return 1; else return 0; } void AddQ(Queue &Q, int x) { if (EmptyQ(Q)) { Q.head=Q.tail=1; Q.a[Q.tail]=x;} else { Q.tail++; Q.a[Q.tail]=x;} } void RemoveQ(Queue &Q, int &x) { if (EmptyQ(Q)) cout<<"\n hang doi rong!:"; else { x=Q.a[Q.head]; if (Q.head==Q.tail) Q.head=Q.tail=0; else Q.head++; } } void main() { Queue q; CreateQ(q); //AddQ(q,3);
AddQ(q,2);
AddQ(q,7);
AddQ(q,6);
int x,n; cout<<"nhap so phan tu can them:"; cin>>n; for(int i=1; i<=n; i++) { cout<<"\n nhap so thu "<<<":"; cin>>x; AddQ(q,x); } while(!EmptyQ(q)) { RemoveQ(q,x); cout<<x<<" "; } getch(); }
[email protected]
AddQ(q,9);
Trang 25
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 16
ỨNG DỤNG HÀNG ĐỢI, IN ĐẢO SỐ NGUYÊN N
#include #define MAXSIZE 1000 typedef struct Queue
#include<stdlib.h> {
int a[MAXSIZE+1]; int head,tail;
}; void CreateQ(Queue &Q) { Q.head=0; Q.tail=0; } int EmptyQ(Queue Q) { if (Q.head==0 && Q.tail==0) return 1; else return 0; } void AddQ(Queue &Q, int x) { if (EmptyQ(Q)) { Q.head=Q.tail=1; Q.a[Q.tail]=x;} else { Q.tail++; Q.a[Q.tail]=x;} } void RemoveQ(Queue &Q, int &x) { if (EmptyQ(Q)) cout<<"\n hang doi rong!:"; else { x=Q.a[Q.head]; if (Q.head==Q.tail) Q.head=Q.tail=0; else Q.head++; } } void indao(int n) { Queue q; CreateQ(q); int x; while (n>0) { AddQ(q, n%10); n=n/10; } while(!EmptyQ(q)) { RemoveQ(q,x); cout<<x<<" "; } } void main() { int n; clrscr(); cout<<"nhap so nguyen duong n:"; cin>>n; cout<<"\n So n in nguoc la:"; indao(n); getch(); } [email protected]
Trang 26
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 17
CÀI ĐẶT HÀNG ĐỢI BẰNG CON TRỎ
#include #include #include<stdlib.h> typedef struct Node { int data; Node *next;}; typedef struct Queue { Node *head,*tail; }; void CreateQ(Queue &Q) { Q.head=NULL; Q.tail=NULL; } int EmptyQ(Queue Q) { if (Q.head==NULL && Q.tail==NULL) return 1; else return 0; } void AddQ(Queue &Q, int x) { Node *t=new Node; t->data=x; t->next=NULL; if (EmptyQ(Q)) Q.head=Q.tail=t; else { Q.tail->next=t; Q.tail=t;} } void RemoveQ(Queue &Q, int &x) { if (EmptyQ(Q)) cout<<"\n hang doi rong!:"; else { Node *z=Q.head; x=Q.head->data; if (Q.head==Q.tail) {Q.head=Q.tail=NULL;} else Q.head=Q.head->next; delete z; } } void indao(int n) { Queue q; CreateQ(q); int x; while (n>0) { AddQ(q, n%10); n=n/10; } while(!EmptyQ(q)) { RemoveQ(q,x); cout<<x<<" "; } } void main() { int n; clrscr(); cout<<"nhap so nguyen duong n:"; cin>>n; cout<<"\n So n in nguoc la:"; indao(n); getch(); } [email protected]
Trang 27
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 18
ỨNG DỤNG NGĂN XẾP VÀ HÀNG ĐỢI KIỂM TRA CHUỖI ĐỐI XỨNG
#include #include #include<stdlib.h> #include<stdio.h> #include<string.h> typedef struct Stack { char data; Stack *next; }; typedef struct Node { char data; Node *next;}; typedef struct Queue { Node *head,*tail; }; void CreateS(Stack *&S) { S=NULL; } int EmptyS(Stack *S) { if (S==NULL) return 1; else return 0; } void PushS(Stack *&S,char x) { Stack *t=new Stack; //data <=> info || next <=> link t->data=x; t->next=S; S=t; } void PopS(Stack *&S,char &x) { if (S==NULL) cout<<"\Ngan xep rong,khong lay duoc!"; else { x=S->data; Stack *q=S; S=S->next; delete q; } } void CreateQ(Queue &Q) { Q.head=NULL; Q.tail=NULL; } int EmptyQ(Queue Q) { if (Q.head==NULL && Q.tail==NULL) return 1; else return 0; } void AddQ(Queue &Q, char x) { Node *t=new Node; t->data=x; t->next=NULL; if (EmptyQ(Q)) Q.head=Q.tail=t; else { Q.tail->next=t; Q.tail=t;} } void RemoveQ(Queue &Q, char &x) { if (EmptyQ(Q)) cout<<"\n hang doi rong!:"; else { Node *z=Q.head; x=Q.head->data; if (Q.head==Q.tail) {Q.head=Q.tail=NULL;} else Q.head=Q.head->next; delete z; } }
[email protected]
Trang 28
Bài tập Cấu trúc dữ liệu và thuật toán int doixung(char *s) { Queue q; CreateQ(q); Stack *t; CreateS(t); for (int i=0; i<strlen(s); i++) { AddQ(q,s[i]); PushS(t,s[i]); } char x,y; while(!EmptyQ(q)) { RemoveQ(q,x); PopS(t,y);//cout<<"("<<x<<" , "<
"; getch();
void main() { int n; clrscr(); char s[100]; cout<<"nhap chuoi s:"; fflush(stdin); gets(s); if(doixung(s)==1) cout<<"Chuoi doi xung"; else cout<<"\n chuoi khong doi xung"; getch(); }
Ví dụ 19
KIỂM TRA CHUỖI CHUẨN HAY KHÔNG (KHÔNG DÙNG NGĂN XẾP)
#include #include #include<stdio.h> #include<string.h> #include<stdlib.h> int chuan(char *st) { // b1 int dem=0; // b2 for(int i=0; i<strlen(st); i++) { if (st[i]=='(') dem++; else if (st[i]==')') if (dem==0) return 0; else dem--; else return 0; // cac ky tu khac {'(', ')'} } // b3 if (dem==0) return 1; else return 0; } void main() { char st[100]; clrscr(); cout<<"\n nhap chuoi can kiem tra:"; gets(st); if(chuan(st)==1) cout<<"\n day la chuan"; else cout<<"\n khong phai chuoi chuan"; getch(); } [email protected]
Trang 29
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 20
CÂY NHỊ PHÂN
#include<stdio.h> #include #include<math.h> typedef struct Tree { int data; Tree *left,*right; }; // tao cay co gia tri goc la x, con trai la l, con phia la r Tree *cay(int x, Tree *l, Tree *r) { Tree *T=new Tree; T->data=x; T->left=l; T->right=r; return T; } // su dung ham cay de tao cay theo yeu cau T4 void taocayT4(Tree *&T) { Tree *a,*b,*c; a=cay(5, cay(8,NULL,NULL),cay(9,NULL,NULL)); b=cay(2,cay(4,NULL,NULL),a); c=cay(3,cay(6,NULL,NULL),cay(7,NULL,NULL)); T=cay(1,b,c); } void taocayT5(Tree *&T) { Tree *a,*b,*c; a=cay(8, cay(7,NULL,NULL),cay(13,NULL,NULL)); b=cay(6,cay(5,cay(1,NULL,NULL),NULL),a); c=cay(24,cay(20,NULL,NULL),cay(32,NULL,NULL)); T=cay(11,b,c); } // tao cay nhi phan co gia tri goc la x, con trai phai = NULL void nhapcay(Tree *&T,int x) { if(T==NULL) { Tree *q=new Tree; q->data=x; q->left=q->right=NULL; T=q; } else if(xdata) nhapcay(T->left,x); else if (x>T->data) nhapcay(T->right,x); else printf("da co gia tri nay trong cay:"); } void duyettientu(Tree *T) { if (T!=NULL) { printf("%5d",T->data); duyettientu(T->left); duyettientu(T->right); } } void duyettrungtu(Tree *T) { if (T!=NULL) { duyettrungtu(T->left); printf("%5d",T->data); duyettrungtu(T->right); } } [email protected]
Trang 30
Bài tập Cấu trúc dữ liệu và thuật toán void duyethautu(Tree *T) { if (T!=NULL) { duyethautu(T->left); duyethautu(T->right); printf("%5d",T->data); } } // duyệt hậu tự, khử đề qui void hautu(Tree *T) { int d[100], vt=0; Tree *m[100],*z; if (T=!NULL) {vt++; m[vt]=T;} while(vt>0) { if (d[vt]==1) { printf("%5d",m[vt]->data); vt=vt-1;} else { d[vt]=1; z=m[vt]; if (z->right!=NULL) { vt++; m[vt]=z->right;d[vt]=0;} if (z->left!=NULL) { vt++; m[vt]=z->left; d[vt]=0;} } } } // duyệt trung tự, khử đề qui void trungtu(Tree *T) { int d[100]; Tree *m[100],*z; int vt=0; if (T=!NULL) {vt++; m[vt]=T;} while(vt>0) { if (d[vt]==1) { printf("%5d",m[vt]->data); vt=vt-1;} else { z=m[vt]; vt=vt-1; if (z->right!=NULL) { vt++; m[vt]=z->right;d[vt]=0;} vt=vt+1; d[vt]=1; m[vt]=z; if (z->left!=NULL) { vt++; m[vt]=z->left; d[vt]=0;} } } } // duyệt trung tự, để khử đề qui void tientu(Tree *T) { Tree *m[100],*z; int vt=0; if (T=!NULL) {vt++; m[vt]=T;} while(vt>0) { z=m[vt]; printf("%5d",m[vt]->data); vt=vt-1; if (z->right!=NULL) { vt++; m[vt]=z->right;} if (z->left!=NULL) { vt++; m[vt]=z->left; } } } // tim gia tri lon nhat trong hai so
[email protected]
Trang 31
Bài tập Cấu trúc dữ liệu và thuật toán
int max(int a, int b) { if (a>b) return a; else return b; } // tinh chieu cao cua cay int chieucao(Tree *T) { if(T==NULL) return 0; else return 1+ max(chieucao(T->left),chieucao(T->right)); } // dem so not trong cay T int sonot(Tree *T) { if(T==NULL) return 0; else return 1+ sonot(T->left)+sonot(T->right); } // dem so not co gia tri le trong cay int sonotle(Tree *T) { if(T==NULL) return 0; else if (T->data%2==1) return 1+ sonotle(T->left)+sonotle(T->right); else return sonotle(T->left)+sonotle(T->right); } // tinh tong cac not co gia tri chan trong cay int tongchan(Tree *T) { if(T==NULL) return 0; else if (T->data%2==0) return T->data+ tongchan(T->left)+tongchan(T->right); else return tongchan(T->left)+tongchan(T->right); } // dem so la cua cay int demla(Tree *T) { if(T==NULL) return 0; else if (T->left==NULL && T->right==NULL) return 1+ demla(T->left)+demla(T->right); else return demla(T->left)+demla(T->right); } // dem so not co day du hai con int haicon(Tree *T) { if(T==NULL) return 0; else if (T->left!=NULL && T->right!=NULL) return 1+ haicon(T->left)+haicon(T->right); else return haicon(T->left)+haicon(T->right); } // dem so not co dung mot con int motcon(Tree *T) { if(T==NULL) return 0; else if ((T->left!=NULL && T->right==NULL)||(T->left==NULL && T->right!=NULL)) return 1; else return motcon(T->left)+motcon(T->right); }
[email protected]
Trang 32
Bài tập Cấu trúc dữ liệu và thuật toán
// tim not co gia tri x trong cay binh thuong int timx(Tree *T,int x) { if (T==NULL) return 0; else if (T->data==x) return 1; else if (timnp(T->left,x)==1) return 1; else return timnp(T->right,x); } // chen not co gia tri x vao cay BST void chenbst(Tree *&T,int x) { if (T==NULL) { T=new Tree; T->data=x; T->left=T->right=NULL; } else if(T->data>x) chenbst(T->left,x); else if(T->data<x) chenbst(T->right,x); else printf("\n da co trong cay\n"); } // tim x trong cay BST int timxbst(Tree *&T,int x) { if (T==NULL) return 0; else if(T->data>x) return timxbst(T->left,x); else if(T->data<x) return timxbst(T->right,x); else return 1; } void taocaybst(Tree *&T) { T=NULL; int x; do { printf("nhap mot so:"); scanf("%d",&x); if (x!=0) chenbst(T,x); } while(x!=0); } // chuyen cac gia tri duoc luu trong cay sang mang mot chieu void chuyensangmang(Tree *T, int *a, int &n) { if (T!=NULL) { chuyensangmang(T->left,a,n); n++; a[n]=T->data; chuyensangmang(T->right,a,n); } } // kiem tra cay co phai la cay BST hay khong, dùng kỹ thuật chuyển mảng int kiemtraBST(Tree *T) { int *a; int n=0,i=1,yes=1; chuyensangmang(T,a,n); while(i
[email protected]
Trang 33
Bài tập Cấu trúc dữ liệu và thuật toán
// dem so not co gia tri bang x trong cay int dem(Tree *T,int x) { if (T==NULL) return 0; else if (T- rel="nofollow">data==x) return 1+ dem(T->left,x)+ dem(T->right,x); else return dem(T->left,x)+ dem(T->right,x); } // tim muc cua not co gia tri x trong cay nhi phan bat ky int tim(Tree *T,int x,int &muc) { if (T==NULL) return 0; else { int k=muc+1; if (T->data==x) {muc=k; return 1;} else if (tim(T->left,x,k)==1) {muc=k; return 1;} else { muc++; return tim(T->left,x,muc);} } } void main() { //clrscr(); Tree *T=NULL;int x=-1; do { printf("nhap mot so:"); scanf("%d",&x); if (x>=0) nhapcay(T,x); } while(x>=0); printf("\n duyet cay theo tien tu:\n"); duyettientu(T); printf("\n"); /* printf("\n duyet cay theo trung tu:\n"); duyettrungtu(T); printf("\nduyet cay theo hau tu:\n"); duyethautu(T); printf(" \nso not co trong cay la:%d",sonot(T)); printf("\n so not le co trong cay la:%d",sonotle(T)); printf(" \nso la co trong cay la:%d",demla(T)); printf("\n tong not chan co trong cay la:%d",tongchan(T)); printf(" \nso not co mot con trong cay la:%d",motcon(T)); printf(" \nso not co hai con trong cay la:%d",haicon(T)); */ getch(); }
[email protected]
Trang 34
Bài tập Cấu trúc dữ liệu và thuật toán
Một số hàm khác // tinh gia tri cay bieu thuc (khong ap dung cho cac cay duoc tao o tren) float tinhgiatri(Tree *T) { if(T==NULL) return 0; else if (T->left==NULL && T->right==NULL) return (float)T->data; else switch(T->data) { case '+': return tinhgiatri(T->left)+ tinhgiatri(T->right); case '-': return tinhgiatri(T->left)- tinhgiatri(T->right); case '*': return tinhgiatri(T->left)* tinhgiatri(T->right); case '/': { float k=tinhgiatri(T->right); if (k==0) return 0; else return tinhgiatri(T->left)/k; } default: { printf("\n Toan tu khong hop le"); return 0;} } }
[email protected]
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 1 DANH SÁCH LIÊN KẾT ĐƠN #include
Phần định nghĩa danh sách liên kết đơn. Danh sách lưu các số nguyên. Nếu muốn lưu dữ liệu khác thì ta định nghĩa lại. Ví dụ muốn thông tin về sinh viên thì ta định nghĩa như sau: typedef struct Node {
int data; Node *next;
char ten[50]; char que[20]; float diemTB; Node *next;
}; void themdau(Node *&L, int x) { //buoc 1 Node *p=new Node; Thêm 1 phần tử giá trị x vào đầu danh sách L. p->data=x; p->next=L; 1. Tạo node mới p và gán dữ liệu x vào p và gắn L vào sau p // buoc 2 2. Cho L trỏ đến p L=p; } void duyet(Node *L) In nội dung danh sách được trỏ bởi L { Cho P trỏ đến L. Node *p=L; Trong khi P khác rỗng thì { in nội dung của P và cho P trỏ đến nốt sau P }. cout<<"--->"; Lưu ý : Lệnh cout dùng để in, tương tự như lệnh printf while (p!=NULL) { cout<
Trang 2
Bài tập Cấu trúc dữ liệu và thuật toán
void main() // hàm main gọi lại các hàm đã định nghĩa ở trên. { Node *L=NULL; //int n; cout<<"\n nhap so not can tao:"; cin>>n; Có thể gọi hàm tạo n nốt hoặc //taods(L,n); gọi hàm tạo như bên. tao(L); cout<<"\n Noi dung danh sach:\n"; duyet(L); cout<<"\n tong cac so="<
!!! Mỗi dòng include viết trên 1 dòng như bài 1
Ví dụ 2
#include
} void chenthuk(Node *&L, int x, int k) { if (k<1) printf("\n vi tri chen ko hop le!"); else if (k==1){ Node *t=new Node; t->data=x; t->next=L; L=t; } else // k>1 { int vt=1; Node *p=L; while (p!=NULL && vt
[email protected]
Trang 3
Bài tập Cấu trúc dữ liệu và thuật toán
void inthuk(Node *L, int k) { Thuật toán in nút thứ k (k>0). int vt=1; Cho con trỏ p trỏ đầu danh sách và vt=1; Node *p=L; Nhảy đến nốt thứ k trong danh sách while (p!=NULL && vt
[email protected]
Trang 4
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 3 #include
[email protected]
Trang 5
Bài tập Cấu trúc dữ liệu và thuật toán
void main() { clrscr(); L=NULL; tao1(L); cout<<"\n Noi dung danh sach:\n"; duyet(L); sapxep(L); cout<<"\n Noi dung danh sach sau khi sap xep:\n"; duyet(L); int x; cout<<"\nnhap gia x can chen:"; cin>>x; chentang(L,x); cout<<"\n Noi dung danh sach sau khi chen gia tri x:\n"; duyet(L); getch(); }
Ví dụ 4 #include
[email protected]
Trang 6
Bài tập Cấu trúc dữ liệu và thuật toán void taotangkotrung(Node *&L) { L=NULL; int x; do { cout<<"nhap so can them:"; cin>>x; if (x!=0) chentangkotrung(L,x); } while(x!=0); /* int i,n,x; cout<<"nhap so phan tu can them:"; cin>>n; for(i=1; i<=n; i++) { cout<<" nhap so thu "<<<":"; cin>>x; chentangkotrung(L,x); } */ } void inds(Node *L) { Node *p=L; cout<<"------>"; while (p!=NULL) { cout<< p->data <<"--> "; p=p->next; cout<<" NULL"; } void tron(Node *&L, Node *L1, Node *L2) // trộn 2 danh sách L1 và L2, kết quả được đưa vào L { Node *p=L1, *q=L2; L=NULL; while(p!=NULL) { chentangdq(L, p->data); p=p->next;} while(q!=NULL) { chentangdq(L, q->data); q=q->next;} } void main() { clrscr(); Node *L1=NULL; cout<<"\n Tao danh cout<<"\n Noi dung inds(L1); Node *L2=NULL; cout<<"\n Tao danh cout<<"\n Noi dung inds(L2); Node *L=NULL; tron(L,L1,L2); cout<<"\n Noi dung inds(L); getch();
sach L1:\n"; taotangkotrung(L1); danh sach L1:\n"; sach L2:\n"; taotangkotrung(L2); danh sach L2:\n";
danh sach L = L1 + L2:\n";
}
[email protected]
}
Trang 7
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 5
MỘT SỐ THAO TÁC XỬ LÝ TRÊN DANH SÁCH LIÊN KẾT ĐƠN
#include<stdio.h> #include<stdlib.h> #include
[email protected]
Trang 8
Bài tập Cấu trúc dữ liệu và thuật toán // thu tuc hien thi noi dung danh sach void in_ds(Node *L) { Node *p=L; if (p==NULL) printf("\n Day la danh sach rong!!!"); else { printf("\nNoi dung danh sach:\n"); printf("===>"); while(p!=NULL) { printf("%d--->",p->data); p=p->next; } printf("NULL"); } } // dat cac gia tri Âm trong danh sach vỀ gia tri 99 void dat_99(Node *&L) { Node *p=L; while(p!=NULL) { if (p->data<0) p->data=99; p=p->next; } printf("\n Da thu hien xong!!!"); } // dem so phan tu cua danh sach L int dem_pt(Node *L) { int dem=0; Node *p=L; while(p!=NULL) { dem++; p=p->next; } return dem; } // dem so phan tu trong danh sach lien ket theo phuong an de qui int dem_ptdq(Node *&L) { if (L==NULL) return 0; else return 1 + dem_ptdq(L->next); }
// dem so phan tu co gia tri x trong danh sach int dem_pt_x(Node *L,int &x) { int dem=0; Node *p=L; while(p!=NULL) { if(p->data==x) dem++; p=p->next; } return dem; } // dem so phan tu co gia tri x trong danh sach theo phuong an de qui
[email protected]
Trang 9
Bài tập Cấu trúc dữ liệu và thuật toán
int dem_pt_xdq(Node *L,int &x) { if (L==NULL) return 0; else if (L->data==x) return 1+ dem_pt_xdq(L->next,x); else return dem_pt_xdq(L->next,x); } //tinh tong cac node co gia tri la boi cua x trong danh sach int tong_boi_x(Node *L,int &x) { Node *p=L; int tong=0; if (x==0) printf("Khong tinh duoc boi cua 0!!!"); else while(p!=NULL) { if(p->data%x==0) tong=tong+p->data; p=p->next; } return tong; } // tinh tong cac not co gia tri la boi cua x theo phuong an de qui int tong_boi_xdq(Node *L,int &x) { if (x==0) { printf("Khong tinh duoc boi cua 0!!!"); return 0; } else if (L==NULL) return 0; else if (L->data%x==0) return L->data+tong_boi_xdq(L->next,x); else return tong_boi_xdq(L->next,x); } //kiem tra trong danh sach co phan tu x hay khong int kiem_tra_x(Node *L,int &x) { Node *p=L; int yes=0; while(p!=NULL && yes==0) if(p->data==x) yes=1; else p=p->next; return yes; } //kiem tra trong danh sach co phan tu x hay khong theo phuong an de qui int kiem_tra_xdq(Node *L,int &x) { if (L==NULL) return 0; else if (L->data==x) return 1; else return kiem_tra_xdq(L->next,x); } //tim phan phu x co trong danh sach hay khong, neu co thi in vi tri cua x void tim_x(Node *L,int &x) { Node *p=L; int yes=0,vt=0; while(p!=NULL && yes==0) { vt++; if(p->data==x) yes=1; else p=p->next;
[email protected]
Trang 10
Bài tập Cấu trúc dữ liệu và thuật toán
} if(yes==1) printf("\n Co gia tri %d trong danh sach o vi tri %d!!!",x,vt); else printf("\n Khong co gia tri %d trong danh sach!!!",x); } // tim phan phu x co trong danh sach hay khong, neu co thi in vi tri cua x void tim_xdq(Node *L,int x, int &vt) { if (L==NULL) printf("\n Khong co gia tri %d trong danh sach!!!",x); else if (L->data==x) printf("\n Co gia tri %d trong danh sach o vi tri %d!!!",x,vt); else { vt++; tim_xdq(L->next,x,vt);} } // cho con tro p tro den phan tu thu k trong danh sach void nhayden_k(Node *&L, int k,Node *&p) { p=NULL; if(k<1) printf("Khong the nhay den vi tri <1 ?!"); else if (L==NULL) printf("Danh sach rong, khong the nhay !!!"); else { int vt=1; p=L; while (p!=NULL && vt
[email protected]
Trang 11
Bài tập Cấu trúc dữ liệu và thuật toán
//xoa phan tu sau con tro P trong danh sach void xoapt_s_p(Node *&L,Node *p) { if (L==NULL) printf("\nDanh sach rong, khong the xoa!!!"); else if(p->next==NULL) printf("\nKhong the xoa phan tu NULL"); else { Node *q=L; while(q!=NULL && q!=p) q=q->next; if (q==NULL) printf("\n Khong ton tai con tro p trong danh sach"); else { q=p->next; p->next=q->next; } } } //xoa phan tu truoc con tro P trong danh sach void xoapt_t_p(Node *&L,Node *p) { if (L==NULL) printf("\nDanh sach rong, khong the xoa!!!"); else if (p==L) printf("Khong co phan tu truoc de xoa!!!"); else if (L->next==p) L=L->next; else { Node *q=L; while(q!=NULL && q->next!=p) q=q->next; if (q==NULL) printf("\nkhong ton tai con tro p trong danh sach"); else { Node *w=L; while(w->next!=q) w=w->next; w->next=p; } } } // xoa phan tu co gia tri x trong danh sach void xoadq(Node *&L,int x) { if (L==NULL) printf("\n khong co gia tri % trong danh sach!",x); else if (L->data==x) { // Node *p=L; L=L->next; delete p; L=L->next; } else xoadq(L->next,x); } // xoa tat ca cac phan tu co gia tri x trong danh sach void xoahetdq(Node *&L,int x) { if (L!=NULL) { if (L->data==x) { L=L->next; xoahetdq(L,x); } // { Node *p=L; L=L->next; delete p; } else xoahetdq(L->next,x); } }
[email protected]
Trang 12
Bài tập Cấu trúc dữ liệu và thuật toán
// kiem tra danh sach co tang dan hay khong int tangdan(Node *&L) { Node *p=L; if(p==NULL||p->next==NULL) return 1; else { Node *q=p->next; int yes=1; while(q!=NULL && yes==1) if(p->data> q->data) yes=0; else { p=q; q=q->next;} return yes; } } // sap xep danh sach tang dan void sapxep(Node *&L) { Node *p,*q; p=L; while (p!=NULL) { q=p->next; while(q!=NULL) { if(p->data>q->data) { int t=q->data; q->data=p->data; p->data=t; } q=q->next; } p=p->next; } } // chen not co gia tri x vao danh sach tang dan o vi tri thich hop void chentang(Node *&L,int x) { Node *t=new Node; t->data=x; t->next=NULL; if (L==NULL) L=t; else if (L->data>=x) { t->next=L; L=t;} else { Node *P=L; while (P!=NULL && P->data<x) P=P->next; Node *Q=L; while (Q->next!=P) Q=Q->next; Q->next=t; t->next=P; } } // tao danh sach lien ket vong TỪ DANH SÁCH LIÊN KẾT ĐƠN void taovong(Node *&L) { Node *P=L; if (P==NULL) printf("\Khong the tao vong danh sach lien ket rong!"); else while (P->next!=NULL) P=P->next; P->next=L; } // noi danh sach L2 vao sau L1
[email protected]
Trang 13
Bài tập Cấu trúc dữ liệu và thuật toán void noi2danhsach(Node *&L1, Node *&L2) // NỐI L2 VÀO SAU L1 { Node *P=L1; if (L1==NULL) L1=L2; else { while (P->next!=NULL) P=P->next; P->next=L2; } } // in cac gia tri trong L1 nhung khong co trong L2 void inkhongtrung(Node *&L1, Node *&L2) { Node *P=L1; while(P!=NULL) { Node *Q=L2; int yes=1; while (Q!=NULL && yes==1) if (P->data=Q->data) yes=0; else Q=Q->next; if( yes==1) printf("%5d", P->data) ; P=P->next; } } void main() { int x; Node *l,*l1,*l2,*p,*q; // clrscr(); nhap_ds(l); in_ds(l); if (tangdan(l)==1) printf("\nDanh sach tang dan!"); else printf("\nDanh sach khong tang dan!"); /* sapxep(l); printf("\nNoi dung danh sach sau khi sap xep:"); in_ds(l); if (tangdan(l)==1) printf("\nDanh sach tang dan!"); else printf("\nDanh sach khong tang dan!"); nhayden_k(l,2,p); xoapt_s_p(l,p); in_ds(l); */ printf("\n nhap gia tri x:"); scanf("%d",&x); xoahetdq(l,x); printf("\nNoi dung danh sach sau xoa phan tu x:"); in_ds(l); getch(); }
[email protected]
Trang 14
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 6
DANH SÁCH LIÊN KẾT VÒNG
#include
[email protected]
Trang 15
Bài tập Cấu trúc dữ liệu và thuật toán void main() { L=NULL; int x; taodsv(L); cout<<"\n Noi dung danh sach:\n"; duyetv(L); cout<<"\n nhap gia tri can tim:"; cin>>x; if (timxv(L,x)==1) cout<<"\n Co gia tri x trong danh sach"; else cout<<"\n Khong co gia tri x trong danh sach"; getch(); }
Ví dụ 7
THÁP HÀ NỘI VÀ DÃY FIBONANCY
#include
#include<stdlib.h>
} void main() { int n; clrscr(); cout<<"\n nhap n:"; cin>>n; //cout<<"\n phan tu thu n ( 0-->n) cua day la:"<
[email protected]
Trang 16
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 8
DANH SÁCH LIÊN KẾT ĐÔI
#include
{ p=p->next; vt++; }
int demx1dsd(DNode *L, int x) { DNode *p=L; int dem=0, vt=1;; while (p!=NULL) { if (p->data==x) { dem++; cout<<"\n co gia tri x tai vi tri "<
Trang 17
Bài tập Cấu trúc dữ liệu và thuật toán
void main() { DNode *L; clrscr(); taodsd(L); indsd(L); int x; cout<<"\n nhap gia tri x can tim:"; cin>>x; int k= timx1dsd(L,x); if (k==0) cout<<"\n khong co gia tri "<<x<<" trong danh sach"; else cout<<"\n co gia tri "<<x<<" trong danh sach o vi tri "<
Ví dụ 9
CHÈN XÓA CÁC NỐT TRÊN DANH SÁCH LIÊN KẾT ĐÔI
#include
"<< p->data;
[email protected]
p=p->next; }
Trang 18
Bài tập Cấu trúc dữ liệu và thuật toán void xoakdsd(DNode *&L,int k) { if(k<1|| L==NULL) cout<<"\n khong xoa duoc"; else { if (k==1) // xoa phan tu dau tien { DNode *q=L; L=L->next; if (L!=NULL) L->prev=NULL; delete q; } else // k> 1 va L<>NULL { // cho p tro den not thu k int vt=1; DNode *p=L; while(p!=NULL && vt
}
if(p==NULL) cout<<" \n Danh sach khong du k phan tu"; else // xoa phan tu duoc tro boi p { p->prev->next=p->next; if (p->next!=NULL) p->next->prev= p->prev; delete p; }
}
} void taodsd(DNode *&L) { int x; DNode *t,*dau,*cuoi; L=NULL; dau=cuoi=NULL; do { cout<<"nhap mot so:"; cin>>x; if (x!=0) { t=new DNode; t->data=x; t->next=t->prev=NULL; if (dau==NULL) dau=cuoi=t; else { cuoi->next=t; t->prev=cuoi; cuoi=t;} } } while (x!=0); L=dau; } void main() { DNode *L; clrscr(); taodsd(L); cout<<"\n danh sach vua nhap:\n"; indsd(L); int k; cout<<"\n nhap vi tri can chen:"; cin>>k; chenkdsd(L, k,100); cout<<"\n danh sach sau khi chen 100 vao vi tri k:\n"; indsd(L); getch(); }
[email protected]
Trang 19
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 10
CÀI ĐẶT NGĂN XẾP BẰNG MẢNG
#include
int a[MAXSIZE+1]; int top;
}; void CreateS(Stack1 &S) { S.top=0; } int EmptyS(Stack1 S) { if (S.top==0) return 1; else return 0; } void PushS(Stack1 &S,int x) { S.top=S.top+1; S.a[S.top]=x; } void PopS(Stack1 &S,int &x) { if (S.top>0) {x=S.a[S.top]; S.top=S.top-1;} else cout<<"\Danh sach rong,khong lay duoc!"; } int TopS(Stack1 S) { if (S.top>0) return S.a[S.top]; else {cout<<"\n ngan xep rong"; return 0;} } void main() { Stack1 S; CreateS(S); int i,x; for(i=1; i<=5; i++) { cout<<"nhap so thu "<<<":"; cin>>x; PushS(S,x); } cout<<"\n Cac so vua them vao ngan xep: "; while (!EmptyS(S)) { PopS(S,x); cout<<x<<" "; } getch(); }
[email protected]
Trang 20
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 11
ỨNG DỤNG NGĂN XẾP
PHÂN TÍCH SỐ N SANG HỆ NHỊ PHÂN và IN ĐẢO
#include
}
void main() { int n; cout<<"\nnhap so nguyen can bieu dien sang nhi phan:"; cin>>n; bieudiennhiphan(n); cout<<"\n So n in theo chieu nguoc la:”; dao(n); getch(); }
[email protected]
Trang 21
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 12
CÀI ĐẶT NGĂN XẾP BẰNG CON TRỎ, IN ĐẢO SỐ NGUYÊN N
#include
#include
#include<stdlib.h>
int data; Stack *next;
}; void CreateS(Stack *&S) { S=NULL; } int EmptyS(Stack *S) { if (S==NULL) return 1; else return 0; } void PushS(Stack *&S,int x) { Stack *t=new Stack; t->data=x; t->next=S; S=t; } void PopS(Stack *&S,int &x) { if (S==NULL) cout<<"\Ngan xep rong,khong lay duoc!"; else { x=S->data; Stack *q=S; S=S->next; delete q; } } int TopS(Stack *S) { if (S==NULL) {cout<<" \n Ngan xep rong"; return 0; } else return S->data; } void dao(int n) { Stack *S; CreateS(S); int x; while(n>0) { x=n%10; PushS(S,x); n=n/10; } Stack *t; CreateS(t); // bo vao ngan xep tam while (!EmptyS(S)) { PopS(S,x); PushS(t,x); } while (!EmptyS(t)) { PopS(t,x); cout<<x; } } void main() { int n; cout<<"\nnhap so nguyen can dao:"; cin>>n; dao(n); getch(); } [email protected]
Trang 22
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 13
IN PHẦN TỬ THỨ K CỦA NGĂN XẾP
#include
Trang 23
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 14
ỨNG DỤNG NGĂN XẾP KIỂM TRA CHUỖI () CHUẨN
#include
Trang 24
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 15
CÀI ĐẶT HÀNG ĐỢI BẰNG MẢNG
#include
int a[MAXSIZE+1]; int head,tail;
}; void CreateQ(Queue &Q) { Q.head=0; Q.tail=0; } int EmptyQ(Queue Q) { if (Q.head==0 && Q.tail==0) return 1; else return 0; } void AddQ(Queue &Q, int x) { if (EmptyQ(Q)) { Q.head=Q.tail=1; Q.a[Q.tail]=x;} else { Q.tail++; Q.a[Q.tail]=x;} } void RemoveQ(Queue &Q, int &x) { if (EmptyQ(Q)) cout<<"\n hang doi rong!:"; else { x=Q.a[Q.head]; if (Q.head==Q.tail) Q.head=Q.tail=0; else Q.head++; } } void main() { Queue q; CreateQ(q); //AddQ(q,3);
AddQ(q,2);
AddQ(q,7);
AddQ(q,6);
int x,n; cout<<"nhap so phan tu can them:"; cin>>n; for(int i=1; i<=n; i++) { cout<<"\n nhap so thu "<<<":"; cin>>x; AddQ(q,x); } while(!EmptyQ(q)) { RemoveQ(q,x); cout<<x<<" "; } getch(); }
[email protected]
AddQ(q,9);
Trang 25
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 16
ỨNG DỤNG HÀNG ĐỢI, IN ĐẢO SỐ NGUYÊN N
#include
#include<stdlib.h> {
int a[MAXSIZE+1]; int head,tail;
}; void CreateQ(Queue &Q) { Q.head=0; Q.tail=0; } int EmptyQ(Queue Q) { if (Q.head==0 && Q.tail==0) return 1; else return 0; } void AddQ(Queue &Q, int x) { if (EmptyQ(Q)) { Q.head=Q.tail=1; Q.a[Q.tail]=x;} else { Q.tail++; Q.a[Q.tail]=x;} } void RemoveQ(Queue &Q, int &x) { if (EmptyQ(Q)) cout<<"\n hang doi rong!:"; else { x=Q.a[Q.head]; if (Q.head==Q.tail) Q.head=Q.tail=0; else Q.head++; } } void indao(int n) { Queue q; CreateQ(q); int x; while (n>0) { AddQ(q, n%10); n=n/10; } while(!EmptyQ(q)) { RemoveQ(q,x); cout<<x<<" "; } } void main() { int n; clrscr(); cout<<"nhap so nguyen duong n:"; cin>>n; cout<<"\n So n in nguoc la:"; indao(n); getch(); } [email protected]
Trang 26
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 17
CÀI ĐẶT HÀNG ĐỢI BẰNG CON TRỎ
#include
Trang 27
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 18
ỨNG DỤNG NGĂN XẾP VÀ HÀNG ĐỢI KIỂM TRA CHUỖI ĐỐI XỨNG
#include
[email protected]
Trang 28
Bài tập Cấu trúc dữ liệu và thuật toán int doixung(char *s) { Queue q; CreateQ(q); Stack *t; CreateS(t); for (int i=0; i<strlen(s); i++) { AddQ(q,s[i]); PushS(t,s[i]); } char x,y; while(!EmptyQ(q)) { RemoveQ(q,x); PopS(t,y);//cout<<"("<<x<<" , "<
"; getch();
void main() { int n; clrscr(); char s[100]; cout<<"nhap chuoi s:"; fflush(stdin); gets(s); if(doixung(s)==1) cout<<"Chuoi doi xung"; else cout<<"\n chuoi khong doi xung"; getch(); }
Ví dụ 19
KIỂM TRA CHUỖI CHUẨN HAY KHÔNG (KHÔNG DÙNG NGĂN XẾP)
#include
Trang 29
Bài tập Cấu trúc dữ liệu và thuật toán
Ví dụ 20
CÂY NHỊ PHÂN
#include<stdio.h> #include
Trang 30
Bài tập Cấu trúc dữ liệu và thuật toán void duyethautu(Tree *T) { if (T!=NULL) { duyethautu(T->left); duyethautu(T->right); printf("%5d",T->data); } } // duyệt hậu tự, khử đề qui void hautu(Tree *T) { int d[100], vt=0; Tree *m[100],*z; if (T=!NULL) {vt++; m[vt]=T;} while(vt>0) { if (d[vt]==1) { printf("%5d",m[vt]->data); vt=vt-1;} else { d[vt]=1; z=m[vt]; if (z->right!=NULL) { vt++; m[vt]=z->right;d[vt]=0;} if (z->left!=NULL) { vt++; m[vt]=z->left; d[vt]=0;} } } } // duyệt trung tự, khử đề qui void trungtu(Tree *T) { int d[100]; Tree *m[100],*z; int vt=0; if (T=!NULL) {vt++; m[vt]=T;} while(vt>0) { if (d[vt]==1) { printf("%5d",m[vt]->data); vt=vt-1;} else { z=m[vt]; vt=vt-1; if (z->right!=NULL) { vt++; m[vt]=z->right;d[vt]=0;} vt=vt+1; d[vt]=1; m[vt]=z; if (z->left!=NULL) { vt++; m[vt]=z->left; d[vt]=0;} } } } // duyệt trung tự, để khử đề qui void tientu(Tree *T) { Tree *m[100],*z; int vt=0; if (T=!NULL) {vt++; m[vt]=T;} while(vt>0) { z=m[vt]; printf("%5d",m[vt]->data); vt=vt-1; if (z->right!=NULL) { vt++; m[vt]=z->right;} if (z->left!=NULL) { vt++; m[vt]=z->left; } } } // tim gia tri lon nhat trong hai so
[email protected]
Trang 31
Bài tập Cấu trúc dữ liệu và thuật toán
int max(int a, int b) { if (a>b) return a; else return b; } // tinh chieu cao cua cay int chieucao(Tree *T) { if(T==NULL) return 0; else return 1+ max(chieucao(T->left),chieucao(T->right)); } // dem so not trong cay T int sonot(Tree *T) { if(T==NULL) return 0; else return 1+ sonot(T->left)+sonot(T->right); } // dem so not co gia tri le trong cay int sonotle(Tree *T) { if(T==NULL) return 0; else if (T->data%2==1) return 1+ sonotle(T->left)+sonotle(T->right); else return sonotle(T->left)+sonotle(T->right); } // tinh tong cac not co gia tri chan trong cay int tongchan(Tree *T) { if(T==NULL) return 0; else if (T->data%2==0) return T->data+ tongchan(T->left)+tongchan(T->right); else return tongchan(T->left)+tongchan(T->right); } // dem so la cua cay int demla(Tree *T) { if(T==NULL) return 0; else if (T->left==NULL && T->right==NULL) return 1+ demla(T->left)+demla(T->right); else return demla(T->left)+demla(T->right); } // dem so not co day du hai con int haicon(Tree *T) { if(T==NULL) return 0; else if (T->left!=NULL && T->right!=NULL) return 1+ haicon(T->left)+haicon(T->right); else return haicon(T->left)+haicon(T->right); } // dem so not co dung mot con int motcon(Tree *T) { if(T==NULL) return 0; else if ((T->left!=NULL && T->right==NULL)||(T->left==NULL && T->right!=NULL)) return 1; else return motcon(T->left)+motcon(T->right); }
[email protected]
Trang 32
Bài tập Cấu trúc dữ liệu và thuật toán
// tim not co gia tri x trong cay binh thuong int timx(Tree *T,int x) { if (T==NULL) return 0; else if (T->data==x) return 1; else if (timnp(T->left,x)==1) return 1; else return timnp(T->right,x); } // chen not co gia tri x vao cay BST void chenbst(Tree *&T,int x) { if (T==NULL) { T=new Tree; T->data=x; T->left=T->right=NULL; } else if(T->data>x) chenbst(T->left,x); else if(T->data<x) chenbst(T->right,x); else printf("\n da co trong cay\n"); } // tim x trong cay BST int timxbst(Tree *&T,int x) { if (T==NULL) return 0; else if(T->data>x) return timxbst(T->left,x); else if(T->data<x) return timxbst(T->right,x); else return 1; } void taocaybst(Tree *&T) { T=NULL; int x; do { printf("nhap mot so:"); scanf("%d",&x); if (x!=0) chenbst(T,x); } while(x!=0); } // chuyen cac gia tri duoc luu trong cay sang mang mot chieu void chuyensangmang(Tree *T, int *a, int &n) { if (T!=NULL) { chuyensangmang(T->left,a,n); n++; a[n]=T->data; chuyensangmang(T->right,a,n); } } // kiem tra cay co phai la cay BST hay khong, dùng kỹ thuật chuyển mảng int kiemtraBST(Tree *T) { int *a; int n=0,i=1,yes=1; chuyensangmang(T,a,n); while(i
[email protected]
Trang 33
Bài tập Cấu trúc dữ liệu và thuật toán
// dem so not co gia tri bang x trong cay int dem(Tree *T,int x) { if (T==NULL) return 0; else if (T- rel="nofollow">data==x) return 1+ dem(T->left,x)+ dem(T->right,x); else return dem(T->left,x)+ dem(T->right,x); } // tim muc cua not co gia tri x trong cay nhi phan bat ky int tim(Tree *T,int x,int &muc) { if (T==NULL) return 0; else { int k=muc+1; if (T->data==x) {muc=k; return 1;} else if (tim(T->left,x,k)==1) {muc=k; return 1;} else { muc++; return tim(T->left,x,muc);} } } void main() { //clrscr(); Tree *T=NULL;int x=-1; do { printf("nhap mot so:"); scanf("%d",&x); if (x>=0) nhapcay(T,x); } while(x>=0); printf("\n duyet cay theo tien tu:\n"); duyettientu(T); printf("\n"); /* printf("\n duyet cay theo trung tu:\n"); duyettrungtu(T); printf("\nduyet cay theo hau tu:\n"); duyethautu(T); printf(" \nso not co trong cay la:%d",sonot(T)); printf("\n so not le co trong cay la:%d",sonotle(T)); printf(" \nso la co trong cay la:%d",demla(T)); printf("\n tong not chan co trong cay la:%d",tongchan(T)); printf(" \nso not co mot con trong cay la:%d",motcon(T)); printf(" \nso not co hai con trong cay la:%d",haicon(T)); */ getch(); }
[email protected]
Trang 34
Bài tập Cấu trúc dữ liệu và thuật toán
Một số hàm khác // tinh gia tri cay bieu thuc (khong ap dung cho cac cay duoc tao o tren) float tinhgiatri(Tree *T) { if(T==NULL) return 0; else if (T->left==NULL && T->right==NULL) return (float)T->data; else switch(T->data) { case '+': return tinhgiatri(T->left)+ tinhgiatri(T->right); case '-': return tinhgiatri(T->left)- tinhgiatri(T->right); case '*': return tinhgiatri(T->left)* tinhgiatri(T->right); case '/': { float k=tinhgiatri(T->right); if (k==0) return 0; else return tinhgiatri(T->left)/k; } default: { printf("\n Toan tu khong hop le"); return 0;} } }
[email protected]
Related Documents
Cau Truc Du Lieu
October 2019 21
Cau Truc Du Lieu
November 2019 16
Cau Truc Du Lieu Va Giai Thuat2
November 2019 12
Cau Truc Du Lieu Va Giai Thuat1
November 2019 23
Cau Truc Du Lieu Cua Database Tinc
October 2019 20