Từ 1 tới 8 trên tổng số 8 kết quả

Đề tài: Heap_sort...

  1. #1
    Ngày gia nhập
    12 2007
    Nơi ở
    Hanoi
    Bài viết
    3

    Arrow Heap_sort...

    chắc những ai đã từng học qua môn cấu trúc dữ liệu và giải thuật đều biết tới thuật toán sắp xếp này.
    Vậy có thể xem hộ mình code này ko? Chẳng biết là có lỗi ở đâu nữa...
    Code:
    #include<stdio.h>
    #define max 1000
    
    void max_heapify(int a[],int i, int n);
    void build_max_heap(int a[],int n);
    void heap_sort(int a[],int n);
    
    int main()
    {
      int i,n,a[max];
      printf("nhap vao so phan tu: ");scanf("%d",&n);
      printf("nhap vao cac phan tu of mang:\n");
      for(i=1;i<=n;i++)  { printf("a[%d]=",i);scanf("%d",&a[i]); }
      heap_sort(a,n);
      printf("mang sau khi sap xep la: \n");
      for(i=1;i<=n;i++)  printf("%d  ",a[i]);
      return 0;
    }
    
    void max_heapify(int a[],int i, int n)
    {
      int temp,t;
      if(2*i+1<n) t=(a[2*i+1]>a[2*i])?(2*i+1):(2*i);
      else t=2*i;
      if(a[i]<a[t]) {temp=a[i];a[i]=a[t];a[t]=temp;}
      max_heapify(a,t,n);
    }
    void build_max_heap(int a[],int n)
    {
      int i;
      for(i=n/2;i>=1;i--)  max_heapify(a,i,n);
    }
    void heap_sort(int a[],int n)
    {
      int temp,i;
      build_max_heap(a,n);
      for(i=n;i>=2;i--)
        {
    	  temp=a[1];a[1]=a[i];a[i]=temp;
    	  max_heapify(a,1,i-1);
    	}
     
    }
    Cảm ơn mọi người nhiều nhé!!!
    kimuzan

  2. #2
    Ngày gia nhập
    01 2008
    Bài viết
    41

    tớ nghĩ cậu sai cơ bản về mặt thuật toán ở hàm max heapify rồi,cậu đọc lại kỹ lý thuyết sẽ thấy ngay,hàm max heapify của cậu kô cần kiểm tra điều kiện đã gọi đệ qui-->gọi đệ qui liên tục cho đến khi segmentation fault,sửa xong hàm max heapify rồi thì mình debug vẫn thấy ra kết quả sai,có lẽ vẫn là do thuật toán sai thôi

  3. #3
    Ngày gia nhập
    06 2007
    Nơi ở
    UIT
    Bài viết
    44

    MÌnh chưa xem code của bạn nhưng mình có làm cái này rồi mình post lên bạn tham khảo nhé



    Code:
    void taoheap(int a[],int l,int r)
    {
        int x,i,j;
        i=l;
        j=2*i+1;
        x=a[i];
        while(j<=r)
        {
            if(j<r)
                 if(a[j]<a[j+1])
                    j++;
    
    
            if(a[j]<=x) return;
            else
            {
                a[i]=a[j];
                a[j]=x;
                i=j;
                j=2*i+1;
                x=a[i];
             }
    
        }
    }
    
    
    void taoheapdau(int a[],int n)
    {
         int l;
         l=n/2-1;
         while(l>=0)
         {
            taoheap(a,l,n-1);
            l=l-1;
         }
    }
    void HeapSort(int a[],int n)
    {
        int r;
        taoheapdau(a,n);
        r=n-1;
        while(r>0)
        {
            hoanvi(a[0],a[r]);
            r--;
            xuatmang(a,n);
                    printf("\n");
            if(r>0)
                taoheap(a,0,r);
        }
    }
    Đã được chỉnh sửa lần cuối bởi vtien_uit : 04-01-2008 lúc 07:09 AM.

  4. #4
    Ngày gia nhập
    01 2008
    Bài viết
    41

    @vtien:ban kô để code vào trong tag khó đọc quá
    @nkgiang
    Code:
    void max_heapify(int a[],int i, int n)
    {
      int temp,t;
      if(2*i+1<=n && a[2*i+1]>a[n])t=2*i+1;
      	else t=i;
      if(2*i<=n && a[2*i]>a[t])t=2*i;
      if(a[i]<a[t])
    	{ {temp=a[i];a[i]=a[t];a[t]=temp;}
      	  max_heapify(a,t,n);
    	}
    }
    mình nghĩ hàm max_heapify bạn nên sủa lại như trên,mình đã test vài trường hợp và thấy có vẻ đúng

  5. #5
    Ngày gia nhập
    12 2007
    Nơi ở
    Hanoi
    Bài viết
    3

    Hóa ra làm theo "thầy" vẫn là an toàn hơn cả hi`hi`...
    Code:
    if(2*i+1<=n && a[2*i+1]>a[n])t=2*i+1;
    sửa một tí sơ suất
    Code:
    if(2*i+1<=n && a[2*i+1]>a[i])t=2*i+1;
    Thanks Huy nhé!
    kimuzan

  6. #6
    Ngày gia nhập
    01 2008
    Bài viết
    41

    Mặc định Heap_sort...

    hihi kô phải là làm theo hay kô làm theo thầy,mà là cậu sai hẳn về thuật toán thôi,chứ heap sort thì có nhiều cách viết lắm,có đứa bạn tớ còn mở rộng để tăng tốc độ tính toán lên nữa cơ

  7. #7
    Ngày gia nhập
    06 2007
    Nơi ở
    UIT
    Bài viết
    44

    có đứa bạn tớ còn mở rộng để tăng tốc độ tính toán lên nữa cơ
    Bạn có thể đưa lên đây cho anh em chiêm ngưỡng được không

  8. #8
    Ngày gia nhập
    01 2008
    Bài viết
    0

    /*
    Chuong trinh: Thuc hanh phuong phap sap xep truc tiep
    */
    Code:
    #include<stdio.h>
    #include<conio.h>
    void HoanVi(int &a,int &b);
    void Shift(int a[],int left,int right);// Ham hieu chinh mang ->Dang Heap;
    void CreateHeap(int a[],int n);// Ham Tao
    void HeapSort(int a[],int n);// Ham chinh;
    void Xuat(int a[],int n);
    void main()
    {
    	int m[]={2,5,1,6,3,8,4,9,7,0};
    	int spt=9;
    	clrscr();
    	CreateHeap(m,spt);//hieu chinh day ban dau thanh heap
    	HeapSort(m,spt);//sap xep bang heap sort
    	Xuat(m,spt);
    	getch();
    }
    void HoanVi(int &a,int &b)
    {
    	int tmp;
    		tmp=a;
    		a = b;
    		b=tmp;
    }
    //hieu chinh day bat ki thanh heap
    void Shift(int a[],int left,int right)
    {
    	int x,i,j;
    	i=left;
    	j=2*i;
    	x=a[i];//phan tu cha
    	while(j<=right)
    	{
    		if(j<right)
    		if(a[j]<a[j+1])//xac dinh phan tu lien doi lon nhat
    			j++;
    			if(a[j]<=x)
    				return;//thoa quan he lien doi dung
    		else
    		{
    			a[i]=a[j];
    			i=j;//xet tiep kha nang hieu chinh lan truyen
    			j=2*i;//cap nhat phan tu lien doi moi
    			a[i]=x;//cap nhat phan tu cha moi
    		}
    	}
    }
    //tao mot heap
    void CreateHeap(int a[],int n)
    {
    	int left;
    	left=(n-1)/2;
    	while(left>=0)//
    	{
    		Shift(a,left,n-1);
    			left--;//xet tu giua ve dau mang
    	}
    }
    //sap sep bang heap sort
    void HeapSort(int a[],int n)
    {
    	int right;
    	CreateHeap(a,n);//tao heap truoc khi xep
    	right=n-1;
    	while(right>0)
    	{
    		HoanVi(a[0],a[right]);
    			right--;//lui ve truoc dua phan tu lon nhat ra sau mang
    		Shift(a,0,right);//hieu chinh day con lai thanh mot heap
    	}
    }
    void Xuat(int a[],int n)
    {
    	printf("\nMang vua sap xep lai la: \n\n\n");
    	for(int i=0;i<n;i++)
    		printf(" %d\t",a[i]);
    }
    --------------------------------------------------------
    Chú ý viết tiếng việt có dấu và đặt code vào tag
    Đã được chỉnh sửa lần cuối bởi Alviss : 06-01-2008 lúc 07:05 PM.

Các đề tài tương tự

  1. heap_sort
    Gửi bởi daretofail trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 02-12-2007, 07:10 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn