[C]Bài tập lớn cấu trúc dữ liệu và giải thuật

[DAo Manh Thang]

chương trình tìm kiếm và sắp xếp một đối tượng cho trước dùng cấu trúc dữ liệu và giải thuật ,gồm 8 hàm tìm kiếm vá sắp sếp đối tương,
<=============================================== >

#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();
}

<=====================================>
các pác tham khảo nếu thấy hay xin liên hệ
manhthangtk271287@yahoo.com
http://class12e.org

tôi rất xằn lòng giúp đỡ các bạn.

[PoPoPoPo]

Nếu bạn nào thích code của toàn bộ các bài tập về cấu trúc dữ liệu và giải thuật thì mail cho mình : thanhson150286@gmail.com
Bao gồm các thao tác trên tập số nguyên, số thực, số phức, ma trận, string,hệ thống File, các giải thuật đệ quy với các bài cái túi, người du lịch liệt kê hoán vị, tổ hợp, cách chia số n, bài toán quân hậu (các thuật toán sinh kế tiếp, quay lui, nhánh cận);stack,queue,link_list,cây,đồ thị và các bài toán tìm đường đi, chu trình, cây bao trùm.
Chúc vui vẻ!

[Xcross87]

Pete cần tìm thuật toán Parallel ... TV là Song Song

[shinichi_haha]

Mình có một cuốn sách tiếng anh nè, về VN đi pete mình cho mượn poto.hi hi

[shinichi_haha]

Bài này thực ra cũng chẳng có gì là ghê gớm. Còn về phần đọc thì cũng dễ hiểu thôi, tên các hàm đã chỉ ra đầy đủ thông tin về nó.

Mình và các bạn chỉ muốn nhắc thêm là viết code phải chú thích thêm phần mình viết chứ ngồi đọc code thì chắc cũng hiểu. Nhưng tốn thời gian lắm.