C Einfach verkettete Liste mit Arrays realisieren

WarSlash · 21. April 2009

Ich soll eine einfach verkettete Liste mit zwei Arrays implementieren.
Nur ich kriegs einfach nicht auf die Reihe.
Ich sitze hier schon Stunden dran und komm einfach kaum weiter!

Ich finde das sowieso witzlos..., dann hat man ne statische Liste...
Man lernt in der Uni halt viel Unsinn und macht nie was Produktives...

Hier mal meine Versuch. Ich habe es selber nicht testen können, weil ich nicht weiter kommen. Kompelieren tut es sich, aber wenn ich den Code theoretisch nachvollziehe läuft das hinten und vorne nicht!

Code:

/*=======================================*/
/* 20.04.2009 - WarSlash*/
/* AuD, Blatt 1, Aufg.2, v1.0 laeuft     */
/* Einfach verkettete Liste                */
/* Tutor:                                */
/*=======================================*/

#include <stdlib.h>
#include <stdio.h>
#include "boolean.h"

enum {N_MAX = 10}; 		/* maximale Laenge der Liste */
typedef int L_datentyp; 	/* Typ der Eintraege */
typedef struct Liste{
  int anf; 			/* Anfang der Liste */
  int z; 			/* Nummer des aktuellen Elementes */
  int z_vorg; 			/* Nummer des Vorgaengers */
  L_datentyp daten[N_MAX]; 	/* Speicherung der Listeneintraege */

  int nachf[N_MAX]; 		/* Verweis auf Speicherplatz des */
				/* nachfolgenden Listenelementes */
  int anzahl;			/* momentane Anzahl der belegten Elemente*/
} Liste;

void l_create(Liste *list){
 (*list).anzahl = 0; 
 (*list).anf = 0;
 (*list).z = 0;
 (*list).z_vorg = 0;
} 

void l_insert(L_datentyp e, Liste *list){

  if ((*list).anzahl > N_MAX) {
   printf("Fehler: Die Liste hat keine freien Plaetze mehr!\n");   
  } 
  else {
     if ( (*list).anzahl == 0 ) {
       /* Fuege Inhalt e in die leere Liste an Position 0 des Arrays ein*/
       (*list).daten[(*list).anzahl] = e;
       /* aktuelles Element soll zugleich Listeende sein  */
       (*list).nachf[(*list).anzahl] = -1;
       (*list).z_vorg = (*list).nachf[(*list).anzahl];
       (*list).z = (*list).z_vorg;
       (*list).anf =  0;
       (*list).anzahl++;  
     } 
     else { 
       (*list).daten[(*list).anzahl] = e;
       
     }
  }
}

int main(void){

 Liste list;
 Liste *pL;
 L_datentyp a=31;
 
 *pL = list;
 
 l_create(pL);
 l_insert(a,pL);

 return 0;
}

Hier mal das Aufgabenblatt dazu: A1, A3, A4 sind leicht und fertig, aber die A2....

http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss09/info2/Ueb/blatt1_ss09.pdf

Dese · 21. April 2009

das ganze ist ganz und gar nicht witzlos. richtig implementiert ist das in sehr vielen situationen nutzbar und dabei deutlich flotter als eine listenimplementierung über pointer.

aber nun zu deiner aufgabe:
ich habs mir kurz angeschaut und bin mir nicht sicher, wie man es mit der dort vorgegeben strukter lösen soll. aber mir scheint, dass es nur ein vorschlag ist. ich selbst würde es anders machen:

1. ein listenelement ist eine struktur der form
struct element {
int next;
datentyp data;
};

jetzt gibt es ein array

struct element e_list[n_max];

und ein array

int free[n_max];

und die variablen
int first; //erstes element, bzw -1 wenn keines vorhanden.
int count; //anzahl der elemente in der liste

das kannn man natürlich in eine struktur zusammenfassen.

das array free wird auf free[0]=0, free[1]=1 .... initialisiert,
count auf 0 und first auf -1;

einfügen:

füge daten in e_list[ free[count] ] ein
wenn es das erste element ist, dann first auf free[count] setzen
count ++;

wenn du ein element entfernst, egal welches, z.b. das element e_list[x],
dann passt du erst mal die vorgänger variablen an, damit die liste das elemnt quasi überspringt und dann
"löscht" du es:
count--;
free[count] = x;

alles klar?

edit: genau so geht auch ne zweifachverkettete liste. das wäre auch deutlich flotter als ne pointer liste. nachteil natürlich sit, dass man immer den speicher für das datenarray schon allokiert hat, auch wenn es fast leer ist.

edit2: einfügen geht genauso wie bei normalen listen über das anpassen der vorgänger zeiger etc. nur den freien platz findest du über's free array.

edit3: wenn doch nur mehr menschen begreifen würden, dass zu wissen wie etwas genau funzt erheblich dazu beiträgt software effizienter zu programmieren. aber uni-stoff is ja so sinnlos... sorry, musste sein

[Moepi]1 · 21. April 2009

WarSlash schrieb:
Ich finde das sowieso witzlos..., dann hat man ne statische Liste...
Man lernt in der Uni halt viel Unsinn und macht nie was Produktives...

Und jetzt überleg Dir, ob Du im richtigen Studiengang bist. Nur weil Du nicht gleich den Sinn dahinter siehst, kann es sehr wohl sinnvoll sein. In sehr vielen Fällen werden Bäume (Listen möglicherweise aus demselben Grund) als Array implementiert. Und zwar nicht, um Studenten zu ärgern, sondern weil es fürn Computer effizienter ist.
Ein Array ist ein zusammenhängender Speicherbereich, der auf einmal geladen und im Cache gehalten werden kann. Das Iterieren durch eine via Pointer verknüpfte Liste bedeutet für den Computer Zugriffe auf mehr oder minder zufällige Speicheradressen. Nur weil RAM Random Access Memory heißt, bedeutet das nicht, dass jeder Zugriff gleich teuer ist. Höhr dazu mal Vorlesungen aus dem Bereich der Technischen Informatik und Du begreifst sehr schnell, warum zusammenhängende Speicherbereiche ne verflucht feine Sache sind.

Und hör auf über Theorie zu schimpfen! Viele Leute haben vor nem Jahrhundert Dinge erdacht, von denen sie keine Ahnung hatten, dass sie heute zur Simulation hochdimensionaler Probleme eingesetzt werden.

Dese · 22. April 2009

WarSlash? gibt's news? hat's geholfen oder sonst irgendeine regung?

WarSlash · 22. April 2009

Ich weiß auch, wie Arrays im Speicher organisiert sind. Der Rechner kann schneller zur nächsten Adresse rechnen, weil die Adressen hintereinander liegen...
Pointer verweisen nur auf zufällig gewählte Adressen.

Sorry, ich war nur sehr erbost darüber, weil mir die Implementation nicht direkt eingefallen ist und ich vorher ne dynamnische Liste geschrieben. Außerdem, so ist das leider, sind teilweise, so war es in der Vergangenheit, Aufgabenstellungen fehlerhaft gewesen.

Mir war nicht direkt klar, wo ich so eine bestimmte Liste direkt verwenden würde. Weil ich da eigentlich direkt eine Array nehmen könnte.

Je nach Anwendungsgebiet macht das eine oder das andere eben Sinn.

Dese · 22. April 2009

kein stress.

listen als array brauchst du dann, wenn du die vorzüge einer liste benötigst (wahlloses einfügen und löschen und direkten zugrif auf elemente über pointer, etc. ) aber die architekturbedingten performancevorzüge eines arrays genießen willst.

jeh nach dem, was du an funktionalität nicht brauchst kann man das sogar noch viel effizienter machen. manchmal kombiniert man verschiedene datenstrukturen miteinander, um mehrere vorteile jeh nach operation nutzen zu können.

was cih nur sagen will, auch wenn dir so manches oft nicht klar wird, wo da der sinn sein soll, da steckt meist weit mehr dahinter als man auf dem ersten blick vermutet.

WarSlash · 22. April 2009

Wie das schon mal so ist: Man sieht den Wald vor lauter Bäume nicht mehr. Im Script war das Beispiel mit Pointern. Mit Arrays ist das ja eh das selbe nur in ne andere Farbe

.

Der Logische Zusammenhang ist ja der selbe. Sorry, dass ich gemotzt habe. Aber wenn man in Rage ist, vergisst man schnell den Rest und den Sinn.

[Moepi]1 · 22. April 2009

Sorry, falls das falsch rübergekommen ist. Ich verfluche auch das ein oder andere Mal die Uni, meine Programme oder nen Professor. (Letzteres recht oft

)
Aber unterm Strich ergibt doch das Meiste Sinn, wenn auch nicht immer auf den ersten Blick.

Dese · 22. April 2009

ich kenn das mit der rage

ja, im grunde übernimmst du bloss die speicherverwaltung. natürlich eine vereinfachte innerhalb eines festen bereichs, dem array eben.

wenn's zudem auch dein interesse dafür ein bisschen geweckt hat noch besser

ansonsten helf ich gern bei so fragen. komm so selten zu praktischeren dingen in letzter zeit

WarSlash · 22. April 2009

Das Dingen läuft nun klasse. Kannste ja gerne verifizieren, ob es den Vorgaben entspricht. Ich meine, dass es passen sollte.

-2 ist freier Speicher, -1 ist Listenende
Output:

Code:

./aufg2
Liste erzeugen
anf = -1
Nr   : | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
Daten: |00|00|00|00|00|00|00|00|00|00|
Nachf: |-2|-2|-2|-2|-2|-2|-2|-2|-2|-2|

Zahlen von 21 bis 31 einfuegen
Fehler: Die Liste hat keine freien Plaetze mehr! @ Daten = 31
anf = 0
Nr   : | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
Daten: |21|22|23|24|25|26|27|28|29|30|
Nachf: | 1| 2| 3| 4| 5| 6| 7| 8| 9|-1|

Erstes Element loeschen
Bei nachf steht -2 fuer freien Speicher!
anf = 1
Nr   : | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
Daten: |00|22|23|24|25|26|27|28|29|30|
Nachf: |-2| 2| 3| 4| 5| 6| 7| 8| 9|-1|

Viertes Element loeschen
Bei nachf steht -2 fuer freien Speicher!
anf = 1
Nr   : | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
Daten: |00|22|23|24|00|26|27|28|29|30|
Nachf: |-2| 2| 3| 5|-2| 6| 7| 8| 9|-1|

43 an Stelle 6 einfuegen
anf = 1
Nr   : | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
Daten: |43|22|23|24|00|26|27|28|29|30|
Nachf: | 7| 2| 3| 5|-2| 6| 0| 8| 9|-1|

9 am Ende der Liste
anf = 1
Nr   : | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|
Daten: |43|22|23|24|09|26|27|28|29|30|
Nachf: | 7| 2| 3| 5|-1| 6| 0| 8| 9| 4|

Quellcode dazu:

Code:

/*=======================================*/
/* 20.04.2009 - (C) 2009 WarSlash */
/* AuD, Blatt 1, Aufg.2, v1.0 laeuft     */
/* Einfach verkettete Liste                */
/* Tutor:                                */
/*=======================================*/

#include <stdlib.h>
#include <stdio.h>
#include "boolean.h"

enum {N_MAX = 10}; 		/* maximale Laenge der Liste */
typedef int L_datentyp; 	/* Typ der Eintraege */
typedef struct Liste{
  int anf; 			/* Anfang der Liste */
  int z; 			/* Nummer des aktuellen Elementes */
  int z_vorg; 			/* Nummer des Vorgaengers */
  L_datentyp daten[N_MAX]; 	/* Speicherung der Listeneintraege */

  int nachf[N_MAX]; 		/* Verweis auf Speicherplatz des */
				/* nachfolgenden Listenelementes */
  int anzahl;			/* momentane Anzahl der belegten Elemente*/
} Liste;

void l_create(Liste *list){
 int i;
 list->anzahl = 0; 
 list->anf = -1;
 list->z = -1;
 list->z_vorg = -1;
 /* -2 := freier Speicher*/
 for (i= 0; i <= N_MAX-1; i++) list->nachf[i] = -2;
 for (i= 0; i <= N_MAX-1; i++) list->daten[i] = 0;
} 

Boolean l_out_of_list(Liste list) {
  return (list.z == -1);
}

int getFirstFreeSpaceNo(Liste *list) {
  int i = 0;
  
 if (!(list->anzahl > N_MAX-1)) {
  while ( list->nachf[i] != -2) {
   i++;
  }
  return i;
 }
 /* -3 := Array ist voll*/
 return -3;
}

void l_insert(L_datentyp e, Liste *list){
  int free_no = 0;

  free_no = getFirstFreeSpaceNo(list);

  /*printf("anzahl = %d\n",list->anzahl);*/

  if ( (list->anzahl > N_MAX-1) || (free_no == -3 ) ) {
   printf("Fehler: Die Liste hat keine freien Plaetze mehr! @ Daten = %d\n",e);   
  } 
  else {
	
        list->daten[free_no] = e; 
        list->nachf[free_no] = list->z;
        if (list->z == list->anf) { /* Vor der Liste einfuegen*/
	  list->anf = free_no;
        } 
        else {
         list->nachf[list->z_vorg] = free_no;
        }
	list->z_vorg = free_no;
        list->anzahl++;
     }
  }

void l_delete(Liste *list, L_datentyp *e) {
  int weg = list->z;
  
  if ( l_out_of_list ( *list))
    printf("Fehler: Aktuelles Element ist ausserhalb der Liste!\n");
  else {
    *e = list->daten[weg];     
    if (list->z_vorg == -1)
     list->anf = list->nachf[weg];
    else 
      list->nachf[list->z_vorg] = list->nachf[weg];

    list->z = list->nachf[weg];
    list->nachf[weg] = -2;
    list->daten[weg] = 0;
    
  list->anzahl--;
  }

}

void l_reset(Liste *list){

  list->z = list->anf;
  list->z_vorg = -1;
}

void l_advance(Liste *list){
  if ( list->z == -1 )
   printf("Fehler: Bereits am Listenende\n");
 else {
  list->z_vorg = list->z;
  list->z = list->nachf[list->z];
 }
}

void liste_ausgeben(Liste list){
 int i;
 /* Anfang ausgeben*/ 
 printf("anf = %d\n",list.anf);
 
/* Nummer ausgeben*/
 printf("Nr   : ");
 for (i=0; i<= N_MAX-1;i++) printf("|%2d",i); 
 printf("|\n");

 /* Daten ausgeben*/
 printf("Daten: ");
 for (i=0; i<= N_MAX-1;i++) printf("|%.2d",list.daten[i]); 
 printf("|\n");

 /* Daten ausgeben*/
 printf("Nachf: ");
 for (i=0; i<= N_MAX-1;i++) printf("|%2d",list.nachf[i]); 
 printf("|\n");

 printf("\n");
}


int main(void){

 Liste list; 
 L_datentyp a = 21; 
 L_datentyp b = 0;
 int i;
 
 /* Liste erzeugen */
 printf("Liste erzeugen\n");
 l_create(&list);
 liste_ausgeben(list); 

 /* Zahlen von 21 bis 31 einfuegen*/
 printf("Zahlen von 21 bis 31 einfuegen\n");
 for (i = 0; i<= 10; i++){
  l_insert(a+i,&list);
 } 
 liste_ausgeben(list); 

 printf("Erstes Element loeschen\n");
 printf("Bei nachf steht -2 fuer freien Speicher!\n");
 l_reset(&list); 
 l_delete(&list,&b);  
 liste_ausgeben(list); 

 printf("Viertes Element loeschen\n");
 printf("Bei nachf steht -2 fuer freien Speicher!\n");
 l_advance(&list); 
 l_advance(&list); 
 l_advance(&list); 
 l_delete(&list,&b);  
 liste_ausgeben(list); 

 printf("43 an Stelle 6 einfuegen\n");  
 l_advance(&list); 
 l_advance(&list);
 a = 43;
 l_insert(a,&list);
 liste_ausgeben(list); 
 
 printf("9 am Ende der Liste\n");  
 a = 9;
 while ( !l_out_of_list(list)) {
  l_advance(&list);   
 }
 l_insert(a,&list);
 liste_ausgeben(list); 
 return 0;
}

Dese · 23. April 2009

warum unterscheidest du freien speicher vom listen ende? wenn du die liste durchgehst findest du das ende sobald der nachfahrenzeiger auf ein freies feld zeigt - fertig. so ist das üblich bei listen.für den anfang hast du einen extra zeiger, der auf den anfang immer zeigt und angepasst wird, falls der anfang geändert wird.

ansonsten hab ich nicht weiter gecshaut ob's richtig ist, ich glaubs dir einfach mal

edit: du brauchst eigentlich gar nichts ins array schreiben, wenn der platz frei ist, auch keine -1 oder -2 oder sonst was. du hast ja ein 2tes array, das als stack dient und darüber buch führt.

WarSlash · 23. April 2009

Das zweite Array fungiert irgendwie nicht als ein Stack sondern, vielmehr als eine Art "Pointer". Wir haben hier also einen reinen Verweis auf die nachfolgende Speicherstelle.

Wenn ich die Liste aufbaue, den Speicher komplett erschöpfe, und dann an Stelle x ein Element entferne, habe ich an x eine Lücke im Daten- und Nachf-Array, sprich freien Speicher. Ich habe nach dieser Operation also n-1 Speicher frei. Woher weiß dann die Insert-Funktion, wo es nun einen neuen Wert einfügen darf, wenn ich den freien Speicher nicht vorher markiert habe? Ich kann ja nicht willkürlich irgendein Feld im Array überschreiben. Und ich habe keine Garantie, dass nach dem Listenende freier überschreibbarer Speicher im Array liegt.

Dafür habe ich getFirstFreeSpaceNo(Liste *list) geschaffen. Diese löst das Problem!

Vielleicht verstehe ich deinen Einwand auch falsch. Aber das war eben meine Überlegung.

Dese · 23. April 2009

also, wenn du ein element entfernst, dann legst du den index also die position dieses elements auf den stack (das zeite array).
wenn du jetzt ein neues element einfügst holst du dir vom stack eine freie position (also von oben des stacks den ersten wert).

fertig.

im datenarray brauchst du keine markierungen für freie stellen.

Suche

C Einfach verkettete Liste mit Arrays realisieren

WarSlash

Cadet 1st Year

Dese

Commodore

[Moepi]1

Lt. Commander

Dese

Commodore

WarSlash

Cadet 1st Year

Dese

Commodore

WarSlash

Cadet 1st Year

[Moepi]1

Lt. Commander

Dese

Commodore

WarSlash

Cadet 1st Year

Dese

Commodore

WarSlash

Cadet 1st Year

Dese

Commodore

Ähnliche Themen