C - Writing quick sort procedure with optional argument

忘是亡心i 2022-11-14 13:26 198阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

/*
     * Writing quick sort procedure with optional argument:
     *   -r : Sorting in reverse (decreasing) order
     *   -n : Sort the input lines numerically
     *   -f : Fold upper and lower case together
     *   -d : Make comparisons only on letters, numbers and blanks
     *
     * QuickSortWithArgument.c - by FreeMan
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    int getline(char *, int);
    char *alloc(int);
    int readlines(char **, int);
    void writelines(char **, int);
    void quicksort(void **, int, int, int (*)(void *, void *));
    int numcmp(char *, char *);
    int mystrcmp(char *, char *);
    
    #define MAXLINES 10000
    #define MAXLEN 1000
    
    char *lineptr[MAXLINES];  /* Pointers to text lines */
    int decreasing = 0;       /* 0 if increasing, 1 if decreasing   -r flag */
    int numeric = 0;          /* 1 if numeric sort   -n flag */
    int fold = 0;             /* 1 if not case-sensitive   -f flag */
    int directory = 0;        /* 1 if directory sort   -d flag */
    
    int main(int argc, char *argv[])
    {
    	int nlines, i;
    
    	while (--argc > 0)
    	{
    		++argv;
    		if ((*argv)[0] == '-')
    		{
    			for (i = 1; (*argv)[i]; ++i)
    			{
    				switch ((*argv)[i])
    				{
    				case 'n':
    					numeric = 1;
    					break;
    				case 'f':
    					fold = 1;
    					break;
    				case 'r':
    					decreasing = 1;
    					break;
    				case 'd':
    					directory = 1;
    					break;
    				default:
    					printf("Usage: sort -dfnr\n");
    					return 1;
    				}
    			}
    		}
    		else
    		{
    			printf("Usage: sort -dfnr\n");
    			return 1;
    		}
    	}
    	if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
    		if (numeric)
    		{
    			quicksort((void **)lineptr,
    				0,
    				nlines - 1,
    				(int (*)(void *, void *))numcmp);
    		}
    		else
    		{
    			quicksort((void **)lineptr,
    				0,
    				nlines - 1,
    				(int (*)(void *, void *))mystrcmp);
    		}
    		writelines(lineptr, nlines);
    		return 0;
    	}
    	else
    	{
    		printf("Input too big to sort\n");
    		return 1;
    	}
    }
    
    /* quicksort: Sort v[left]...v[right] into increasing or decreasing order */
    void quicksort(void *v[], int left, int right, int (*comp)(void *, void *))
    {
    	int i, last;
    	void swap(void *v[], int, int);
    
    	if (left >= right) /* Do nothing if array contains fewer than two elements */
    	{
    		return;
    	}
    	swap(v, left, (left + right) / 2);  /* Move element to sort left */
    	last = left;
    	/* Move all elements < or > sort element to the left according to order */
    	for (i = left + 1; i <= right; ++i)
    	{
    		if (!decreasing)
    		{
    			if ((*comp)(v[i], v[left]) < 0)
    			{
    				swap(v, ++last, i);
    			}
    		}
    		else
    		{
    			if ((*comp)(v[i], v[left]) > 0)
    			{
    				swap(v, ++last, i);
    			}
    		}
    	}
    	swap(v, left, last); /* Move sort element to its final position */
    	quicksort(v, left, last - 1, comp); /* Sort left subarray */
    	quicksort(v, last + 1, right, comp); /* Sort right subarray */
    }
    
    /*
     * mystrcmp: Compares s1 and s2 lexicographically.
     * Ignores characters that are not letters, numbers, or whitespace if directory flag
     * is set.
     * If the fold flag is set, it isn't case sensitive.
     */
    int mystrcmp(char *s1, char *s2)
    {
    	if (directory)
    	{
    		while (!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1)
    		{
    			++s1; /* Ignore bad characters */
    		}
    		while (!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2)
    		{
    			++s2; /* Ignore bad characters */
    		}
    	}
    	while (fold ? (tolower(*s1) == tolower(*s2)) : (*s1 == *s2))
    	{
    		if (*s1 == '\0')
    		{
    			return 0;
    		}
    		++s1;
    		++s2;
    		if (directory)
    		{
    			while (!isdigit(*s1) && !isalpha(*s1) && !isspace(*s1) && *s1)
    			{
    				++s1; /* Ignore bad characters */
    			}
    			while (!isdigit(*s2) && !isalpha(*s2) && !isspace(*s2) && *s2)
    			{
    				++s2; /* Ignore bad characters */
    			}
    		}
    	}
    	return fold ? (tolower(*s1) - tolower(*s2)) : (*s1 - *s2);
    }
    
    /* numcmp: Compare s1 and s2 numerically */
    int numcmp(char *s1, char *s2)
    {
    	double v1, v2;
    
    	v1 = atof(s1);
    	v2 = atof(s2);
    	if (v1 < v2)
    	{
    		return -1;
    	}
    	else if (v1 > v2)
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    
    void swap(void *v[], int i, int j)
    {
    	void *temp;
    
    	temp = v[i];
    	v[i] = v[j];
    	v[j] = temp;
    }
    
    /* readlines: Read input lines.
     * This version is slightly modified to read longer lines than the limit set by
     * MAXLEN.
     */
    int readlines(char *lineptr[], int maxlines)
    {
    	int len, nlines = 0;
    	char *p, line[MAXLEN];
    	int longline = 0;
    
    	while ((len = getline(line, MAXLEN)) > 0)
    	{
    		if (nlines >= maxlines || (p = alloc(len)) == NULL)
    		{
    			return -1;
    		}
    		else
    		{
    			if (line[len - 1] == '\n')
    			{
    				line[len - 1] = '\0';  /* Delete newline */
    				strcpy_s(p, sizeof line, line);
    				if (!longline)
    				{
    					lineptr[nlines++] = p;
    				}
    				else
    				{
    					longline = 0;
    				}
    			}
    			else
    			{
    				strcpy_s(p, sizeof line, line);
    				if (!longline)
    				{
    					lineptr[nlines++] = p;
    					longline = 1;
    				}
    			}
    		}
    	}
    	return nlines;
    }
    
    /* writelines: Write output lines */
    void writelines(char *lineptr[], int nlines)
    {
    	while (nlines-- > 0)
    	{
    		printf("%s\n", *lineptr++);
    	}
    	return;
    }
    
    int getline(char *s, int max)
    {
    	int c;
    	char *ps = s;
    	while (--max && (c = getchar()) != EOF && c != '\n')
    	{
    		*s++ = c;
    	}
    	if (c == '\n')
    	{
    		*s++ = '\n';
    	}
    	*s = '\0';
    	return s - ps;
    }
    
    #define ALLOCSIZE 2000000
    
    static char allocbuf[ALLOCSIZE];  /* Storage for alloc */
    static char *allocp = allocbuf;    /* Next free position */
    
    char *alloc(int n)
    {
    	if (allocbuf + ALLOCSIZE - allocp >= n) /* It fits */
    	{
    		allocp += n;
    		return allocp - n; /* Old p */
    	}
    	else /* Not enough room */
    	{
    		return 0;
    	}
    }

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter