TONG HOP
//////////////////////////////////////STACK/////////////////////////////
//////////////////////////////////////QUEUE///////////////////////////////////////////////////
///////////////////////////////////////DUYTREE/////////////////////////
////////////////////////////////////////DSLK,,/////////////////////////////////////
///////////////////////////////////////CNPTK_HAI..../////////////////////////
///////////////////////////////////////6.CPP.////////////////////////
///////////////////////////////////////5.CPP/////////////////////////
///////////////////////////////////////4.CPP/////////////////
//////////////////////////////////STACK/////////////////////////////
/* stack: last in first out. Pt cho vao' cuoi cung thi lay ra dau^' tien^.
O day dung thuat toan la' tao. ra cau^' truc' stack co 1 con tro? *top chi vao pt tren^ cung' cua stack.
Khi them vao 1 pt, thi' pt moi do' dc gan' = *top de chi? ra vi tri tren^ cung' cua stack
Khi lay 1 pt ra, thi' pt ngay sau pt tren^ cun'g vua' bi lay ra se~ la' *top.
*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
struct sinhvien{
char ten[30];
int diem;
};
struct node{
sinhvien info;
node *next;
};
struct stack{
node *top; //con tro? chi vi tri' cua pt tren^ cung' stack
};
void nhap(sinhvien &sv){ //nhap 1 sinh vien
printf("
Ho va ten: ");fflush(stdin);gets(sv.ten);
printf("
Diem: ");fflush(stdin);scanf("%d",&sv.diem);
}
void xuat(sinhvien &sv,int stt){ //xuat gia tri ve 1 sinh vien
printf("
\t\t|%5d |%9s |%6d |",stt,sv.ten,sv.diem);
printf("
\t\t------------------------------------");
}
void duyet(stack &s){ //hien thi toan bo cac phan tu trong stack
node *p=new node;
p=s.top;
int stt=1;
printf("
\t\t------------------------------------");
printf("
\t\t| STT | Ho va ten | MSV | ");
printf("
\t\t------------------------------------");
while(p!=NULL){
xuat(p->info,stt);
p=p->next;
stt++;
}
}
//------------------------------------------Ket thuc khai bao--------------------------------------
void khoitao(stack &s){
s.top=NULL; //dat pt du*ng' dau^' stack = NULL
}
int ktrong(stack &s){
if(s.top==NULL) return 1;
return 0;
}
void push(stack &s,sinhvien &sv){
node *p=new node;
p->info=sv;
if(ktrong(s)){
s.top=p; //stack rong thi phan tu dua vao cung chinh la pt tren cung'
}
else{
p->next=s.top; //stack ko rong,
s.top=p; // p la pt dua vao, nen no se~ la pt tren^ cung' cua? stack, dat lai vi tri cua pt dau tien
}
duyet(s); //thanh cong thi in ra cac pt cua stack
}
void get(stack &s){
sinhvien sv;
node *p=new node;
if(ktrong(s)){
printf("
Stack rong.
");
return;
}
p=s.top; //p tro? vao vi tri' tren^ cugn' cua stack
s.top=p->next; //khi lay ra pt tre^n cu'ng xong ta se~ phai xoa pt do' trong stack, nen pt dau tien luc nay' se~ la pt tiep sau, dat lai vi tri cua? s.top
sv=p->info;
printf("
Phan tu lay ra la:");
printf("
\t\t------------------------------------");
printf("
\t\t| STT | Ho va ten | MSV | ");
printf("
\t\t------------------------------------");
xuat(sv,1);
printf("
");
printf("
Trong stack con lai cac phan tu:");
duyet(s);
free(p); //lay ra pt tren^ cung (tu*c' la p) thi xoa' p khoi stack
}
void clear(stack &s){
node *p=new node;
node *q=new node;
p=s.top;
while(p!=NULL){
q=p;
p=p->next;
q->next=NULL;
delete q;
}
s.top=NULL; //sau khi vong' lap ket thuc, se~ con' lai 1 pt chua xoa' la' top, xoa' not^' cho no = NULL :-D
}
/* ham clear thuc hien viec xoa toan bo phan tu trong stack
nhung neu muon an gian,ko muon viet ham clear thi luc chay cu goi lai luon ham khoitao(s) =))
Dam bao hien ra dep nhu la da~ xoa' =))
*/
void viewtop(stack &s){
sinhvien sv;
sv=s.top->info; //chi xem gia tri vi tri dau tien cua stack nhu*ng ko xoa' vi tri' dau tien nhu ham' get()
printf("
\t\t------------------------------------");
printf("
\t\t| STT | Ho va ten | MSV | ");
printf("
\t\t------------------------------------");
xuat(sv,1);
}
void main(){
sinhvien sv;
stack s;
int chon;
do{
printf("
1. Khoi tao stack.");
printf("
2. Them mot phan tu vao trong stack.");
printf("
3. Lay mot phan tu cua stack.");
printf("
4. Xem phan tu o dinh stack.");
printf("
5. Xoa stack.");
printf("
6. Duyet stack.");
printf("
7. Thoat.");
printf("
Moi chon chuong trinh can thuc hien: ");
scanf("%d",&chon);
switch(chon){
case 1:khoitao(s);printf("
Stack da duoc khoi tao.
");getch();break;
case 2:nhap(sv);push(s,sv);getch();break;
case 3:get(s);getch();break;
case 4:viewtop(s);getch();break;
case 5:clear(s);getch();break;
case 6:duyet(s);getch();break;
}
}while(chon != 7);
}
//////////////////////////////////////QUEUE///////////////////////////////////////////////////
#include<conio.h>
#include<stdio.h>
#include<iostream.h>
struct sinhvien{
char hoten[25];
int diem;
};
struct node{
sinhvien info;
node *next;
};
struct hangdoi{
node *pfirst,*plast;
};
void init(hangdoi &q){
q.pfirst=NULL;
q.plast=NULL;
}
void xoa(hangdoi &q){
node *p,*p1;
p=q.pfirst;
while(p!=NULL){
p1=p;
p=p->next;
delete p1;
}
q.pfirst=NULL;
}
int ktrong(hangdoi &q){
return(q.pfirst==NULL);
}
//dua vao cuoi hag doi
void push(hangdoi &q,sinhvien sv){
node *p;
p=new node;
p->info=sv;p->next=NULL;
if(q.pfirst==NULL){
q.pfirst=p;
q.plast=p;
return;
}
q.plast->next=p;
q.plast=p;
}
//lay tu dinh
sinhvien get(hangdoi &q){
if(!ktrong(q)){
sinhvien sv;
sv=q.pfirst->info;
node *p=q.pfirst;
q.pfirst=q.pfirst->next;
delete p;
if(q.pfirst==NULL)q.plast=NULL;
return(sv);
}
}
sinhvien viewDinh(hangdoi &q){
if(!ktrong(q)){
sinhvien sv=q.pfirst->info;
return(sv);
}
}
void menu(){
sinhvien sv;
hangdoi q;
int chon;
do{
printf("
1.khoi tao hang doi");
printf("
2.dua 1 sv vao cuoi hag doi");
printf("
3.lay 1 sv dinh hag doi ");
printf("
4.xoa hang doi");
printf("
5.xem pan tu o dinh hag doi");
printf("
6.thoat");
printf("
ban chon: ");
chon=getch();
switch(chon){
case'1':init(q);getch();
break;
case'2':printf("
nhap ho ten:");scanf("%s",&sv.hoten);
printf("
nhap diem:");scanf("%d",&sv.diem);
push(q,sv);getch();
break;
case'3':sv=get(q);getch();
printf("
ho ten:%s",sv.hoten);
printf("
diem:%d",sv.diem);
break;
case'4':xoa(q);getch();
break;
case'5':viewDinh(q);
printf("
ho ten:%s",q.pfirst->info.hoten);
printf("
diem:%d",q.pfirst->info.diem);
getch();
break;
}
}while(chon!='6');
}
void main(){
menu();
getch();
}
////////////////////////////////DUYTREE/////////////////////////
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <ctype.h>
#include <stdlib.h>
struct sinhvien{
char ten[20];
int ma;
};
struct node{
sinhvien info;
node *left,*right;
};
void khoitao(node *&proot){
proot=NULL;
}
int ktrong(node *proot){
return proot==NULL;
}
node *taonode(sinhvien sv){
node *p=new node;
p->info=sv;
p->left=NULL;
p->right=NULL;
return p;
};
void duyetgiua(node *proot){
if(proot!=NULL){
duyetgiua(proot->left);
cout<<"
========";
cout<<"
Ten :"<<proot->info.ten;
cout<<"
MA :"<<proot->info.ma;
cout<<"
========" ;
duyetgiua(proot->right);
}
}
node * timkiem(node *proot,sinhvien sv){
if(proot==NULL){
return NULL;
}
if(proot->info.ma==sv.ma)
{return proot;
}
else{
if(sv.ma<proot->info.ma) return timkiem(proot->left,sv) ;
else return timkiem(proot->right,sv);
}
}
void timkiem2(node *proot,int ma){
if(proot==NULL){
cout<<"
k tim thay!!";
return ;
}
if(proot->info.ma==ma)
{cout<<"
Ten sinh vien can tim la:"<<proot->info.ten;
}
else{
if(ma<proot->info.ma) timkiem2(proot->left,ma) ;
else timkiem2(proot->right,ma);
}
}
node *timptthaythe(node *&p,node *proot)
{
if(p->right!=NULL)
return timptthaythe(p->right,proot);
proot->info=p->info; // dua du lieu cua p vao proot
node *ptemp=p;
p=p->left; //luu lai nhanh con cua no
return ptemp; //Xoa phan tu thay the
}
void del(node *&proot)
{
node *ptemp=proot;
//kiem tra
if(proot->right==NULL)
proot=proot->left;
else
if(proot->left==NULL)
proot=proot->right;
else
ptemp=timptthaythe(proot->left,proot);
delete ptemp;
}
// Xoa mot phan tu................................................ .......
int xoamotpt(node *&proot,sinhvien sv)
{
if(proot==NULL)
return 0;
if(proot->info.ma>sv.ma)
return xoamotpt(proot->left,sv);
else
{
if(proot->info.ma<sv.ma)
return xoamotpt(proot->right,sv);//da tim thay va dung ham delete de xoa
del(proot);
return 1;
}
}
void them(node* &proot, sinhvien sv){
if(proot==NULL){
proot=taonode(sv);
return;
}
if(timkiem(proot,sv)){
cout<<"
node da co, k them duoc!";
return;
}
if(sv.ma<proot->info.ma) them(proot->left,sv);
else them(proot->right,sv);
}
main(){
clrscr();
node *proot;
sinhvien sv;
int chon,ma;
do{
clrscr();
cout<<"
1.Khoi tao";
cout<<"
2.Them";
cout<<"
3.Tim kiem";
cout<<"
4.Duyet tu giua (cac duyet khac tuong tu)";
cout<<"
5.Xoa 1 node";
cout<<"
0.Thoat";
cout<<"
Moi ban chon: ";
cin>>chon;cin.ignore();
switch(chon){
case 1:khoitao(proot);
cout<<"
Danh sach da khoi tao!";
getch();
break;
case 2:cout<<"
Nhap ten sinh vien :";fflush(stdin);gets(sv.ten);
cout<<"
Nhap ma sinh vien :";fflush(stdin);cin>>sv.ma;
them(proot,sv);
getch();
break;
case 3: cout<<"
Nhap ma sv can tim:";cin>>ma;
timkiem2(proot,ma);
getch();
break;
case 4: if(proot!=NULL){
cout<<"
Node goc la:"<<proot->info.ten<<" "<<proot->info.ma;
duyetgiua(proot);
}
else cout<<"
Cay khong co gi!!!";
getch();
break;
case 5: node *p;
printf("
Cay truoc khi xoa mot phan tu!
");
duyetgiua(proot);
printf("
Nhap ma sinh vien can xoa: ");
scanf("%d",&sv.ma);
p=timkiem(proot,sv);
if(p)
xoamotpt(proot,sv);
else
printf("
Khong co phan tu de xoa.
");
break;
}
}while(chon!=0);
getch();
}
/////////////////////////////////////////////DSLK,,/////////////////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define true 1
#define false 0
#include<iostream.h>
struct sinhvien{
char ten[30];
int ma;
};
struct node{
sinhvien info;
node *next;
};
struct danhsach{
node *pfirst,*plast;
};
void nhap(sinhvien &sv){
printf("
\t Ho va ten: ");fflush(stdin);gets(sv.ten);
printf("
\t Ma sinh vien: ");fflush(stdin);scanf("%d",&sv.ma);
}
void xuat(sinhvien &sv,int stt){
printf("
\t\t|%5d |%9s |%6d |",stt,sv.ten,sv.ma);
printf("
\t\t------------------------------------");
}
void duyet(danhsach &d){
node *p=new node;
p=d.pfirst;
int stt=1;
printf("
\t\t------------------------------------");
printf("
\t\t| STT | Ho va ten | MSV | ");
printf("
\t\t------------------------------------");
while(p!=NULL){
xuat(p->info,stt);
p=p->next;
stt++;
}
printf("
");
}
void khoitao(danhsach &d){
d.pfirst=d.plast=NULL;
}
int ktrong(danhsach &d){
if(d.pfirst==NULL) return 1;
return 0;
}
void themdau(danhsach &d){
node *p=new node;
sinhvien sv;
nhap(sv);
p->info=sv;
if(ktrong(d)){
d.pfirst=p;
d.plast=p;
}
else{
p->next=d.pfirst;
d.pfirst=p;
}
duyet(d);
}
void themcuoi(danhsach &d){
node *p=new node;
sinhvien sv;
nhap(sv);
p->info=sv;
if(ktrong(d)){
d.pfirst=d.plast=p;
}
else{
d.plast->next=p;
p->next=NULL;
d.plast=p;
}
duyet(d);
}
void themsauk(danhsach &d,int k){
node *p=new node;
node *q=new node;
sinhvien sv;
p=d.pfirst;
int found=0,count=1;
if(k==0){
themdau(d);
return;
}
while(p!=NULL && found ==0){
if(p->next==NULL){
printf("
\tKhong the them");
}
if(count==k){
nhap(sv);
q->info=sv;
q->next=p->next;
p->next=q;
found=1;
duyet(d);
}
p=p->next;
count++;
}
}
void xoatruock(danhsach &d,int k){
node *p=new node;
node *q=new node;
p=d.pfirst;
int found=0,count=1;
if(ktrong(d)){
printf("
\t Danh sach rong.
");
return;
}
if(k==2){
d.pfirst=p->next;
p->next=NULL;
free(p);
duyet(d);
}
while(p != NULL && found==0){
if(p->next==NULL){
printf("
\t Khong the xoa.
");
return;
}
if(count==k-2){
q=p->next;
if(q->next==NULL){
d.plast=p;
p->next=NULL;
}
else{
p->next=q->next;
q->next=NULL;
}
free(q);
found=1;
duyet(d);
}
p=p->next;
count++;
}
}
void xoasauk(danhsach &d,int k){
node *p=new node;
node *q=new node;
p=d.pfirst;
int found=0,count=1;
if(ktrong(d)){
printf("
\t Danh sach rong.
");
return;
}
if(k==0){
d.pfirst=p->next;
p->next=NULL;
free(p);
duyet(d);
}
while( p != NULL && found==0){
if(p->next==NULL){
printf("
\t Khong the xoa.
");
return;
}
if(count==k){
q=p->next;
p->next=q->next;
q->next=NULL;
free(q);
if(p->next==NULL) d.plast=p;
found=1;
duyet(d);
}
p=p->next;
count++;
}
}
void main(){
int chon,k;
danhsach d;
do{
printf("
\t\t\tChuong trinh thao tac voi sach lien ket don");
printf("
\t 1. Khoi tao danh sach rong.");
printf("
\t 2. Them mot phan tu vao cuoi danh sach.");
printf("
\t 3. Them mot phan tu vao dau danh sach.");
printf("
\t 4. Them mot phan tu sau vi tri k.");
printf("
\t 5. Xoa mot phan tu trong danh sach truoc vi tri k.");
printf("
\t 6. Xoa mot phan tu trong danh sach sau vi tri k.");
printf("
\t 7. Hien thi danh sach.");
printf("
\t 8. Thoat khoi chuong trinh.");
printf("
\t Xin moi chon chuong trinh muon thuc hien: ");
scanf("%d",&chon);
switch(chon){
case 1: printf("
\t Danh sach da duoc khoi tao.
");khoitao(d);break;
case 2: themcuoi(d);break;
case 3: themdau(d);break;
case 4: printf("
\t Moi nhap vi tri: ");scanf("%d",&k);
themsauk(d,k);break;
case 5: printf("
\t Moi nhap vi tri: ");scanf("%d",&k);
xoatruock(d,k);break;
case 6: printf("
\t Moi nhap vi tri: ");scanf("%d",&k);
xoasauk(d,k);break;
case 7: duyet(d);break;
}
}while(chon != 8);
getch();
}
////////////////////////////////CNPTK_HAI..../////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
struct canbo{
char ten[30];
int macb;
};
struct node{
canbo info;
node *left,*right;
};
void nhap(canbo &cb){
printf("
Ten can bo: ");fflush(stdin);gets(cb.ten);
printf("
Ma can bo : ");fflush(stdin);scanf("%d",&cb.macb);
}
void in(){
printf("
\t\t --------------------------");
printf("
\t\t| Ho va ten | MCB | ");
printf("
\t\t --------------------------");
}
void xuat(canbo &cb){
printf("
\t\t|%9s |%6d |",cb.ten,cb.macb);
printf("
\t\t --------------------------");
}
//-------------------------------------------Ket thuc khai bao--------------------------------------------
void khoitao(node *&proot){ //CHU' Y':truyen vao *&proot thay vi *proot nhu cac' ham' khac'
proot=NULL; //khoitao va the^m la 2 ham bat buoc^. phai truyen *&proot thay vi *proot nhu cac ham' khac'
}
void xoacay(node *proot){
if(proot==NULL){
printf("
Cay nhi phan rong. Khong co phan tu de xoa.");
return;
}
if(proot!=NULL){
xoacay(proot->left);
xoacay(proot->right);
free(proot);
}
}
int ktrong(node *proot){
if(proot==NULL) return 1;
return 0;
}
node *makenode(canbo &cb){
node *p=new node;
p->info=cb;
p->left=NULL;
p->right=NULL;
return p;
}
void duyettruoc(node *proot){
if(proot!=NULL){
xuat(proot->info);
duyettruoc(proot->left); //duyet truoc thi xuat o truoc
duyettruoc(proot->right);
}
}
void duyetgiua(node *proot){
if(proot!=NULL){
duyetgiua(proot->left);
xuat(proot->info); //duyet giua thi xuat o giua
duyetgiua(proot->right);
}
}
void duyetsau(node* proot){
if(proot!=NULL){
duyetsau(proot->left);
duyetsau(proot->right); //duyet sau thi xuat o sau
xuat(proot->info);
}
}
node *timkiem(node *proot,int &ma){
node *p=new node;
if(proot==NULL) return NULL;
if(proot->info.macb == ma) return proot;
if(proot->info.macb < ma ) p=timkiem(proot->left,ma);
else p=timkiem(proot->right,ma);
return p;
}
void them(node *&proot,canbo &cb){ //truyen vao *&proot thay vi *proot nhu cac' ham' khac'
if(proot==NULL){
proot=makenode(cb);
return;
}
if(timkiem(proot,cb.macb)){
printf("
Nut da ton tai. Khong the them.");//Khong the co 2 can bo cung' ma~.
return;
}
if(proot->info.macb < cb.macb) them(proot->left,cb);
else them(proot->right,cb);
}
node *timkiem2(node *proot,node *&fp,int &ma){ //timkiem2 khac timkiem o*? cho^~ tim' duoc nut' cha cua nut can^' tim'
node *p=proot;
fp=NULL; //fp la nut cha cua nut' p can^' tim
while(p!=NULL){
if(p->info.macb==ma) return p; // tim thay thi tra ve ngay p
if(proot->info.macb < ma){
fp=p;
p=p->left;
}
else{
fp=p;
p=p->right;
}
}
return NULL; //vong lap ket thuc' ma' ko tim thay thi dua ve NULL(do ham' nay' la ham' tra ve con tro? dang. node)
}
/* se co 3 truong hop xoa' nut' p:
1. Nut' xoa' la' nut' la:
2. Nut' xoa' co' 1 nut' con( ben^ trai' hoac be^n phai)
3. Nut' xoa' co' 2 nut' con
*/
void xoa(node *proot,int &ma){
node *fp,*p,*f,*rp,*q;
p=timkiem2(proot,fp,ma);
if(p==NULL){
printf("
Cay nhi phan rong. Khong thay");
return;
}
//nut' can^' xoa la 1 nut la'
if(p->left==NULL && p->right==NULL){
if(p==proot){free(proot);proot=NULL;return;}//nut' xoa chinh la nut' go^c', tuc la' cay np chi co' 1 pt la nut' goc^'
if(fp->left==p){ fp->left=NULL;free(p);return;} //p la nut' la' ben trai' cua nut fp
if(fp->right==p){fp->right=NULL;free(p);return;}//p la nut' la' ben phai? cua nut fp
}
//nut' xoa' co 1 nut' con
if(p->left!=NULL && p->right==NULL){//chi co 1 nut' con ben trai'
if(fp->left==p){fp->left=p->left;free(p);return;}
if(fp->right==p){fp->right=p->left;free(p);return;}
}
if(p->left==NULL && p->right!=NULL){//chi co 1 nut' con ben trai'
if(fp->left==p){fp->left=p->right;free(p);return;}
if(fp->right==p){fp->right=p->right;free(p);return;}
}
f=p;
rp=p->left;
while(rp->right!=NULL) {f=rp;rp=rp->right;}
f->right=rp->left;/*rp la phai nhat, do do khong co con phai
vi khong con rp nen nut cha phai chi den nut sau do*/
p->info=rp->info; //doi noi dung cua p va rp, roi xoa rp
free(rp);
rp==NULL;
}
int main(){
node *proot,*p;
int chon,ma;
canbo cb;
do{
printf("
1.Khoi tao.");
printf("
2.Them nut.");
printf("
3.Tim nut.");
printf("
4.Xoa nut.");
printf("
5.Duyet truoc");
printf("
6.Duyet giua");
printf("
7.Duyet sau");
printf("
8.Thoat.");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:khoitao(proot);printf("
Cay nhi phan da duoc khoi tao.
");break;
case 2:nhap(cb);them(proot,cb);break;
case 3:printf("
Moi nhap ma can bo: ");scanf("%d",&ma);p=timkiem(proot,ma);
if(p!=NULL){ in();xuat(p->info);}
else printf("
Khong tim thay nut.
");
break;
case 4:printf("
Moi nhap ma can bo: ");scanf("%d",&ma);xoa(proot,ma);in();duyettruoc(proot);break;
case 5:in();duyettruoc(proot);break;
case 6:in();duyetgiua(proot);break;
case 7:in();duyetsau(proot);break;
}
}while(chon!=8);
getch();
}
////////////////////////////////////6.CPP.////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#define true 1
#define false 0
struct node{
int info;
node *next;
};
struct queue{
node *pfirst,*plast;
};
//----------------------------------Ket thuc phan khai bao-------------------------------
void khoitao(queue &q){
q.pfirst=q.plast=NULL;
}
int ktrong(queue &q){
if(q.pfirst==NULL) return 1;
return 0;
}
void clear(queue &q){
node *p,*p1;
p=q.pfirst;
while(p!=NULL){
p1=p;
p=p->next;
free(p1);
}
}
void put(queue &q,int x){
node *p=new node;
p->info=x;
if(ktrong(q)){
q.pfirst=q.plast=p;
}
else{
q.plast->next=p;
p->next=NULL;
q.plast=p;
}
}
int get(queue &q){
node *p=new node;
p=q.pfirst;
int x;
x=p->info;
q.pfirst=p->next;
p->next=NULL;
free(p);
return x;
}
/*Chuyen 1 so co phan thap phan sang nhi phan ta se~ nha^n lien tiep so do' voi 2 cho toi khi nao het phan
thap phan thi dung lai. Trong qua' trinh' nhan neu co phan nguyen >0 thi ta tru' di phan nguyen, chi lay phan
thap phan roi tiep tuc nhan. Dua phan nguyen vao trong queue
vd: 0.125 x 2 = 0.25 dua phan nguyen 0 vao trong queue, lay phan than phan 0.25 - 0 = 0.25, tiep tuc nhan voi 2
thuc hien lien tuc nhu the.
*/
void nhiphan(queue &q,float x){
float v=x;
int k=0,h,t;
while(fabs(v)>0.00001){
v=v*2; //nhan lien tiep voi 2
h=int(v); //lay phan nguyen cua so^' do', gan' = h
put(q,h); //day phan nguyen vao queue
v=v-int(v); //loai bo phan nguyen lay phan thap phan, tiep tuc vong lap
}
printf("
%f chuyen sang nhi phan la : 0.",x);
while(!ktrong(q)){
t=get(q);
printf("%d",t);
}
clear(q);
printf("
");
}
void main(){
int n,chon;
float x;
queue q;
do{
printf("
1. Khoi tao queue.");
printf("
2. Dua mot phan tu vao trong queue.");
printf("
3. Lay mot phan tu ra khoi queue.");
printf("
4. Chuyen doi mot so (n<1) sang dang nhi phan.");
printf("
5. Thoat");
printf("
Moi chon chuong trinh can thuc hien: ");
scanf("%d",&chon);
switch(chon){
case 1: khoitao(q);printf("
Queue da duoc khoi tao.
");break;
case 2: printf("
Moi nhap phan tu can dua vao: ");scanf("%d",&n);
put(q,n);break;
case 3: printf("
Phan tu lay ra la: %d",get(q));break;
case 4: printf("
Moi nhap so can chuyen: ");fflush(stdin);scanf("%f",&x);
clear(q);nhiphan(q,x);break;
}
}while(chon != 5);
getch();
}
/////////////////////////////5.CPP/////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1;
#define false 0
struct node{
int info;
node *next;
};
struct stack{
node *phead;
};
//-------------------------------------Ket thuc phan khai bao------------------------------
int ktrong(stack &s){
if(s.phead==NULL) return 1;
return 0;
}
void khoitao(stack &s){
s.phead=NULL;
}
void clear(stack &s){
node *p,*q;
p=s.phead;
while(p!=NULL){
q=p;
p=p->next;
free(q);
}
}
void push(stack &s,int &k){
node *p=new node;
p->info=k;
if(ktrong(s)){
s.phead=p;
}
else{
p->next=s.phead;
s.phead=p;
}
}
int pop(stack &s){
node *p;
int x;
if(ktrong(s)){
return 0;
}
else{
p=s.phead;
s.phead=s.phead->next;
x=p->info;
p->next=NULL;
free(p);
return x;
}
}
void nhiphan(stack &s,int n){
int du,m=n,t;
while(m>0){
du=m%2; //chia 2 lay du
push(s,du); //day phan du vao trong stack
m=m/2; //chia lien tiep cho 2
}
printf("
So %d chuyen sang nhi phan la: ",n);
while(!ktrong(s)){
printf("%d",pop(s));
}
clear(s);
printf("
");
}
void main(){
int n,chon,t;
stack s;
do{
printf("
1. Khoi tao stack.");
printf("
2. Dua mot phan tu vao trong stack.");
printf("
3. Lay mot phan tu ra khoi stack.");
printf("
4. Chuyen doi mot so sang dang nhi phan.");
printf("
5. Thoat");
printf("
Moi chon chuong trinh can thuc hien: ");
scanf("%d",&chon);
switch(chon){
case 1: khoitao(s);printf("
Stack da duoc khoi tao.
");break;
case 2: printf("
Moi nhap phan tu can dua vao: ");scanf("%d",&n);
push(s,n);break;
case 3: printf("
Phan tu lay ra la: %d",pop(s));break;
case 4: printf("
Moi nhap so can chuyen: ");fflush(stdin);scanf("%d",&t);
clear(s);nhiphan(s,t);break;
}
}while(chon != 5);
getch();
}
//////////////////////////4.CPP/////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct sinhvien{
int masinhvien;
char hoten[25];
};
struct node{
sinhvien info;
node *next;
};
struct list{
node *pfirst,*plast;
};
void nhap(sinhvien &sv){ //nhap du lieu cho 1 sinh vien
printf("
Ma sinh vien: ");fflush(stdin);scanf("%d",&sv.masinhvien);
printf("
Ho va ten: ");fflush(stdin);gets(sv.hoten);
}
void xuat(sinhvien &sv,int stt){ //xuat du lieu ve 1 sinh vien
printf("
| %d |%8d |%14s |",stt,sv.masinhvien,sv.hoten);
printf("
-----------------------------------------------");
}
//---------------------------Ket thuc phan khai bao----------------------------
void make(list &d){ //khoi tao danh sach rong
d.pfirst=d.plast=NULL;
}
int empty(list &d){ //ha'm kiem tra rong
if(d.pfirst==NULL) return 1;
else return 0;
}
void duyet(list &d){
node *p;
p=d.pfirst;
int stt=0;
printf("
-----------------------------------------------");
printf("
| STT | Ma sinh vien | Ho va ten |");
printf("
-----------------------------------------------");
while(p!=NULL){
stt++; //stt tang dan de^? in ra cho no dep ko thac mac :))
xuat(p->info,stt); //xuat ra gia tri
p=p->next; //moi 1 vong' lap, con tro p se~ tro? vao phan tu tiep theo, cho den^' het danh sach tuc la khi p->next=NULL
}
}
void themdau(list &d,sinhvien &sv){ //ham' the^m 1 phan^' tu? vao da^'u danh sach'
node *p=new node; //tao ra 1 phan tu node , con tro p tro? vao' phan tu moi' tao. ra
p->info=sv; //gan' gia tri cua phan tu moi do = sv
if(empty(d)){
d.pfirst=d.plast=p; //neu danh sach rong, phan tu dau va cuoi deu = p
p->next=NULL;
}
else{
p->next=d.pfirst; //p la phan tu dau, nen pfirst luc' nay phai tro vao p
d.pfirst=p; //de^? chi? ra vi tri ptu dau cua danh sach'
} //ne^'u ko chi? cac' ham' ve^' sau se~ bi sai le^ch.
}
void timkiem(list &d,int k){
node *p;
p=d.pfirst;
int found=0;
while(p!=NULL && found==0){
if(p->info.masinhvien==k){
printf("
-----------------------------------------------");
printf("
| STT | Ma sinh vien | Ho va ten |");
printf("
-----------------------------------------------");
xuat(p->info,1);
found=1; //tim thay sinh vien, found=1 de vong lap ket thuc ngay tai day^
}
p=p->next;
}
if(found==0) printf("
Khong tim thay sinh vien
"); //vong lap ket thuc ma ko tim ra thi in ra ko tim thay
}
void xoatruock(list &d,int &k){ //ham' xoa' phan tu truoc vi tri thu k
node *p;
node *q;
p=d.pfirst;
int found=0,count=1;
if(empty(d)){
printf("
\t Danh sach rong.
");
return;
}
if(k==2){ //k=2 tuc la xoa vi tri dau^' tien
d.pfirst=d.pfirst->next;//dich con tro first tien^' len^ 1 phan^' tu
p->next=NULL; //cat dut lien ket cua p voi ds
free(p); //xoa p
duyet(d); //xoa thanh cong thi duyet de in ra ds sau khi da~ xoa'
}
while(p!=NULL && found==0){
if(p->next==NULL){ //tranh' truong hop nhap k qua lon hoc qua nho?
printf("
Khong tim thay.
");
}
else if(count==(k-2)){
q=p->next; //khi count=k-2 thi p dang tro vao vi tri k-2 va q tro? vao vi tri thu k-1
if(q->next==NULL){ //q->next==NULL tuc la q dang tro vao vi tri cuoi cung' cua ds
d.plast=p; //dua con tro d.plast lui' ve^' 1 phan^' tu, tuc la p
p->next=NULL; //p se~ la phan tu cuoi cung sau khi q bi xoa', nen p->next phai = NULL
}//kiem tra de tranh truong hop sau khi xoa q(dang tro? vao vi tri cuoi cung) thi ds bi mat d.plast
else{
p->next=q->next;//q bi xoa', nen p->next phai tro? vao vi tri ma' q dang tro? toi'
q->next=NULL; //cat dut lien ket cua q voi danh sach'
} //cat dut lien ket cua q voi ds
free(q); //xoa' q
found=1; //found=1 khi xoa' thanh' cong^, vong' lap ket thuc ngay tai. day^
duyet(d); //xoa' thah' cong^ thi in ra danh sach'
}
p=p->next; //con tro? p dich sang phan tu tiep theo sau moi vong' lap^.
count++; //count dung' de^? de^'m, dem^' den^' khi nao count == k-2 thi thuc hien cong^ viec^. tren^
}
}
void main(){
sinhvien sv;
list d;
int chon,k;
clrscr;
do{
printf("
1. Khoi tao");
printf("
2. Them dau");
printf("
3. Tim kiem sinh vien theo ma sinh vien");
printf("
4. Xoa 1 phan tu truoc vi tri k");
printf("
5. Duyet danh sach.");
printf("
6. Thoat");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:make(d);printf("
Danh sach da duoc khoi tao.
");break;
case 2:nhap(sv);themdau(d,sv);duyet(d);break;
case 3:printf("
Moi ma sinh vien can tim: ");fflush(stdin);scanf("%d",&k);
timkiem(d,k);break;
case 4:printf("
Moi nhap vi tri can xoa: ");fflush(stdin);scanf("%d",&k);
xoatruock(d,k);break;
case 5:duyet(d);break;
};
}while(chon!=6) ;
getch();
}
Bạn đang đọc truyện trên: Truyen2U.Com