> 文档中心 > 100 Days of Code-day25-sort simple version

100 Days of Code-day25-sort simple version

Let us a write a program that will sort a set of text lines in alphabetical order, a stripped down version of unix sort program.

#define _CRT_SECURE_NO_WARNINGS#include#include#include#define MAXLINES 5000   /* max #lines to be sorted */char *lineptr[MAXLINES];//因为读取输入行、对文本行进行排序、按次序打印文本行//这三个步骤均需要指针数组的地址int readlines(char *lineptr[], int nlines);void writelines(char *lineptr[], int nlines);void qsort(char *lineptr[], int left, int right);/* sort input lines */int main(void){int nlines; /* number of input lines read */if ((nlines = readlines(lineptr, MAXLINES)) >= 0){qsort(lineptr, 0, nlines - 1);writelines(lineptr, nlines);return 0;}else{printf("error: input too big to sort \n");return 1;}}#define MAXLEN 1000 /* max length of any input line */int mgetline(char *, int);char *alloc(int);//读取输入行的两个重要环节://1.从输入中获取,过程中要检查输入行的长度是否超过限制(在getline函数)//2.为获取的内容申请足够的空间,以便于将其保存//需要注意的地方:输入的行数是否超过限制,然后看是否有空间存放该输入行/* readlines: read input lines */int readlines(char *lineptr[], int maxlines){int len, nlines;char *p, line[MAXLEN];//指针p用来接收每个待排序字符串的首地址nlines = 0;//进行排序的行数(也就是指针数组元素的个数)while ((len = mgetline(line, MAXLEN)) > 0)if (nlines >= maxlines || (p = alloc(len)) == NULL)return -1;else{line[len - 1] = '\0';//去掉字符串尾部的换行符strcpy(p, line);//将所读取到的行复制到大字符数组allocbuf中lineptr[nlines++] = p;//将该字符串首字符地址赋给指针数组的元素,因为p为局部变量,如果不及时保存到指针数组中,就会出现之后输入内容将之前的内容覆盖掉,导致最终打印的内容都是最后一次输入的内容(字符串)//strcpy(lineptr[nlines++], line);不正确的原因是:lineptr[nlines++]在这里只能表示它是一个指针数组//其包含的元素为空指针,指向的空间未知。所以起不到初始化未知空间(在这里指待放入字符串的空间)的内容//所以必须要为其申请空间,将输入的字符串复制到该已知空间中,然后将该空间的地址传给大字符数组lineptr的指针元素}return nlines;}/* writelines: write output lines */void writelines(char *lineptr[], int nlines){int i;for (i = 0; i < nlines; i++)printf("%s\n", lineptr[i]);}/* qsort: sort v[left] ... v[right] into increasing order */void qsort(char *v[], int left, int right){int i, last;void swap(char *v[], int i, int j);//递归调用必须要有终止条件if (left >= right)return;swap(v, left, (left + right) / 2);last = left;for (i = left + 1; i <= right; i++)//起始条件应该是从被选定划分子集元素的下一个元素开始if (strcmp(v[i], v[left]) < 0)//比较其余字符串的与所选定的字符串(作用:划分子集)的长度swap(v, ++last, i);//如果长度小于指定字符串的,则要将其往前放swap(v, left, last);qsort(v, left, last - 1);qsort(v, last + 1, right);}/* swap: interchange v[i] and v[j] */void swap(char *v[], int i, int j){char *temp;temp = v[i];v[i] = v[j];v[j] = temp;}#define ALLOCSIZE 10000  /* size of available space */static char allocbuf[ALLOCSIZE];    /* storage for alloc */static char *allocp = allocbuf;     /* next free position *///作为全局变量,要想使其对外不可见可以使用关键字staticchar *alloc(int n)  /* return pointer to n characters */{if (allocbuf + ALLOCSIZE - allocp >= n)//指针的算术运算中可使用数组最后一个元素的下一个元素的地址//allocbuf[ALLOCSIZE]表示该数组包括下标从0到9999,allocbuf + ALLOCSIZE指向下标为9999之后一个元素的地址(在指针数组运算中合法)//大字符数组最后一个元素的下一个元素的地址与当前位置的差//表示剩余可放入字符串的空间{allocp += n;return allocp - n;//返回分配前的指针,也就是被放入字符串的首字符的地址}elsereturn 0;}void free(char *p){if(p>=allocbuf && p < allocbuf + ALLOCSIZE)p = allocbuf;}int mgetline(char *s, int lim){int c;char *t = s;while (--lim > 0 && (c = getchar()) != EOF && c != '\n')*s++ = c;if (c == '\n')*s++ = c;*s = '\0';return s - t;}

小故事网