[ C ] Einfach verkettete Liste

M

myKam

0
Hiho und zwar möchte ich, oder besser gesagt mein Informatik Lehrer das ich
eine einfach verkettete Liste erzeuge mit ein paar Algorithmen.

Also Vorgabe für diese Aufgabe habe ich einige Funktionsprototypen, die Struktur und einen Globalen Pointer bekommen

Code: 
// Funktionsprototypen
LE* NeuesListenElement(int);
LE* ListenElementEinfuegen(LE*,LE*);
void ListenAusgabe(LE*);
void ListeLoeschen(LE*);
Code: 
struct ListenElement  
{
       int Inhalt;
       struct ListenElement * next;
};
    
typedef struct ListenElement LE;   

LE * Wurzel = NULL;


Meine Funktion NeuesListenElement sieht wie folgt aus:
Code: 
LE* NeuesListenElement(int Wert)
{
	LE* Z; // Zeiger Z
	Z=(LE*)malloc(sizeof(LE));  // Speicher auf Heap allozieren
	if(Z==NULL)  // 0 abfrage
	{
		printf("Heapspeicher ist voll !");
	}
	else
	{
		Z->Inhalt=Wert;  // Daten in Inhalt schreiben	
		Z->next=NULL;  // Zeiger next Erden
		Wurzel = Z;
	}
	return (Z);
}

Mein Problem besteht jetzt darin das ich zwar hiermit ein Listenelement erzeugen kann, aber nicht ansatzeise weiß wie ich es jetzt anstellen soll eine Kette aufzubauen.

Wär toll wenn mir jemand zumindest einen Denkanstoß geben könnte =)

mfg myKam
 
der erste hit bei google sollte dir deine frage beantworten. http://moritz.faui2k3.org/de/dmisc/einfach-verkettete-listen

deinem lehrer sollte man nahelegen mal nen paar weiterbildungen zu besuchen oder das fach nichtmehr zu unterrichten. jeder der auch nur ein kleines bisschen was von didaktik versteht wird nicht c als erste sprache unterrichten, erst recht nicht, wenn er selbst nichtmal die grundlegenden konventionen beherrscht. den schulstoff kann man mit ungetypten sprachen mit garbage collector auch abhaken. grausam, wie an deutschen schulen unterrichtet wird.

btw. wozu braucht die insertfunction nen returnvalue?
 
achso und sagt deinem lehrer das er ein idiot ist, globale variablen zu verwenden ist nicht gut, am besten baust du noch goto's in deinem code ein ;)
vorallemdingen nicht für so ein 'problem' :D


achso, zu deinen prob:
ich poste gleich mal meine lösung rein, vlt. kannst du damit was anfangen.

-> sorry, ich hab leider keine reine C lösung.
ich habe eine C++ lösung, die aber eine doppeltverkettete Liste darstellt.
vlt. schreib ich noch mal eine.....
 
Original von _fux_
achso und sagt deinem lehrer das er ein idiot ist, globale variablen zu verwenden ist nicht gut [..]
Zum Vergrößern anklicken....
Schwachfug! Grade bei Listen macht eine globale Variable (Basis) Sinn. Du hast x Funktionen die alle auf diese Variable benutzen, wo liegt denn bitte der Sinn jedes mal die als Parameter zu uebergeben? Das ist 1. unnoetige Schreibarbeit und 2. unter dem Aspekt der Effizienz nicht gut. Es ist eine sind pro Funktion mind 2 Instructions mehr.
 
Original von dmesg
Schwachfug! Grade bei Listen macht eine globale Variable (Basis) Sinn. Du hast x Funktionen die alle auf diese Variable benutzen, wo liegt denn bitte der Sinn jedes mal die als Parameter zu uebergeben? Das ist 1. unnoetige Schreibarbeit und 2. unter dem Aspekt der Effizienz nicht gut. Es ist eine sind pro Funktion mind 2 Instructions mehr.
Zum Vergrößern anklicken....

Es macht überhauptkeinen sinn. Manchmal wäre es nett, wenn man den funktionen sagen könnte auf welcher Liste sie arbeiten sollen. Stell dir mal vor alle container in der STL wären singleton. Damit wären die quasi unbrauchbar.
Und die 2 instructions fallen auch weg sobald die compileroptimierung auf die idee kommt die zu inlinen.
 
In den meisten Faellen sind die Funktionen so geschrieben, dass sie nur mit einer Art von Liste umgehen koennen. Mir faellt spontan keine praktischer Nutzen ein zwei oder mehrere gleiche Listentypen nebeneinander zu fuehren.
 
Original von dmesg
In den meisten Faellen sind die Funktionen so geschrieben, dass sie nur mit einer Art von Liste umgehen koennen. Mir faellt spontan keine praktischer Nutzen ein zwei oder mehrere gleiche Listentypen nebeneinander zu fuehren.
Zum Vergrößern anklicken....

Nur im sicherzustellen, dass wir nich aneinander vorbeireden. Ich hab vorhin verstanden, dass du ne Liste schreibst und Funktionen wie sort() oder sowas keine Parameter haben, weil die lib nen global mit der liste hat.

Es geht also nicht um mehrere parallele Listentypen, sondern um mehrere Instanzen. wenn du ne liste mit äpfeln und eine mit eiern hast, aber der sortfunktion nicht sagen kannst, ob du jetzt die äpfel oder die eier sortieren möchtest ist das in der tat mist.

Allgemein zum thema globals reicht es mal bei google danach zu suchen, um zu verstehen, warum die problematisch sind. In der Praxis arbeitet man halt nicht alleine an einem projekt.
 
dmesg, wie lange programmierst du schon?!
golbale variablen sind das dümmste was man machen kann.....sind zwar einfach, aber absolut unsicher! omg omg....naja mach was du für richtig hälst :D
ich übergeb' lieber ne längere paramterliste als das ich irgendwann mal globals verwende......
 
hey leute ich wollte hier keine Diskussion zum Thema Globals entfachen^^
Das sind nunmal meine Vorgaben und darum werde ich nicht drum rumkommen :/

mfg
 
@ArnoNühm: Nein ganz ohne Parameter ist auch nicht gut, lediglich am Beispiel einer Liste meinte ich, dass man die Basis global deklarieren kann. Ich glaub wir haben dran vorbeigeredet ;)

@myKam: nu ist zu spaet :P

@_fux_: Ich programmiere schon seit ca 3,5 Jahren. Jetzt interessiert mich deine Meinung, warum globale Variablen unsicher sind. Außerdem gibt es Situationen in den globale Variablen unumgaenglich sind, zB: bei Callbackfunktionen.
 
hehe recht hast du, ist mir auch gerade eingefallen.

also:

Code: 
LE* NeuesListenElement(int);
LE* ListenElementEinfuegen(LE*,LE*);
void ListenAusgabe(LE*);
void ListeLoeschen(LE*);

mit NeuesListenElement erstellst du eine neue, leere Liste (beim 1ten Aufruf) mit einem Wert [x] und hast somit schon den Anfang (wurzel) deiner liste

bei:
Code: 
ListenElementEinfuegen(LE* kLISTE, LE* neuELE);
übergibts du:
- bei dem ersten LE* die komplette liste [nenne ich mal kLISTE]
- beim zweiten LE* das" NeueListenElement". [nenne ich mal neuELE]

anschließen kannst du sowas wie:
Code: 
kLISTE = wurzel.
while(kLISTE->next=null){
kLISTE = kLISTE->next
}
kLISTE->next = neuELE
reinbasteln.

bei:
Code: 
void ListenAusgabe(LE*);

übergibst du mit LE* die komplette liste Liste und springst vom anfang (Wurzel) bist zum ende [wenn ->next = null ist].
bsp.:
nennen diese nochmal kLISTE:
dann machst du in der funktion noch einen LE* pointer (nenne ich einfach mal pLE)
und sagst:
Code: 
pLE = wurzel;

do{
cout << pLE->inhalt;
pLE = pLE->next; // damit wird der pointer auf das nächste Listenelement geschoben
}
while(pLE->next != null); // bis das ende erreicht ist


also die beschreibungen sind recht oberflächlich.... ich weiß auch nicht inweit du (oder allgemein) man diese verstehen kann, bin nicht so der erklärtyp, ich hoffe das du damit einigermaßen klarkommst ;)
ansonsten frag' einfach nochmal nach.
beim löschen bin ich mir in C nicht sicher, bei C++ würde ich einfach delete benutzen (wieder von element zu elment springen, da kann man 2 pointer nehmen, einmal auf: das zu löschende element und auf dem nachfolger vom dem was man löschen will. anschließend elemtn löschen, und die pointer nochmal um eins verschieben. wenn next-> null ist, dann einfach das element löschen...., ich glaube so geht das *g* hab' das dummerweise selbst noch nie richtig ausprogrammiert).

achso, hab das gerade in der schnelle gemacht, vorallemdingen bei den schleifen musst du noch schauen ob die abbruchbedingungen auch richtig sind ;) *gg*
-> hab atm etwas kopfweh deswegen hau ich nu vom PC ab oder daddel was ;) das hilft *gg*
 
Ich hatte zufaellig noch etwas Code fuer eine FIFO-Liste in meinem Ordner gefunden, dass ist zwar nicht die komplette Lsg deines Problems, aber es hilft dir bestimmt:
Code: 
#include <stdio.h>
#include <windows.h>

//+----------+   +----------+   +----------+   +----------+   
//|   data   |-->|   data   |-->|   data   |-->|   data   |-->NULL
//+----------+   +----------+   +----------+   +----------+   
//      ^
//      |
//     base

typedef struct _data
{
   DWORD          wert;
   PVOID          next;
}data, *pdata;

pdata base;

VOID delfromlist(pdata p)
{
   pdata         run;
   
   run=base;
   if(run==p)
   {
      if(run->next==NULL)
         base=NULL;
      else
         base=run->next;
   }
   else
   {
      while(run->next!=p)
         run=run->next;
      if(p->next==NULL)
         run->next=NULL;
      else
         run->next=p->next;
   }
   free((PVOID)p);
}

VOID addtolist(pdata p)
{
   pfinfo         run;


   if(base==NULL)
      base=p;
   else 
   {
      run=base;
      while(run->next)
         run=run->next;
      run->next=(PVOID)p;
   }
}

int main(void)
{
   int i;
   pfinfo f;
   
   base=NULL;
   for(i=0;i<6;i++)
   {
      f=(pdata)malloc(sizeof(data));
      memset(f, 0, sizeof(data));
      f->wert=i;
      printf("%d\n", f->wert);
      addtolist(f);
   }  

   f=base;
   do
   {      
      printf("%d\n", f->wert);
   }while(f=f->next);
   return 0;
}

@_fux_, du schuldest mir noch eine Antwort, von mir aus auch pn, aber es interessiert bestimmt auch andere.
 
Was hast du gegen diskussion? Solange das auf nem gewissen niveau bleibt, lernen doch alle beteiligten dabei.

Also weiter zu den globals:
Warum es gerade für listen gut sein soll, hab ich bisher noch nicht verstanden, könntest ja noch mal konkret erklären, warum du der meinung bist.

Bei Callbacks in gut designeten API's braucht man sie eigentlich auch nicht. Der standardweg wäre neben dem callback noch nen pointer auf nen parameterset mitzruegistrieren, was dem callback beim aufruf immer mitgegeben wird. Dann hat man bei sehr allgemeinen callbacks (z.B. in der Winapi bei CreateThread) zwar nen auch nicht so schönen downcast im callback, aber der ist meines erachtens nach weniger gefährlich. Bei schlechten API's, wo du diese möglichkeit nicht hast, brauchst du die globals leider.

Aber ich hab auch 1 Argument für globals. Singleton, wobei softwaretheoretiker auch bei denen der meinung sind, dass sie in vielen fällen auf einen schlechten entwurf hindeuten. Allerdings ist das vermeiden oft mit unvertretbar hohem aufwand verbunden.

Nun wieder zum Thema:

Das delete pendant in c heißt free(void*).

Für den Lehrer:

void insertElement(LE**,LE*),
void initElement(LE*),
das global hat dort nix zu suchen.



Warum?:
Aus den Konventionen, die ich im ersten Post angesprochen hab gehört u.a. dass eine funktion, die auf einer datenstruktur arbeitet diese nie in einem ungültigen zustand hinterlässt. seine insertfunction macht das, wenn ich beim verwenden deren rückgabewert ignoriere (es sei denn er updatet das global innerhalb der funktion, dann braucht er aber auch keinen rückgabewert).
Weiterhin sollte speicher möglicht in der gleichen funktion freigegeben werden, in der er allociert wurde. deshalb ist die eine initialisierende funktion einer erzeugenden funktion vorzuziehen.

Ferner gibt es Konventionen zur Namensgebung (structs haben nen großen anfangsbuchstaben, membervariablen enden oder beginnen mit _, funktionen klein, variablen klein, ...). Wenn er nicht versteht warum, geb ihm mal 10k loc, bei denen das nicht so ist und er soll erklären was dort passiert. Danach bekommt er ne idee davon.
 
ich habe nichts gegen diskusionen, aber das thema passt hier nicht rein;) der arme junge der hier was über eine einfach verkette liste interessiert, will das sicherlich nicht lesen, hat er ja schon gesagt ;) außerdem wäre das OffTopic in dem zusammenhang....
=D macht nen' neuen diskusionsthread und ich bin dabei ;-) *g
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben