Verkettete Liste und Dynamisches Array Funktionen: remove_all, length, split_list

ch275

Grünschnabel
Hallo.

Ich blicke bisher bei Listen noch nicht so ganz durch. Deshalb komme ich auch mit meinen Aufgaben nicht so ganz zurecht.

1. eine Funktion remove_all, die aus einer Liste alle Vorkommen einer eingegeben Zahl löscht:

C++:
void remove_all(list_type *list, int value) {

    while (index_of(list, value) != -1){
		delete_at(list, index_of(list, value));
	}
}

Ich habe dies sowohl für das dynamische Array als auch für die verkettete Liste. Es funktioniert auch. Aber ich soll zusätzlich die Frage beantworten, worin sich beide Implementierungen unterscheiden. Ich sehe aber keinen Unterschied.

2. eine Funktion length, die die Länge einer Liste zurückgibt

für das dynamische Array:
C++:
 int length(list_type *list){
	 int i;

	 i=list->size;

	 return(i);
	 
 }

für verkettete Liste
C++:
 int length(list_type *list){
	int k=0;
	element_type *el;
	el= list->head;

	while(el->next != NULL){ 
		el= el->next;
		k++;                    //die Schleife wird k-mal durchlaufen
	}
	k++;					
	return (k);
}

3. eine Funktion split_list, die ausgehend von einer Liste zwei neue dynamisch erstellt, wobei die erste neue Liste alle Elemente der alten bis zu einem bestimmten Element enthält, die zweite neue dann dieses Element selbst und den Rest. So eine Funktion habe ich auch, allerdings soll die alte Liste nicht verändert werden, aber ich denke meine Funktion tut dies (ich konnte es nicht ausprobieren, weil immer noch Syntax-Fehler angezeigt werden). Ich bin auf die Idee gekommen, dass ich ja zuerst die alte Liste kopieren könnte, allerdings weiß ich nicht, wie ich das implementieren soll

C++:
void split_list(list_type *list, int value, list_type *before, list_type *after){

element_type *el;
	 el=list->head;


	 int i;
	 i=index_of(list, value);
	 int j;

	 for(j=0; j<i; i++){
		 append(before, element_at(list, j));
	 }
	 j=i;
	 while(el!=NULL){
		 append(after, element_at(list, j));
		 j++;
		 el=el->next;
	 }
 }

Wäre für Hilfe echt dankbar.
 
Hi
Ich blicke bisher bei Listen noch nicht so ganz durch. Deshalb komme ich auch mit meinen Aufgaben nicht so ganz zurecht.

1. eine Funktion remove_all, die aus einer Liste alle Vorkommen einer eingegeben Zahl löscht:

C++:
void remove_all(list_type *list, int value) {

    while (index_of(list, value) != -1){
		delete_at(list, index_of(list, value));
	}
}
Du solltest die Implementation dieser Funktion nochmal überdenken. Die Laufzeit sollte O(n) sein. Du iterierst für jedes Vorkommen einer Zahl 3 mal über die Liste.
Ich habe dies sowohl für das dynamische Array als auch für die verkettete Liste. Es funktioniert auch. Aber ich soll zusätzlich die Frage beantworten, worin sich beide Implementierungen unterscheiden. Ich sehe aber keinen Unterschied.
Indizierter Zugriff bei Listen ist aber auch keine gute Idee.
2. eine Funktion length, die die Länge einer Liste zurückgibt
War das eine Frage?
3. eine Funktion split_list, die ausgehend von einer Liste zwei neue dynamisch erstellt, wobei die erste neue Liste alle Elemente der alten bis zu einem bestimmten Element enthält, die zweite neue dann dieses Element selbst und den Rest. So eine Funktion habe ich auch, allerdings soll die alte Liste nicht verändert werden, aber ich denke meine Funktion tut dies (ich konnte es nicht ausprobieren, weil immer noch Syntax-Fehler angezeigt werden). Ich bin auf die Idee gekommen, dass ich ja zuerst die alte Liste kopieren könnte, allerdings weiß ich nicht, wie ich das implementieren soll
Du führst nur ändernde Funktionen auf die neuen Listen before und after aus. Ich sehe keine Stelle wo du die alte Liste modifizierst.

Aber auch hier ist es suboptimal auf die Liste per Index zuzugreifen.

Gruß
 
Hallo.

Zu 1:
Wäre eine for-Schleife angebrachter?
Für das dynamische Array etwa:
Code:
for(i=0; i<list->size-1; i++){
     int k;
     k=index_of(list, value);
     if (k!=-1){
        delete_at(list, k);
     }
}

Zu 2:
Die Frage sollte lauten: Ist das so richtig?

Zu 3:
Ich weiß, dass ich die alte Liste verändere. Aber ich weiß nicht, wie ich das ändern kann. Vielleicht eine Kopie erstellen? Ich weiß aber auch nicht, wie ich das machen sollte.
 
Hey

Zu 1:
Warum läufst du nicht einfach einmal über alle Elemente deiner Liste und entfernst alle, deren Wert übereinstimmt mit dem, den du entfernen solltest? Dann erreichst du auch O(n).
 
Ich soll die Funktionen index_of und delete_at verwenden. Ich weiß nicht wie ich das anders machen kann. Entweder mit der while-Schleife oder mit der for-Schleife.
 
Zu 1:
Wäre eine for-Schleife angebrachter?
Es geht nicht um die Art der Schleife. Jede Schleife kann durch eine andere Art von Schleife ersetzt werden.
Zu 2:
Die Frage sollte lauten: Ist das so richtig?
Was haben denn deine Tests ergeben?
Zu 3:
Ich weiß, dass ich die alte Liste verändere.
Dann beweise es. Schreib ein Minimal-Programm, stell es hier rein. In deinem Code ist jedenfalls keine Stelle enthalten.
Ich soll die Funktionen index_of und delete_at verwenden. Ich weiß nicht wie ich das anders machen kann.
Kann es sein, dass du da etwas missverstanden hast? Für Listen macht das keinen Sinn.

Gruß
 
Zurück