• Diese Seite verwendet Cookies. Indem du diese Website weiterhin nutzt, erklärst du dich mit der Verwendung von Cookies einverstanden. Erfahre mehr

Listen in C

Themenstarter #1
Hallo,

zwei Köpfen sind bekanntlich ja immer besser als Einer, daher hoffe ich jemand hat Lust und Zeit sich das folgende Problem anzuschauen.

Hatte heute die Idee meine "Liste", welche ich immer wieder kopieren, mal an einer Stelle zentral zu hinterlegen. Jetzt hab ich aber scheinbar irgendwo den Wurm drin, da sich eine Endlos-Schleife (siehe Kommentar in list.c) ergibt und dann das ganze mit SEGFAULT abstürzt.

Würde mich über einen Hinweis freuen. :-)

Weiterhin einen schönen Sonntag! :-)

Leider kann ich die Files nicht hochladen, daher im folgenden als Code-Listing:

list.h
C:
#ifndef _LIST_H
#define _LIST_H 1

#define LST_LIFO 0
#define LST_FIFO 1

struct s_list
{
    void *element;
    struct s_list *next;
    struct s_list *prev;
    struct s_list *last;
};
typedef struct s_list TList;

void ldump(TList *lst);
void list_push(TList **lst, void *element, int lst_type);
void list_pop (TList **lst);

void lappend (TList **lst, void *element);
void lprepend (TList **lst, void *element);

void *lindex(TList *lst, unsigned int idx);
unsigned int llength(TList *lst);

TList *lrange(TList *lst, unsigned int elem_1st, unsigned int elem_lst);
TList *lsort(TList *lst);

TList *list(int argc, ...);

#endif
list.c
C:
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

#include "list.h"

void ldump(TList *lst)
{
    TList *pt = lst;

    int idx = 0;

    if (!pt)
    {
        fprintf(stderr, "%i => %lu\n", idx, (long unsigned int) pt);
        return;
    }

    for (; pt; pt = pt->next)
    {
        fprintf(stderr, "%i => %lu (p: %lu n: %lu l: %lu)\n",
                        idx,
                        (long unsigned int) pt,
                        (long unsigned int) pt->prev,
                        (long unsigned int) pt->next,
                        (long unsigned int) pt->last);
        idx++;
    }

    return;
}

void list_push(TList **lst, void *element, int lst_type)
{
    if (!element) return;

    TList *new = (TList *)calloc(1, sizeof(TList));

    new->element = element;

    switch ( lst_type )
    {
        case LST_LIFO:
        {
               if ( ! *lst )
            {
                *lst = new;
            }
            else
            {
                new->next = *lst;
                *lst = new;
            }
        }
        break;
        case LST_FIFO:
        {
              if ( ! *lst )
               {
                *lst = new;
            }
            else
            {
                new->prev = (*lst)->last;
                (*lst)->last->next = new;
            }

            (*lst)->last = new;
        }
        break;
    }

    return;
}

void list_pop(TList **lst)
{
    if ( ! *lst ) { return; }

    TList *erase = *lst;

    *lst = (*lst)->next;

    free ((void *)erase);

    return;
}

void lappend (TList **lst, void *element)
{
    list_push(lst, element, LST_FIFO);
    return;
}

void lprepend(TList **lst, void *element)
{
    list_push(lst, element, LST_LIFO);
    return;
}

void *lindex(TList *lst, unsigned int idx)
{
    TList *pt = lst;
    int cnt = 0;

    TList *prev = 0;
    while (pt)
    {
        if (cnt == idx) { break; }

        prev = pt;
        pt = pt->next;
        ++cnt;
    }

    void *ret_val = 0;
    if (pt) { ret_val = pt->element; }
    else if (prev) { ret_val = prev->element; }

    return ret_val;
}

unsigned int llength(TList *lst)
{
    unsigned int nelements = 0;

    if (! lst ) { return nelements; }

    for (TList *l = lst; l; l = l->next)
        ++nelements;

    return nelements;
};

TList *lrange(TList *lst, unsigned int elem_1st, unsigned int elem_lst)
{
    TList *l = lst;
    TList *new = 0;

    unsigned int cnt = 0;
    while ( l )
    {
        if ( cnt < elem_1st )
        {
            l = l->next;
            ++cnt;
            continue;
        }
        if ( cnt > elem_lst ) { break; }

        lappend(&new, l->element);
        l = l->next;
        ++cnt;
    }

    return new;
}

TList *my_merge(TList *left, TList *right)
{
    TList *new = 0;

    return new;
}

TList *my_mergesort(TList *lst)
{
    unsigned int nelements = 0;
    nelements = llength(lst);
   
    /* endless loop caused by memory corruption ? */
    if (nelements <= 1) { return lst; }

    unsigned int last = nelements / 2;
    unsigned int first = last + 1;

    TList *left = lrange(lst, 0, last);
    TList *right = lrange(lst, first, (nelements - 1));

    left = my_mergesort(left);
    right = my_mergesort(right);

    return 0;
}

TList *lsort(TList *lst)
{
    TList *tmp = lst;

    return my_mergesort(tmp);
}

TList *list(int argc, ...)
{
    TList *lst = 0;
    va_list va;

    va_start(va, argc);

    for ( int cnt = 0; cnt < argc; ++cnt)
    {
        void *p = va_arg(va, void*);
        lappend(&lst, p);
    }

    va_end(va);

    return lst;
}
main.c
C:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "list.h"

int main(int argc, char **argv)
{
    TList *lst = list(9, 100, 20, 30, 2, -10, 23, 12, 32, 1000);

    fprintf(stdout, "elements in list: %d\n", llength(lst));

    for (TList *l = lst; l; l = l->next)
    {
        fprintf(stdout, "%d\n", (int) l->element);
    }

    fprintf(stdout, "> lrange\n");
    TList *new = lrange(lst, 4, 7);

    TList *l = new;
    while(l)
    {
        fprintf(stdout, "%d\n", (int) l->element);
        l = l->next;
    }

    lsort(lst);

    return EXIT_SUCCESS;
}
 

turrican

Well-Known Member
#2
ich würd folgendes machen:
Code mit Option -g compilieren (für die Debug-Infos) und dann mit valgrind laufen lassen:
Code:
 valgrind <binary>
ggf gibt Valgrind schon einen ersten Hinweis auf das Problem - oder auch nicht.

Hernach dann noch in gdb laden und an der nelements Stelle die nelements und die anderen Zeiger/Variablen mal beobachten/prüfen - gib ein gutes grafisches Tool für gdb: ddd
 
Themenstarter #3
Hi turrican,

vielen Dank für Deine Mühe und Deinen Hinweis!

-g verwendet ich Defaultmäßig in Kombination mit gdb. Valgrind hat mich auf einen stack overflow hingewiesen und ich habe das Problem gefunden :-)

Hier die aktuelle my_mergesort:
C:
TList *my_mergesort(TList *lst)
{
    unsigned int nelements = 0;
    nelements = llength(lst);
    
    if (nelements <= 1) { return lst; }

    unsigned int last = nelements / 2;
    unsigned int first = last + 1;
    if (nelements == 2)
    {
        /* prevent endless recursion */
        last = 0;
        first = 1;
    }
 
    TList *left = lrange(lst, 0, last);
    TList *right = lrange(lst, first, (nelements - 1));

    left = my_mergesort(left);
    right = my_mergesort(right);

    return 0;
}
Das ganze ist nicht unbedingt schön, aber zu mindest weis ich jetzt schon mal wo der Wurm ist! :-)

Vielen Dank nochmal!
 
#4
Schön dass du den Fehler gefunden hat. Ich hatte auch recht skeptisch auf die Abbruchbedingung geschaut da ich kürzlich einen ähnlichen Fehler hatte, hatte aber noch keine Zeit mir das genauer anzuschauen.

Was ich mich frage ist warum du eine so komplizierte doppelt verlinkte Liste benutzt. Listen sind eigendlich recht einfache Datenstrukturen die recht effektiv sind wenn man sie nur in einer Richtung durchgeht. Für weitergende Ansprüche gibt es bessere Datenstrukturen, Bäume etc. Kommt aber auf den jeweiligen Anwendungsfall an.
 
Themenstarter #5
Ich habe häufig den Fall, dass ich in der Liste entweder Begin+N betrachte und/oder End-N betrachte. Desweiteren habe ich das Interesse, die Liste von beiden Enden für jedes Element bearbeiten zu können. Sortierung spielt auch häufig eine Rolle in diesem Bereich (Liste) und MergeSort hat bisher ganz gute Dienste geleistet.

Hier noch zur Vollständigkeit:
C:
TList *my_merge(TList *left, TList *right)
{
    TList *new = 0;

    while( left && right )
    {
        if ( (int) left->element <= (int) right->element )
        {
            lappend(&new, left->element);
            left = left->next;
        }
        else
        {
            lappend(&new, right->element);
            right = right->next;
        }
    }
    
    while( left )
    {
        lappend(&new, left->element);
        left = left->next;
    }

    while( right )
    {
        lappend(&new, right->element);
        right = right->next;
    }

    return new;
}

TList *my_mergesort(TList *lst)
{
    unsigned int nelements = 0;
    nelements = llength(lst);
    
    if (nelements < 2) { return lst; }

    unsigned int last = nelements / 2;
    unsigned int first = last + 1;
    if (nelements == 2)
    {
        /* prevent endless recursion */
        last = 0;
        first = 1;
    }
 
    TList *left = lrange(lst, 0, last);
    TList *right = lrange(lst, first, (nelements - 1));

    left = my_mergesort(left);
    right = my_mergesort(right);

    return my_merge(left, right);
}