List insertion sort Problem

This is a discussion on List insertion sort Problem within the C Programming forums, part of the General Programming Boards category; Hi, I have a problem with my list insertion sort function... - wrote it with some help from a book. ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    51

    List insertion sort Problem

    Hi,
    I have a problem with my list insertion sort function... - wrote it with some help from a book.
    The output seems to always be a 'SEG FAULT' and if i'm not wrong, i traced the problem to the sorting part ( 'for' loops).

    My test string was "GAAGAA".

    Code:
    typedef struct node node_t;
    
    struct node {
            int start;
            int end; /*indices of substring*/
            int freq;
            node_t *next;
    };
    
    
    node_t *makelist(TNode *tree, char *s){
           char *substring(char *,int, int);
           node_t heada, headb;
           int i, j;
           node_t *t, *u, *x, *a = &heada, *b;
            
           
           for(i=0, t=a; i<strlen(s); i++) {
     	    	for(j=i; j<strlen(s); j++){
                         t->next = malloc(sizeof(*t));
                         t = t->next;
                         t->next = NULL;
                         t->start = i;
                         t->end   = j;
                         t->freq  = 0;
                }
           }
    
          /*Problem lies hence forth*/
           
           b = &headb;
           b->next = NULL;
           
          
           for(t = a->next; t!=NULL; t=u){
                 u = t->next;
                 for(x = b; x->next != NULL; x = x->next)
                       if(substrcmp(s, x->next->start, x->next->end, t->start, t->end) == 1)    
                                   break;
                       t->next = x->next;
                       x->next = t;
           }
                          
          return b;
    }
    
    void printlist(node_t *ptr) {
         
         while(ptr != NULL) {
                    printf("%d %d %d\n", ptr->start, ptr->end, ptr->freq);
                    printf("\n");
                    ptr=ptr->next;
         }
    }
    
    int substrcmp(char *s, int s1, int e1, int s2, int e2) {
        char c = s[s1];
        char d = s[s2];
        int x = s1 - e1;
        int y = s2 - e2;
        
        if(c>d || x>y) return 1;
        else
        return 0;
    }

  2. #2
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    A quick safety check ...

    Code:
                         t->next = malloc(sizeof(*t));
                         t = t->next;
                         t->next = NULL;
    Ask yourself the question "What if the malloc fails?"

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
           for(t = a->next; t!=NULL; t=u){
    If a is null, your program will crash on the first assignment in your for loop here.

    Code:
                 for(x = b; x->next != NULL; x = x->next)
    Likewise with b here.
    Code:
                       if(substrcmp(s, x->next->start, x->next->end, t->start, t->end) == 1)
    Try something simple like replacing, or inserting before, this with a line to print the contents of the current node.

    Code:
                       t->next = x->next;
                       x->next = t;
    You can probably crash your program here too, coupling it with your assignment in the loop here.

    T = something.
    X = something.
    T->next = X->next ... fine if X isn't null.
    X->next = T; ... making a loop here for any particular reason?

    Follow the logic of the assignment. Add a printf statement or two to see what's really going on.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Some more logic errors
    Code:
           b = &headb;             // b pointing to a local variable
           b->next = NULL;
           
           for(t = a->next; t!=NULL; t=u){
                 u = t->next;
                 for(x = b; x->next != NULL; x = x->next)  // x->next is NULL for shure
                       if(substrcmp(s, x->next->start, x->next->end, t->start, t->end) == 1)    
                                   break;
                       t->next = x->next;
                       x->next = t;
           }
                          
          return b;  // will be lost after return
    Kurt

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with linked list and shared memory
    By Sirfabius in forum C Programming
    Replies: 10
    Last Post: 11-10-2008, 04:45 PM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 07:16 PM
  3. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 12:30 PM
  4. Help with Insertion sort on a single linked list
    By goron350 in forum C++ Programming
    Replies: 4
    Last Post: 07-11-2005, 09:38 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21