Doppelt verkettete Liste in C

bisaflor · April 23, 2016, 5:53am

Aufgabe:

Sie sollen die Funktionalität einer doppelt verlinkten Liste in der Programmiersprache C implementieren. Dazu schreiben Sie ein Programm, dem man über die Kommandozeile Zahlen übergeben kann, aus der Sie im nächsten Schritt die Liste erzeugen. Ein beispielhafter Aufruf Ihres Programms könnte wie folgt aussehen:

./DLLTest 3 4 2 1

Für jede eingegebene Zahl erzeugen Sie einen Knoten, der Ihrer Liste hinzugefügt wird. Jeder Knoten node soll einen Zeiger prev auf den Vorgänger, einen Zeiger next auf den Nachfolger und einen Wert val besitzen. Implementieren Sie für das Hinzufügen eines Knotens zur Liste die Funktion addNode(…).
Sobald Sie die Liste vollständig erzeugt haben, geben Sie deren Inhalt auf der Konsole aus. Implementieren Sie dazu die Funktion printList(…).
Vergessen Sie nicht am Ende Ihres Programms jeglichen von Ihnen allokierten Speicher wieder freizugeben. Die Freigabe des Speichers der Liste soll in einer Funktion clearList(…) geschehen.

Mein Ansatz:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>



//struct node *next = NULL;


struct node {
    struct node* next;
    struct node* prev;
    int val;

};


struct node *start = NULL;
//struct node *next = NULL;
struct node *end = NULL;



void addNode(int val) {
	
  struct node *pointer = NULL; 	
  
  struct node *temp = NULL;
	
	
  if(start == NULL) {
	  
	  
	  start = (struct node*)malloc(sizeof(struct node));
	  
	  end = malloc(sizeof(struct node));
	  
	  
	  start->val = val;
	  
	  start->next = NULL;
	  
	  start->prev = NULL;
	  
	  
	  end = start;
  }	else {
	  
	  pointer = start;
	  
	  
	  while(pointer->next != NULL) {
		  
		  pointer = pointer->next;
	  }
	  
	  temp = pointer;
	  
	  pointer->next = (struct node*)malloc(sizeof(struct node));
	  
	  pointer = pointer->next;
	  
	  pointer->val = val;
	  
	  pointer->next = NULL;
	  
	  end = pointer;
	  
	  pointer->prev = temp;
	  
	  temp->next = pointer;
	
	  
}}


void printList() {
	
	struct node * pointer2;
	
	pointer2 = start;
	
	while(pointer2 != NULL) {
		printf("der Wert des Knotens lautet %d
",pointer2->val);
		pointer2 = pointer2->next;
	}
	
}


void clearList() {
	
	struct node * temp;
	struct node * temp2;
	
	if(anf == NULL) {
		
		
	} else {
		
	   temp = anf-> next;
	   
	   while(temp != NULL) {
		   
		   temp2 = temp1->next;
		   
		   anf->next = temp2;
		   
		   temp2->prev = anf;
		   
		   
		   free(temp);
		   
		   temp = temp2;
		   
		   
		   
	   }	
		
	
	
   }
	
}



int main(int argc, char ** argv) {
	
	int i,a;
	
	
	
	
	for( i=1; i < argc; i++) {
	    a = atoi(argv**);
	    
	    
	    addNode(a);
	   
	}
	
	
	printList();

    


  return 0;
}

Meine Fragen:

Erfüllt mein Ansatz die Aufgabenstellung?

Gibt es Verbesserungsmöglichkeiten?

Wie kann ich mit der IDE Geany vernüftig automatisch einrücken?

Was würde mit dem Speicher passieren, wenn ich das Programm einfach beende, statt es mit free() freizugeben?

*** Edit ***

bei der Verbesserungen bitte auch berücksichtigen, dass in der nächsten Teilaufgabe mergeSort auf der Liste implementiert werden soll.

CyborgBeta · April 23, 2016, 7:38am

[QUOTE=bisaflor]
Gibt es Verbesserungsmöglichkeiten?

Wie kann ich mit der IDE Geany vernüftig automatisch einrücken?

Was würde mit dem Speicher passieren, wenn ich das Programm einfach beende, statt es mit free() freizugeben?

*** Edit ***

bei der Verbesserungen bitte auch berücksichtigen, dass in der nächsten Teilaufgabe mergeSort auf der Liste implementiert werden soll.[/QUOTE]

typedef wäre schön, damit nicht immer struct geschrieben werden muss.

Das Verketten der Elems sieht richtig aus.

automatische Code Formatierung z. B. mit Eclipse möglich, wenn du wechseln darfst/kannst/willst.

Geany reiner Texteditor mit Oberfläche.

Es würde auch “aufgeräumt” werden, aber das Programm soll ja noch erweitert werden.

Speicher könnte ohne free() wachsen.

MergeS auf eine verkettete Liste könnte schwierig werden, beim Tauschen von zwei Elems an Stelle i und j.

Dann müsste umverknüpft werden.

Grüße

anon77772267 · April 23, 2016, 8:44am

Nach dem Schließen des Programms wird nicht freigegebener Speicher vom System freigegeben. Doch wenn das Programm länger läuft, kann der Speicherverbrauch massiv ansteigen (= Memory Leak).

Marco13 · April 23, 2016, 9:02am

Zusätzlich zu CyborgBetas hilfreichem, laber-freiem on-topic-post* :

Im clearList kommt noch ein unbekanntes „anf“ vor - das kann so ja nicht compilieren, d.h. da wirst du wohl nochmal drüberschauen. Den Knackpunkt, dass man einen einzelnen Knoten nicht löschen darf, solange man nicht weiß, wo man danach hin geht, scheinst du ja schon erkannt zu haben:


free(current);
current = current->next; // KRACH!

Ansonsten wirst du früher oder später merken, dass bestimmte „Muster“ mehrfach auftreten. Man müßte jetzt genauer überlegen, was bei einem MergeSort alles an Operationen gemacht wird, aber einiges, was jetzt in „addNode“ steht, könnte ggf. ausgelagert werden. Man KÖNNTE (!) (nur um die Idee zu verdeutlichen!) Helferlein definieren wie etwa


void appendAsNext(node *n, node* next) {
    ...
}

(oder ähnlich), die die Teile zusammenfassen, die gemacht werden müssen, damit der Zustand „konsistent“ ist. Es geht darum, dass z.B. die Invariante
n->next->prev == n (für n!=NULL und n->next!=NULL)
nach JEDEM Funktionsaufruf erfüllt sein muss. Solche Sachen in jeder Funktion aufs neue, lokal durch händisches Pointer-Jonglieren sicherzustellen kann fehleranfällig sein.

EDIT: Sollte die while(pointer->next != NULL)-Schleife in der „addNode“-Funktion durch das Speichern des jeweils aktuellen „end“-Nodes nicht vermieden werden können?

Ich versuch’ nur, das positiv zu bekräftigen

Timothy_Truckle · April 23, 2016, 3:21pm

Solange das Programm es Performanz-Technisch verkraftet würde ich auf die „redundante“ Speicherung der Endknoten-Adresse (end) verzichten und dafür lieber das Suchen des letzten Knotens in eine eigene Funktion auslagern, die dann in den anderen Funktionen benutzt wird…
Redundante Speicherung birgt nämlich immer die Gefahr der Inkonsistenz.

bye
TT

mogel · April 25, 2016, 1:33am

moin,

addNode() ist mir zu chaotisch …


void addNode(int val) {
    tNODE* node = malloc(sizeof(tNODE));
    node->value = val;
    if (start == null) {
        start = node;
    } else {
        tNODE* temp = start;
        while(temp->next != NULL) temp = temp->next;
        node->prev = temp;
        temp->next = node;
    }
}

müsste auf das gleiche rauskommen. Um die while-Schleife zu sparen, kannst Du auch die Start-Node durch die Neue ersetzen. Also an den Anfang hängen.


void addNode(int val) {
    tNODE* node = malloc(sizeof(tNODE));
    node->value = val;
    if (start == null) {
        start = node;
    } else {
        start->prev = node;
        node->next = start;
        start = node;
    }
}

Marco13 · April 25, 2016, 3:47am

[ot]
Der C-Code-Formatter ist gerade kaputt. Lieber code verwenden
[/ot]

Sicher könnte man die “addNode” etwas vereinfachen. Aber die Initialisierungen wie start->next = NULL; usw. darf man NICHT weglassen. malloc allokiert nur, aber in dem Speicher kann noch Müll stehen. (mit calloc wäre das anders)

CyborgBeta · April 25, 2016, 5:58am

Hallo nochmal,

das erstellt bei mir zumindest kein Segmentation fault:

/*
 * VerkListeInt.c
 *
 *  Created on: 25.04.2016
 *      Author: unbk.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct node {
	struct node * next;
	struct node * prev;
	int val;
};

struct node * start = NULL;
struct node * end = NULL;

void addNode(int val) {
	struct node * node = (struct node *) malloc(sizeof(struct node));
	node->next = NULL;
	node->prev = NULL;
	node->val = val;

	if (start == NULL) {
		start = node;
		end = node;
	} else {
		struct node * tmp = start;
		while (tmp->next != NULL) {
			tmp = tmp->next;
		}

		tmp->next = node;
		node->prev = tmp;
		end = node;
	}
}

void printList(void) {
	struct node * tmp = start;
	while (tmp != NULL) {
		printf("der Wert des Knotens lautet %d
", tmp->val);
		tmp = tmp->next;
	}
	printf("
");
	tmp = end;
	while (tmp != NULL) {
		printf("der Wert des Knotens lautet %d
", tmp->val);
		tmp = tmp->prev;
	}
}

void clearList(void) {
	struct node * tmp = start;
	while (tmp != NULL) {
		struct node * tmp2 = tmp->next;
		free(tmp);
		tmp = NULL;
		tmp = tmp2;
	}

	start = NULL;
	end = NULL;
}

int main(int argc, char ** argv) {
	int i = 11;

	printList();
	printf("
");

	for (; i < 23; i++) {
		addNode(i);
	}

	printList();
	printf("
");

	clearList();

	printList();
	printf("
");

	addNode(111);

	printList();
	printf("
");

	return EXIT_SUCCESS;
}

Eclipse funktionierte gerade bei mir nicht, weil das Jdk weg ist, hab es deswegen online durchrattern lassen.

Jetzt möchte ich euch bitten:

Drüberzuschauen, ob ich irgendwo etwas Falsches/Redundantes/Kompliziertes habe,
code=c “wiederherzustellen”.

@bisaflor : du müsstest dich jetzt um argv, das Sortieren, eigene Funktion(en) und so etwas kümmern.

Generell, hab ich glaube ich nicht zu viel verraten, denn wenn man nach c doubl(e/y) linked list(s) (int) googelt, findet man so einiges.

Falls doch, den gesamten Beitrag wieder löschen.

bisaflor · April 25, 2016, 9:10am

dry für die späte Rückmeldung ich bin schon weiter ich poste meinen Code später heute

bisaflor · April 28, 2016, 6:09am

#include <stdio.h>
#include <string.h>
#include <stdlib.h>



//struct node *next = NULL;


struct node {
    struct node* next;
    struct node* prev;
    int val;

};

void split(struct node* source, struct node** firstHalf, struct node** secondHalf);

struct node* merge(struct node* a, struct node*b);


struct node *start = NULL;
//struct node *next = NULL;
//struct node *end = NULL;



void addNode(int val) {
    struct node *pointer = NULL; 	
    struct node *temp = NULL;
	if(start == NULL) {
	start = (struct node*)malloc(sizeof(struct node));
	//  end = malloc(sizeof(struct node));
	start->val = val;
	start->next = NULL;
	start->prev = NULL;
	//end = start;
    } else {
	    pointer = start;
	    while(pointer->next != NULL) {
		    pointer = pointer->next;
		}
	    temp = pointer;
	    pointer->next = (struct node*)malloc(sizeof(struct node));
	    pointer = pointer->next;
	    pointer->val = val;
	    pointer->next = NULL;
	    //end = pointer;
	    pointer->prev = temp;
	    temp->next = pointer;
	}
}


void printList(struct node* sta) {
    struct node * pointer2;
	pointer2 = sta;
	printf("[");
	while(pointer2 != NULL) {
		printf("%d ",pointer2->val);
		pointer2 = pointer2->next;
	}
	printf("]");
}

void clearList() {
	struct node * temp;
	struct node * temp2;
	if(start == NULL) {
		
		
	} else {
		
	   temp = start-> next;
	   
	   while(temp != NULL) {
		   
		   temp2 = temp->next;
		   
		   if(temp2 == NULL)
		     break;
		   
		   start->next = temp2;
		   
		   temp2->prev = start;
		   
		   
		   free(temp);
		   
		   temp = temp2;
		   
		   
		   
	   }	
		
	
	
   }
	
}



void MergeSort(struct node** headRef, int rekDep) {
	
	struct node* head = *headRef;
	
	struct node* a = NULL;
	
	struct node* b = NULL;
	
	//struct node* c = NULL;
	
	printf("mergeSort:");
	
	printList(head);
	
	printf("
");
	//Basisfall 1 Element oder kein Element
	if(head == NULL || head->next == NULL) {
		
		return;
	}
	
	split(head,&a,&b);
	
	MergeSort(&a, rekDep+1);
	
	MergeSort(&b, rekDep+1);
	
	*headRef = merge(a,b);
	
	if(rekDep == 0) {
        printf("Liste nach Sortieren:");
        printList(*headRef);
    	
	}
}
// Splittet eine Liste mit der fast/slow Pointer Strategie
void split(struct node* source, struct node** frontRef, struct node** backRef) {
	
	struct node* fast;
	
	struct node* slow;
	

	
	
	
	if(source == NULL || source->next == NULL) {
		
	   *frontRef = source;
	   *backRef = NULL;
		
		
	} else {
		
		printf("split:");
  
		printList(source);
  
		printf(" into: ");
		
		
		slow = source;
		
		fast = source->next;
		
		while(fast != NULL) {
		fast = fast->next;
		
		if(fast != NULL) {
			fast = fast->next;
			slow = slow->next;
		
		
		
	}
	
	
}
  *frontRef = source;
  *backRef = slow->next;
  slow->next = NULL;
  
  
  
  printList(*frontRef);
  
  printList(*backRef);
  
  printf("
");
  
  
   
}

}


struct node * merge(struct node* a, struct node* b) {
	
	printf("merge:");
	
	printList(a);
	
	printf("and");
	
	printList(b);
	
	printf("
");
	
	struct node* res = NULL;
	
	if(a == NULL) 
		return b;
	else if(b == NULL)
	    return a;
	    
	if(a->val <= b->val) {
		
		res = a;
		res->next = merge(a->next,b);
	
} else {
	res = b;
	res->next = merge(a,b->next);
}

return res;
}
   

int main(int argc, char ** argv) {
	
	int i,a;
	
	
	
	
	
	for( i=1; i < argc; i++) {
	    a = atoi(argv**);
	    
	    
	    addNode(a);
	   
	}
	
	printf("Liste vor Sortieren:");
	printList(start);
	printf("
");
	struct node ** startRef = &start;
	
	MergeSort(startRef,0);
	
	
    clearList();


  return 0;
}

Hat leider doch nochmal länger gedauert. Etwas verplant

mfg

*** Edit ***

das Programm benutzt man so :

./DLLTest 1 2 3 4 dann wird eine doppelt verkettete Liste erstellt und anschließend mit MergeSort sortiert

SlaterB · April 28, 2016, 6:43am

	    temp = pointer;
	    pointer->next = (struct node*)malloc(sizeof(struct node));
	    pointer = pointer->next;
	    [..]
	    temp->next = pointer;  // nötig?

next von ehemaligen pointer, jetzigen temp ist doch sicher schon gesetzt, wenn genau dort allokiert

	   temp = start-> next;
	   
	   while(temp != NULL) {
		   
		   temp2 = temp->next;
		   
		   if(temp2 == NULL)
		     break;

start wird überhaupt nicht gelöscht, und sobald das Listenende erreicht ist, temp2 null ist, wird das temp-Element zu dieses Zeitpunkt, also das letzte Element, auch nicht gelöscht

fange mit temp = start an, befreie in jedem Fall temp in der Schleife,
vorher aber noch next holen, erst in temp2 ablegen, nach dem Befreien in temp schreiben,

kein break nötig, while-Bedingung zur nächsten Runde nutzen

oder statt Schleife rekursiver Aufruf, wie ja auch beim Merge

beim Merge, falls das wirklich schon was tut, prev-Verlinkungen auch würdigen, neu setzen

bisaflor · April 28, 2016, 6:52am

Danke ich werde das noch korrigieren. Allerdings von der Programmausgabe scheint es schon zu “passen” oder gibt es da Grenzfälle wo mein Programm nicht die richtige Ausgabe ausgibt?

SlaterB · April 28, 2016, 6:58am

Tipp 1 war doppelter Code, kann kaum schaden,
Tipp 2 war falsche Speicherfreigabe, wird sich kaum in der Ausgabe bemerkbar machen, aber könnte trotzdem als mächtig falsch gelten
Tipp 3 war falsche prev-Links, die nutzt du bisher nirgendwo, insofern programmtechnisch sekundär, aber gewiss auch nicht schön

bisaflor · April 28, 2016, 7:14am

okay, was ich aber nicht verstehe, wenn der Speicher nach Programmende eh freigegeben wird. Brauch ich ja quasi auch keine Funktion clearList() aufrufen, weil Sie ja kurz vor Programmende läuft und der Speicher ja kurze Zeit später sowieso vom BS freigegeben würde oder?

SlaterB · April 28, 2016, 7:18am

ein Segen für Mensch und Tier, ja,
aber üblicherweise haben ‚Aufgabenstellungen‘ für solche Erkenntnisse wenig Verständnis

ob du die Funktion programmierst oder nicht ist deine Entscheidung, wenn dann evtl. korrekt(er)

Timothy_Truckle · April 28, 2016, 7:52am

[quote=SlaterB]Tipp 1 war doppelter Code, kann kaum schaden,[/quote]Zumindest nicht bezüglich der Programmkorrektheit,

Für die Weitereentwicklung ist doppelter Code der Horror schlecht hin! (Ich spreche da aus Erfahrung…)

Also:
Wehret den Anfängen!

bye
TT

SlaterB · April 28, 2016, 7:53am

fange hier gleich an: TT

CyborgBeta · April 28, 2016, 8:37am

Vorweg: Eine “vernünftige” autom. Codeformatierung bekommst du nur mit Eclipse, NetBeans, Visual Studio oder Ähnlichen (nicht kostenlosen) Ides hin.

Dann hast du ja doch ziemlich viel geändert. Ich dachte, du “kopierst” das von mir einfach.

Dann MergeSort auf einer verketteten Liste stelle ich mir schwierig vor. MergeSort geht ja so, das die Mitte ermittelt werden muss. Laufzeit ist dann nicht O(1) sondern O(n/2).
Allerdings setzt du dann ein Elem., z. B. aus der rechten Teilhälfte, an den Anfang. Dadurch stimmen dann die Pointer der Parameter der anderen Aufrufe nicht mehr.

Div:
4 3 1 2
4 3 und 1 2
4 und 3 und 1 und 2
Con:
usw.

Ok, mal anders gefragt, welche Funktion(en) funktioniert noch nicht richtig?

bisaflor · April 28, 2016, 8:51am

passt jetzt erstmal, danke trotzdem. Ich glaube ich werde deinem Tipp folgen und mir Eclipse für C/C++ Entwickler besorgen

SlaterB · April 28, 2016, 9:16am

‘fast/slow pointer strategy’ und damit der Code ist anscheinend von hier
Interview Questions: Sorting a linked list

frech frech…