Avatar billede phbecker Nybegynder
19. marts 2005 - 23:00 Der er 7 kommentarer

Split og sortering af singly linked list?

Hejsa!

Jeg prøver at sortere en singly linked list, og har hentet masser af fremragende hjælp i denne tråd: http://eksperten.dk/spm/417877 - problemet er bare, at jeg ikke helt kan få sorteringen til at fungere. Problemet er, at der sådan set slet ikke bliver ændret på rækkefølgen af elementerne i min linked list. Min tilpasning af algoritmen ser sådan her ud:

void sort(struct node *node)
{
    struct node *HeaderO = NULL, *HeaderR = NULL, *first, *parent=NULL;
    // HeaderO is the ordered list, HeaderR is the remaining elements of the old linked list
    int i = 0; // Index variable for use in the loop

    while (node) // As long as we're inside the original linked list
    {
        if (i == 0) // If we're at the start of the un-ordered list, we need to create our ordered list header
        {
            HeaderO = (struct node *) malloc(sizeof(struct node)); // Allocates memory
            HeaderO->name = node->name;
            HeaderO->grade = node->grade;
            HeaderO->next = NULL; // Only has one node so far!
        }
        else
        {
            HeaderR = (struct node *) malloc(sizeof(struct node));
            if (i == 1)
                first = HeaderR;
           
            HeaderR->name = node->name;
            HeaderR->grade = node->grade;
            HeaderR->next = NULL;
            if(parent)
                parent->next = HeaderR;
           
            parent = HeaderR;
        }
        node = node->next;
        i++;
    }
}

Og den bliver kaldt med sort(start), hvor start er pointeren til det første element i min linked list, som jeg på forhånd har fået oprettet uden problemer. Sidenhen kalder jeg min funktion til udskrivning:

void printgrades(struct node *node) // Prints the name and grade of each node element
{
    while(node)
    {
        printf("Name: %s, grade: %i\n", node->name, node->grade);
        node = node->next;
    }
}

Som bliver kaldt med printgrades(start). Når jeg gør dette, lader det ikke til, at der overhovedet er blevet gjort noget ved listens elementers rækkefølge... Hvad er det, jeg gør forkert og/eller overser? :-)

For god ordens skyld får I her min struct:

struct node
{
    char* name;
    int grade;
    struct node* next;
};
Avatar billede arne_v Ekspert
19. marts 2005 - 23:04 #1
Har vi ikke lige haft den med double linked liste ?
Avatar billede arne_v Ekspert
19. marts 2005 - 23:06 #2
Hvor jeg postede en double linked version af det single linked program jeg endte
med at lave til tchami den gang.
Avatar billede arne_v Ekspert
19. marts 2005 - 23:06 #3
#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;
}
Avatar billede phbecker Nybegynder
19. marts 2005 - 23:12 #4
Jo det er sandt nok :) Sidder og leger med linked lists og prøver at forstå dem så godt som muligt. Men den funktion du nævner her, splitter den listen op i to forskellige?
Avatar billede arne_v Ekspert
19. marts 2005 - 23:16 #5
Næh - den sorterer bare.

Hvorfor og hvordan vil du have delt op ?
Avatar billede phbecker Nybegynder
19. marts 2005 - 23:28 #6
Jeg prøver at lære mig selv lidt om flytning af elementer mellem linked lists, og tænkte derfor at det kunne være en god ide at prøve det med sådan en sortering, hvor man som udgangspunkt har en linked list indeholdende (tal)værdier, hvor man så tager dens første element og laver en separat linked list ud af det. Så gennemløber man resten af den anden liste og smider hvert element, algoritmen når til, ind i den nye liste på den rette relative plads... Kan bare ikke lige få skrevet det ned i kode, når nu det jeg postede øverst ikke virker... :(
Avatar billede arne_v Ekspert
19. marts 2005 - 23:33 #7
Man kan sagtens sortere på den måde.

lav ny tom liste
while noget i den game liste {
    find mindste node i den gamle liste
    fjern den node
    indsæt den node i den nye liste
}
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester