List insertion sort Problem

[wuzzo87]

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".

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;
}

[SKeane]

A quick safety check ...

                     t->next = malloc(sizeof(*t));
                     t = t->next;
                     t->next = NULL;

Ask yourself the question "What if the malloc fails?"

[quzah]

       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.

             for(x = b; x->next != NULL; x = x->next)

Likewise with b here.

                   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.

                   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.

[ZuK]

Some more logic errors

       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