WinFuture-Forum.de: [C]: Letztes Element eines Vektors ermitteln - WinFuture-Forum.de

Zum Inhalt wechseln

Nachrichten zum Thema: Entwicklung
Seite 1 von 1

[C]: Letztes Element eines Vektors ermitteln Effektive Methode


#1 Mitglied ist offline   Fabi 

  • Gruppe: aktive Mitglieder
  • Beiträge: 1.958
  • Beigetreten: 30. August 04
  • Reputation: 1
  • Geschlecht:Männlich

geschrieben 09. Februar 2013 - 14:05

Hi,

ich frage mich gerade, ob es eine effektive Methode gibt das letzte (gültige) Element eines Vektors auf effektive Weise zu ermitteln. Mit effektiv meine ich nicht das Druchlaufen des gesamten Vektors, bis ich das Ende erreicht habe.

Hier mal ein Beispiel um die Frage zu verdeutlichen:
#define LEN 5

void ausgabe( int *liste )
{
	int *last;
	int cnt = 0;
	
	/*Letztes Element aus der Liste ermitteln*/
	while( *liste != -1 )
		last = liste++;

	while( cnt < LEN - 1 )
	{
		printf( "Zahl: %d\n", *last-- );
		cnt++;
	}
}
int main( void )
{
	int *liste;

	liste = malloc( sizeof(int) * LEN );

	if( liste != NULL )
	{
		liste[0] = 4;
		liste[1] = 3;
		liste[2] = 2;
		liste[3] = 1;
		liste[4] = -1;
		
		ausgabe( liste );		
	}
	return 0;
}



Der Vektor wird mit -1 am Ende abgeschlossen, damit ich das Ende erkennen kann. Wie man aber in der Funktion ausgbe sieht muss ich erst ans Ende des Vektors "laufen" um die Speicheradresse des letzten Elements zu ermitteln.

Jetzt meine Frage, geht das auch irgendwie ohne die WHILE-Schleife?

Danke für eure Hilfe.

Grüße

Fabi
0

Anzeige



#2 Mitglied ist offline   Mr. Floppy 

  • Gruppe: VIP Mitglieder
  • Beiträge: 4.115
  • Beigetreten: 01. Juli 08
  • Reputation: 271
  • Geschlecht:Männlich

geschrieben 09. Februar 2013 - 15:46

Vielleicht verstehe ich die Frage nicht richtig, aber was meinst Du mit einem gültigen Element, alles != -1? Wozu brauchst Du die -1 überhaupt? Du weißt doch wie groß das Array bzw. der Vektor ist. Falls das letzte gültige Element auch schon vorm Ende des allozierten Speichers kommen kann, würde ich es mit einer verketteten Liste probieren. Da ist der Aufwand das letzte Element zu finden gleich 1. Nur das Einfügen und Löschen von Elementen ist dann mit etwas mehr Aufwand verbunden (Zeiger von Vorgänger und Nachfolger aktualisieren).
0

#3 Mitglied ist offline   Fabi 

  • Gruppe: aktive Mitglieder
  • Beiträge: 1.958
  • Beigetreten: 30. August 04
  • Reputation: 1
  • Geschlecht:Männlich

geschrieben 10. Februar 2013 - 13:05

Beitrag anzeigenZitat (Mr. Floppy: 09. Februar 2013 - 15:46)

Vielleicht verstehe ich die Frage nicht richtig, aber was meinst Du mit einem gültigen Element, alles != -1? Wozu brauchst Du die -1 überhaupt? Du weißt doch wie groß das Array bzw. der Vektor ist. Falls das letzte gültige Element auch schon vorm Ende des allozierten Speichers kommen kann, würde ich es mit einer verketteten Liste probieren. Da ist der Aufwand das letzte Element zu finden gleich 1. Nur das Einfügen und Löschen von Elementen ist dann mit etwas mehr Aufwand verbunden (Zeiger von Vorgänger und Nachfolger aktualisieren).

Ich denke ich habe meine Frage nicht ganz sauber formuliert.
Nehmen wir mal an ich habe einen Vektor und weiß die größe nicht und möchte/kann auch keine verkettete Liste verwenden.

Dann ist meine Frage, wie kann ich das letzte gültige Element möglichst performant ermitteln. Das -1 dient nur der Untermalung des Beispiels.

Grüße

Fabi
0

#4 _nobido_

  • Gruppe: Gäste

geschrieben 17. Februar 2013 - 18:30

Naja, jeh nachdem ob die Daten nach Ermittlung des letzten gültigen Element noch gebraucht werden oder nicht... Wie wäre es mit einem Stack?

greetz
0

#5 Mitglied ist offline   RalphS 

  • Gruppe: VIP Mitglieder
  • Beiträge: 8.895
  • Beigetreten: 20. Juli 07
  • Reputation: 1.126
  • Geschlecht:Männlich
  • Wohnort:Zuhause
  • Interessen:Ja

geschrieben 17. Februar 2013 - 22:27

Das klingt alles irgendwie nach Theoretischer Informatik, Übungsaufgabe ^_^

- Performantest: Direktzugriff, wenns die Datenstruktur hergibt. Das wär dann O(1).
- Enumerieren, letztes nehmen: O(n). Also wie oben. Und so ziemlich die langsamste Variante (realistisch gesehen. Man kriegt alles irgendwie langsamer.)

Wie schon angedeutet, eine Stackstruktur wäre das effizienteste. Nur halt nicht mit pop() greifen, sondern mit top().

Suchen wär auch ne Option - dann O(log n) -- steh aber grad ein bißchen auf dem Schlauch, wie man das Problem entsprechend umbauen müßte.
"If you give a man a fish he is hungry again in an hour. If you teach him to catch a fish you do him a good turn."-- Anne Isabella Thackeray Ritchie

Eingefügtes Bild
Eingefügtes Bild
0

Thema verteilen:


Seite 1 von 1

1 Besucher lesen dieses Thema
Mitglieder: 0, Gäste: 1, unsichtbare Mitglieder: 0