乱数プログラム 使用例４

/*		test4.c		*/
#include <stdio.h>
#include <stdlib.h>
#include "random.h"

int dbldel_c(unsigned char *a[], int n, int flag);
void qsort_c(unsigned char *a[], int n);
void inssort_c(unsigned char *a[], int n);
int strcomp(unsigned char *a, unsigned char *b);

main()
{
	int *a, *ip;
	unsigned char *c, *cp;
	double *d, *dp;
	unsigned char **s, **sp, **sw, **swp;
	int i, n = 100, nn;

	init_mkdata(init_ornd0, ornd0, 1L);

	a = mkdata_i(n, 1, 99);
	printf("a = mkdata_i(n, 1, 99);\n");
	for(i = 0, ip = a; i < n; i++)	printf("%d ", *ip++);
	putchar('\n');

	c = mkdata_c(n, 'a', 'z');
	printf("\nc = mkdata_c(n, 'a', 'z');\n");
	for(cp = c; *cp; )	printf("%c", *cp++);
	putchar('\n');

	d = mkdata_d(n, -99., 99.);
	printf("\nd = mkdata_d(m, -99., 99.);\n");
	for(i = 0, dp = d; i < n; i++)	printf("%f ", *dp++);
	putchar('\n');

	s = mkdata_s(n, 1, 3, 'A', 'Z');
	printf("\ns = mkdata_s(n, 1, 3, 'A', 'Z');\n");
	for(i = 0, sp = s; i < n; i++)	printf("%3s ", *sp++);
	putchar('\n');
	sw = (unsigned char **)malloc(n * sizeof(unsigned char *));
	for(i = 0, swp = sw, sp = s; i < n; i++)	*swp++ = *sp++;
	qsort_c(sw, n);
	nn = dbldel_c(sw, n, 0);
	printf("重複数 = %d\n\n", n - nn);

	s = mkdata_sd(n, 1, 3, 'A', 'Z');
	printf("s = mkdata_sd(n, 1, 3, 'A', 'Z');\n");
	for(i = 0, sp = s; i < n; i++)	printf("%3s ", *sp++);
	putchar('\n');
	for(i = 0, swp = sw, sp = s; i < n; i++)	*swp++ = *sp++;
	qsort_c(sw, n);
	nn = dbldel_c(sw, n, 0);
	printf("重複数 = %d\n", n - nn);

	return 1;
}

int dbldel_c(unsigned char *a[], int n, int flag)
{
	int i, nn;
	unsigned char **dp, **wp;

	nn = 1;
	wp = dp = a + 1;
	for(i = 1; i < n; i++, dp++)	if(strcmp(*(dp - 1), *dp))	nn++;
	if(nn != n && flag)
	{
		wp = a;
		dp = a + 1;
		i = n - nn;
		while(i > 0)
		{
			if(strcmp(*wp, *dp) == 0)
			{
				**dp = '\0';
				i--;
			}
			else	wp = dp;
			dp++;
		}
	}
	return nn;
}

void qsort_c(unsigned char *a[], int n)
{
	unsigned char **i, **j, **l, **r;
	unsigned char **st1[32], **st2[32], ***s1, ***s2;
	unsigned char *x, *w;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_c()\n");
		return;
	}

	s1 = st1;
	s2 = st2;
	*s1 = a;
	*s2 = a + n - 1;
	do
	{
		l = *s1--;
		r = *s2--;
		if(r - l < 11)	inssort_c(l, r - l + 1);
		else
		{
			do
			{
				i = l;
				j = r;
				x = *(l + (int)((r - l) / 2));
				do
				{
					while(strcomp(x, *i) > 0)	i++;
					while(strcomp(*j, x) > 0)	j--;
					if(i > j)	break;
					w = *i;
					*i++ = *j;
					*j-- = w;
				} while(i <= j);
				if(j - l < r - i)
				{
					if(i < r)
					{
						*(++s1) = i;
						*(++s2) = r;
					}
					r = j;
				}
				else
				{
					if(l < j)
					{
						*(++s1) = l;
						*(++s2) = j;
					}
					l = i;
				}
			} while(l < r);
		}
	}while (s1 >= st1);
	return;
}

void inssort_c(unsigned char *a[], int n)
{
	unsigned char *x;
	int i, j;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_c()\n");
		return;
	}
	for(i = 1; i < n; i++)
	{
		x = a[i];
		j = i - 1;
		while(j >= 0 && strcomp(a[j], x) > 0)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = x;
	}
}

int strcomp(unsigned char *a, unsigned char *b)
{
	unsigned char *p, *q;

	p = a;
	q = b;
	while(*p)
	{
		if(*p > *q)	return 1;
		if(*p++ < *q++)	return -1;
	}
	if(*q)	return -1;
	return 0;
}