Bài tập cấu trúc dữ liệu cơ bản

jinyotino · 11 Tháng một 2010

Đây là bài tập về danh sách đặc, kĩ thuật tìm kiếm tuần tự, tìm kiếm nhị phân không đệ quy, có đệ quy, sắp xếp chọn,chèn,nổi bọt. Mình share cho bạn nào đang học cấu trúc dữ liệu cơ bản

#include <stdio.h>
#include <conio.h>

#define max 10

typedef struct
{
int element[max-1];
int last;
}list;

void make_list(list *L)
{
L->last=0;
}
int empty_list(list L)
{
return L.last==-1;
}

int full_list(list L)
{
return L.last==max-1;
}

void add_list(list *L,int x,int p)
{
if(full_list(*L))
printf("Danh sach day!");
else if(p<0 || p>L->last-1)
printf("Vi tri khong hop le");
else
{
for(int i=L->last-1;i>=p;i--)
L->element[i+1]=L->element;
L->element[p]=x;
L->last++;
}
}

void del_list(list *L,int p)
{
if(empty_list(*L))
printf("Danh sach rong!");
else if(p<0 || p>L->last-1)
printf("Vi tri khong hop le!");
else
{
for(int i=p;i<L->last;i++)
L->element=L->element[i+1];
L->last--;
}

}
void swap(int *a,int *b)
{
int tam;
tam=*a;
*a=*b;
*b=tam;
}

void sap_xep_chon(list *L)
{
for(int i=0;i<L->last;i++)
{
int m=i;
for(int j=i+1;j<L->last;j++)
{
if(L->element[j]<L->element[m])
m=j;
}
if(m!=i)
{
swap(&L->element,&L->element[m]);
}
}
}

void sap_xep_chen(list *L)
{
for(int i=1;i<L->last;i++)
{
int x=L->element,j=i-1;
while(x<L->element[j])
{
L->element[j+1]=L->element[j];
j--;
}
L->element[j+1]=x;
}
}

void sap_xep_noi_bot(list *L)
{
for(int i=0;i<=L->last-2;i++)
for(int j=L->last-1;j>=i+1;j--)
{
if(L->element[j]<L->element[j-1])
{
swap(&L->element[j],&L->element[j-1]);
}
}
}

int tim_kiem_tuan_tu(list L,int x)
{
int i=0;
while(i<L.last && L.element!=x)
i++;
if(i==L.last)
return -1;
else
return i;
}

int tim_kiem_nhi_phan1(list L,int x)
{
int l=0,r=L.last-1,m;
while(l<=r)
{
m=(l+r)/2;
if(x<L.element[m])
r=m-1;
else if(x>L.element[m])
l=m+1;
else
return m;
}
return -1;
}

int tim_kiem_nhi_phan2(int l,int r,list L,int x)
{
int loc,m;
if(l>r)
loc=-1;
else
{
m=(l+r)/2;
if(x<L.element[m])
loc=tim_kiem_nhi_phan2(l,m-1,L,x);
else if(x>L.element[m])
loc=tim_kiem_nhi_phan2(m+1,r,L,x);
else
loc=m;
}
return loc;
}

void main()
{
clrscr();
list *L;
make_list(L);
for(int i=0;i<5;i++)
{
printf("Nhap %d : ",i+1);
scanf("%d",&L->element);
L->last++;
}
printf("Xuat ra : ");
for(i=0;i<L->last;i++)
{
printf("%d ",L->element);
}
/*
int k,v;
printf("\n Nhap phan tu can nhap vao : ");
scanf("%d",&k);
printf("\n Nhap vi tri can chen : ");
scanf("%d",&v);
add_list(L,k,v-1);
printf("Update : ");
for(i=0;i<L->last;i++)
{
printf("%d ",L->element);
}
int x;
printf("\nNhap vi tri can xoa");
scanf("%d",&x);
del_list(L,x-1);
printf("Update : ");
for(i=0;i<L->last;i++)
{
printf("%d ",L->element);
}
*/

// printf("\nSau khi sap xep chon : ");
// sap_xep_noi_bot(L);
// printf("\nUpdate : ");
// for(i=0;i<L->last;i++)
// {
// printf("%d ",L->element);
// }
sap_xep_noi_bot(L);
printf("\nUpdate : ");
for(i=0;i<L->last;i++)
{
printf("%d ",L->element);
}
int a,b;
printf("\nNhap phan tu can tim kiem : ");
scanf("%d",&a);
b=tim_kiem_nhi_phan2(0,L->last-1,*L,a);
printf("Vi tri %d la %d ",a,b+1);
getch();
}

Đăng nhập hoặc Đăng ký

DIỄN ĐÀN 2MIT.ORG SẼ CHUYỂN SANG CHẾ ĐỘ READ-ONLY

Bài tập cấu trúc dữ liệu cơ bản

jinyotino

Chia sẻ trang này

Tìm kiếm hữu ích

Bài tập cấu trúc dữ liệu cơ bản

jinyotino

Chia sẻ trang này