4. Einfach Verkettete Liste

Einfach Verkettete Liste

  • R

    Ich hab mal eine kleine Frage zu einfach verketteten Listen.

    und zwar hier mal ein Kleines Beispiel.

    #inlcude <stdlib.h>

struct DATA
{
  int number;
  char name[20];  //irgendwelche Daten halt
};

struct list
{
  struct list *pointer; // Pointer auf nächstes Element
  struct DATA daten;    // Jeweilige Daten eines Elements
};

int main(void)
{
  //wie erstell ich jetzt hier die verkettete liste wo jeweils
  //im Element der Zeiger auf das nächste element drin steht
  struct list *pointer;
  pointer = (struct list*) malloc (sizeof(struct list));

  return 0;
}

    kann mir da einer weiterhelfen.

    0
  • A

    Wo liegt denn jetzt genau das Problem? Eine Liste mit 100 Elementen koennstest du z.B. so erstellen:

    struct list* aktuelles_element = (struct list*) malloc (sizeof(struct list));

for(int i = 0; i < 99; i++) {
  struct list* naechstes_element = (struct list*) malloc (sizeof(struct list));
  naechstes_element->daten.number = i+1;

  aktuelles_element->pointer = naechstes_element;

  aktuelles_element = naechstes_element;

}

    🤡

    0
  • R

    Danke, das hat mir sehr geholfen. Ich wusste nicht wie ich die Pointer initialisiere.

    Probiers gleich mal aus.

    0
  • R

    Eine kleine Frage noch.

    Wenn ich jetzt zum Beispiel auf den daten.number des 6ten elements zugreifen will, wie mach ich das ohen alles durch zu gehen.

    printf("Number = %d", ??);

    THX

    0
  • R
     

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

struct DATA 
{ 
  int number;	  //zum Beispiel eine Zahl
  char name[20];  //oder ein "string"
}; 

struct list 
{ 
  struct list *pointer; // Pointer auf nächstes Element 
  struct DATA daten;    // Jeweilige Daten eines Elements 
}; 

int main(void) 
{ 
	int i;
	struct list* aktuelles_element = (struct list*) malloc (sizeof(struct list)); 
	struct list* erstes_element = aktuelles_element;
	aktuelles_element->daten.number = 0;
	for(i = 0; i <= 9; i++) 
	{ 
		struct list* naechstes_element = (struct list*) malloc (sizeof(struct list)); 
		naechstes_element->daten.number = i+1; 
		aktuelles_element->pointer = naechstes_element; 
		aktuelles_element = naechstes_element; 
//diesen Schritt versteh ich nicht, ich setze doch schon den nächsten zeiger
		if (i == 9) aktuelles_element->pointer = NULL; //so setzt man das ende der Liste
	}
	aktuelles_element = erstes_element;
	i = 0;
	while (aktuelles_element->pointer != NULL)
	{
		printf("%d.Element, Number = %d, Name = %s\n",++i,aktuelles_element->daten.number,aktuelles_element->daten.name);
		aktuelles_element = aktuelles_element->pointer;
	}
	free(aktuelles_element);
	free(erstes_element);
	return 0; 
}

    Also ich glaub ich hab das so langsam verstanden, nur den schritt wo man sagt "aktuelles_element = nächstes_element" nicht. Warum muss ich das noch machen, reicht es nicht das ich in meiner STRUCT List den pointer des nächsten Elements angegeben habe?

    0
  • Z

    Lass doch den Schritt mal weg...

    Dann siehst du warum man den Schritt benötigt...

    Erklärung:

    Situation nach Einfügen des nächsten Elements

    act->pointer = next;
 ------    ------
|1     |->|2     |
 ------    ------
   ^
   |
 ------
|cur   |
 ------

    Lässt du jetzt

    act = next;

    weg sieht es im nächsten Schritt so aus...

    act->pointer = next;
 ------    ------
|1     |->|3     |
 ------    ------
   ^
   |
 ------
|cur   |
 ------

    Machst du hingegen die Zuweisung ist die Ausgangssituation folgende...

    act->pointer = next;
act = next;
 ------    ------
|1     |->|2     |
 ------    ------
   ----------^
   |
 ------
|cur   |
 ------

    und das Ergebnis bei der nächsten Einfügeoperation ist das gewünschte nämlich

    act->pointer = next;
 ------    ------    ------
|1     |->|2     |->|3     |
 ------    ------    ------
   ----------^
   |
 ------
|cur   |
 ------

act = next
 ------    ------    ------
|1     |->|2     |->|3     |
 ------    ------    ------
   --------------------^
   |
 ------
|cur   |
 ------

    Gruß
    zeigerzeiger

    0
  • R

    Ahh das war ein sehr gutes Beispiel, jetzt hab ichs verstanden. wenn man den schritt nicht machen würde dann zeigt der act nicht auf den wirklichen act sondern auf den alten.

    OK, aber noch zu der Frage wegen den 6ten oder 7ten element anzeigen.

    Muss ich jetzt also immer vom ersten zum zweiten zum ... um auf das 7 Element zu sprigen oder kann ich zu Beispiel gleich number von Element sieben ausgeben, nur mit Hilfe des Zeigers auf das erste Element?

    Grüße Zeiger

    0
  • Z

    Nein, du mußt dich durchhangeln, da du nicht weißt wo die Elemente im Speicher liegen wie beim Array... Du kannst quasi nicht weiterspringen mit (zeiger+6) sondern musst dich durchhangeln...

    Gruß
    zeigerzeiger

    0
  • D

    Entspricht nicht mehr dem eigentlichen Thema, aber deine free()-Anweisungen mußt du anders plazieren, sonst gibts nicht freigegebenen Speicher. 😮

    0
  • R

    wie muss ich die freeanweisung dann anwenden?

    0
  • Z

    Du musst alle Elemente der Liste freigeben und nicht nur das ertste und das aktuelle...

    Gruß
    zeigerzeiger

    0
  • A

    Hallo,

    ich habe ein Problem mit folgenden Programm. Es geht auch um eine verkettete Liste.
    Das Problem ist, dass beim allerersten Allocate-Aufruf das Programm hängt und den Speicher "frisst".

    Code:

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

// File Pointer
FILE *fil;

// Chained List
struct list_element {
	int						ship;
	struct list_element		*next;
};

int print_usage() {
	printf("usage: container [filename]\n");
	exit(-1);
}

// Returns the next character from file with error handling
int fget_next_char() {

	printf("fget_next_char()");

	int temp	= fgetc(fil);
	if (temp == EOF) {
		if (ferror(fil)) {
			printf("File Error");
			fclose(fil);
			exit(-1);
		}
			if (feof(fil)) {
			printf("EOF reached");
		}
		fclose(fil);
	}
	return temp;	
}

int main(int argc, char* argv[]) {

	struct list_element* 		firstnode;
	struct list_element* 		lastnode;
	struct list_element* 		node;

	firstnode 	= NULL;
	lastnode 	= NULL;

	// Temp var for read data from file
	int read_input 	= 0;
	int i			= 1;

	// If less or more than one paramter is given, print usage and quit
	if ( argc != 2) {
		print_usage();
	}

	// Try to open the given file
	fil = fopen(argv[argc-1], "r");
	if (fil == NULL) {
		printf("Error opening file\n");
		exit(-1);
	}

	printf("File opened successfully\n");

	while (fil != NULL) {
		read_input = fget_next_char();

		if (fil != NULL) {

			printf("%d ",i); i++;
			// Allocate Memory for a node
			node = (struct list_element*) malloc(sizeof(struct list_element));

			if (node == NULL) {
				// TODO output to stderr
				printf("Out of memory");
				fclose(fil); exit(-1);
			}

			// Create 1st node
			node->ship 		= read_input;
			node->next 		= NULL;
			firstnode		= node;
			lastnode		= node; 

			read_input = fget_next_char();
		}

		while (fil != NULL || read_input != '\n') { 

			if (read_input != ',') {

				// Allocate Memory for a node
				node = (struct list_element*) malloc(sizeof(struct list_element));

				if (node == NULL) {
					// TODO output to stderr
					printf("Out of memory");
					fclose(fil); exit(-1);
				}

				node->ship		= read_input;
				lastnode->next	= node;
				lastnode		= node;
				node->next		= NULL;
			}			
		}

		node = firstnode;

		/*while (firstnode != NULL) {

			if (node->ship >= node->next->ship) {

		}
		*/
		while (node->next != NULL) {
			printf("%c|",node->ship);
			node = node->next;
		}

	}
	return(0);
}

    gdb:

    [Session started at 2007-09-16 19:52:19 +0200.]
GNU gdb 6.3.50-20050815 (Apple version gdb-573) (Fri Oct 20 15:50:43 GMT 2006)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-apple-darwin".
Loading program into debugger…

tty /dev/ttyp3
Program loaded.
sharedlibrary apply-load-rules all
run
[Switching to process 1227 local thread 0xf03]
Running…
Pending breakpoint 1 - ""container.c:65" resolved
File opened successfully
1 
(gdb) continue
container(1227) malloc: *** vm_allocate(size=1069056) failed (error code=3)
container(1227) malloc: *** error: can't allocate region
container(1227) malloc: *** set a breakpoint in szone_error to debug
Out of memory

    malloc() hat schon beim ersten Aufruf Probleme (siehe die Ausgabe "1" von Zeile 72).

    Hat jemand ne Idee, woran es liegen könnte ?

    Vielen Dank schon mal im Voraus

    MfG, abc-man

    0
Anmelden zum Antworten