|
<![CDATA[
# include <stdio.h>
#define debug 0
#define MaximumKey 017777777777
#define MaxKey 4590
#define MinKey 1
#define NoKey (-1)
#define M 10
#define D 4
#define Error printf("An error has been detected\n")
typedef int typekey;
typedef struct rec {
typekey k;
struct rec *next;
} *list;
typekey LastRand;
list Last, r;
list sort();
typekey rand()
/*** simple minded random number generator ***/
/*** it uses Xn+1 = 11*Xn mod 4591 (11 is a prim root in 4591) ***/
{
extern typekey LastRand;
LastRand = 11*LastRand % 4591;
if ( LastRand<=0 ) LastRand = 1;
return(LastRand);
};
checkorder( t )
list t;
{
list i;
if ( debug ) {
i = t;
printf("checkorder ");
while ( i != NULL ) {
printf(", %d", i->k);
i = i->next;
};
printf("\n");
};
while ( t!=NULL ) {
if ( t->next != NULL )
if ( t->k > t->next->k ) printf("t out of order\n");
t = t->next;
}
};
int hash( t )
list t;
{
int sum;
sum = 0;
while ( t != NULL ) {
sum += t->k * (t->k+1);
t = t->next;
};
return( sum );
};
trysort()
{
int h;
h = hash( r );
r = sort( r, 1 );
if ( hash(r) != h )
printf("Bad hash value\n");
checkorder( r );
};
topins( val )
typekey val;
{
list i;
i = (list)malloc(sizeof(struct rec));
i->k = val;
i->next = r;
r = i;
};
main()
{
int i, is;
if (debug) printf("try with a null table \n");
r = NULL; trysort();
if (debug) printf("try with a one-element table \n");
topins(1); trysort();
if (debug) printf("try with a two-element table \n");
topins(2); trysort();
r = NULL; topins(2); topins(2); trysort();
r = NULL; topins(2); topins(1); trysort();
if (debug) printf("try with 10-element table \n");
r = NULL; for (i=1; i<=10; i++) topins(i); trysort();
r = NULL; for (i=1; i<=10; i++) topins(4321); trysort();
r = NULL; for (i=1; i<=10; i++) topins(101-i*i); trysort();
LastRand = 101;
for (is=1; is<=10; is++) {
r = NULL; for (i=1; i<=10; i++) topins(rand());
trysort();
}
exit( 0 );
}
charac(i,k)
int i,k;
{int b;
b = 100000;
for (; i>0; i--) b /= 10;
return( (k%b) / (b/10) );
};
list sort( s, j )
list s;
int j;
{
int i;
list head[M], t;
struct rec aux;
extern list Last;
if (s==NULL) return(s);
if ( s->next == NULL ) {Last = s; return(s);}
if ( j>D ) {
for (Last=s; Last->next!=NULL; Last = Last->next);
return( s );
}
for (i=0; i<M; i++) head[i] = NULL;
/* Place records in buckets */
while (s != NULL) {
i = charac( j, s->k );
t = s;
s = s->next;
t->next = head[i];
head[i] = t;
}
/* sort recursively */
t = &aux;
for (i=0; i<M; i++) if (head[i]!=NULL) {
t->next = sort( head[i], j+1 );
t = Last;
}
return(aux.next);
}
]]> |
![[Home]](../../images/home_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (423.perdido.c) 