{ printf("nhap phan tu thu %d:",i+1); NhapSinhVien(&sv);
L->element[i]=sv;
L->count++;i++;
printf("ban nhap tiep khong c/k? "); fflush(stdin);kt=getchar();
}
while (kt!='k');
}
//ham in danh sach sinh vien ra man hinh
void PrintList(list L)
{ int i;
Có thể bạn quan tâm!
-
Cấu trúc dữ liệu và giải thuật - CĐN Công nghiệp Hà Nội - 20 -
Cấu trúc dữ liệu và giải thuật - CĐN Công nghiệp Hà Nội - 21 -
Cấu trúc dữ liệu và giải thuật - CĐN Công nghiệp Hà Nội - 22 -
Cấu trúc dữ liệu và giải thuật - CĐN Công nghiệp Hà Nội - 24
Xem toàn bộ 200 trang tài liệu này.
if (EmptyList(L))
{ printf("Danh sach rong"); return;
}
for (i=0; i<L.count;i++) HienSinhVien(L.element[i]);
}
// ham InsertionSort sap xep danh sach theo ho ten
void InsertionSort (list *L)
{ int i, j;
Item temp;
for (i=1 ; i<L->count; i++)
{ temp=L->element[i]; j = i-1;
while ((j>=0) &&
(stricmp(temp.Hten,L->element[j].Hten)>0))
{
L->element[j+1] = L->element[j]; j--;
}
L->element[j+1]=temp ;
}
}
//ham SelectionSort sap xep theo ho ten
void SelectionSort (list *L)
{ int i, j, m;
Item temp;
for (i=0 ; i<L->count-1; i++)
{ m = i ;
for (j=i+1 ; j<L->count; j++)
if (stricmp(L->element[i].Hten,L->element[j].Hten)>0) m=j;
temp=L->element[i];
L->element[i]=L->element[m]; L->element[m]=temp ;
}
}
// ham InterchangeSort sap xep theo ho ten
void InterchangeSort(list *L)
{ int i, j; SinhVien temp;
for ( i=0; i<L->count-1;i++)
for ( j=i+1;j< L->count ;j++)
if (stricmp(L->element[i].Hten,L->element[j].Hten)>0)
{ temp=L->element[i];
L->element[i]= L->element[j]; L->element[j]=temp ;
}
}
//ham BubleSort sap xep theo ho ten
void BubleSort (list *L)
{ int i, j;
Item temp;
for (i=0 ; i<L->count-1; i++)
for (j=L->count-1 ; j<=i+1; j--)
if (stricmp(L->element[i].Hten,L->element[j].Hten)>0)
{ temp=L->element[j];
L->element[j]=L->element[j-1]; L->element[j-1]=temp ;
}
}
// ham QuickSort sap xep theo ho ten
void QuickSort(list *L, int left , int right)
{ int i, j;
Item key,temp;
key= L->element[left]; i = left; j = right;
do
{ while ((stricmp(L->element[i].Hten, key.Hten)<0) && (i <=
right))
i++;
while ((stricmp(L->element[j].Hten, key.Hten)>0) && (j >=left)) j--;
if(i <=j)
{
}
} while(i <= j); if(left<j)
temp=L->element[i];
L->element[i]=L->element[j]; L->element[j]=temp;
i++ ; j--;
QuickSort(L, left, j); if(i<right)
QuickSort(L, i, right);
}
//ham QuickSort sap xep theo masv
void QuickSortMSV(list *L, int left , int right)
{ int i, j;
Item key,temp;
key= L->element[left]; i = left; j = right;
do
{
while ((stricmp(L->element[i].masv,key.masv)<0) && (i <= right)) i++;
while ((stricmp(L->element[j].masv,key.masv)>0) && (j >=left)) j--;
if(i <=j)
{
temp=L->element[i];
L->element[i]=L->element[j]; L->element[j]=temp;
i++ ; j--;
}
} while(i <= j); if(left<j)
QuickSort(L, left, j); if(i<right)
QuickSort(L, i, right);
}
// ham Sequen-Search tim kiem theo masv
int Sequen_Search(list L, char X[])
{ int i=0;
for (i=0; i<L.count; i++)
if (stricmp(X,L.element[i].masv)==0)
return (i); return (-1);
}
/* ham Sequen_Search theo cach 2
int Sequen_Search1(list L, char X[])
{ int i; strcpy(L.element[L.count].masv,X); while (stricmp(X,L.element[i].masv)!=0)
i++;
if (i<L.count)
return (i);
}*/
else
return (-1);
//ham BinarySearch tim kiem theo masv
int BinarySearch (list L, char X[])
{ int mid, left=0, right=L.count-1; do
{
mid=(left+right)/2;
if (stricmp(X,L.element[mid].masv)==0)
return (mid);
else
if (stricmp(X,L.element[mid].masv)<0) right=mid-1;
else
left=mid+1;
} while(left<=right);
return -1;
}
//ham menu
int menu()
{ int chon; clrscr();
printf("n MOT SO GIAI TOAN VE SAP XEP VA TIM KIEMnn");
printf(" Nhan so tuong ung de chon chuc nang:n"); printf(" 1. Khoi tao danh sach n");
printf(" 2. Nhap cac phan tu cho danh sachn"); printf(" 3. In cac phan tu cua danh sachn");
printf(" 4. ham InsertionSort sap xep theo ho tenn"); printf(" 5. ham SelectionSort sap xep theo ho tenn"); printf(" 6. ham InterchangeSort sap xep theo ho tenn"); printf(" 7.ham BubleSort sap xep theo ho ten n"); printf(" 8.ham QuickSort sap xep theo ho ten n"); printf(" 9 ham Sequen-Search timf kiem theo masvn"); printf(" 10 ham BinarySearch tim kiem theo masv n"); printf(" 0. Thoat khoi chuong trinhn");
printf(" Nhap so tuong ung: "); scanf("%d",&chon); return (chon);
}
//ham chinh main
void main()
{list *L,*M; int chon,pos, n; char ma[10]; do
{ chon=menu(); switch (chon)
{
case 1:
initializeList(L); break;
case 2:
CreateList(L);M=L;
case 3:
case 4:
case 5:
case 6:
case 7:
break;
printf("n Cac phan tu co trong danh sach:nn") ; PrintList(*L);
getch(); break;
L=M;
InsertionSort (L);
printf(" Da sap xep theo ho tenn"); getch();
break;
L=M;
SelectionSort (L);
printf(" Da sap xep theo ho tenn"); getch();
break;
L=M;
InterchangeSort (L);
printf(" Da sap xep theo ho tenn"); getch();
break;
L=M;
BubleSort (L);
printf(" Da sap xep theo ho tenn"); getch();
break; case 8:
L=M;
case 9:
QuickSort (L,0,L->count-1); printf(" Da sap xep theo ho tenn");
getch(); break;
L=M;
printf(" Nhap ma sinh vien can tim: "); fflush(stdin); gets(ma);
pos= Sequen_Search(*L,ma); if (pos==-1)
printf("khong tim thay masv %sn", ma);
else
printf(" Da tim thay masv %s tai vi tri getch();
%dn",ma,pos);
break; case 10:
QuickSortMSV(L,0,L->count-1 ); printf(" Nhap ma sinh vien can tim: "); fflush(stdin); gets(ma);
pos= BinarySearch (*L,ma); if (pos==-1)
printf("khong tim thay masv %sn", ma);
else
printf(" Da tim thay masv %s tai vi tri %dn",ma,pos);
getch(); break;
default: printf ("n ban chon sai roi! ");
}
} while (chon!=0);
}