Thread: question about linklist

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    1

    Exclamation question about linklist

    The question I found it from the text as following:
    You are required to design, implement and test a function, sort_list(.), which will sort such a list according to the priority value computed by whatever function is passed as its second argument. The first argument is to be a pointer to the head of the list. Since the OS will have other structures with pointers to IORB's, the list must be sorted in place.

    typedef struct iorb {

    short base_pri;
    struct iorb *link;
    char filler[110];

    } IORB;
    void sort_list(IORB **list,int(*newpr)(short));
    int newp(short base)
    {
    return base;
    }
    question
    1) provide the coding for inserting a value
    2) insert into a list

    Thanks,
    Frank

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    I'm sorry, but I can't find your question anywhere in that post. All I see is an exercise (from a book?). But I'll humor you and offer some suggestions:

    >the list must be sorted in place.
    If you mean by not using any extra memory then it's hard not to sort a list in place. If you mean by performing exchanges within the same list then you're going about it in an inefficient way. You'll find sorting a list easier if you build a new list from the old one by removing from the old list and adding the removed item in sorted position to the new list.

    That would be how you perform insertion sort easily with linked lists, and mergesort. It's also possible (thought slightly more difficult and with annoying degenerate cases) to use binary search tree insertion and traversal routines to sort a linked list without using any extra memory:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
      int data;
      struct node *prev, *next;
    };
    
    static struct node *treeinsert ( struct node *tree, struct node *item )
    {
      if ( tree == NULL ) {
        tree = item;
      }
      else if ( item->data < tree->data ) {
        tree->prev = treeinsert ( tree->prev, item );
      }
      else {
        tree->next = treeinsert ( tree->next, item );
      }
    
      return tree;
    }
    
    static void traverse ( struct node *tree, struct node **list )
    {
      struct node *save;
    
      if ( tree == NULL ) {
        return;
      }
      traverse ( tree->next, list );
      save = tree->prev;
      tree->prev = NULL;
      tree->next = *list;
      if ( *list != NULL ) {
        (*list)->prev = tree;
      }
      *list = tree;
      traverse ( save, list );
    }
    
    struct node *treesort ( struct node *list )
    {
      struct node *tree = NULL;
      struct node *save;
    
      while ( list != NULL ) {
        save = list->next;
        list->prev = list->next = NULL;
        tree = treeinsert ( tree, list );
        list = save;
      }
      traverse ( tree, &list );
    
      return list;
    }
    
    int main ( void )
    {
      struct node *list = NULL;
      struct node *n;
      int i;
    
      for ( i = 0; i < 10; i++ ) {
        n = malloc ( sizeof *n );
        if ( n == NULL ) {
          break;
        }
        n->data = rand() % 10;
        n->prev = NULL;
        n->next = list;
        if ( list != NULL ) {
          list->prev = n;
        }
        list = n;
      }
      printf ( "Unsorted\n" );
      for ( n = list; n->next != NULL; n = n->next ) {
        printf ( "%d->", n->data );
      }
      printf ( "%d\n", n->data );
      for ( ; n != NULL; n = n->prev ) {
        printf ( "%d%s", n->data, n->prev == NULL ? "\n" : "->" );
      }
      list = treesort ( list );
      printf ( "Sorted\n" );
      for ( n = list; n->next != NULL; n = n->next ) {
        printf ( "%d->", n->data );
      }
      printf ( "%d\n", n->data );
      for ( ; n != NULL; n = n->prev ) {
        printf ( "%d%s", n->data, n->prev == NULL ? "\n" : "->" );
      }
    
      return 0;
    }
    There are a few advantages to this approach:

    1) You can easily sort a double linked list without jumping through hoops.
    2) The code is easily accessable to anyone familiar with simple binary search trees.
    3) For random data, it's every bit as efficient as sophisticated sorts (O(n log n))
    4) It's easy to write. What I posted was the first try, and it compiled/ran correctly the on the first compile.

    There is a big disadvantage too.

    1) If the list is already sorted, the performance of the tree slows the sort down considerably.

    I don't really recommend such a beast because mergesort is better, but this should get you started.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM