Member(Array[Arrayelement]) einer Struktur löschen

outlop

Habe eine Möglichkeit gefunden, mithilfe dieses Links wo das "löschen" von Arrayelementen erklärt wird.
http://www.informatikerboard.de/board/archive/1306/thread.html

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

#define PERSONANZ 3

void initPerson();

struct structspieler{
		char spielername[20]; 
		int alter; 
		struct structgruppe{ 
			struct structperson{
				char personname[20];
				int wert1; 
				int wert2; 
			}person[PERSONANZ];
		char gruppename[20];
		int gruppenpunkte;
		}gruppe;
	}; 

struct structspieler spieler[1]; //Strukturvariable (Array)

void printArray(struct structspieler *spieler, int length){
	int index = 0; 
	if (length == 0) 
	{
		printf("Leer"); 
		return; 
	}

	//printf("%s\n", spieler[0].gruppe.person[index].personname);
	for(index = 0; index < length; index++)
	{
		printf("Person:%s Wert1:%d\n", spieler[0].gruppe.person[index].personname, spieler[0].gruppe.person[index].wert1); 
	}
	printf("\n");
}

void deleteElement(struct structspieler *spieler,int *len, int element){
	int index = 0; 

	if(element+1==*len){
		--*len; 
		return; 
	}

	//alle Elemente hinter dem zu löschenden Element um 1 nach vorne kopieren und zu löschendes Element überschreiben. 
	for (index = element; index < *len-1; index++)
	{
		spieler[0].gruppe.person[index] = spieler[0].gruppe.person[index + 1];
	}

	//die Länge um 1 verkürzen
	--*len; 
}

void initPerson(){
	//Werte in Strukturvariable schreiben
	strncpy(spieler[0].gruppe.person[0].personname, "prs1", sizeof(spieler[0].gruppe.person[0].personname)); 
	strncpy(spieler[0].gruppe.person[1].personname, "prs2", sizeof(spieler[0].gruppe.person[1].personname)); 
	strncpy(spieler[0].gruppe.person[2].personname, "prs3", sizeof(spieler[0].gruppe.person[2].personname)); 

	spieler[0].gruppe.person[0].wert1 = 10; 
	spieler[0].gruppe.person[0].wert2 = 10; 
	spieler[0].gruppe.person[1].wert1 = 20;
	spieler[0].gruppe.person[1].wert2 = 20;
	spieler[0].gruppe.person[2].wert1 = 30;
	spieler[0].gruppe.person[2].wert2 = 30;
}

int _tmain(int argc, _TCHAR* argv[])
{
	initPerson(); 
	int length = PERSONANZ; 
	printArray(spieler, length);
	deleteElement(spieler, &length, 1);
	printArray(spieler, length);

	getche();
	return 0;
}

outlop schrieb:

Habe eine Möglichkeit gefunden, mithilfe dieses Links wo das "löschen" von Arrayelementen erklärt wird.

Schön.

Das ist aber genau das, was Wutz vorgeschlagen hat.

Wenn du oft Elemente in einem Array "löschen" willst, würde ich dir eher zu verketteten Listen raten.
Vorteil: Kannst relativ leicht weitere Elemente hinzufügen und löschen.
Nachteil: 4 Byte Speicherverschwendung pro Node auf 32-Bit-Systemen ist dir gewiss (8 Byte auf 64-Bit, und wenn du von hinten nach vorne iterieren willst, sind's sogar 8/16 Byte).
Außerdem ist der Zugriff auf diese langsam, weil du immer die Liste durchgehen musst, um zu wissen, bei welchem Element du gerade bist.

[ironie]
Aber dafür kannst du dann ein Array mit Pointern machen, die auf die Elemente zeigen, dann ist der Zugriff wieder schnell.
[/ironie]

outlop

DirkB schrieb:

outlop schrieb:

Habe eine Möglichkeit gefunden, mithilfe dieses Links wo das "löschen" von Arrayelementen erklärt wird.

Schön.

Das ist aber genau das, was Wutz vorgeschlagen hat.

Ja, der Hinweis von Wutz war massgebend... Danke

outlop

dachschaden schrieb:

Wenn du oft Elemente in einem Array "löschen" willst, würde ich dir eher zu verketteten Listen raten.
Vorteil: Kannst relativ leicht weitere Elemente hinzufügen und löschen.
Nachteil: 4 Byte Speicherverschwendung pro Node auf 32-Bit-Systemen ist dir gewiss (8 Byte auf 64-Bit, und wenn du von hinten nach vorne iterieren willst, sind's sogar 8/16 Byte).
Außerdem ist der Zugriff auf diese langsam, weil du immer die Liste durchgehen musst, um zu wissen, bei welchem Element du gerade bist.

[ironie]
Aber dafür kannst du dann ein Array mit Pointern machen, die auf die Elemente zeigen, dann ist der Zugriff wieder schnell.
[/ironie]

Ok, teste ich mal, verkettete listen sind doch auch Strukturen ?

etwa so ?

struct structspieler{
	char spielername[20];
	int alter; 
	struct structgruppe gruppe; 
	struct structspieler *next; 
}

struct structgruppe{
	char gruppenname[20]; 
	int gruppenpunkte; 
	struct structperson person1; 
	struct structperson person2; 
	struct structperson person3; 
}

struct structperson{
	char personname[20];
	int wert1;
	int wert2; 
}

Wutz

Verkettete Listen sind akademisches Geschwätz und damit Praxismüll.

Wutz schrieb:

Verkettete Listen sind akademisches Geschwätz und damit Praxismüll.

dachschaden schrieb:

[ironie]
Aber dafür kannst du dann ein Array mit Pointern machen, die auf die Elemente zeigen, dann ist der Zugriff wieder schnell.
[/ironie]

@Wutz:
Kannst du das mal bitte erklären, ich suche nähmlich auch eine Möglichkeit eine große Anzahl von der selben Struktur anzulegen und mit der zu arbeiten. Dabei hatt ich auch verkettete Listen (noch nie damit gearbeite sondern nur darüber gelesen) im Hinterkopf. Eine weitere Möglichkeit die ich in Betracht ziehe ist der der Ironische Vorschlag von dachschaden, ich find den eigentlich ganz gut. Aber mangels Erfahrung und Wissen bin ich da auch noch etwas verunsichert. Ich denke mal, es kommt dabei ganz stark darauf an was man mit den Daten in der Struktur machen will. Wenn die pro Sekunde x-mal durchsucht werden ist die verkettete Liste vieleicht nicht die richtige Wahl. Wer hat da Erfahrung und kann dazu mal ein Paar Tips geben?

@jackass

Keine Ahnung, was Wutz sich dabei denkt. Ich fand bereits etliche wunderschöne Anwendungen von verketteten Listen, wo das Löschen aus einem Array einfach unglaublich teuer ist. Mit verketteten Listen hatte ich dann schöne Performancegewinne.
Aber vielleicht will Wutz das ja näher ausführen.

Die Ironie bezog sich eher auf meinen Vorschlag, die Liste von Pointern wieder in ein Array zu tun. Wenn du dann wieder Elemente löschen oder hinzufügen willst, hast du das gleiche Problem . wenn auch in abgeschwächter Form, weil du diesmal nicht wieder ganze Strukturobjekte verschieben musst (dachte da an memcpy bzw. memmove , aber frag mich nicht, ob es die auch für Windows gibt - sollte es aber:

man memcpy schrieb:

KONFORM ZU
SVr4, 4.3BSD, C89, C99, POSIX.1-2001.

), sondern halt nur die Pointer. Du hast dann verringerten Overhead beim Neuanlegen und Löschen von Elementen in der Liste und zusätzlich schnelleren Indizierungszugriff, aber durch die Liste nicht viel gewonnen (weil du in deinem Array dennoch immer Buch führen musst, in welcher Position welcher Pointer auf das jeweilige Objekt zeigt). Das ist dann scheiße - wenn es eines gibt, was du in deinem Programm haben willst, dann ist es reduzierte Komplexität. Deswegen die Ironietags.

Besser ist es, wenn du kaum Lesezugriffe auf die Liste hast. Oder wenn du dir jedes Drittel oder Viertel der Liste einen Hilfspointer machst und dann sagst, heuristisch gesehen muss ich die Liste nur ab der Hälfte der Elemente iterieren. Aber schön ist das auch nicht.
Manchmal ist es aber die schnellste Lösung. Wie dem Boyer-Moore-Suchalgorithmus, wo du erst eine Jump Table deiner Nadel machst, die du in dem Heuhaufen sehen willst. Und es muss zum Anwendungsfall passen - Boyer-Moore ist dann richtig schnell, wenn wenige Teilnadeln im Heuhaufen vorkommen. Weil Boyer-Moore dann heuristisch immer eine gute Nadellänge überspringen kann.

Aber merke: ich sage, diese Lösung ist wegen dem Array mit seinen Hilfspointern unschön. Ich sage nicht, dass verkettete Listen unschön sind - ich hatte damals wahnsinnige Probleme, diese korrekt zu verstehen, keine Ahnung, ob das bei dir anders sein wird, aber gleichzeitig haben sie auch unglaublich weitergeholfen.

SeppJ

dachschaden schrieb:

Keine Ahnung, was Wutz sich dabei denkt. Ich fand bereits etliche wunderschöne Anwendungen von verketteten Listen, wo das Löschen aus einem Array einfach unglaublich teuer ist. Mit verketteten Listen hatte ich dann schöne Performancegewinne.

Die Sache ist: Dann bist du der einzige. Von allen Programmierern. Auf der ganzen Welt. Verkettete Listen versagen sogar bei künstlichen Benchmarks, die nur auf die Stärken der verketteten Liste ausgelegt sind. Die Nachteile der Nichtlokalität sind derart groß, ganz besonders auf modernen Rechnern, dass jede Art von Zugriff alle eventuellen Vorteile mehr als wett macht.
Das heißt, selbst wenn du die ganze Zeit nur Listen splicest oder kombinierst, bist du in der Regel langsamer als alternative Datenstrukuren, allein dadurch, dass du irgendwie zu den beteiligten Elementen kommen musst.

Jetzt beleidigst du mich - denn die Typen, die zum Beispiel malloc implementieren, verwenden verkettete Listen. struct malloc_chunk beinhaltet einen Pointer auf das nächste Element vom gleichen Typen.

Und zu meinen persönlichen Erfahrungen: ich hatte Fälle, wo verkettete Listen einen immensen Geschwindigkeitsvorteil gegenüber Arrays anboten. Ich rede hier nicht von 20, oder 60, oder 100%, sondern von >500%. Und besondere Optimierungen habe ich damals nicht vorgenommen.

Ja, wahrscheinlich bin ich der einzige, der so blöd ist.