C: Einfach verkettete Liste mit Arrays realisieren

[WarSlash]

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!

/*=======================================*/
/* 20.04.2009 - WarSlash*/
/* AuD, Blatt 1, Aufg.2, v0.0.0 laeuft nix */
/* Einfach verkette 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

[pest]

ichn habe mir deine aufgabenblätter nicht angesehen,
aber eine dynamische kette über 2 arrays zu implementieren bedeutet
das in dem einen die knoten-werte stehen und in dem anderen (bei zweien) die next-pointer, und das machst du ja.
das ist auch dynamisch, in dem sinne.

[Pinoccio]

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...Wenn du irgendwann dir selber mal eine Datenstruktur überlegen mußt, die einem sehr speziellen Zewck erfüllen sol, wirst du froh sein, das an so einem leichten Beispiel geübt zu haben.
(Abgesehen davon, pests Lösung ist einfach und schnell implementiert.)

mfg

[WarSlash]

Wenn du irgendwann dir selber mal eine Datenstruktur überlegen mußt, die einem sehr speziellen Zewck erfüllen sol, wirst du froh sein, das an so einem leichten Beispiel geübt zu haben.
(Abgesehen davon, pests Lösung ist einfach und schnell implementiert.)

mfg

Ich weiß das ja auch, ich brauch nen Denkanstoss. Ich komme einfach nicht drauf! Der Code ist micht Sicherheit falsch.

[Trap]

*pL = list;

Ist falsch. Ob der Rest stimmt hab ich nicht nachgeprüft.

[pest]

du setzt die next-pointer beim einfügen ja garnicht

z.b.

neuer_kopf = neues_element
next[neues_element] = alter_kopf

[rotalever]

Wie würde man das eigentlich ohne zwei Arrays machen?

[Gast]

Wie würde man das eigentlich ohne zwei Arrays machen?

Mit reinen Pointern, was viel einfacher ist! In PHP und C++ bzw jeder Sprache mit OOP gehts nocht einfacher zu implementieren!

[pest]

Mit reinen Pointern, was viel einfacher ist!

aber nicht unbedingt schneller

[rotalever]

aber nicht unbedingt schneller
Ja das waren meine Bedenken. Wenn man sich für jedes neue Element erst mal Speicher holen muss wird es recht langsam.

[pest]

Ja das waren meine Bedenken. Wenn man sich für jedes neue Element erst mal Speicher holen muss wird es recht langsam.

das kann man (von hand) umgehen indem man den speicher in pools anfordert
nen schlauer mm sollte das selber machen, und dann nimmt sich das nichtmehr viel
mit nen paar tricks ist die array-variante trotzdem schneller da löschen
und einfüge-operationen sehr billig sind

[rotalever]

das kann man (von hand) umgehen indem man den speicher in pools anfordert
nen schlauer mm sollte das selber machen, und dann nimmt sich das nichtmehr viel
mit nen paar tricks ist die array-variante trotzdem schneller da löschen
und einfüge-operationen sehr billig sind
Wie füllt man eigentlich schnell die Lücken in so einem Array? Ich meine wenn ich neue Elemente immer hinten anfüge ist das ja schnell, aber wenn ich jetzt ein Element lösche ist irgendwo in der Mitte des Arrays eine Lücke. Ich könnte mir vorstellen, dass man das letzte gelöschte Element zunächst nur als "gelöscht" markiert und dann beim Einfügen eines neuen Elements noch weiß wo die Lücke ist, aber was ist, wenn man sehr viele Elemente der Liste löscht?

[pest]

Wie füllt man eigentlich schnell die Lücken in so einem Array? Ich meine wenn ich neue Elemente immer hinten anfüge ist das ja schnell, aber wenn ich jetzt ein Element lösche ist irgendwo in der Mitte des Arrays eine Lücke. Ich könnte mir vorstellen, dass man das letzte gelöschte Element zunächst nur als "gelöscht" markiert und dann beim Einfügen eines neuen Elements noch weiß wo die Lücke ist, aber was ist, wenn man sehr viele Elemente der Liste löscht?

das kommt immer auf den Kontext an in dem man programmiert
eine verkette Liste als Array bietet sich z.b. (geschwindigeitsmäßig) dort an, wo die Listen-Elemente eindeutig unterscheidbar sind und einen begrenzten Werte-bereich besitzen, z.b. beim Hashing

dann entstehen keine Lücken, weil der Wert des Elementes der Index ist ;)

Löschen des Elementes s geht dann so

next[prev[s]] = next[s]

[RMC]

Ja das waren meine Bedenken. Wenn man sich für jedes neue Element erst mal Speicher holen muss wird es recht langsam.

Dafür ist es flexibel


Ich versteh ebenfalls nicht ganz, warum ihr in der Aufgabe 2 eine statische, einfach verkettete Liste implementieren müsst, wenn ihr zuvor in Aufgabe 1 sowieso schon eine dynamische, doppelt verkettete Liste habts. Irgendwie unnütz, eine Liste mit Arrays fixer Länge umzusetzen (die praktische Relevanz geht gegen 0), wenn das Beispiel zuvor eh schon die Sinnhaftigkeit einer verketteten Liste deutlich gemacht hat. Aber gut...ich kann deine Kritik nachvollziehen.

[pest]

die praktische Relevanz geht gegen 0

Unsinn

[rotalever]

eine verkette Liste als Array bietet sich z.b. (geschwindigeitsmäßig) dort an, wo die Listen-Elemente eindeutig unterscheidbar sind und einen begrenzten Werte-bereich besitzen, z.b. beim Hashing
dann entstehen keine Lücken, weil der Wert des Elementes der Index ist ;)

Ja das macht Sinn. Da muss man dann nur noch einen Anwendungsbereich finden ;)

[pest]

Da muss man dann nur noch einen Anwendungsbereich finden ;)

Rabin-Karp Suchalgorithmus
Zip-Verfahren

fallen mir da spontan ein

[Der_Donnervogel]

Ich versteh ebenfalls nicht ganz, warum ihr in der Aufgabe 2 eine statische, einfach verkettete Liste implementieren müsst, wenn ihr zuvor in Aufgabe 1 sowieso schon eine dynamische, doppelt verkettete Liste habts. Irgendwie unnütz, eine Liste mit Arrays fixer Länge umzusetzen (die praktische Relevanz geht gegen 0), wenn das Beispiel zuvor eh schon die Sinnhaftigkeit einer verketteten Liste deutlich gemacht hat. Aber gut...ich kann deine Kritik nachvollziehen.Eine Liste selbst zu implementieren ist so gut wie nie praxisrelevant. Eine so grundlegende Datenstruktur wie eine Liste wird einem normalerweise immer durch die Sprache, bzw. deren Bibliothek zur Verfügung gestellt. Vom Lernaspekt her könnte ich mir aber durchaus vorstellen, dass die zweite Version mit der Liste im Array Sinn macht. Es gibt ja durchaus Algorithmen/Datenstrukturen wo sowohl Listen, als auch Arraydarstellung Sinn machen können. Ein Beispiel das mir gerade spontan einfällt wären bei Graphen Adjazenzliste bzw. Adjazenzmatrix. In solchen Fällen ist es dann wichtig die jeweilige Datenstruktur verstanden zu haben und ihre Vor- und Nachteile zu kennen. Sich mit solchen Sachen im Studium etwas zu spielen, um das Verständnis zu vertiefen kann IMO nicht schaden, auch wenn der direkt sichtbare Praxisnutzen gering ist.

[Gast]

Es geht beim Studium NUR darum, dass man sich mit den Grundlagen beschäftigt und diese versteht. Die Praxis kommt dann ganz von alleine, aber dafür ist das Zeit den Studiums meistens zu kurz. Wenn man die Grundlagen verstanden hat, dann kann man mit etwas Übung sich Programmierkenntnisse gut aneignen und kann hochwertige Software schreiben. Ohne Grundlagen nur mit Probieren wird man ein bisschen Access Klickerei machen können und wird Programme schreiben, an denen andere später noch lange Zeit verzweifeln werden.

[Gast (KilBil)]

Dafür ist es flexibel


Ich versteh ebenfalls nicht ganz, warum ihr in der Aufgabe 2 eine statische, einfach verkettete Liste implementieren müsst, wenn ihr zuvor in Aufgabe 1 sowieso schon eine dynamische, doppelt verkettete Liste habts. Irgendwie unnütz, eine Liste mit Arrays fixer Länge umzusetzen (die praktische Relevanz geht gegen 0), wenn das Beispiel zuvor eh schon die Sinnhaftigkeit einer verketteten Liste deutlich gemacht hat. Aber gut...ich kann deine Kritik nachvollziehen.


Hi Forum,

Das Thema ist zwar schon alt, aber ohne ein Beispiel für eine praxisnahe Benutzung von statischen verketteten Listen zu nennen, konnte ich nicht tun.

Die beste praktische Anwendung solchen Listen kann man in der Automotive Industrie finden, wenn man nach strengen Vorgaben der AUTOSAR Richtlinien implementiert!

In diesem Fall hat man keine bestehenden library's zu Listen handling's zu Verfügung. Malloc und free von Speicherplätzen ist strengstens untersagt. Hier ist dann die statische verkettete Liste sogar fast die einzige Variante...