Sortowanie typu Heap Sort

Odpowiedz Nowy wątek
2011-12-13 16:07
0

Witajcie programiści !
Piszę bo mam problem do opanowania, a dokładnie program do zrobienia w języku C++.
Zadanie znajduje się pod linkiem: http://imageshack.us/f/855/heapsort.jpg/

A tutaj jest mój pomysł na to wykonanie tylko wiem, że są tutaj błędy, pomogłaby mi jakaś osoba. Program nie jest trudny dla zorientowanych w programowaniu obiektowym. Jeśli macie jakiejś pytania piszcie.


#include "stdafx.h"
#include <iostream.h>
#include <conio.h>

using namespace std;
  void sortuj(char);
  struct punkt
   {
     float x;
     float y;
    };     
  int ile,xy;
  char ch; 
  punkt *tab; 
int main(int argc,char *argv[])
{
    cin >>x
  cout<<"podaj ile wsporzednych punktow chcesz wprowadzic ";
  cin>>ile;
   tab=new struct punkt[ile];  
    for(int i=0;i<ile;i++)
     {
       cout<<"podaj wspolrzedna x "<<i+1<<" punktu ";     
       cin>>tab[i].x;
       cout<<"podaj wspolrzedna y "<<i+1<<" punktu ";     
       cin>>tab[i].y;
       }
   system("cls");    
   cout<<"tablica wspolrzednych przed sortowaniem"<<endl;    
     for(int i=0;i<ile;i++)      
 cout<<"punkt "<<i+1<<" wspolrz. x="<<tab[i].x<<" wspolrz. y="<<tab[i].y<<endl;
 cout<<"jak chcesz sortowac wg wspolrz. x wpisz x, gdy y wpisz y ";
 cin>>ch;
 sortuj(ch);
  cout<<"tablica wspolrzednych po sortowaniu wg wspolrz. "<<ch<<endl;   
      for(int i=0;i<ile;i++)      
 cout<<"punkt "<<i+1<<" wspolrz. x="<<tab[i].x<<" wspolrz. y="<<tab[i].y<<endl;
 getch();      
delete [] tab;
 return 0;
}
    void sortuj(char ch)
 {  
   for(int i=1;i<ile;i++)
   for(int j=ile-1;j>=i;j--)
    { 
      if(ch=='x') if(tab[j-1].x<tab[j].x)     
      {
       float px=tab[j-1].x;  
       float py=tab[j-1].y;
       tab[j-1].x=tab[j].x;
       tab[j-1].y=tab[j].y;
       tab[j].x=px;
       tab[j].y=py;
      }
      if(ch=='y') if(tab[j-1].y<tab[j].y)     
      {
       float px=tab[j-1].x;  
       float py=tab[j-1].y;
       tab[j-1].x=tab[j].x;
       tab[j-1].y=tab[j].y;
       tab[j].x=px;
       tab[j].y=py;        
      }   
    } 
 }

Pozostało 580 znaków

2011-12-13 16:21
0

Pierwszy oczywisty błąd to używanie zmiennych globalnych (tutaj nie mają one żadnego uzasadnienia). Zmień funkcję sortuj, żeby przyjmowała jako parametry tablicę oraz jej długość.

Pozostało 580 znaków

2011-12-14 08:25
0

Słuszna uwaga, a czy teraz prawidłowo wykonałem kod z Heap sortem:

#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;

float dlugosc(int L[2],int R[2]){

return sqrt((L[0]-R[0])(L[0]-R[0])+(L[1]-R[1])(L[1]-R[1]));
}
void HEAP(int A[][2],int p,int q,int r){
int n1,n2,i,j,k;
n1=q-p+1;
n2=r-q;
int L[n1+1][2],R[n2+1][2];

for(i=0;i<n1;i++){
L[i][0]=A[p+i][0];
L[i][1]=A[p+i][1];
}
for(j=0;j<n2;j++){
R[j][0]=A[q+j+1][0];
R[j][1]=A[q+j+1][1];
}
L[n1][0]=100;
L[n1][1]=100;
R[n2][0]=100;
R[n2][1]=100;
i=0;
j=0;
for(k=p;k<=r;k++){
if(dlugosc(L[i],A[0]) <= dlugosc(R[j],A[0])){
A[k][0]=L[i][0];
A[k][1]=L[i][1];
i++;
}
else{
A[k][0]=R[j][0];
A[k][1]=R[j][1];
j++;
}
}
}

int HEAPSORT(int A[][2],int p,int q){
if(p==q)return 1;
int d=(p+q)/2;
HEAPSORT(A,p,d);
HEAPSORT(A,d+1,q);
HEAP(A,p,d,q);

return 0;
}
int main(){
cout <<"Podaj kolejno wspolrzedne"<<endl<<endl;
int n,i;
int A[101][2];
cin>>A[0][0];
cin>>A[0][1];
cin>>n;
n<100;
for(i=1;i<=n;i++){
cin>>A[i][0];
cin>>A[i][1];

}

HEAPSORT(A,1,n);
cout <<"Wynik";
for(i=1;i<=n;i++){

cout<<"\n";
cout<<A[i][0]<<" "<<A[i][1]<<"\n";

}

system("PAUSE");
return 0;
}

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0