Quicksort i -singly linked list-

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


/* function prototypes                                                    */
struct node * initnode( char *, int );
void printnode( struct node * );
void printlist( struct node * );
void insertnode( struct node * );
void numorderedlist( struct node * );
void printnode2( struct node *ptr , int i );
void printrevlist( struct node *ptr );
void avarage( struct node *ptr);
void shuffle( struct node *ptr);
int cntelmts( struct node *ptr);
void swap(struct node *a, struct node *b);
void qsort_recurse(struct node *a, struct node *b);
void sort(struct node *p);

/* definition of a data node for holding af student information            */
struct node
{
    char name[20];
    int  grade;
    struct node *next;
};

/* head points to first node in list, end points to last node in list      */
/* initialise both to NULL, meaning no nodes in list yet                  */
struct node *head = (struct node *) NULL;
struct node *end  = (struct node *) NULL;

/* this initialises a node, allocates memory for the node, and returns    */
/* a pointer to the new node. Must pass it the node details, name and grade*/
struct node * initnode( char *name, int grade )
{
  struct node *ptr;
  ptr = (struct node *) calloc( 1, sizeof(struct node ) );
  if( ptr == NULL )                      /* error allocating node?      */
      return (struct node *) NULL;        /* then return NULL, else      */
  else {                                  /* allocated node successfully */
      strcpy( ptr->name, name );          /* fill in name details        */
      ptr->grade = grade;                      /* copy grade details    */
      return ptr;                        /* return pointer to new node  */
  }
}

/* this prints the details of a node, eg, the name and grade              */
/* must pass it the address of the node you want to print out            */
void printnode( struct node *ptr )
{
    printf("Grade: %d\tName: %s\n",ptr->grade,ptr->name);
}

/* this prints all nodes from the current address passed to it. If you    */
/* pass it 'head', then it prints out the entire list, by cycling through */
/* each node and calling 'printnode' to print each node found            */
void printlist( struct node *ptr )
{
    while( ptr != NULL )          /* continue whilst there are nodes left */
    {
        printnode( ptr );          /* print out the current node          */
        ptr = ptr->next;          /* goto the next node in the list        */
    }
    printf("\npress a key to continue\n");
    getch();
}

/* this adds a node to the end of the list. You must allocate a node and  */
/* then pass its address to this function                                */
void add( struct node *new )  /* adding to end of list */
{
    if( head == NULL )
    {                                        /* if an empty list,        */
        head = new;                          /* set 'head' to it          */
        end = new;
        head->next = NULL;
    }
    else
    {
        new->next = head;            /* link next field to original list */
        head = new;                  /* head adjusted to new node        */
    }
}


/* show the nodes in num-ordered list */
void numorderedlist( struct node *ptr )
{
    int i;
    for(i=3 ; i<=13 ; i++)
    {
        while( ptr != NULL )         
        {
            printnode2( ptr , i);     
            ptr = ptr->next;         
        }
        ptr = head;
    }

    printf("\npress a key to continue\n");
    getch();
}

/* print if num == grade */
void printnode2( struct node *ptr , int i )
{
    if(i == ptr->grade)
    {
        printf("Grade: %d\tName: %s\n",ptr->grade,ptr->name);
    }
}

/* reverse order list printout */
void printrevlist( struct node *ptr)
{
    struct node *temp = ptr;
   
    while(temp->next != NULL)
    {
            temp = temp->next;
    }
    printnode(temp);
    while(temp != head)
    {
        while(ptr->next != temp)
        {
            ptr = ptr->next;
        }
        printnode(ptr);
        temp = ptr;
        ptr = head;
    }
    printf("\npress a key to continue\n");
    getch();
}

void avarage( struct node *ptr)
{
    float avg_grade = 0;
    float tal = 0;

    while( ptr != NULL )         
    {
        tal++;
        avg_grade = avg_grade + ptr->grade;
        ptr = ptr->next;
    }
    printf("Avarage is: %0.1f\n",avg_grade/tal);
   
    printf("\npress a key to continue\n");
    getch();
}

void histogram( struct node *ptr )
{
    int i;
    int tal=0;

    printf("\n");
    for(i=3 ; i<=13 ; i++)
    {
        if(i!=4 && i!=12)
        {
            while(ptr != NULL)
            {
                if(ptr->grade == i)
                    tal++;
                ptr = ptr->next;         
            }
            printf("Num of %d's \t= %d\n",i,tal);
            tal = 0;
            ptr = head;
        }
    }
    printf("\npress a key to continue\n");
    getch();
}

/* count the number of elements */
int cntelmts( struct node *ptr)
{
    int tal = 0;
    while(ptr != NULL)
    {
        tal++;
    }
    return tal;
}


void shuffle( struct node *ptr)
{
   
}

void swap(struct node *s1, struct node *s2) {
    struct node temp1,temp2;
    temp1 = *s1;
    temp1.next = s2->next;
    temp2 = *s2;
    temp2.next = s1->next;
    *s1 = temp2;
    *s2 = temp1;
    printf("%s\n",s1->name);
}

void qsort_recurse(struct node *a, struct node *b)
{
    struct node *i = a, *k = b;
    static struct node *current,*pivot_pos;       
   
    printf("SORTING\n");
   
    for(;;)
    {
        i = i->next;

        for(current=i ; current != k->next ; current=current->next)
            if(*a->name < *current->name)
            { i = current; break; }

        if( current == k->next )
        { pivot_pos=k; break; }

        swap( i , k );           
    }

    swap( pivot_pos , a );   
    if( pivot_pos->next != b && pivot_pos != b )
        qsort_recurse( pivot_pos->next , b );
}

void bubblesort(struct node *p)
{
    // bubble method
    struct node *p1, *p2;
    p1 = p;
    while(p1)
    {
        p2 = p1->next;
        while(p2)
        {
            if(strcmp((p2->name),(p1->name))>0)
            {
                swap(p1,p2);
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}


void qsort_array(struct node *ptr)
{
    while(ptr != NULL)
    {
       
    }
}

/*
    ## ##  ##  ### #  #
    # # # #  #  #  ## #
    #  # ####  #  # ##
    #  # #  # ### #  #
*/
main()
{
  char name[20];
  unsigned short grade, ch = 1;
  struct node *ptr;

  //clrscr();
  add(initnode("ABC",3));
  add(initnode("DEF",7));
  add(initnode("HIJ",11));
  add(initnode("CDE",6));
  add(initnode("GHI",8));
  add(initnode("JKL",13));
  add(initnode("IJK",12));
  add(initnode("BCD",5));
  add(initnode("EFG",9));
  add(initnode("FGH",10));
 
    while( ch != 0 )
    {
        printf("#############################################################\n");
        printf("# 1. Show grade list                                        #\n");
        printf("# 2. Show grade list in reverse order                      #\n");
        printf("# 3. Oder list in increase order of the grades              #\n");
        printf("# 4. Add new grade                                          #\n");
        printf("# 5. Show avarage of all grades                            #\n");
        printf("# 6. Show grade histogram                                  #\n");
        printf("# 7. Shuffle grade list                                    #\n");
        printf("# 8. Alphabetically order grade list using std. quicksort  #\n");
        printf("# 9. Alphabetically order grade list using my quicksort    #\n");
        printf("# 0. quit                                                  #\n");
        printf("#############################################################\n");
        scanf("%d", &ch );
        switch( ch )
        {
            case 1:  /* list all nodes */
                printlist( head );
                break;
            case 2:  /* reverse list */
                printrevlist( head );
                break;
            case 3:  /* numeric ordered list */
                numorderedlist( head );
                break;
            case 4:  /* add a name in list */
                printf("Enter in name: ");
                scanf("%s", name );
                printf("Enter in grade: ");
                scanf("%d", &grade );
                ptr = initnode( name, grade );
                add( ptr );
                break;
            case 5: /* show the avarage */
                avarage( head );
                break;
            case 6: /* show histogram of grades */
                histogram( head );
                break;
            case 7: /* shuffle gradelist */
                shuffle( head );
                break;
            case 8: /* standard quicksort */
                qsort_recurse( head , head );
                break;
            case 9: /* our quicksort */
                break;
        }
    }
}

bubble-sorten som ikke bruges - virker... men jeg SKAL bruge bubblesort !

haha... fuk... det jeg mente var at jeg SKAL bruge Quicksort !!

hehe... jeg er åbentbart ikke den eneste fra mit kursus der er inde på eksperten.dk, går i hvert fald ud fra at du går på samme kursus idet at der er præcis den samme opgave jeg sidder med :D

Nå men til det med quicksort, du kan ikke bruge quicksort direkte på linked list da man normalt bruger quicksort på arrays.
Men man kan gøre er at lave et array (som er lige så langt som der er elementer i listen) og så kopiere pointerne (som er dine 'next' pointer i data strukturen) over i arrayet. Nu kan du oxo tilgå din data via. arrayet f.eks. mitArray[3]->grade
Nu kan du uden problemer sortere dit array med quicksort.
Når du saa har sortet dit array genskaber du din liste ud fra dit array.
Men lige for at dele det op så:
1) lav en listToArray() funktion
2) lav en quicksort() funktion
3) lav en arrayToList() funktion

Hvis du skal have lidt info om quicksort så er denne side god http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html

>Nå men til det med quicksort, du kan ikke bruge quicksort direkte på linked list da >man normalt bruger quicksort på arrays.

okay... skal jeg bare kalde qsort(head,0,max) eller ?

>Men man kan gøre er at lave et array (som er lige så langt som der er elementer i >listen) og så kopiere pointerne (som er dine 'next' pointer i data strukturen) over >i arrayet. Nu kan du oxo tilgå din data via. arrayet f.eks. mitArray[3]->grade
>Nu kan du uden problemer sortere dit array med quicksort.

har problemer med at få lavet det array :-(

1) lav en listToArray() funktion
2) lav en quicksort() funktion ---  burde være den jeg allerede har lavet...??
3) lav en arrayToList() funktion

qsort() tager 4 argumenter
qsort(
      (void*)a, // arrayet som skal sorteres
      antal,    // antal 'elementer' i dit array
      sizeof(a[0]), // størrelsen på de elementer i arrayet
      myCompare); // compare funktion som du selv skal lave
}
compare funktionen er der ingen ben, den skal bare returner en int som er negativ hvis a < b, 0 hvis a == b og positiv hvis a > b
Ovenstående er for qsort som findes i stdlib.h

Hvis du selv har lavet en quicksort algoritme kender du nok bedst selv de inputs den skal have ;-)

Men uanset hvilken quicksort du bruger skal du have lavet dig de to funktioner som konvertere mellem listen og arrayet.
Det er i virkeligheden ikke så vanskeligt. Når du skal lave dit array løber du i præncippet bare din liste igennem, du skal så bare lige huske at kopiere dine 'next' pointers over i arrayet mens du løber din liste igennem.
En god til for forståelsen er at tage et stykke papir og blyant, og så lige tegne det man gerne vil have den til at gøre. Det var i hvert fald det der var 'gennembrudet' for mig.
Men hvis det stadig driller kan jeg godt poste koden (hvis du vil have det), men det er jo altid sjovest hvis man selv kan løse det ;-)
Håber det hjalp lidt, ellers så bare spørg igen.

Faktisk goer listToArray og ArrayToList funktionerne det en hel del lettere for mange af de andre opgaver vi skal løse.
Jeg bruger dem f.eks i alle 3 sorterings opgaver og shuffle. Som du sikkert oxo ved så er det meget lettere at arbejde med arrays (i hvert fald for vores opgaver) end med lister. Derfor bliver det hele jo meget lettere hvis vi middlertidig kan representere listen i et array og så 'genskabe' listen efter arrayet.

tjae... jeg har grublet over det i mange dage snart....

void arrayToList(nod** a, nod** heada){
    int amount, i;
    nod* head = *heada;
    *heada = a[0];
    amount = count(head);
    for(i=0; i<amount; i++){
        if(i<(amount-1)){
            a[i]->next =a[i+1];
        }else{
            a[i]->next = NULL;
        }
    }

}

nod** listToArray(nod* head){
    int i;
    int amount = count(head);
    nod** linkedArray = (nod**)malloc(amount * sizeof(nod*));
    for(i=0; i<amount; i++){
        linkedArray[i] = head;
        head = head->next;
    }
    return linkedArray;
}
int myCompare(const void* a, const void* b){
    nod* a1 = *(nod**)a; nod* b1 = *(nod**)b;
    return a1->grade - b1->grade;
}
int count(nod* head){
    if(head->next==NULL){
        return 1;
    }else{
        return 1 + count(head->next);
    }
}

int main(){
  //head er pointer til din liste
  int antal = count(head);
  nod** a = listToArray(head);
  qsort((void*)a, antal, sizeof(a[0]), myCompare);
  arrayToList(a, &head);
  free(a);
}

jdd