Verkettete Liste für ASURO

[Wsk8]

Ich hab jetzt ehrlich gesagt keine Lust mich durch die ganzen Fehler zu wuseln, deshalb kriegste meine funktionierende Lösung. Kompiliert fehlerfrei und in meinem Test gabs auch keine Mem Leaks. Kann aber trotzdem Fehler enthalten.

Gespeichert wird hier der Pointer auf einen String.

#ifndef LIST_H
#define LIST_H




typedef struct Node {
  char *dirpath;
  struct Node *pNext;
} TNode;


void Prepend(TNode **pList, char const *path);
void Append(TNode **pList, char const *path);
void Delete(TNode **pList, char const *path);
void DeleteAll(TNode *pPath);




#endif

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


#include "list.h"




/* Make new node */
static TNode *MakeNode(char const *path) {
    TNode *const pNewNode = malloc(sizeof(*pNewNode));


    if(pNewNode == 0) {
        fprintf(stderr, "MakeNode(): No memory!\n");
    }


    if(1 > strlen(path)) {
        fprintf(stderr, "MakeNode(): Warning! Empty directory is inserted!");
    }


    pNewNode->dirpath = malloc(strlen(path)+1);
    strcpy(pNewNode->dirpath, path);
    pNewNode->pNext = 0;


    return pNewNode;
}


//add node at start
void Prepend(TNode **pList, char const *path) {
    TNode *pNewNode = MakeNode(path);


        pNewNode->pNext = *pList;
        *pList = pNewNode;
}


//add node at end
void Append(TNode **pList, char const *path) {
    TNode *pNewNode = MakeNode(path);
    TNode *pNode = *pList;
    TNode *pPrev = *pList;


    if(*pList == 0) {            //empty list
        *pList = pNewNode;
    }else{
        while(pNode != 0) {
            pPrev = pNode;
            pNode = pNode->pNext;
        }
        pPrev->pNext = pNewNode;    //catenation with the last new node
    }
}


void Delete(TNode **pList, char const *path) {
    TNode *pPrev = *pList;
    TNode *pNode = *pList;


    while(pNode != 0) {
        if(strcmp(pNode->dirpath, path) == 0) {
                pPrev->pNext = pNode->pNext;
                free(pNode->dirpath);
                free(pNode); pNode = 0;
                break;
        }
        pPrev = pNode;
        pNode = pNode->pNext;
    }
}


void DeleteAll(TNode *pPath) {
    TNode *pNode = 0;            //Pointer


    while(pPath != 0) {            //stop if end of list reached
        pNode = pPath;
        pPath = pNode->pNext;        //next node
        free(pNode->dirpath);
        free(pNode); pNode = 0;        //delete pointer and set to 0
    }
}

mfg

[Valen]

Auch ich habe keine Lust das ganzen durch zu gehen. Aber hier solltest du es ein wenig mit reduzieren können.

test.c:36: error: 'wort' undeclared (first use in this function)
test.c:36: error: (Each undeclared identifier is reported only once
test.c:36: error: for each function it appears in.)

...
do { SerRead(wort[16] ,15,0);
} while( getchar()!='\n');
...

Die String "wort" besteht nicht in dem void Funktion "neuerKnoten". Es ist zwar als Teil von den Struktur "knoten" definiert. Aber das ist kein Speicherplatz.

struct knoten {
    char wort[16];
    struct knoten *next;
};

test.c: In function 'loescheKnoten':
test.c:45: error: invalid initializer
test.c:45: error: expected ',' or ';' before 'else'
test.c:50: error: expected '}' before 'else'
test.c:44: warning: unused variable 'tmp'

void loescheKnoten(char txt[]){
KnotenPtr_t hilfZeiger1;
KnotenPtr_t hilfZeiger2;
if(anfang != NULL){
char tmp[] = anfang->wort //Hmm, gehört hier nicht ein ; und } wenn dannach ein else if-Zweich anfangt?
else if( strcmp(txt[], tmp[]) == 0 ){ // [] ist nicht notwendig wenn du den gesamten Strings bedeutest. Hier oben aber schon.
...

[Spacy Bar]

Tschuldige ich habe meine erste Fehlermeldung geposted. Ein paar Fehler hatte ich schon behoben.
Jedoch Vielen Dank für die schnellen Antworten und die Codes.

LG
Spacy Bar

[Sisor]

Ich dachte mir, dass kann der Robby auch nur Zahlen sind witzlos, es müssen schon char-Arrays/Strings sein. Das ganze endete in einem Zeigergewirr mit Strukturgewirr verknüpft. Ich hoffe ihr habt eine Lösung für mein Problem, ich habe 'ne ganze menge Zeit rein investiert.
...
So, jetzt seit ihr dran

Du schaffst dir ein 'komplexes' Problem, weil eine einfache Lösung witzlos ist?!
Dann bekommst du es nicht gelöst, es endet in einem Gewirr! Jetzt soll das Forum ran?

Der war gut...

[markusj]

Davon abgesehen: malloc zu verwenden ist auf so kleinen Plattformen wie dem AVR in der Regel keine gute Idee. Zum sind malloc und free "teuer" und zum anderen kannst du es früher oder später mit Speicherfragmentierung zu tun bekommen. In der Regel reicht eine statische Speicherreservierung aus, ist dabei einfacher und im Zweifelsfall auch zuverlässiger.

mfG
Markus

[Spacy Bar]

Du schaffst dir ein 'komplexes' Problem, weil eine einfache Lösung witzlos ist?!
Dann bekommst du es nicht gelöst, es endet in einem Gewirr! Jetzt soll das Forum ran?

Der war gut...

Tut mir leid, das ist von dir falsch verstanden worden. Deswegen habe ich den Zwinker-Smiley dahinter gesetzt, damit es als Witz verstanden wird, das gilt in meinem Umfeld als absolute Entschuldigung.


- - - Aktualisiert - - -

Davon abgesehen: malloc zu verwenden ist auf so kleinen Plattformen wie dem AVR in der Regel keine gute Idee. Zum sind malloc und free "teuer" und zum anderen kannst du es früher oder später mit Speicherfragmentierung zu tun bekommen. In der Regel reicht eine statische Speicherreservierung aus, ist dabei einfacher und im Zweifelsfall auch zuverlässiger.[...]

Das kann ich zum einen nachvollziehen, da der µC nur 1 kb RAM hat, zum anderen Funktionierte das Programm als Zahlenspeicher für den PC ebenfalls nur im Bereich unter einem KB (solange man keinen Zahlenwald darein gepflanzt hat).

LG
Spacy Bar

[markusj]

Das kann ich zum einen nachvollziehen, da der µC nur 1 kb RAM hat, zum anderen Funktionierte das Programm als Zahlenspeicher für den PC ebenfalls nur im Bereich unter einem KB (solange man keinen Zahlenwald darein gepflanzt hat).

Das Problem der Speicherfragmentierung hat erst einmal nichts mit dem verfügbaren Speicher zu tun. Speicherfragmentierung entsteht, wenn im Adressraum einzelne Bereiche belegt sind und andere dazwischen frei. Wenn von den 1kB rechnerisch 50% frei sind kann es so trotzdem passieren, dass selbst ein malloc für 100 Bytes fehlschlagen kann, wenn kein zusammenhängender freier Speicherbereich >=100 Byte vorhanden ist. Ein solcher Flickenteppich im RAM entsteht dann, wenn du unterschiedlich große Speicherblöcke anforderst und der allozierte Speicher dann sehr unterschiedliche "Lebensdauern" hat.
Ein Beispiel (Je Zeichen 64 Byte, + entspricht belegtem Speicher, _ entspricht freiem Speicher) bei dem nur noch Speicheranforderungen bis zu zwei Einheiten (128 Byte) möglich sind - Und wenn man das ganze auf Byte-Ebene betrachtet kann die Fragmentierung noch viel schlimmer werden:
_+++__+__+_++_+_

mfG
Markus

[Spacy Bar]

Das Problem der Speicherfragmentierung hat erst einmal nichts mit dem verfügbaren Speicher zu tun. Speicherfragmentierung entsteht, wenn im Adressraum einzelne Bereiche belegt sind und andere dazwischen frei. Wenn von den 1kB rechnerisch 50% frei sind kann es so trotzdem passieren, dass selbst ein malloc für 100 Bytes fehlschlagen kann, wenn kein zusammenhängender freier Speicherbereich >=100 Byte vorhanden ist. Ein solcher Flickenteppich im RAM entsteht dann, wenn du unterschiedlich große Speicherblöcke anforderst und der allozierte Speicher dann sehr unterschiedliche "Lebensdauern" hat.
Ein Beispiel (Je Zeichen 64 Byte, + entspricht belegtem Speicher, _ entspricht freiem Speicher) bei dem nur noch Speicheranforderungen bis zu zwei Einheiten (128 Byte) möglich sind - Und wenn man das ganze auf Byte-Ebene betrachtet kann die Fragmentierung noch viel schlimmer werden:
_+++__+__+_++_+_

Erstmal Danke für die Erklärung, von den Grundsätzen der Heap-Fragmentierung hatte ich zwar im C-Grundkurs von Jürgen Wolf schon gelesen, aber offensichtlich nicht richtig verstanden. Da stand etwas von Heap-Defragmentierung per Funktionsimplimentierung, allerdings kein Beispiel. Wenn du davon was verstehst, würde ich mich sehr über eine Erklärung freuen.
Außerdem wurde die alternative Funktion alloca() erwähnt, mit der Speicher vom Stack angefordert wird. Wird sie genauso verwendet und macht sie in meinem Fall Sinn?
Ich freue mich über jegliche erklärenden Antworten.

LG
Spacy Bar