Hægtede lister

Kig evt. her:
http://en.wikipedia.org/wiki/Linked_list

Okay, det prøver jeg :)

Princippet med en linked list er at hvert element i listen peger på det næste af samme type.

(mit eksempel er i java.. men det vel det samme princip:))

class Link {
    Link naeste;
    Data nogetData;
}

og så et andet sted

    Link forsteLed = null;          // her gemmer vi efterhånden hele listen

    public void tilfojLed(Link nytLed) {
        nytLed.naeste = null;
        if ( forsteLed == null ) {
            forsteLed = nytLed;
            return;
        }
        Link sidsteFundet = forsteLed;
        while ( sidsteFundet.naeste != null ) {
            sidsteFundet = sidsteFundet.naeste;
        }
        sidsteFundet.naeste = nytLed;
    }


Håber ikke jeg forvirrede :o)

Jeg har C++'ificeret kalps kode (med den ændring at der er en pointer til sidste element i listen):

#include <iostream>

using namespace std;

struct Node
{
    struct Node *next;
    char data;
};

struct List
{
    struct Node *head;
    struct Node *tail;
};

// create a new list
// O(1)
List* newList()
{
    List *list = new List;
    list->head = NULL;
    list->tail = NULL;
    return list;
}

// delete the list and collect the garbage from memory
// O(n), n is |listen|
List* delList(List *list)
{
    Node *iter = list->head;
    Node *temp;
    while(iter) //delete all nodes
    {
    temp = iter;
    iter = iter->next;
    delete temp;
    } 
    delete list;
    return NULL;
}

// add an element to the list
// O(1)
void addNode(List *list, char data)
{
    Node *elem = new Node;
    elem->next = NULL;
    elem->data = data;
    if(list->head == NULL)
    {
    list->head = elem;
    list->tail = elem;
    }
    else
    {
    list->tail->next = elem;
    list->tail = elem;
    }
}

// prints the elements of the list
// O(n), n is |listen|
void printList(List *list)
{
    Node *iter = list->head;
    while(iter)
    {
    cout << iter->data;
    iter = iter->next;
    }
}

int main()
{
    List *list = newList();
    addNode(list, 'a');
    addNode(list, 'b');
    addNode(list, 'e');
    addNode(list, 'k');
    addNode(list, 'a');
    addNode(list, 't');
    addNode(list, '\n');
    printList(list);
    list = delList(list);

    return 0;
}

Det er kun et eksempel, hvis du skal bruge det kan du jo omskrive som det passer dig og dit problem. Det ville nok ikke være så tosset at lave en klasse der indkapsler listen.. :-)

Puha, det ser avanceret ud :D

Men jeg takker for inputs, i kan lige smide et par svar, hvis i vil, så deler jeg lidt point ud :)

Nej tak jeg bidrog kun med et supplement til soreno's kommentar:)
Det forvirrede sikkert mere end det gavnede hehe:)

En Node er en struktur bestående af 2 variable.
En pointer til næste Node i listen og
en char som er det data som er associeret med noden.
Sidste Node i listen peger på NULL

En List består af 2 variable.
En pointer til første element i listen og
en pointer til sidste element i listen.

En ny liste (newList) initialiserer listen (head og tail peger på NULL)

Der er 2 tilfælde ved indsættelse af en node (addNode)
Hvis listen er tom, så skal head og tail pege på den node som initialiseres
Ellers opdateres tail til at pege på den node som initialiseres

Endnu et eksempel som ligner:

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

struct node
{
  char *name;
  int val;
  struct node *next;
};

void add(struct node **first, char *name, int val)
{
    struct node *extra,*last;
    extra = (struct node *)malloc(sizeof(struct node));
    extra->name = name;
    extra->val = val;
    extra->next = NULL;
    if(*first==NULL)
    {
        *first = extra;
    }
    else
    {
        last = *first;
        while(last->next!=NULL) last=last->next;
        last->next = extra;
    }
}

void print(struct node *first)
{
    struct node *curr;
    printf("----------------\n");
    curr = first;
    while(curr!=NULL)
    {
        printf("%s %d\n",curr->name,curr->val);
        curr = curr->next;
    }
    printf("----------------\n");
}

void sort(struct node **first)
{
    struct node *p1,*p2,*pp1,*pp2,*temp;
    p1 = *first;
    pp1 = NULL;
    while(p1!=NULL)
    {
        pp2 = p1;
        p2 = p1->next;
        while(p2!=NULL)
        {
            if(p2->val < p1->val)
            {
                /* swap pointers */
                temp = p2;
                p2 = p1;
                p1 = temp;
                /* update next pointers */
                if(p2->next!=p1)
                {
                    temp = p2->next;
                    p2->next = p1->next;
                    p1->next = temp;
                    pp2->next = p2;
                }
                else
                {
                    p2->next = p1->next;
                    p1->next = p2;
                }
                if(pp1==NULL)
                {
                    *first = p1;
                }
                else
                {
                    pp1->next = p1;
                }
            }
            pp2 = p2;
            p2 = p2->next;
        }
        pp1 = p1;
        p1 = p1->next;
    }
}

int main()
{
  struct node *first = NULL;
  add(&first, "a", 111);
  add(&first, "bb", 22);
  add(&first, "ccc", 3);
  printf("usorteret:\n");
  print(first);
  sort(&first);
  printf("sorteret:\n");
  print(first);
  add(&first, "d", 4);
  add(&first, "e", 5);
  printf("usorteret:\n");
  print(first);
  sort(&first);
  printf("sorteret:\n");
  print(first);
  return 0;
}

Arne:
Hvad er pointen(!) med "en pointer til en pointer".. ?

Pointen er første gang add kaldes returnerer jeg en pointer.

Tak for det arne.

Smider du et svar også?

Jeg synes du skal give soreno alle pointene - mit eksmepel viser grundliggende kun
det samme som hans

Jamen det gør jeg da så :)

Lige et lille tillægsspørgsmål, hvis i skulle ha lyst (ellers kan jeg godt oprette et nyt spørgsmål, hvis det er?)

Jeg har oprettet følgende struct:

struct medlemmer {
    char navn[20];
    char gade[20];
    char postnummer[8];
    char by[20];
    char tlf[20];
    char mobil[20];
    char email[20];
    int medlemsnr;
    struct medlemmer *ptrnext;
    };

Og jeg kan da også fint skrive til den osv, men problemet kommer når jeg skriver det ned til en fil. Hvis navnet ikke er 20 chars præcist, kommer der en masse underlige tegn ned i filen :/ Vi fik at vide, at det var fordi vi brugte arrays, og at vi skulle bruge hægtede lister istedet, men det giver da nøjagtigt det samme problem?