开发者

Insertion sort debug help

开发者 https://www.devze.com 2023-01-22 17:14 出处:网络
The following C code doesn\'t work (it just clears the list): /* Takes linkedlist of strings */ static int insertSort (linkedlist *list) {

The following C code doesn't work (it just clears the list):

/* Takes linkedlist of strings */
static int insertSort (linkedlist *list) {
  linkedlist sorted;
  void *data;
  node *one, *two, *newnode;
  开发者_运维知识库unsigned int comp, x;

  removeHeadLL (list, &data);
  initLL (&sorted);
  addHeadLL (&sorted, data);

  while (list->count) {
    removeHeadLL (list, &data);
    two = sorted.head;

    x = 0;
    for (comp = strcomp (data, two->data) ; comp > 1 && x < sorted.count ; x++) {
      one = two;
      two = two->next;
    }

    if (x) {
      newnode = malloc (sizeof(node));
      newnode->next = two;
      newnode->data = data;
      one->next = newnode;
    }
    else {
      addHeadLL(&sorted, data);
    }

    (sorted.count)++;
  }

  destroythis (list);
  list = &sorted;
  return 0;
}

Full context: http://buu700.res.cmu.edu/CMU/15123/6/


If your intent is really to modify the input pointer list to point to the memory allocated inside this function, then you need to declare the function as

static int insertSort (linkedlist **list)

and then return the newly-built list from sorted like so:

*list = &sorted;

As it stands, the call to destroylist frees up what is in list on entry, but the assignment only modifies a local copy of the input pointer.

In other words, in your original code this line:

list = &sorted;

has exactly zero effect outside the function, but this line:

  destroythis (list);

does indeed free up the memory that was owned by list on entry. So after return, your input pointer now accesses an empty list.


Danger, Will Robinson: untested code.

struct list { char *datum; struct list *next; };
typedef struct list *listptr;

listptr insert(char *x, listptr xs) {  

  listptr result = xs;
  listptr *from = &result;
  listptr new = (listptr) malloc(sizeof(struct list));

  while (xs != null && strcmp(xs.datum, x) < 0) {
    from = &xs;
    xs = xs->next;
  }

  new.datum = x;
  new.next = xs;
  *from = new;

  return result;
}

listptr isort(listptr xs) {
  listptr result = null;
  for(; xs != null; xs = xs->next) {
    insert(xs.datum, result);
  }
  return result;
}
0

精彩评论

暂无评论...
验证码 换一张
取 消