array Iteration

blurry333

ich hab grad voll den blackout.

wie kann man denn ein char array mit einer Schleife durchlaufen ?

for(int i=0;arr[i];i++)
{

cout<<arr[i]<<" ";

}

so gehts natürlich nicht

SeppJ

Wieso geht das so natürlich nicht? Das ist eine gängige Möglichkeit einen C-String zu durchlaufen.

padreigh

Vielleicht besser

int i = -1;
while (a[++i] != '\0')
{
std::cout << a[i];
}

damits nicht kracht ?

blurry333

Ihr habt recht.
Ich weiß auch woher mein Fehler kommt. Mein heapsort schreibt auf
die erste STelle eine 0. deswegen hat die Ausgabe dann beim ersten Buchstaben
abgebrochen. Es scheint noch ein winziger Fehler in meinem downheap oder heapsort zu sein. Kann sich das mal einer anschaun

void downheap(char* arr,int N,int i)
{    
	int j; char tmp= arr[i];
	while( i<N/2)
	{   j=2*i+1;  //linken Sohn finden
	   if(j<N-1 && arr[j] < arr[j+1]) j++; // groesseren sohn wählen
	   if(tmp >= arr[j])break;      Knoten groesser gleich
	   arr[i]=arr[j];i=j;     //Tausch swap
	}
	arr[i]=tmp ;

}

void heapsort(char* arr, int N)
{
	   int i;
	   for(i=N/2-1;i>=0;i--) downheap(arr,N,i);  // Subheap variante
	   while(N>0)
	   { 
		   char tmp=arr[0];
		   arr[0]=arr[N-1];
		   arr[N-1]=tmp;

		   downheap(arr,--N,0);
	   }
}

blurry333

ok hat sich alles erledigt.
Hab das array um 1 Byte zu groß angelegt. Scheint zu diesem komischen
Verhalten geführt zu haben, dass auf arr[0] eine 0 gestanden ist.

blurry333

Hier mein jetzt funktionierendes Programm

#include <iostream>

using namespace std;

void downheap(char* arr,int N,int i)
{    
	int j; char tmp= arr[i];
	while( i<N/2)
	{j=2*i+1;
	   if(j<N-1 && arr[j] < arr[j+1]) j++;
	   if(tmp >= arr[j])break;
	   arr[i]=arr[j];i=j;
	}
	arr[i]=tmp ;

}

void heapsort(char* arr, int N)
{
	   int i;
	   for(i=N/2-1;i>=0;i--) downheap(arr,N,i);
	   while(N>0)
	   { 
		   char tmp=arr[0];
		   arr[0]=arr[N-1];
		   arr[N-1]=tmp;

		   downheap(arr,--N,0);
	   }
}

void main(void){

	const int length=7;  // hier hatte ich vorher 8 übergeben =>Fehler ??

	char x[length+1]="ASTERIX";

	heapsort(x,length);

	for(int i=0;x[i];i++)
	{
		std::cout<<x[i];
	}
}

blurry333

klar die Länge des arrays geht ja in die Berechnung des heapSort mit ein.
Deswegen der Fehler

ich glaub die obige Implementierung ist die beste für den heapsort.
Sie beruht auf den subheaps.

SeppJ

blurry333 schrieb:

ich glaub die obige Implementierung ist die beste für den heapsort.
Sie beruht auf den subheaps.

Wodurch wird eine Implementierung besser als andere?

blurry333

indem sie weniger Vergleiche oder Kopieraktionen hat.
zumindest ist diese Implementierung für mich die bislang
logischste. Ich find sie klasse.

volkard

blurry333 schrieb:

Sie beruht auf den subheaps.

Du machst aber auch immer Sachen...
Jeder Heap beruht auf Subheaps.
Vielleicht würde ein Buch da helfen. Sedgewicks Algorithmen in C würde ich sagen.