Code:
#include"stdio.h"
#include"conio.h"
void nhap(int a[],int *n)//ham nhap mang so nguyen:;
{int i;
printf("\nnhap gioi han cua cac phan tu:");
scanf("%d",n);
for(i=0;i<*n;i++)
{printf("nhap phan tu thu a[%d]",i+1);
scanf("%d",&a[i]);
}
}
void in(int a[],int n)//ham in day so:;
{int i;
for(i=0;i<n;i++)
printf("%3d",a[i]);
}
void hoanvi(int *a,int *b)//ham hoan vi;
{int p;
p=*a;
*a=*b;
*b=p;
}
void tuyentinh(int a[],int n,int x)//ham tim kiem tuyen tinh ;
{int i,*p,kt=1;
p=a;
for(i=0;i<n;i++)
if(*(p+i)==x)
{printf("co so can tim");
kt=0;
break;
};
if( kt==1)
printf("\n khong co so can tim");
}
void nhiphan(int a[],int n,int x) //chuong trinh tim kiem nhi phan
{
int i,j,right,left,middle,kt=1;
left=0;
right=n-1;
printf("nhap gia tri can tim:");
scanf("%d",&x);
//Doan ma sap xep day so tang dan de tim kiem cho ket qua cao;
for(i=0;i<n-1;i++)
for(j=n-1;j>i;j--)
if(a[j]<a[j-1])
hoanvi(&a[j],&a[j-1]);//goi ham hoan vi ;
do
{
middle=(left+right)/2;
if(x==a[middle])
{kt=0;
printf("tim thay gia tri %d trong mang",x);
break;
}
else if(x<a[middle])
right=middle-1;
else left=middle+1;
}
while (left<=right);
if(kt==1)
printf("khong tim thay gia tri %d trong mang",x);
}
void selectionsort(int a[],int n)//sap xep chon truc tiep;
{int i,j,min;
for(i=0;i<n-1;i++)
{min=i;
for(j=i+1;j<n;j++)
if(a[j]<a[min])
min=j;
if(min!=i)
hoanvi(&a[min],&a[i]);
}
printf("day da sap xep tang dan la:");
in(a,n);
}
void insertionsort(int a[],int n)//sap xep chen truc tiep;
{
int pos,i,x;
for(i=1;i<n;i++)
{x=a[i];
pos=i-1;
while((pos>=0)&&(a[pos]>x))
{a[pos+1]=a[pos];
pos=pos-1;
}
a[pos+1]=x;
}
printf("day da sap xep la:");
in(a,n);
}
void bubblesort(int a[],int n) //sap xep noi bot;
{int i,j;
for(i=0;i<n-1;i++)
for(j=n-1;j>i;j--)
if(a[j]<a[j-1])
hoanvi(&a[j],&a[j-1]);//goi ham hoan vi ;
printf("day da sap sep tang dan theo phuong phap noi bot la:");
in(a,n);
}
void shellsort(int a[],int n) //sap xep voi do dai buoc giam dan.;
{int k=3,h[3]={6,4,1},i,j,x,l,t;
for(t=0;t<k;t++)
{l=h[t];
for(i=l;i<n;i++)
{j=i-l;
x=a[i];
while((j>=0)&&(x<a[j]))
{a[j+l]=a[j];
j=j-l;
}
a[j+l]=x;
}
}
printf("day so sau khi sap xep tang dan la:");
in(a,n);
}
void quicksort(int a[],int l,int r)//phuong phap sap xep nhanh;
{int i,j,x;
x=a[(l+r)/2];
i=l;
j=r;
do
{while(a[i]<x)
i++;
while(a[j]>x)
j--;
if(i<=j)
{hoanvi(&a[i],&a[j]);
i++;
j--;
}
} while(i<j);
if(l<j)quicksort(a,l,j);
if(i<r) quicksort(a,i,r);
}
void Shift(int a [ ],int l, int r)
{ int x, i, j, cont;
i = l; j = 2*i+1;
cont = 1;
x = a[i ];
while ((j<=r)&& (cont))
{ if (j <r)
if (a[j]>a[j+1])
j=j+1;
if (a[j]>x)
cont = 0;
else
{ hoanvi(&a[i],&a[j]);
i = j;
j=2*i+1;
}
}
}
void CreateHeap(int a[ ],int N)
{
int i;
i = N/2;
while (i >0)
{ i--;
Shift(a,i,N-1);
}
}
void Heapsort(int a[ ],int N)
{
int r;
r = N-1;
while (r >0)
{
hoanvi(&a[0],&a[r]);
r--;
Shift(a,0,r);
}
}
void main()
{clrscr();
textcolor(9);
textbackground(11);
tt:
printf("\n");
cprintf(" Bai tap lon cau truc du lieu va giai thuat ");
printf("\n");
printf("\nname :Dao Manh Thang");
printf("\nbirthday :27/12/1987");
printf("\nclass :CN1K5C");
printf("\nteacher :Dong Thi Lan");
printf("\n");
cprintf("\n MENU \r");
cprintf("\nban nhap vao so [1] chuong trinh tim kiem tuyen tinh\r");
cprintf("\nban nhap vao so [2] chuong trinh tim kiem nhi phan\r");
cprintf("\nban nhap vao so [3] chuong trinh sap xep chon truc tiep\r");
cprintf("\nban nhap vao so [4] chuong trinh sap xep chen truc tiep\r");
cprintf("\nban nhap vao so [5] chuong trinh sap xep Bubllesort\r");
cprintf("\nban nhap vao so [6] chuong trinh sap xep shellsort\r");
cprintf("\nban nhap vao so [7] chuong trinh sap xep quicksort\r");
cprintf("\nban nhap vao so [8] chuong trinh sap xep Heapsort\r");
cprintf("\nban bam phim [X] xe thoat khoi chuong trinh <=> Exit\r");
printf("\n");
int a[100],n,i,j,x,k,r;
char kt,ch;
printf("\nnhap mot ky tu:");
scanf("%c",&kt);
switch(kt)
{case '1':t1:
{cprintf("\nchuong trinh tim kiem tuyen tinh\r");
nhap(a,&n);
printf("nhap so can tim:");
scanf("%d",&x);
tuyentinh(a,n,x);
printf("\nBan co muon tiep tuc chuong trinh tim kiem tuyen tinh khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t1;
else goto tt;
}
case '2': t2:
{cprintf("\nchuong trinh tim kiem nhi phan\r");
nhap(a,&n);
nhiphan(a,n,x);
printf("\nBan co muon tiep tuc chuong trinh tim kiem Nhi phan khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t2;
else goto tt;
}
case '3': {t3:
cprintf("\nchuong trinh sap xep chon truoc tiep:\r");
nhap(a,&n);
selectionsort(a,n);
printf("\nBan co muon tiep tuc chuong trinh sap xep chon truoc tiep khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t3;
else goto tt;
}
case '4':{t4:
cprintf("\nchuong trinh sap xep theo phuong phap chen truc tiep:\r");
nhap(a,&n);
insertionsort(a,n);
printf("\nBan co muon tiep tuc chuong trinh sap xep chen truoc tiep khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t4;
else goto tt;
}
case '5':{t5:
cprintf("\nchuong trinh sap xep theo phuong phap noi bot:\r");
nhap(a,&n);
bubblesort(a,n);
printf("\nBan co muon tiep tuc chuong trinh sap xep noi bot khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t5;
else goto tt;
}
case '6':{t6:
cprintf("\nchuong tring sap xep theo phuong phap sap xep do dai giam dan:\r");
nhap(a,&n);
shellsort(a,n);
printf("\nBan co muon tiep tuc chuong trinh sap xep do dai buoc giam dan khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t6;
else goto tt;
}
case '7':{t7:
cprintf("\nchuong tring sap xep theo phuong phap sap xep nhanh:\r");
nhap(a,&n);
quicksort(a,0,n-1);
printf("day da sap xep la:");
in(a,n);
printf("\nBan co muon tiep tuc chuong trinh sap xep nhanh (Quicksort) khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t7;
else goto tt;
}
case '8':{t8:
cprintf("\nchuong tring sap xep theo phuong phap sap xep Vun dong:\r");
nhap(a,&n);
Heapsort(a,n);
printf("day da sap xep giam dan la:");
in(a,n);
printf("\nBan co muon tiep tuc chuong trinh sap xep Vung dong (Heapsort) khong? Y/N\r");
printf("\n");
scanf("%c",&ch);
ch=getch();
if(ch=='y'||ch=='Y')goto t8;
else goto tt;
}
case 'x':{ cprintf("\nBan muon thoat chuong trinh dung khong ? Y/N :=");
scanf("%c",&ch);
ch=getch();
if(ch=='n'||ch=='N')goto tt;
}
}
getch();
}
<=====================================>