c - can you please tell me whats wrong with this -
need please need please code compiles fine when run gives seg fault , have no idea why. have gone on code many times still no clue problem is. need please.
void insertionsort(listnode ** listptr, listnodecomparefcn compare) { listnode * sorted = *listptr; listnode * swapper; listnode * prev; int swapped; while(sorted != null) { swapper = sorted -> next; prev = findprev(*listptr, swapper); swapped = 0; while(swapper != null && prev != null && swapper != *listptr && compare(swapper,prev)) { swapnodes(*listptr, prev, swapper); prev = findprev(*listptr, swapper); swapped = 1; } if (!swapped) sorted = sorted -> next; } } static listnode * findprev(listnode * head, listnode * ptr){ listnode * current = head; while (current -> next != null){ if ((current -> next) == ptr) return current; current = current -> next; } return null; } void swapnodes(listnode * head, listnode * l1, listnode * l2){ listnode * prev = findprev(head, l1); prev -> next = l2; l1 -> next = l2 -> next; l2 -> next = l1; }
i commented:
i've done enough work on sscce know major part of problem not being careful enough head of list. if swap head node , next node, need update head node pointer, otherwise lose front of list. i'm tolerably that's component of trouble [it in fact whole trouble]. given valid list,
findprev()function works fine. neitherswapnodes()norinsertionsort()can given clean bill of health (yet!), think. instance, iffindprev()returns null,swapnodes()happily dereferences null pointer; crash!
here sscce version of code, updated back-channel information fix swapnodes() identified in comment above. compare() function turns out c++ style comparator rather c style comparator; is, returns true if node 1 comes before node 2 , false otherwise (whereas c style comparator returns -1, 0, +1 — or, strictly, negative, zero, positive — less than, equal to, greater than). fix swapnodes() — interface , code change — , correct comparator semantics, list sorted correctly. hardly exhaustive test, start.
#include <assert.h> #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct listnode listnode; struct listnode { int datum; listnode *next; }; typedef int (*listnodecomparefcn)(const listnode *n1, const listnode *n2); //static void swapnodes(listnode *head, listnode *l1, listnode *l2); static void swapnodes(listnode **head, listnode *l1, listnode *l2); static listnode *findprev(listnode *head, listnode *ptr); static int node_compare(const listnode *n1, const listnode *n2) // sscce { assert(n1 != 0 && n2 != 0); printf("compare: %2d , %2d\n", n1->datum, n2->datum); if (n1->datum < n2->datum) return 1; // if (n1->datum < n2->datum) // return -1; // else if (n1->datum > n2->datum) // return +1; else return 0; } static void insertionsort(listnode **listptr, listnodecomparefcn compare) { listnode *sorted = *listptr; while (sorted != null) { listnode *swapper = sorted->next; listnode *prev = findprev(*listptr, swapper); int swapped = 0; while (swapper != null && prev != null && swapper != *listptr && compare(swapper, prev)) { //swapnodes(*listptr, prev, swapper); swapnodes(listptr, prev, swapper); prev = findprev(*listptr, swapper); swapped = 1; } if (!swapped) sorted = sorted->next; } } static listnode *findprev(listnode *head, listnode *ptr) { listnode *current = head; assert(current != 0); while (current->next != null) { if (current->next == ptr) return current; current = current->next; } return null; } // update via email void swapnodes(listnode **listptr, listnode *l1, listnode *l2) { listnode *prev = findprev(*listptr, l1); if (prev == null) { l1->next = l2->next; *listptr = l2; l2->next = l1; } else { prev->next = l2; l1->next = l2->next; l2->next = l1; } } /* static void swapnodes(listnode *head, listnode *l1, listnode *l2) { listnode *prev = findprev(head, l1); prev->next = l2; l1->next = l2->next; l2->next = l1; } */ static listnode *node_insert(listnode *head, int datum) // sscce { listnode *node = malloc(sizeof(*node)); node->datum = datum; node->next = head; return node; } static void print_list(const char *tag, const listnode *list) // sscce { printf("%-8s", tag); while (list != 0) { printf(" -> %2d", list->datum); list = list->next; } putchar('\n'); } int main(void) // sscce { static const int unsorted[] = { 29, 3, 14, 2, 91, 87, 13, 29, 1 }; enum { num_values = sizeof(unsorted) / sizeof(unsorted[0]) }; listnode *head = 0; print_list("empty:", head); (int = 0; < num_values; i++) { head = node_insert(head, unsorted[i]); print_list("added:", head); } (listnode *curr = head; curr != 0; curr = curr->next) { listnode *prev = findprev(head, curr); if (prev == 0) printf("%2d - no prior node\n", curr->datum); else printf("%2d - prior node %2d\n", curr->datum, prev->datum); } print_list("before:", head); insertionsort(&head, node_compare); print_list("after:", head); return 0; } output (including diagnostics) sscce:
empty: added: -> 29 added: -> 3 -> 29 added: -> 14 -> 3 -> 29 added: -> 2 -> 14 -> 3 -> 29 added: -> 91 -> 2 -> 14 -> 3 -> 29 added: -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 added: -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 added: -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 added: -> 1 -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 1 - no prior node 29 - prior node 1 13 - prior node 29 87 - prior node 13 91 - prior node 87 2 - prior node 91 14 - prior node 2 3 - prior node 14 29 - prior node 3 before: -> 1 -> 29 -> 13 -> 87 -> 91 -> 2 -> 14 -> 3 -> 29 compare: 29 , 1 compare: 13 , 29 compare: 13 , 1 compare: 87 , 29 compare: 91 , 87 compare: 2 , 91 compare: 2 , 87 compare: 2 , 29 compare: 2 , 13 compare: 2 , 1 compare: 14 , 91 compare: 14 , 87 compare: 14 , 29 compare: 14 , 13 compare: 3 , 91 compare: 3 , 87 compare: 3 , 29 compare: 3 , 14 compare: 3 , 13 compare: 3 , 2 compare: 29 , 91 compare: 29 , 87 compare: 29 , 29 after: -> 1 -> 2 -> 3 -> 13 -> 14 -> 29 -> 29 -> 87 -> 91
Comments
Post a Comment