Re: In-place list manipulation

On Nov 24, 4:47 am, CBFalconer <cbfalco...@xxxxxxxxx> wrote:
Aki Tuomi wrote:

When doing mergesort in place, I have ran into a following problem:

How to perform in-place interleave during merge without need of
auxilliarylistor array?

Try the following burst of code:

/*Listhandling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form alinkedlist*/
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/*Reversea singlylinked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ======================================================= */
/* splitlistp into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */

/* ================================================== */
/* Recursively sort alinkedlist. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)); /* compare */
#endif
/* end listops.h */

/*Listhandling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/*Reversea singlylinked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-emptylist*/
curr = root->next;
root->next = NULL; /* terminate newlist*/
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else emptylistis its ownreverse; */
return root;

} /* revlist */

/* ======================================================= */
/* splitlistp into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form newlistafter p2 */
p3->next = NULL; /* terminate 1st half */
return p2;

} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least onelistnow empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;

} /* mergelists */

/* ================================================== */
/* Recursively sort alinkedlist. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items inlist*/
p = splitlist(root); /* alterslistroot */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or emptylistis already sorted */

return root;

} /* mergesort */

/* end listops.c */

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account fromhttp://www.teranews.com

chekout
http://yepoocha.blogspot.com
.

Relevant Pages

  • Re: C Pointers
    ... Make a singly linked list and apply merge sort. ... nodeptr revlist; ... nodeptr mergesort(nodeptr root, ... mergesort(p, cmp), ...
    (comp.lang.c)
  • Re: Partially sorting a linked list
    ... typedef struct node { ... nodeptr revlist; ... /* Recursively sort a linked list. ... nodeptr mergesort(nodeptr root, ...
    (comp.programming)
  • Re: Iterative Merge Sort Using Circular Linked List
    ... lists need not be circular. ... typedef struct node { ... nodeptr revlist; ... nodeptr mergesort(nodeptr root, ...
    (comp.lang.c)
  • Re: reverse a link list
    ... typedef struct node { ... nodeptr revlist; ... /* Recursively sort a linked list. ... nodeptr mergesort(nodeptr root, ...
    (comp.lang.c)
  • Re: merge sort
    ... typedef struct node { ... nodeptr revlist; ... nodeptr mergesort(nodeptr root, ... mergesort(p, cmp), ...
    (comp.programming)