///////////////////////////1.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){
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){
printf("
| %d |%8d |%14s |",stt,sv.masinhvien,sv.hoten);
printf("
-----------------------------------------------");
}
//---------------------------Ket thuc phan khai bao---------------------------
void make(list &d){
d.pfirst=d.plast=NULL;
}
int empty(list &d){
if(d.pfirst==NULL) return 1;
else return 0;
}
void themcuoi(list &d,sinhvien &sv){
node *p=new node;
p->info=sv;
p->next=NULL;
if(empty(d)){
d.pfirst=d.plast=p;
return;
}
else{
d.plast->next=p;
d.plast=p;
return;
}
}
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++;
xuat(p->info,stt);
p=p->next;
}
}
void themk(list &d,int &k){
node *p=new node;
node *q=new node;
p=d.pfirst;
sinhvien sv;
int found=0,count=1,dem=0;
while(p!=NULL){
p=p->next;
dem++;
}
if(k==0){
nhap(sv);
q->info=sv;
q->next=d.pfirst;
d.pfirst=q;
duyet(d);
}
else if(k>=(dem+1)){
printf("
Khong the them.
");
}
else{
nhap(sv);
p=d.pfirst;
while(p!=NULL && found==0){
if(count==k){
q->next=p->next;
q->info=sv;
p->next=q;
found=1;
duyet(d);
}
if(p->next==NULL){
themcuoi(d,sv);
}
p=p->next;
count++;
}
}
}
void main(){
sinhvien sv;
list d;
int chon,k;
do{
printf("
1. Khoi tao");
printf("
2. Them cuoi");
printf("
3. Xem danh sach");
printf("
4. Them 1 phan tu sau vi tri k");
printf("
5. 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);themcuoi(d,sv);duyet(d);break;
case 3:duyet(d);break;
case 4:printf("
Moi nhap vi tri can them: ");fflush(stdin);scanf("%d",&k);
themk(d,k);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){
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){
printf("
| %d |%8d |%14s |",stt,sv.masinhvien,sv.hoten);
printf("
-----------------------------------------------");
}
//---------------------------Ket thuc phan khai bao----------------------------
void make(list &d){
d.pfirst=d.plast=NULL;
}
int empty(list &d){
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++;
xuat(p->info,stt);
p=p->next;
}
}
void themdau(list &d,sinhvien &sv){
node *p=new node;
p->info=sv;
if(empty(d)){
d.pfirst=d.plast=p;
p->next=NULL;
}
else{
p->next=d.pfirst;
d.pfirst=p;
}
}
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;
}
p=p->next;
}
if(found==0) printf("
Khong tim thay sinh vien
");
}
void xoatruock(list &d,int &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){
d.pfirst=d.pfirst->next;
p->next=NULL;
free(p);
duyet(d);
return;
}
while(p!=NULL && found==0){
if(p->next==NULL){
printf("
Khong tim thay.
");
}
else 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 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 : ");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();
}
////////////////////////////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;
else 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);
}
s.phead=NULL;
}
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;
}
}
void pop(stack &s){
node *p;
int x;
if(ktrong(s)){
printf("Stack rong");
return;
}
else{
p=s.phead;
s.phead=s.phead->next;
x=p->info;
p->next=NULL;
free(p);
printf("%d",x);
}
}
void nhiphan(int n){
stack s;
khoitao(s);
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)){
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: ");pop(s);printf("
");break;
case 4: printf("
Moi nhap so can chuyen: ");scanf("%d",&t);
nhiphan(t);break;
}
}while(chon != 5);
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;
}
}
void get(queue &q){
node *p=new node;
if(ktrong(q)){
printf("Queue rong.");
}
else{
p=q.pfirst;
int x=p->info;
q.pfirst=p->next;
p->next=NULL;
free(p);
printf("%d",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(float x){
queue q;
khoitao(q);
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)){
get(q);
}
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: ");get(q);printf("
");break;
case 4: printf("
Moi nhap so can chuyen: ");fflush(stdin);scanf("%f",&x);
nhiphan(x);break;
}
}while(chon != 5);
getch();
}
///////////////////////7.cpp////////////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
#define MAX 20
template <class T>
void swap(T& x,T& y){
T tmp=x;x=y;y=tmp;
};
struct sinhvien{
int masinhvien;
char hoten[25];
};
//---------------------------------Ket thuc khai bao------------------------------
void nhap(sinhvien a[],int &n){
printf("
Moi nhap so luong sinh vien: ");fflush(stdin);scanf("%d",&n);
for(int i=0;i<n;i++){
printf("
Sinh vien thu %d",i+1);
printf("
\tMa sinh vien: ");fflush(stdin);scanf("%d",&a[i].masinhvien);
printf("
\tHo va ten: ");fflush(stdin);gets(a[i].hoten);
}
}
void xuat(sinhvien a[],int &n){
int stt=1;
printf("
-----------------------------------------------");
printf("
| STT | Ma sinh vien | Ho va ten |");
printf("
-----------------------------------------------");
for(int i=0;i<n;i++){
printf("
| %d |%8d |%14s |",stt,a[i].masinhvien,a[i].hoten);
printf("
-----------------------------------------------");
stt++;
}
}
void sx_chon(sinhvien a[],int n){
int k;
for(int i=0;i<n-1;i++){
k=i;
for(int j=i+1;j<n;j++){
if(a[j].masinhvien < a[k].masinhvien) k=j;
}
swap(a[i],a[k]);
}
xuat(a,n);
}
void sv_heap(sinhvien a[],int n) {
int i, s, f;
sinhvien x;
for (i = 1; i <= n; i++) {
x = a[i];
s = i;
while (s > 0 && x.masinhvien > a[(s-1)/2].masinhvien) {
a[s] = a[(s-1)/2];
s = (s-1)/2;
}
a[s] = x;
}
for (i = n; i > 0; i--) {
x = a[i]; a[i] = a[0];
f = 0;
s = 2 * f + 1;
if(s + 1 < i && a[s].masinhvien < a[s + 1].masinhvien) s = s + 1;
while (s < i && x.masinhvien < a[s].masinhvien) {
a[f] = a[s];
f = s;
s = 2 * f + 1;
if (s + 1 < i && a[s].masinhvien < a[s + 1].masinhvien) s = s + 1;
}
a[f] = x;
}
xuat(a,n);
}
void main(){
sinhvien a[MAX];
int n,chon;
do{
printf("
1. Nhap danh sach");
printf("
2. Xem danh sach ");
printf("
3. Sap xep tang dan bang SELECTION Sort");
printf("
4. Sap xep tang dan bang HEAP Sort");
printf("
5. Thoat");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:nhap(a,n);break;
case 2:xuat(a,n);break;
case 3:sx_chon(a,n);break;
case 4:sv_heap(a,n);break;
}
}while(chon!=5);
}
///////////////////////////////8.cpp//////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 20
template <class T>
void swap(T& x,T& y){
T tmp=x;x=y;y=tmp;
};
struct sinhvien{
int masinhvien;
char hoten[25];
};
//---------------------------------Ket thuc khai bao------------------------------
void nhap(sinhvien a[],int &n){
printf("
Moi nhap so luong sinh vien: ");scanf("%d",&n);
for(int i=1;i<=n;i++){
printf("
Sinh vien thu %d",i);
printf("
\tMa sinh vien: ");scanf("%d",&a[i].masinhvien);
printf("
\tHo va ten: ");fflush(stdin);gets(a[i].hoten);
}
}
void xuat(sinhvien a[],int &n){
int stt=1;
printf("
-----------------------------------------------");
printf("
| STT | Ma sinh vien | Ho va ten |");
printf("
-----------------------------------------------");
for(int i=1;i<=n;i++){
printf("
| %d |%8d |%14s |",stt,a[i].masinhvien,a[i].hoten);
printf("
-----------------------------------------------");
stt++;
}
}
void bubblesort(sinhvien a[],int &n) {
int i,doicho;
do {
doicho=0;
for (i=1;i<=n;i++)
if (a[i].masinhvien > a[i+1].masinhvien) {
swap(a[i],a[i+1]);
doicho = 1;
}
} while (doicho==1);
}
void mergesort(sinhvien a[], int &n) {
int i, j, k, low1, up1, low2, up2;
int size;
sinhvien *Listtmp = new sinhvien[n + 1];
size = 1;
while (size < n) {
low1 = 1; k = 1;
while (low1 + size <= n) {
low2 = low1 + size;
up1 = low2 - 1;
up2 = (low2 + size - 1 <= n) ? low2 + size - 1 : n;
for (i = low1, j = low2; i <= up1 && j <= up2; k++)
if(a[i].masinhvien <= a[j].masinhvien) Listtmp[k] = a[i++];
else Listtmp[k] = a[j++];
for(; i <= up1; k++) Listtmp[k] = a[i++];
for(; j <= up2; k++) Listtmp[k] = a[j++];
low1 = up2 + 1;
}
for(i = low1; k <= n; i++) Listtmp[k++] = a[i];
for(i = 1; i <= n; i++) a[i] = Listtmp[i];
size *= 2;
}
}
void main(){
sinhvien a[MAX];
int n,chon;
do{
printf("
1. Nhap danh sach");
printf("
2. Xem danh sach ");
printf("
3. Sap xep tang dan bang BUBLE Sort");
printf("
4. Sap xep tang dan bang MERGE Sort");
printf("
5. Thoat");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:nhap(a,n);break;
case 2:xuat(a,n);break;
case 3:bubblesort(a,n);xuat(a,n);break;
case 4:mergesort(a,n);xuat(a,n);break;
}
}while(chon!=5);
}
///////////////////////////9.cpp///////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
#define MAX 20
template <class T>
void swap(T& x,T& y){T
tmp=x;x=y;y=tmp;
};
struct sinhvien{
int masinhvien;
char hoten[25];
};
//---------------------------------Ket thuc khai bao------------------------------
void nhap(sinhvien a[],int &n){
printf("
Moi nhap so luong sinh vien: ");fflush(stdin);scanf("%d",&n);
for(int i=0;i<n;i++){
printf("
Sinh vien thu %d",i+1);
printf("
\tMa sinh vien: ");fflush(stdin);scanf("%d",&a[i].masinhvien);
printf("
\tHo va ten: ");fflush(stdin);gets(a[i].hoten);
}
}
void xuat(sinhvien a[],int &n){ //xuat du lieu ve 1 sinh vien
int stt=1;
printf("
-----------------------------------------------");
printf("
| STT | Ma sinh vien | Ho va ten |");
printf("
-----------------------------------------------");
for(int i=0;i<n;i++){
printf("
| %d |%8d |%14s |",stt,a[i].masinhvien,a[i].hoten);
printf("
-----------------------------------------------");
stt++;
}
}
void sx_chen(sinhvien a[],int n){
for(int i=1;i<n;i++){
sinhvien temp=a[i];
int j=i-1;
while(a[j].masinhvien > temp.masinhvien && j>=0 ){
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
xuat(a,n);
}
void partition(sinhvien a[],int low,int up,int &privot){
sinhvien privital=a[low];
int i=low;
int j=up;
while(i<j){
while(a[i].masinhvien <= privital.masinhvien && i<up) i++;
while(a[j].masinhvien > privital.masinhvien) j--;
if(i<j) swap(a[i],a[j]);
}
swap(a[low],a[j]);privot=j;
}
void sx_nhanh(sinhvien a[],int low,int up){
int privot;
if(low>up) return;
partition(a,low,up,privot);
sx_nhanh(a,low,privot-1);
sx_nhanh(a,privot+1,up);
}
void main(){
sinhvien a[MAX];
int n,chon;
do{
printf("
1. Nhap danh sach");
printf("
2. Xem danh sach ");
printf("
3. Sap xep tang dan bang INSERT Sort");
printf("
4. Sap xep tang dan bang QUICK Sort");
printf("
5. Thoat");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:nhap(a,n);break;
case 2:xuat(a,n);break;
case 3:sx_chen(a,n);break;
case 4:sx_nhanh(a,0,n-1);xuat(a,n);break;
}
}while(chon!=5);
}
////////////////////////////////////////11.cpp/////////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
struct sinhvien{
char hoten[30];
int masinhvien;
};
struct node{
sinhvien info;
node *left,*right;
};
void nhap(sinhvien &sv){
printf("
Ten sinh vien: ");fflush(stdin);gets(sv.hoten);
printf("
Ma sinh vien: ");fflush(stdin);scanf("%d",&sv.masinhvien);
}
void in(){
printf("
\t\t --------------------------");
printf("
\t\t| Ho va ten | MSV | ");
printf("
\t\t --------------------------");
}
void xuat(sinhvien &sv){
printf("
\t\t|%9s |%6d |",sv.hoten,sv.masinhvien);
printf("
\t\t --------------------------");
}
//-------------------------------------------Ket thuc khai bao--------------------------------------------
void khoitao(node *&proot){
proot=NULL;
}
int ktrong(node *proot){
if(proot==NULL) return 1;
return 0;
}
node *makenode(sinhvien &sv){
node *p=new node;
p->info=sv;
p->left=NULL;
p->right=NULL;
return p;
}
node *timkiem(node *proot,int ma){
node *p=new node;
if(ktrong(proot)) return NULL;
if(proot->info.masinhvien==ma) return proot;
if(proot->info.masinhvien > ma) p=timkiem(proot->left,ma);
else p=timkiem(proot->right,ma);
return p;
}
void them(node *&proot,sinhvien &sv){
if(ktrong(proot)){
proot=makenode(sv);
return;
}
if(timkiem(proot,sv.masinhvien)){
printf("
Nut da ton tai ko the them.");
return;
}
if(proot->info.masinhvien > sv.masinhvien) them(proot->left,sv);
else them(proot->right,sv);
}
void duyetgiua(node *proot){
if(!ktrong(proot)){
duyetgiua(proot->left);
xuat(proot->info);
duyetgiua(proot->right);
}
}
node *timkiem2(node *proot,node *&fp,int &ma){
node *p=proot;
fp=NULL;
while(p!=NULL){
if(p->info.masinhvien==ma) return p;
if(proot->info.masinhvien > ma){
fp=p;
p=p->left;
}
else{
fp=p;
p=p->right;
}
}
return NULL;
}
void xoa(node *proot,int &ma){
node *fp,*p,*f,*rp,*q;
p=timkiem2(proot,fp,ma);
if(p==NULL){
printf("
Khong tim thay");
return;
}
if(p->left==NULL && p->right==NULL){
if(p==proot){free(proot);proot=NULL;return;}
if(fp->left==p){ fp->left=NULL;free(p);return;}
if(fp->right==p){fp->right=NULL;free(p);return;}
}
if(p->left!=NULL && p->right==NULL){
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){
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;
p->info=rp->info;
free(rp);
rp==NULL;
}
void main(){
node *proot,*p;
int chon,ma;
sinhvien sv;
do{
printf("
1.Khoi tao.");
printf("
2.Them nut.");
printf("
3.Duyet giua");
printf("
4.Xoa nut.");
printf("
5.Thoat.");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:khoitao(proot);printf("
Khoi tao thanh cong.
");break;
case 2:nhap(sv);them(proot,sv);break;
case 3:printf("
Nut goc la:");in();xuat(proot->info);
printf("
Cac phan tu cua cay nhi phan:
");in();duyetgiua(proot);break;
case 4:printf("
Moi nhap ma can bo: ");scanf("%d",&ma);xoa(proot,ma);in();duyetgiua(proot);break;
}
}while(chon!=5);
getch();
}
//////////////////////////////////////////12.cpp/////////////////////////////
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define true 1
#define false 0
struct sinhvien{
char hoten[30];
int masinhvien;
};
struct node{
sinhvien info;
node *left,*right;
};
void nhap(sinhvien &sv){
printf("
Ten sinh vien: ");fflush(stdin);gets(sv.hoten);
printf("
Ma sinh vien: ");fflush(stdin);scanf("%d",&sv.masinhvien);
}
void in(){
printf("
\t\t --------------------------");
printf("
\t\t| Ho va ten | MSV | ");
printf("
\t\t --------------------------");
}
void xuat(sinhvien &sv){
printf("
\t\t|%9s |%6d |",sv.hoten,sv.masinhvien);
printf("
\t\t --------------------------");
}
//-------------------------------------------Ket thuc khai bao--------------------------------------------
void khoitao(node *&proot){
proot=NULL;
}
int ktrong(node *proot){
if(proot==NULL) return 1;
return 0;
}
node *makenode(sinhvien &sv){
node *p=new node;
p->info=sv;
p->left=NULL;
p->right=NULL;
return p;
}
node *timkiem(node *proot,int ma){
node *p=new node;
if(ktrong(proot)) return NULL;
if(proot->info.masinhvien==ma) return proot;
if(proot->info.masinhvien > ma) p=timkiem(proot->left,ma);
else p=timkiem(proot->right,ma);
return p;
}
void them(node *&proot,sinhvien &sv){
if(ktrong(proot)){
proot=makenode(sv);
return;
}
if(timkiem(proot,sv.masinhvien)){
printf("
Nut da ton tai ko the them.");
return;
}
if(proot->info.masinhvien > sv.masinhvien) them(proot->left,sv);
else them(proot->right,sv);
}
void duyetgiua(node *proot){
if(!ktrong(proot)){
duyetgiua(proot->left);
xuat(proot->info);
duyetgiua(proot->right);
}
}
node *timkiem2(node *proot,node *&fp,int &ma){
node *p=proot;
fp=NULL;
while(p!=NULL){
if(p->info.masinhvien==ma) return p;
if(proot->info.masinhvien > ma){
fp=p;
p=p->left;
}
else{
fp=p;
p=p->right;
}
}
return NULL;
}
void xoa(node *proot,int &ma){
node *fp,*p,*f,*rp,*q;
p=timkiem2(proot,fp,ma);
if(p==NULL){
printf("
Khong tim thay");
return;
}
if(p->left==NULL && p->right==NULL){
if(p==proot){free(proot);proot=NULL;return;}
if(fp->left==p){ fp->left=NULL;free(p);return;}
if(fp->right==p){fp->right=NULL;free(p);return;}
}
if(p->left!=NULL && p->right==NULL){
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){
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;
p->info=rp->info;
free(rp);
rp==NULL;
}
void main(){
node *proot,*p;
int chon,ma;
sinhvien sv;
do{
printf("
1.Khoi tao.");
printf("
2.Them nut.");
printf("
3.Tim kiem theo ma sinh vien");
printf("
4.Xoa nut.");
printf("
5.Thoat.");
printf("
Moi nhap chuong trinh can chon: ");
scanf("%d",&chon);
switch(chon){
case 1:khoitao(proot);printf("
Khoi tao thanh cong.
");break;
case 2:nhap(sv);them(proot,sv);break;
case 3:printf("
Moi nhap ma sinh vien: ");scanf("%d",&ma);p=timkiem(proot,ma);
if(p==NULL) printf("
Khong tim thay.
");
else {in();xuat(p->info);}break;
case 4:printf("
Moi nhap ma sinh vien: ");scanf("%d",&ma);xoa(proot,ma);
in();duyetgiua(proot);break;
}
}while(chon!=5);
getch();
}
///////////////////////////////////CNPTK.CPP/////////////////////
#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){ //truyen vao *&proot thay vi *proot nhu cac' ham' khac'
proot=NULL; //khoitao va them 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;
}
else{
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 tim 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;
}
void 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();
}
Bạn đang đọc truyện trên: Truyen2U.Pro