Verkettete Listen
Steffen Nitz
wie kann man auf dem Amiga verkette Listen realisieren?
Ich möchte aus folgener Beispiel Struktur eine Liste erstellen die
die wenn nötig den kompletten Ramspeicher verbrauchen kann.
struct test
{
int var1;
int var2;
char text[100];
};
Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
Im Internet habe ich nach allen möglichen begriffen gesucht aber nichts
gefunden, zumindest keine Beispiel-Sources.
--
Gruß Steffen
Michael Kraemer
>
> wie kann man auf dem Amiga verkette Listen realisieren?
>
> Ich möchte aus folgener Beispiel Struktur eine Liste erstellen die
> die wenn nötig den kompletten Ramspeicher verbrauchen kann.
>
> struct test
> {
> int var1;
> int var2;
> char text[100];
> };
>
> Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
> realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
>
z.B. so (+- Tippfehler):
struct test {
struct Node ln;
... Dein Zeug ...
};
struct test test;
struct List lh;
...
NewList( &lh );
...
AddTail( &lh, &(test.ln) );
...
if ( lh.lh_Head ) {
while( ln = (struct Node *) RemTail( &lh ) ) {
... privates Zeug freigeben, falls noetig ...
}
}
th...@math.tu-berlin.de
Hi Steffen,
> wie kann man auf dem Amiga verkette Listen realisieren?
Nun, da hätte ich mehrere Möglichkeiten anzubieten:
1) Die Exec-Strukturen verwenden,
2) selbst stricken:
Hierzu gibt's eine Menge Literatur, da Listen einer der Standard-
Konstrukte sind, die man alle Nase lang braucht.
In der Amiga Aktuell schreib' ich gerade einen C++ Kurs, dort
werde ich auch was zu Listen sagen (allerdings zunächst nur
einfach verkettete, und selbstgestrickte).
> Ich möchte aus folgener Beispiel Struktur eine Liste erstellen die
> die wenn nötig den kompletten Ramspeicher verbrauchen kann.
> struct test
> {
> int var1;
> int var2;
> char text[100];
> };
> Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
> realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
#include <exec/nodes.h>
#include <exec/lists.h>
#include <proto/exec.h>
struct test {
struct Node node;
int var1;
int var2;
char text[100];
};
struct List testlist;
void init(void)
{
NewList(&testlist);
}
void AddElement(struct List *list,struct test *node)
{
AddHead(list,&(node->node));
}
void RemoveElement(struct test *node)
{
Remove(&(node->node));
}
Reicht das zumindest so für's grobe?
Exec-Listen gehen über eine Node bzw. MinNode-Struktur, die man
zweckmäßigerweise an den Anfang seiner eigenen Struktur setzt.
Operiert man dann mit den Exec-Funktionen auf der Node-Struktur
innerhalb der eigenen Struktur, so wird gewissermaßen der Rest
der eigenen Struktur gleich mit "ungehängt".
Mit der folgenden Schleife geht man beispielsweise alle Elemente
einer Liste durch:
void PrintList(struct List *list)
{
struct test *node;
for(node = (struct test *)(list->mh_Head);
node->node.mn_Succ;
node = (struct test *)(node->node.mn_Succ)) {
printf("%s\n",node->text);
}
}
Man beachte, dass bei der Exec-Konstruktion eine Liste dann "zuende"
ist, wenn man auf einen Knoten trifft, dessen mn_Succ-Feld auf NULL
steht (und nicht erst, wenn node == NULL ist). Das liegt daran, dass
der letzte Knoten de fakto auf das list->mh_Tail-Feld des Listenkopfes
zeigt und man bei "node->mn_Succ == NULL" dann eigentlich einen Pointer
auf dieses Feld in der Hand hält - und keine Node.
Das casting oben ist notwendig, da exec seine Nodes natürlich so
definiert, dass mn_Succ wieder auf "struct Node*" zeigt. Tut es
auch, aber auf die "struct Node" innerhalb der "struct test", deren
erster Teil sie ist. Darüber sollte man ein klein wenig nachdenken.
Grüße,
Thomas
Steffen Nitz
Hi,
> > wie kann man auf dem Amiga verkette Listen realisieren?
> >
> > Ich möchte aus folgener Beispiel Struktur eine Liste erstellen die
> > die wenn nötig den kompletten Ramspeicher verbrauchen kann.
> >
> > struct test
> > {
> > int var1;
> > int var2;
> > char text[100];
> > };
> >
> > Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
> > realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
> >
>
> z.B. so (+- Tippfehler):
[...]
Ich komm einfach nicht klar. Würde es ein bischen genauer gehen? Ich weis
z.B. nicht wie man sich in der Liste bewegt und wie man auf die eigentlichen
Variablen zugreift. Ein gutes Beispiel waehre ungefähr folgenes, anhand der
oberen Struktur:
Eintrag anlegen;
der var1 einen Wert zuweisen;
var1 ausgeben;
Nächsten Eintrag anlegen;
wieder var1 einen anderen Wert zuweisen;
var1 augeben;
Zum ersten Eintrag gehen;
var1 ausgeben;
Zum zweiten Eintrag gehen;
var1 ausgeben;
Ich bin noch C-Anfänger mit BB2-Erfahrung und ein bischen überfordert (mit C).
Ohne diese Listen brauch ich in C gar nicht mehr weiter machen :-((
--
Gruß Steffen
Steffen Nitz
> > wie kann man auf dem Amiga verkette Listen realisieren?
>
> Nun, da hätte ich mehrere Möglichkeiten anzubieten:
>
> 1) Die Exec-Strukturen verwenden,
> 2) selbst stricken:
> Hierzu gibt's eine Menge Literatur, da Listen einer der Standard-
> Konstrukte sind, die man alle Nase lang braucht.
> In der Amiga Aktuell schreib' ich gerade einen C++ Kurs, dort
> werde ich auch was zu Listen sagen (allerdings zunächst nur
> einfach verkettete, und selbstgestrickte).
>
> > Ich möchte aus folgener Beispiel Struktur eine Liste erstellen die
> > die wenn nötig den kompletten Ramspeicher verbrauchen kann.
>
> > struct test
> > {
> > int var1;
> > int var2;
> > char text[100];
> > };
>
> > Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
> > realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
[...]
Ich seh überhaupt nicht durch, bitte siehe vohriges Posting. Ich hab den ganzen
Vormittag mit diesen blöden Testrprogramm vergeudet:
#include <stdio.h>
#include <exec/lists.h>
#include <clib/alib_protos.h>
#include <clib/exec_protos.h>
struct structtest
{
struct Node node;
int var1;
int var2;
TEXT text[100];
};
struct List testliste;
struct structtest test;
void main(void)
{
printf("List-Grösse:%i\n",(int) sizeof(struct List));
printf("Node-Grösse:%i\n",(int) sizeof(struct Node));
NewList(&testliste);
AddHead(&testliste,&(test.node));
test.var1 = 11;
test.var2 = 12;
strcpy(test.text,"Test");
printf("Var1: %i\n",test.var1);
printf("Var2: %i\n",test.var2);
printf("text: '%s'\n",test.text);
printf("Node: %i\n",(int) test.node.ln_Succ);
AddHead(&testliste,&(test.node));
printf("Var1: %i\n",test.var1);
printf("Var2: %i\n",test.var2);
printf("text: '%s'\n",test.text);
printf("Node: %i\n",(int) test.node.ln_Succ);
}
für ein gutes Beispiel waehre ich dankbar.
--
Gruß Steffen
th...@math.tu-berlin.de
> Ich seh überhaupt nicht durch, bitte siehe vohriges Posting.
> Ich hab den ganzen
> Vormittag mit diesen blöden Testrprogramm vergeudet:
> #include <stdio.h>
> #include <exec/lists.h>
> #include <clib/alib_protos.h>
> #include <clib/exec_protos.h>
> struct structtest
> {
> struct Node node;
> int var1;
> int var2;
> TEXT text[100];
> };
> struct List testliste;
> struct structtest test;
Ist ok, bis auf die Tatsache, dass ich "proto" und nicht "clib"
einbinden würde.
> void main(void)
> {
> printf("List-Grösse:%i\n",(int) sizeof(struct List));
> printf("Node-Grösse:%i\n",(int) sizeof(struct Node));
Ist zwar richtig, aber warum brauchst Du die Größen hier?
> NewList(&testliste);
> AddHead(&testliste,&(test.node));
Beides korrekt. Damit hast Du eine Liste, deren erste und
einzige Node "test" ist.
> test.var1 = 11;
> test.var2 = 12;
> strcpy(test.text,"Test");
> printf("Var1: %i\n",test.var1);
> printf("Var2: %i\n",test.var2);
> printf("text: '%s'\n",test.text);
Soweit ok.
> printf("Node: %i\n",(int) test.node.ln_Succ);
> AddHead(&testliste,&(test.node));
Das geht nun nicht mehr. Die node ist bereits Teil der Liste. Damit
vermurxt Du die Liste leider.
> printf("Var1: %i\n",test.var1);
> printf("Var2: %i\n",test.var2);
> printf("text: '%s'\n",test.text);
> printf("Node: %i\n",(int) test.node.ln_Succ);
> für ein gutes Beispiel waehre ich dankbar.
Was für eine Sorte Beispiel brauchst Du denn? Bzw, was willst Du mit
Listen eigentlich machen?
Grüße,
Thomas
Steffen Nitz
> > Ich seh überhaupt nicht durch, bitte siehe vohriges Posting.
> > Ich hab den ganzen
> > Vormittag mit diesen blöden Testrprogramm vergeudet:
[...]
> > struct List testliste;
> > struct structtest test;
>
> Ist ok, bis auf die Tatsache, dass ich "proto" und nicht "clib"
> einbinden würde.
Warum? Habe das aber erstmal gemacht, und für NewList das
entsprechene Makro aus "inline/alib.h" eingebunden.
> > printf("List-Grösse:%i\n",(int) sizeof(struct List));
> > printf("Node-Grösse:%i\n",(int) sizeof(struct Node));
>
> Ist zwar richtig, aber warum brauchst Du die Größen hier?
Wollte nur den Speicherverbrauch rausbekommen.
[..]
> > printf("Node: %i\n",(int) test.node.ln_Succ);
> > AddHead(&testliste,&(test.node));
>
> Das geht nun nicht mehr. Die node ist bereits Teil der Liste. Damit
> vermurxt Du die Liste leider.
Äh womit? Mit AddHead? Aber warum? Ich denk das man damit ein
neues Element der List hinzufügt.
> > printf("Var1: %i\n",test.var1);
> > printf("Var2: %i\n",test.var2);
> > printf("text: '%s'\n",test.text);
> > printf("Node: %i\n",(int) test.node.ln_Succ);
>
> > für ein gutes Beispiel waehre ich dankbar.
>
> Was für eine Sorte Beispiel brauchst Du denn? Bzw, was willst Du mit
Am besten waehre für mich, ein fuktionierener Source ala
Eintrag anlegen;
der var1 einen Wert zuweisen;
var1 ausgeben;
Nächsten Eintrag anlegen;
wieder var1 einen anderen Wert zuweisen;
var1 augeben;
Zum ersten Eintrag gehen;
var1 ausgeben;
Zum zweiten Eintrag gehen;
var1 ausgeben;
wie ich schon mal schrieb, als Antwort auf Michael.
> Listen eigentlich machen?
Noch nichts spezielles, aber nach meiner Erfahrung in Blitz2 werde ich das
bald brauchen.
Ich habe ein paar Makros gefunden, die den Blitz2-Befehlen für Listen
ziemlich nahe kommen. (Ersatz der BB2-Funk. FirstItem(),LastItem() usw.)
#define FirstNode_(l) (((struct List *) (l))-lh_Head)
#define LastNode_(l) (((struct List *) (l))-lh_TailPred)
#define NxtNode_(n) (((struct Node *) (n))-ln_Succ)
#define PrvNode_(n) (((struct Node *) (n))-ln_Pred)
#define SetData_(n, d) ((struct Node *) (n))-ln_Name = (void *) (d)
#define NodeData_(n) ((struct Node *) (n))-ln_Name
#define IsTail_(n) (!NxtNode(NxtNode(n)))
#define IsHead_(n) (!PrvNode(PrvNode(n)))
#define IsListEmpty_(l) (LastNode(l) == (Node *) (l) )
#define AtListEnd_(n) (!NxtNode(n))
Eine Schleife soll dann auch nach folgener art möglich sein.
for (n=FirstNode(l) ; !AtListEnd(n) ; n=NxtNode(n))
{
......
}
Nur komme ich damit aber nicht zurecht, entweder kommt eine Pointer-Fehlermeldung,
oder das lh_Head usw. nicht deffiniert ist.
Wie setze ich die ein? Und wofür ist "In_Name" gedacht?
--
Gruß Steffen
Gunther Nikl
>> einbinden würde.
>
> Warum?
Weil es dann egal ist, wie eine Compilersystem Stubfunktionen (=amiga.lib)
umgeht.
> Habe das aber erstmal gemacht, und für NewList das entsprechene Makro aus
> "inline/alib.h" eingebunden.
Das bekommst Du nur beim GCC gratis, wenn Du schön <proto/> benutzt.
Du solltest auf keinen Fall "inline/alib.h" selber einbinden!
Bei anderen Compilern kommt NewList() aus amiga.lib mit Prototype in
clib/alib_protos.h. Dieses File solltest allerdings selber einbinden,
denn dafür gibt es kein Pendant in <proto/>.
Gunther
--
Linux is only free if your time has no value
- Jamie Zawinsky
Stefan Kleinheinrich
"Steffen Nitz" <Steffe...@T-Online.de> schrieb im Newsbeitrag
news:a40mhe$gv4$07$1...@news.t-online.com...
schnippeldieschnapp.
>
> Wie setze ich die ein? Und wofür ist "In_Name" gedacht?
Für die Exec-Funktion "FindName" natürlich :))
Die Exec-Nodes werden im OS zur Verwaltung beliebiger Structuren wie
Tasks oder Libraries verwendet. Wenn du z.B OpenLibrary("dippel.library,0L)
aufrufts überprüft Exec erstmal anhand seiner internen Liste ob die Library
schon
im Speicher ist und ruft dafür FindName(LibList,"dippel.library") auf.
MfG
Stefan
th...@math.tu-berlin.de
Hi,
>> Ist ok, bis auf die Tatsache, dass ich "proto" und nicht "clib"
>> einbinden würde.
> Warum? Habe das aber erstmal gemacht, und für NewList das
> entsprechene Makro aus "inline/alib.h" eingebunden.
Die Includes aus "proto" beinhalten ebenso die "pragmas", die der
Compiler für schnellere Aufrufe gebrauchen kann. Die "clib" beinhalten
nur die Prototypen für die C-Aufrufe.
>> > printf("Node: %i\n",(int) test.node.ln_Succ);
>> > AddHead(&testliste,&(test.node));
>>
>> Das geht nun nicht mehr. Die node ist bereits Teil der Liste. Damit
>> vermurxt Du die Liste leider.
> Äh womit? Mit AddHead? Aber warum? Ich denk das man damit ein
> neues Element der List hinzufügt.
Richtig, aber *dieses* Element war schon in der Liste, siehe weiter
oben in Deinem Programm.
>> Was für eine Sorte Beispiel brauchst Du denn? Bzw, was willst Du mit
> Am besten waehre für mich, ein fuktionierener Source ala
> Eintrag anlegen;
> der var1 einen Wert zuweisen;
> var1 ausgeben;
> Nächsten Eintrag anlegen;
> wieder var1 einen anderen Wert zuweisen;
> var1 augeben;
> Zum ersten Eintrag gehen;
> var1 ausgeben;
> Zum zweiten Eintrag gehen;
> var1 ausgeben;
/* mit dynamischer Speicherverwaltung */
struct testnode *node1,*node2;
NewList(&testlist);
node1 = malloc(sizeof(struct testnode)); /* allozieren */
node1->var1 = 0;
node2 = malloc(sizeof(struct testnode)); /* allozieren */
node2->var2 = 2;
AddHead(&testlist,&(node1->node)); /* einfügen */
AddHead(&testlist,&(node2->node)); /* einfügen */
/*
Bitte die Abfrage, ob der Speicher erfolgreich alloziert wurde, hier
noch einfügen, ebenso die Freigabe des Speichers.
*/
node->var1 = 1;
/* Zum "ersten Eintrag" gehen: Ersten im welchem Sinne? */
struct testnode *first,*next;
first = (struct testnode *)(testlist.lh_Head);
/* Prüfe, ob wir nicht auch eine leere Liste
* haben könnten.
*/
if (first->node.ln_Succ) {
printf("%d\n",first->var1);
/*
lh_Head zeigt immer auf den ersten, lh_TailPred immer auf den
letzten Eintrag. lh_Tail ist immer NULL.
Zum nächsten Eintrag gehen.
*/
next = (struct testnode *)(first->node.ln_Succ);
/* prüfe, ob wir wirklich mehr als einen Eintrag haben
*/
if (next->node.ln_Succ) {
printf("%d\n",next->var1);
}
}
>> Listen eigentlich machen?
> Noch nichts spezielles, aber nach meiner Erfahrung in Blitz2 werde ich das
> bald brauchen.
> Ich habe ein paar Makros gefunden, die den Blitz2-Befehlen für Listen
> ziemlich nahe kommen. (Ersatz der BB2-Funk. FirstItem(),LastItem() usw.)
> #define FirstNode_(l) (((struct List *) (l))-lh_Head)
> #define LastNode_(l) (((struct List *) (l))-lh_TailPred)
Bedarf aber noch der Überprüfung, ob diese Knoten auch wirklich
existieren:
first = list->lh_Head;
if (first->ln_Succ) {
/* existiert! */
}
last = list->lh_TailPred;
if (last->lh_Pred) {
/* existiert */
}
Die Listen könnten auch leer sein.
> #define NxtNode_(n) (((struct Node *) (n))-ln_Succ)
> #define PrvNode_(n) (((struct Node *) (n))-ln_Pred)
Ditto, siehe oben.
> #define SetData_(n, d) ((struct Node *) (n))-ln_Name = (void *) (d)
> #define NodeData_(n) ((struct Node *) (n))-ln_Name
Daten würde ich eigentlich in ln_Name nicht hineinstellen, ein String
wäre schon besser geeignet.
> #define IsTail_(n) (!NxtNode(NxtNode(n)))
> #define IsHead_(n) (!PrvNode(PrvNode(n)))
> #define IsListEmpty_(l) (LastNode(l) == (Node *) (l) )
> #define AtListEnd_(n) (!NxtNode(n))
> Eine Schleife soll dann auch nach folgener art möglich sein.
> for (n=FirstNode(l) ; !AtListEnd(n) ; n=NxtNode(n))
> {
> ......
> }
> Nur komme ich damit aber nicht zurecht, entweder kommt eine Pointer-Fehlermeldung,
> oder das lh_Head usw. nicht deffiniert ist.
Hast Du exec/lists.h eingebunden?
Schleife durchgehen:
#include <exec/lists.h>
#include <exec/nodes.h>
struct Node *node;
struct List *list;
for(node = list->lh_Head; node->ln_Succ; node = node->ln_Succ) {
...
}
> Wie setze ich die ein? Und wofür ist "In_Name" gedacht?
Die Makros? Am besten gar nicht, das geht gerade noch von Hand. (-;
ln_Name dient optional zur Benahmung eines Knotens (wie der Name ja schon
sagt). Solange Du mit Deinen eigenen Listen arbeitest, kannst Du diesen
Zeiger natürlich verwenden, wie Du magst. Das Betriebssytem verwendet
diesen Zeiger etwa bei der Verwaltung der Bibliotheken ("libraries"), die
auch in solchen Knoten-Strukturen im Speicher vorliegen. ln_Name zeigt
dann auf den Namen der Library.
Grüße,
Thomas
Kai Scherrer
> wie kann man auf dem Amiga verkette Listen realisieren?
>
> Ich möchte aus folgener Beispiel Struktur eine Liste erstellen die
> die wenn nötig den kompletten Ramspeicher verbrauchen kann.
>
> struct test
> {
> int var1;
> int var2;
> char text[100];
> };
>
> Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
> realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
Diese Funktionen der exec-library sind tatsächlich dazu gedacht, verkettete
Listen zu verwalten, aber man sollte diese Funktionen nur verwenden, wenn
man beispielsweise auf betriebssysteminterne Listen zugreifen möchte. Wenn
möglich (also immer :)) sollte man eine solche Liste per Hand erzeugen oder
die Standardbibliothek von C++ (die darf dann auf oben genannte Funktionen
aufsetzen, wenn sie will) verwenden, damit hält man seinen Source portabel.
Generell lassen sich verkettete Listen mit objektorientierter Programmierung
unter C++ wirklich deutlich eleganter und fehlerunanfälliger lösen als mit
Standard C, bei gleicher Leistung. Es lohnt sich hier also wirklich sich mit
C++ zu beschäftigen.
Falls du wirklich explizit die Benutzung der obigen Funktionen erlernen
willst, empfehle ich dir trotzdem, erstmal das Grundprinzip von doppelt
verketteten Listen in C zu verstehen, denn dann fällt dir die Verwendung
dieser Funktionen quasi in den Schoss :)
Hier jetzt ein Beispielprogramm für eine doppelt verkettete Liste. Es werden
nicht alle Möglichkeiten beschrieben, es fehlt zum Beispiel eine Funktion um
Elemente in der Liste umzupositionieren oder zwischen zwei Elemente
einzufügen, aber wenn du den Source verstanden hast, kannst du dir diese
Funktionen problemlos selbst schreiben. Aber wie gesagt, verwende besser C++
und deren Standardbibliothek, damit machst du dir das Leben wirklich
leichter. Dann ist aber de.comp.lang.iso-c++ dein Freund :)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TEST_TEXTLENGTH 100
struct test
{
struct test *next; // Zeiger auf das folgende Element
struct test *prev; // Zeiger auf das vorherige Element
int var1;
int var2;
char text[TEST_TEXTLENGTH];
};
struct testlist
{
struct test *first; // Erstes Element der Liste
struct test *last; // Letztes Element der Liste
};
int addtest(struct testlist *mytestlist,int var1,int var2,char*text)
{
struct test *newtest,*tmp;
// Neues Element erzeugen
newtest=(struct test*)malloc(sizeof(struct test));
if(!newtest)return 0;
// Element ans Ende der Liste hängen
tmp=mytestlist->last; // Das alte letzte Element sichern
mytestlist->last=newtest; // Das Neue Element als letztes Element eintragen
newtest->prev=tmp; /* Das vorherige letzte Element als vorheriges Element
des neuen Elements eintragen */
newtest->next=0; // Das nachfolgende Element auf 0 setzen
if(newtest->prev)newtest->prev->next=newtest; /* Wenn es ein vorheriges
Element gibt, dort als nächstes
Element das neue Element
eintragen */
if(!mytestlist->first)mytestlist->first=newtest; /* Wenn es noch kein
erstes Element gibt (weil dies das
allererste Element in der Liste ist) das
neue Element auch als erstess Element
eintragen */
// Werte ins neue Element kopieren
newtest->var1=var1;
newtest->var2=var2;
strncpy(newtest->text,text,TEST_TEXTLENGTH);
return 1;
}
void remtest(struct testlist *mytestlist,struct test *testtodelete)
{
struct test *wanderer;
wanderer=mytestlist->first;
while(wanderer)
{
if(wanderer==testtodelete) // Element gefunden
{
/* Element aus der Liste aushängen, dabei die Sonderfälle beachten,
dass es sich um das erste oder letzte Element der Liste handeln
könnte */
if(wanderer->prev)wanderer->prev->next=wanderer->next;
else mytestlist->first=wanderer->next;
if(wanderer->next)wanderer->next->prev=wanderer->prev;
else mytestlist->last=wanderer->prev;
free(wanderer); // Speicher freigeben
return;
}
wanderer=wanderer->next;
}
return;
}
struct test* findtest(struct testlist *mytestlist,int var1,int
var2,char*text)
{
struct test *wanderer;
wanderer=mytestlist->first;
while(wanderer)
{
if(var1 && wanderer->var1==var1)return wanderer;
if(var2 && wanderer->var2==var2)return wanderer;
if(text && !strncmp(wanderer->text,text,TEST_TEXTLENGTH))return wanderer;
wanderer=wanderer->next;
}
return 0;
}
void printtest(struct test *mytest)
{
printf("var1:%d var2:%d text:%s\n",mytest->var1,mytest->var2,mytest->text);
return;
}
void printlist(struct testlist *mytestlist)
{
struct test *wanderer;
int zaehler=0;
wanderer=mytestlist->first;
while(wanderer)
{
printf("%d: ",zaehler++);
printtest(wanderer);
wanderer=wanderer->next;
}
return;
}
void deletelist(struct testlist *mytestlist)
{
struct test *wanderer,*tmp;
wanderer=mytestlist->first;
while(wanderer)
{
tmp=wanderer->next;
free(wanderer);
wanderer=tmp;
}
return;
}
int main()
{
struct testlist liste;
// Liste initialisieren
liste.first=0;
liste.last=0;
// Ein paar Beispieldaten einfügen
addtest(&liste,1,100,"eins");
addtest(&liste,2,200,"zwei");
addtest(&liste,3,300,"drei");
addtest(&liste,4,400,"vier");
// Liste ausgeben
printlist(&liste);
// Nach Datensatz suchen und ausgeben
printtest(findtest(&liste,0,0,"drei"));
// Nach Datensatz suchen und löschen
remtest(&liste,findtest(&liste,4,0,0));
// Noch einen Datensatz anhängen
addtest(&liste,5,500,"fünf");
// Liste nochmal ausgeben
printlist(&liste);
// Liste löschen
deletelist(&liste);
return 0;
}
Ciao,
Kai
Steffen Nitz
ich habe jetzt den angehangenen Source anhand eurer Infos getippt.
Ist der ok so, oder könnten Probleme auftreten?
--
Gruß Steffen
Steffen Nitz
> > Ich weiss das man das irgendwie mit AddHead, AddTrail, Remove, usw.
> > realisieren kann, nur nicht wie. Ein Beispiel-Source währe ganz nett.
Auch Anhand deines Beispieles habe ich was getippt, (hat den größten Teil
der Zeit verschlungen) wozu ich die Frage habe, ob es in C überhaupt brauchbar
ist, wegen der Kompatiblitat (Listview usw.). Ich glaube jetzt das die ganze tipperei
um sonst wahr :-(( (Vom Lerneffekt mal abgesehen :-) ). Der Source funktioniert
aber nicht 100%tieg, da das rückwerts löschen der Liste nicht klappt und die
Kommentare sind auch nicht gerade so gelungen. (Copy&Paste, spätere Source-
Änderungen usw.)
Als Angang ging es nicht. (Error: no binary-group)
also mach ich es so:
----Source----
#include <stdio.h>
#include <stdlib.h>
#include <exec/types.h>
struct liste
{
struct liste *next; /* Zeiger auf den nächsten Eintrag */
struct liste *prev; /* Zeiger auf den vorherigen Eintrag */
int var1;
int var2;
char text$[100];
} *item; /* Zeiger auf den aktueller Eintrag der Liste */
struct listPos
{
struct liste *start; /* Erster Eintrag der liste merken */
struct liste *end; /* Letzter Eintrag der liste letzen */
int eintraege; /* Gesamt-Eintraege */
int pos; /* Position in der liste */
} listpos;
int AddLast(int var1,int var2, char *text) /* Einen Eintrag am Ende der Liste hinzufügen
*/
{
struct liste *dummy; /* Umgehungszeiger ob das Element angelagt werden konnte */
struct liste *enditem; /* Zeiger auf das Letzte Element der liste */
dummy = (struct liste *) malloc(sizeof(struct liste));
if (dummy) /* Kann ein neuer Eintrag angelegt werden? */
{
enditem = listpos.end; /* Zum letzten Element gehen */
enditem->next = dummy; /* Damit das letzte Element auf das jetzt neu
angelegte zeigt*/
dummy->prev = enditem;
dummy->next = 0;
item = dummy; /* Den neuen Einteag zum aktuellem Eintrag werden
lassen */
if (!listpos.eintraege) /* Falls es das erste Element ist, ... */
{
listpos.start = item; /* ... merken (als erstes Element) */
}
listpos.end = item; /* Da das neue das letzte Element ist, als letztes
Element merken */
listpos.pos = listpos.eintraege; /* Listen Positionszaehler auf den
aktuellen Eintrag (letzten) setzen */
listpos.eintraege += 1; /* Anzahl der Eintraege um einen erhöhen */
/* Werte übergeben */
item->var1 = var1;
item->var2 = var2;
strcpy(item->text$,text);
return TRUE;
}
return FALSE;
}
int AddFirst(int var1,int var2,char *text)
{
struct liste *dummy; /* Umgehungszeiger ob das Element angelagt werden konnte */
struct liste *firstitem; /* Zeiger auf das Letzte Element der liste */
dummy = (struct liste *) malloc(sizeof(struct liste));
if (dummy) /* Kann ein neuer Eintrag angelegt werden? */
{
firstitem = listpos.start; /* Zum ersten Element gehen */
firstitem->prev = dummy; /* Damit das alte erste Element auf das jetzt
neu angelegte zeigt*/
dummy->prev = 0; /* Zeigt auf das letzte Element */
dummy->next = firstitem;
item = dummy; /* Den neuen Einteag zum aktuellem Eintrag
werden lassen */
if (!listpos.eintraege) /* Falls es das erste Element ist, ... */
{
listpos.end = item; /* ... merken (als erstes Element) */
}
listpos.start = item; /* Da das neue das letzte Element ist, als letztes
Element merken */
listpos.pos = 1; /* Listen Positionszaehler auf den aktuellen
Eintrag (letzten) setzen */
listpos.eintraege += 1; /* Anzahl der Eintraege um einen erhöhen */
/* Werte übergeben */
item->var1 = var1;
item->var2 = var2;
strcpy(item->text$,text);
return TRUE;
}
return FALSE;
}
int AddItem(int var1,int var2,char *text)
{
struct liste *dummy; /* Umgehungszeiger ob das Element angelagt werden konnte
*/
struct liste *next,*prev; /* Zeiger auf das Letzte Element der liste */
dummy = (struct liste *) malloc(sizeof(struct liste));
if (dummy) /* Kann ein neuer Eintrag angelegt werden? */
{
next = item;
prev = item->prev;
item = dummy;
if (prev)
{
prev->next = item;
item->prev = prev;
}
else
{
listpos.start = item;
listpos.pos = 1;
}
if (next)
{
next->prev = item;
item->next = next;
listpos.pos += 1;
}
else
{
listpos.end = item;
listpos.pos = listpos.eintraege + 1;
}
listpos.eintraege += 1;
/* Werte übergeben */
item->var1 = var1;
item->var2 = var2;
strcpy(item->text$,text);
return TRUE;
}
return FALSE;
}
int KillItem(void) /* Eintrag löschen */
{
struct liste *prev,*next; /* Zeiger aus das vorherige und nächste Element */
if (item)
{
prev = item->prev;
next = item->next;
//free(item); /* Aktuellen Eintrag löschen */
/* Zeiger richtig setzen */
if (!prev)
{ /* Falls es keinen vorherigen Eintrag gibt... */
if (next)
{ /* Wenn es einen nächsten Eintrag gibt */
listpos.start = next; /* Neuen Starteintrag merken */
next->prev = 0; /* Zeiger auf das vorherige Element löschen */
item = next; /* Eintrag zum aktuellen machen */
}
else
{
/* ... und keinen nächsten ist die Liste leer */
listpos.end = 0;
listpos.start = 0;
item = 0;
listpos.eintraege = 0;
return FALSE;
}
}
else
{
/* Wenn es einen nachfolgeen Eintrag gibt */
printf("Prev\n");
if (!next)
{
printf("Prev & Next\n");
prev->next = next;
next->prev = prev;
item = next; /* Zum aktuellem Eintrag machen */
}
else
{
printf("Prev & !Next\n");
if (next)
{
item = next;
}
else
{
item = prev;
}
}
listpos.pos -=1;
}
listpos.eintraege-=1; /* Einträge um einen runterzählen */
return TRUE;
}
return FALSE;
}
int FirstItem(void) /* Zum ersten Element der Liste springen */
{
if (listpos.start)
{
item = listpos.start;
listpos.pos = 1;
return TRUE;
}
return FALSE;
}
int LastItem(void) /* Zum letzten Eintrag springen*/
{
if (listpos.end)
{
item = listpos.end;
listpos.pos = listpos.eintraege;
return TRUE;
}
return FALSE;
}
int NextItem(void) /* Zum naechsten Eintrag gehen */
{
if (item->next)
{
item = item->next;
listpos.pos +=1 ;
return TRUE;
}
return FALSE;
}
int PrevItem(void) /* Zum vorherigen Eintrag gehen */
{
if (item->prev)
{
item = item->prev;
listpos.pos -=1 ;
return TRUE;
}
return FALSE;
}
int GotoItem(int eintrag)
{
int pos;
if ((eintrag <= listpos.eintraege) && (FirstItem()))
{
for (pos=2;pos<=eintrag;pos++) { NextItem(); } return TRUE;
}
return FALSE;
}
void Anzeigen(int *pos)
{
printf("Eintrag Nr: %i\n",*pos);
printf("Var1: %i\n",item->var1);
printf("Var2: %i\n",item->var2);
printf("Text: '%s'\n",item->text$);
}
void main(void)
{
listpos.eintraege = 0;
AddLast (11,12,"Addlast 1");
AddLast (21,22,"Addlast 2");
AddLast (31,32,"Addlast 3");
AddFirst(41,42,"AddFirst 1");
AddItem (51,52,"AddItem 1");
AddLast (61,62,"Addlast 4");
AddItem (71,72,"AddItem 2");
if (FirstItem())
{
printf("Erster Eintrag\n");
Anzeigen(&listpos.pos);
if (LastItem())
{
printf("\nLetzer Eintrag\n");
Anzeigen(&listpos.pos);
}
}
else
{
printf("Keine Eintraege vorhanden!");
exit(0);
}
/* Alle Eintraege zeigen */
printf("\nListe vorwerts ausgeben:\n");
FirstItem();
do
{
Anzeigen(&listpos.pos);
} while(NextItem());
/* Alle Eintraege zeigen */
printf("\nListe rückwerts ausgeben:\n");
LastItem();
do
{
Anzeigen(&listpos.pos);
} while(PrevItem());
printf("\nVierten Eintrag ausgeben:\n");
if (GotoItem(4))
{
Anzeigen(&listpos.pos);
printf("\nVierten Eintrag löschen:\n");
KillItem();
printf("\nDer Aktuelle Eintrag ist jetzt:\n");
Anzeigen(&listpos.pos);
printf("\nListe nochmal ausgeben:\n");
FirstItem();
do
{
Anzeigen(&listpos.pos);
} while(NextItem());
printf("\nListe rückwerts ausgeben:\n");
LastItem();
do
{
Anzeigen(&listpos.pos);
} while(PrevItem());
}
else
{
printf("Eintrag nicht vorhanden!!");
}
printf("\nAlle Eintrage löschen\n");
LastItem();
do
{
printf("Lösche Eintrag: %i\n",listpos.eintraege);
} while(KillItem());
printf("\n********** Ende **********\n");
}
---- Source-Ende ----
--
Gruß Steffen
Kai Scherrer
> Auch Anhand deines Beispieles habe ich was getippt, (hat den größten Teil
> der Zeit verschlungen) wozu ich die Frage habe, ob es in C überhaupt
brauchbar
> ist, wegen der Kompatiblitat (Listview usw.). Ich glaube jetzt das die
ganze tipperei
> um sonst wahr :-(( (Vom Lerneffekt mal abgesehen :-) ).
Naja, bei dem Beispiel ging es auch nur um den Lerneffekt. Ohne
objektorientierte Programmierung ist aber die Implementation von verketteten
Listen imho sehr umständlich und auch sehr fehleranfällig. Wie schon gesagt,
ich würde dir wirklich empfehlen dich speziell bei solchen Sachen mit C++
auseinanderzusetzen, da man mit C++ wirklich deutlich sicherer und sauberer
programmieren kann. Ausserdem gibts da eine Standardbibliothek, welche dir
Listen mit allem SchnickSchnack zur Verfügung stellen.
exec-Listen funktionieren im Prinzip genauso und nehmen dir nur ein bisschen
Arbeit ab, durch die Liste hangeln und deine Elemente richtig allozieren und
freigeben musst du dich dort. Aber ich würde die nur verwenden, wenn du
darauf angewiesen bist.
> Der Source funktioniert
> aber nicht 100%tieg, da das rückwerts löschen der Liste nicht klappt und
die
> Kommentare sind auch nicht gerade so gelungen. (Copy&Paste, spätere
Source-
> Änderungen usw.)
Da waren Fehler in KillItem(), ich habe das unten mal kommentiert.
> #include <stdio.h>
> #include <stdlib.h>
> #include <exec/types.h>
Hier hast du '#include <string.h>' vergessen, du verwendest die Funktion
strcpy().
> int KillItem(void) /* Eintrag löschen */
> {
> struct liste *prev,*next; /* Zeiger aus das vorherige und nächste
Element */
> if (item)
> {
> prev = item->prev;
> next = item->next;
> //free(item); /* Aktuellen Eintrag löschen */
Wieso ist das free() auskommentiert? Das ist schon richtig an dieser Stelle.
>
> /* Zeiger richtig setzen */
> if (!prev)
> { /* Falls es keinen vorherigen Eintrag gibt... */
> if (next)
> { /* Wenn es einen nächsten Eintrag gibt */
> listpos.start = next; /* Neuen Starteintrag merken */
> next->prev = 0; /* Zeiger auf das vorherige
Element löschen */
> item = next; /* Eintrag zum aktuellen machen
*/
> }
> else
> {
> /* ... und keinen nächsten ist die Liste leer */
> listpos.end = 0;
> listpos.start = 0;
> item = 0;
> listpos.eintraege = 0;
> return FALSE;
> }
> }
> else
> {
> /* Wenn es einen nachfolgeen Eintrag gibt */
> printf("Prev\n");
> if (!next)
Hier wolltest du wohl 'if(next)' schreiben :)
> {
> printf("Prev & Next\n");
> prev->next = next;
> next->prev = prev;
Und hier gibts einen Absturz, da next hier in jedem Fall auf 0 zeigt und du
einen Schreibzugriff darauf machst. Wenn du oben das 'if(!next)'
korrigierst, kannst du das hier lassen.
> item = next; /* Zum aktuellem Eintrag machen */
> }
> else
> {
> printf("Prev & !Next\n");
> if (next)
Unötige Abfrage, da 'next' hier immer 0 ist (wenn du das 'if(!next)' oben
korrigiert hast) Dagegen machen wir nur folgendes hier:
prev->next=0;
item=prev;
> }
> listpos.pos -=1;
> }
>
> listpos.eintraege-=1; /* Einträge um einen runterzählen */
> return TRUE;
> }
> return FALSE;
> }
> void main(void)
WAAAH! Es heist 'int main()' oder 'int main(int argc,char**argv)' Wenn du
ein Buch hast, das sowas wie 'void main()' schreibt, dann verbrenne es!
Ciao,
Kai
Gunther Nikl
> ich würde dir wirklich empfehlen dich speziell bei solchen Sachen mit C++
> auseinanderzusetzen, da man mit C++ wirklich deutlich sicherer und sauberer
> programmieren kann. Ausserdem gibts da eine Standardbibliothek, welche dir
> Listen mit allem SchnickSchnack zur Verfügung stellen.
Den gibt es auch bei Java :-)
Kai Scherrer
> In de.comp.sys.amiga.tech Kai Scherrer <k...@kaiiv.de> wrote:
>> ich würde dir wirklich empfehlen dich speziell bei solchen Sachen mit C++
>> auseinanderzusetzen, da man mit C++ wirklich deutlich sicherer und
sauberer
>> programmieren kann. Ausserdem gibts da eine Standardbibliothek, welche
dir
>> Listen mit allem SchnickSchnack zur Verfügung stellen.
>
> Den gibt es auch bei Java :-)
Java ist auf Amigas aber nicht wirklich eine Option :)
Ciao,
Kai
Steffen Nitz
> > Auch Anhand deines Beispieles habe ich was getippt, (hat den größten Teil
> > der Zeit verschlungen) wozu ich die Frage habe, ob es in C überhaupt
> brauchbar
> > ist, wegen der Kompatiblitat (Listview usw.). Ich glaube jetzt das die
> ganze tipperei
> > um sonst wahr :-(( (Vom Lerneffekt mal abgesehen :-) ).
>
> Naja, bei dem Beispiel ging es auch nur um den Lerneffekt. Ohne
> objektorientierte Programmierung ist aber die Implementation von verketteten
> Listen imho sehr umständlich und auch sehr fehleranfällig. Wie schon gesagt,
> ich würde dir wirklich empfehlen dich speziell bei solchen Sachen mit C++
> auseinanderzusetzen, da man mit C++ wirklich deutlich sicherer und sauberer
> programmieren kann. Ausserdem gibts da eine Standardbibliothek, welche dir
> Listen mit allem SchnickSchnack zur Verfügung stellen.
> exec-Listen funktionieren im Prinzip genauso und nehmen dir nur ein bisschen
> Arbeit ab, durch die Liste hangeln und deine Elemente richtig allozieren und
> freigeben musst du dich dort. Aber ich würde die nur verwenden, wenn du
> darauf angewiesen bist.
Auf jeden fall habe ich das mit den Listen jetzt kappiert.
> > Der Source funktioniert
> > aber nicht 100%tieg, da das rückwerts löschen der Liste nicht klappt und
> die
> > Kommentare sind auch nicht gerade so gelungen. (Copy&Paste, spätere
> Source-
> > Änderungen usw.)
>
> Da waren Fehler in KillItem(), ich habe das unten mal kommentiert.
Ja.
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <exec/types.h>
>
> Hier hast du '#include <string.h>' vergessen, du verwendest die Funktion
> strcpy().
Ist mir gar nicht aufgefallen, der Compiler bringt zumindest keine Warnungen/Errors,
wie sonst immer!?!?
> > int KillItem(void) /* Eintrag löschen */
> > {
> > struct liste *prev,*next; /* Zeiger aus das vorherige und nächste
> Element */
> > if (item)
> > {
> > prev = item->prev;
> > next = item->next;
> > //free(item); /* Aktuellen Eintrag löschen */
>
> Wieso ist das free() auskommentiert? Das ist schon richtig an dieser Stelle.
War nur der test ob das die Absturzstelle ist. (bevor if (item) eingebunden war)
> > printf("Prev\n");
> > if (!next)
>
> Hier wolltest du wohl 'if(next)' schreiben :)
War ein bischen genervt, von den vielen abstürzen, das ich bald bloss noch
stuss geschrieben und den Source hier rein gehauen habe. :-(
[...]
> > void main(void)
>
> WAAAH! Es heist 'int main()' oder 'int main(int argc,char**argv)' Wenn du
> ein Buch hast, das sowas wie 'void main()' schreibt, dann verbrenne es!
Noch ein Fehler vom ersten C-Tag an. Im Buch stand immer bloss 'main()' und
da der GCC immer mit Warnugen kam habe ich einfach solange rumprobiert
bis keine mehr kamen und dann ist das zu einer dummen gewohnheit geworden :-|
--
Gruß Steffen
Dirk Stoecker
> > Naja, bei dem Beispiel ging es auch nur um den Lerneffekt. Ohne
> > objektorientierte Programmierung ist aber die Implementation von verketteten
> > Listen imho sehr umständlich und auch sehr fehleranfällig. Wie schon gesagt,
> > ich würde dir wirklich empfehlen dich speziell bei solchen Sachen mit C++
> > auseinanderzusetzen, da man mit C++ wirklich deutlich sicherer und sauberer
> > programmieren kann. Ausserdem gibts da eine Standardbibliothek, welche dir
Hmm. Fuer Listen braucht man wirklich keine Objektorientierung. Und
besonders kompliziert ist es auch nicht. Man muss nur je nach Anwendung
entscheiden, wie man Anfang und Ende handhabt und ob einfach oder doppelt
verkettet.
> > > void main(void)
> >
> > WAAAH! Es heist 'int main()' oder 'int main(int argc,char**argv)' Wenn du
> > ein Buch hast, das sowas wie 'void main()' schreibt, dann verbrenne es!
>
> Noch ein Fehler vom ersten C-Tag an. Im Buch stand immer bloss 'main()' und
> da der GCC immer mit Warnugen kam habe ich einfach solange rumprobiert
> bis keine mehr kamen und dann ist das zu einer dummen gewohnheit geworden :-|
Und das stimmt so auch nicht.
Laut ISO 9899:1999 Pargraph 5.1.2.2.1 hast Du recht. Paragraph 5.1.2.2.3
jedoch gibt den Sonderfall wieder, dass main nicht int zurueckgibt (in
5.1.2.2.1 steht auch "shall" und nicht "must"). Und bei einigen Compilern
ist dies tatsaechlich der Fall. Der Standard-Startup-Code von MaxonC++
verwirft z.B. den Rueckgabewert. Somit ist es bei diesem Compiler auch
sinnvoll main als void zu deklarieren (Was es dann ja auch ist).
Um Compilerwarnungen vorzubeugen (speziell bei GCC) sollte man jedoch
heutzutage immer int nutzen.
Ciao
--
____ _ _ ____ _ _ _ _ ____
| | | | | | \ / | | | the cool Gremlin from Bischofswerda
| __ | ____| | \/ | | | WWW: http://www.dstoecker.de/
| | | | | | | | PGP key available on www page.
|____| _|_ |____| _|_ _|_ |____| I hope AMIGA never stops making fun!
Gunther Nikl
>> > #include <stdio.h>
>> > #include <stdlib.h>
>> > #include <exec/types.h>
>>
>> Hier hast du '#include <string.h>' vergessen, du verwendest die Funktion
>> strcpy().
>
> Ist mir gar nicht aufgefallen, der Compiler bringt zumindest keine Warnungen/Errors,
> wie sonst immer!?!?
Versuchs mit -fno-builtin und -Wmissing-prototypes. Dann wird der Compiler
schon gesprächig.
Marius Schwarz
entschuldige , aber das Crossposten muß nun wirklich nicht sein.
On 11-Feb-02, you wrote:
> Naja, bei dem Beispiel ging es auch nur um den Lerneffekt. Ohne
> objektorientierte Programmierung ist aber die Implementation von verketteten
> Listen imho sehr umständlich und auch sehr fehleranfällig. Wie schon gesagt,
Ich bin mal gespannt wie eine Lösung der verketten Liste in OOP viel eleganter
aussehen kann... Bitte:
Regards
--
The real Cyborg - Amigasoft and more !
Marius Schwarz
On 11-Feb-02, you wrote:
>>> Listen mit allem SchnickSchnack zur Verfügung stellen.
>>
>> Den gibt es auch bei Java :-)
>
> Java ist auf Amigas aber nicht wirklich eine Option :)
nativ schon.
Steffen Nitz
"Jörg Strohmayer" <joe...@expires-2002-02-28.nexgo.de> schrieb im Newsbeitrag
news:18...@js.dhis.org...
Steffen Nitz <Steffe...@T-Online.de> schrieb:
>> ich habe jetzt den angehangenen Source anhand eurer Infos getippt.
>> Ist der ok so, oder könnten Probleme auftreten?
[Source]
Erst Remove(), danach free().
Danke, habe mich schon gewundert warum es mal funktioniert (scheinbar) und
mal nicht.
--
Gruß Steffen