Verkettete Liste in einer Funktion erstellen

Herakles

Herakles

Profifragensteller
Moin!

Ich möchte eine verkette Liste erstellen, bekomme das auch wunderbar hin, wenn ich das in meiner main-Funktion mache.

Irgendwie sehe ich aber bei einem Aufbau dieser Liste in einer Funktion vor lauter Bäumen den Wald nicht. Was mache ich falsch?

Code: 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>

struct linked_list {
        uint8_t data;
	struct linked_list *next;
};

void liste_aufbauen(struct linked_list *f) {
  f=malloc(sizeof (struct linked_list));
  memset(f,1,sizeof (struct linked_list));
  f->next = malloc(sizeof (struct linked_list));
}

int main(void) {
  struct linked_list *Pfirst_element = NULL;
  
  printf("vor %p\n",Pfirst_element);
  Pfirst_element=malloc(sizeof (struct linked_list));
  memset(Pfirst_element,1,sizeof (struct linked_list));
  Pfirst_element->next = malloc(sizeof (struct linked_list));
  //liste_aufbauen(Pfirst_element);
  printf("nach %p\n",Pfirst_element);
  printf("%d\n",Pfirst_element->data);
  exit(0);
}

Der hier gezeigte Code funktioniert. Sobald man aber das Ganze in die Funktion "liste_aufbauen" auslagert(indem die auskommentierte Zeile einkommentiert wird und dafür die drei Zeilen drüber auskommentiert), funktioniert es nicht.

Also so:
Code: 
(...)
  //Pfirst_element=malloc(sizeof (struct linked_list));
  //memset(Pfirst_element,1,sizeof (struct linked_list));
  //Pfirst_element->next = malloc(sizeof (struct linked_list));
  liste_aufbauen(Pfirst_element);
(...)
Was muss ich tun, damit es funktioniert?

Danke für jeden Tipp!


Herakles
 
malloc gibt dir doch einen Pointer (einen neuen Pointer!) auf den Adressbereich zurueck, den er allokiert hat. Woher soll so denn in main einer wissen, wie der pointer aussieht, wenn du ihn nicht entweder als return wert uebergibst, oder einen Pointer auf den Pointer setzt? ;)

Ich wuerde mir einfach in deiner Funktion "liste_aufbauen" das erste malloc sparen und direkt einen Pointer zu einem deklariertem struct uebergeben, also etwa so:

Code: 
void liste_aufbauen(struct linked_list *f) {
  memset(f,1,sizeof (struct linked_list));
  f->next = malloc(sizeof (struct linked_list));
}

int main(void) {
  struct linked_list Pfirst_element;
  
  printf("vor %p\n",Pfirst_element);
  liste_aufbauen(&Pfirst_element);
  printf("nach %p\n",Pfirst_element);
  printf("%d\n",Pfirst_element.data);
  exit(0);
}
(Habs nicht ausprobiert)
 
Oder du gibst den Pointer einfach als Rückgabewert zurück und weist ihn der Variablen zu. Auch ein Pointer auf den eigentlichen Pointer wäre möglich, wird aber unlesbarer.
 
Ich versuche das mal anders zu formulieren.

Parameter werden kopiert, du setzt nur f, Pfirst_element wird nicht verändert. Du hast 3 Möglichkeiten:

1. Wie vorgeschlagen die Adresse zurückgeben
2. In C++ eine Referenz verwenden
3. Pointer auf den Pointer verwenden

Wenn du etwas verwendbares produzieren würde ich das aber objektorientiert machen.
 
Als "Fingerübung" sind verkette Listen sicher ganz nett unter C zu schreiben.

Aber wenn man nur den Nagel sauber in die Wand hauen möchte, würde ich zur glib oder zu C++ raten. Wenn man sich denn C++ antun möchte;)
(Ich mag C++ und bin drauf hängen geblieben).
Und unter C++ einfach std::vector oder wenn man weiß was man tut vielleicht auch std::list.
Referenzen sind auch gut oder vielleicht den neuen "move constructor" unter C++0x bzw. C11.
 
ich schliesse mich s-tlk an.
das erste malloc macht keinen sinn, ausser dass du den pointer der der funktion uebergeben wurde ueberschreibst.
damit hat f in den zwei funktionen zwei verschiedene inhalte.

danach kannst du aber die liste mit
Code: 
liste_aufbauen(&Pfirst_element);
liste_aufbauen(Pfirst_element.next);
erweitern.

danach wird es etwas komplizierter
Code: 
liste_aufbauen(&Pfirst_element);
liste_aufbauen(Pfirst_element.next); 
liste_aufbauen((linked_list*)(Pfirst_element.next)->next); 
liste_aufbauen((linked_list*)((linked_list*)(Pfirst_element.next)->next)->next);

ich weiss nicht ob die casts notwendig sind.
man sieht hier aber sehr schoen drei verschiedene arten der referenzierung!
 
Hi,

"man queue" bzw. queue(3) ist dein Freund. :-).

Bspw.:
Code: 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <errno.h>

#include <sys/queue.h>


struct linked_list {
	uint8_t ll_data;
	SLIST_ENTRY(linked_list) ll_next;
};
typedef struct linked_list *ll_ent_p;

/* 
 * Definiert Listenkopf als 'struct ll_head' 
 * welche einen ptr des o. g. Strukturdatentyps
 * kapselt bzw. enthaelt.
 */
SLIST_HEAD(ll_head, linked_list);
typedef struct ll_head *ll_head_p;

static ll_head_p 	ll_alloc(void);
static void	ll_free(ll_head_p *hd);

static int 	ll_ent_set(ll_head_p *hd, uint8_t val);
static void * 	ll_ent_get(ll_head_p *hd, uint8_t val);
static void 	ll_ent_insrt(ll_head_p *hd, void *arg);
static int 	ll_ent_rm(ll_head_p *hd, uint8_t val);


/* Allozieren eines Listenkopf einer einfach verketteten Liste. */
static ll_head_p 	
ll_alloc(void) 
{
	ll_head_p lh = NULL;
  	
  	lh = malloc(sizeof(*lh));
	if (!lh)
	  	return(NULL);

	SLIST_INIT(lh);
  
  	return(lh);
}

/* Freigeben des fuer diese verkettete Liste reservierten Speichers. */
static void 	
ll_free(ll_head_p *hd)
{
	while (!SLIST_EMPTY(*hd)) {       
		ll_ent_p le = SLIST_FIRST(*hd);
		
		SLIST_REMOVE_HEAD(*hd, ll_next);
		free(le);
	}
	
	free(*hd);
}

/* Allozieren und integrieren eines Listenelements. */
static int 	
ll_ent_set(ll_head_p *hd, uint8_t val)
{
	ll_ent_p le = NULL;
	
	le = malloc(sizeof(*le));
	if (!le)
		return(ENOMEM);
	
	le->ll_data = val;
	SLIST_INSERT_HEAD(*hd, le, ll_next);
	
	return(0);
}

/* Suchen und entnehmen eines Listenelements. */
static void * 	
ll_ent_get(ll_head_p *hd, uint8_t val)
{
	ll_ent_p le = NULL, tmp = NULL;
		
	SLIST_FOREACH_SAFE(le, *hd, ll_next, tmp) {
		if (le->ll_data == val) {
			SLIST_REMOVE(*hd, le, linked_list, ll_next);
			return(le);
		}
	}
	
	return(NULL);
}

/* Integrieren eines existierenden Listenelements. */
static void 	
ll_ent_insrt(ll_head_p *hd, void *arg)
{	
	SLIST_INSERT_HEAD(*hd, (ll_ent_p)arg, ll_next);
}

/* Suchen und loeschen eines Listenelements. */
static int 	
ll_ent_rm(ll_head_p *hd, uint8_t val)
{
	ll_ent_p le = NULL, tmp = NULL;
		
	SLIST_FOREACH_SAFE(le, *hd, ll_next, tmp) {
		if (le->ll_data == val) {
			SLIST_REMOVE(*hd, le, linked_list, ll_next);
			free(le);
			return(0);
		}
	}
	
	return(EINVAL);
}

/* ... etc.pp. ... */
static void 	
ll_print(ll_head_p *hd)	
{
	ll_ent_p le = NULL;

	if (SLIST_EMPTY(*hd))
		return;

	(void)printf("Linked List Entries:\n");

	SLIST_FOREACH(le, *hd, ll_next) {
		(void)printf(" > %u\n", le->ll_data);
	}
	
	(void)printf("\n");
}


int 	
main(void) 
{
	int err;
	ll_head_p lh = NULL, lh0 = NULL;	  
	uint8_t *dtp;

	lh = ll_alloc();
	if (!lh)
  		exit(EXIT_FAILURE);
  	
  	err = ll_ent_set(&lh, 1);
 	if (err) {
 		ll_free(&lh);
 		exit(EXIT_FAILURE);
 	}
 	
 	err = ll_ent_set(&lh, 2);
 	if (err) {
 		ll_free(&lh);
 		exit(EXIT_FAILURE);
 	}
  	
  	err = ll_ent_set(&lh, 3);
 	if (err) {
 		ll_free(&lh);
 		exit(EXIT_FAILURE);
 	}
  	
  	ll_print(&lh);
  	
  	lh0 = ll_alloc();
	if (lh0) {
 		dtp = ll_ent_get(&lh, 2);
		if (dtp) {
			(void)printf(" got data: %u\n\n", *dtp);
			
			ll_ent_insrt(&lh0, dtp);
			ll_print(&lh0);
			ll_print(&lh);
		
			(void)ll_ent_set(&lh, *dtp);
 			(void)ll_ent_set(&lh, *dtp);
 			(void)ll_ent_set(&lh, *dtp);
		}
		
		ll_free(&lh0);	
	}
	
	err = ll_ent_rm(&lh, 1);
  	if (!err)
  		ll_print(&lh);
	
	ll_free(&lh);
  	
  	exit(EXIT_SUCCESS);
}
 
Zuletzt bearbeitet von einem Moderator:
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben