鲁达 我们来处理一个按字母表顺序排序字符串的实际问题。准备名单表、创建索引和许多其他情况下都会用到字符串排序。该程序主要是用strcmp()函数来确定两个字符串的顺序。一般的做法是读取字符串函数、排序字符串并打印出来。之前，我们设计了一个读取字符串的方案，该程序就用到这个方案。打印字符串没问题。程序使用标准的排序算法，稍后解释。我们使用了一个小技巧，看看读者是否能明白。程序演示了这个程序。
/* -- reads in strings and sorts them */ #include <; #include <; #define SIZE 81 /* string length limit, including 0 */ #define LIM 20 /* maximum number of lines to be read */ #define HALT "" /* null string to stop input */ void stsrt(char *strings[], int num);/* string-sort function */ char * s_gets(char * st, int n); int main(void) { char input[LIM][SIZE]; /* array to store input */ char *ptstr[LIM]; /* array of pointer variables */ int ct = 0; /* input count */ int k; /* output count */ printf("Input up to %d lines, and I will sort ;,LIM); printf("To stop, press the Enter key at a line's ;); while (ct < LIM && s_gets(input[ct], SIZE) != NULL && input[ct][0] != '0') { ptstr[ct] = input[ct]; /* set ptrs to strings */ ct++; } stsrt(ptstr, ct); /* string sorter */ puts("nHere's the sorted list:n"); for (k = 0; k < ct; k++) puts(ptstr[k]) ; /* sorted pointers */ return 0; } /* string-pointer-sorting function */ void stsrt(char *strings[], int num) { char *temp; int top, seek; for (top = 0; top < num-1; top++) for (seek = top + 1; seek < num; seek++) if (strcmp(strings[top],strings[seek]) > 0) { temp = strings[top]; strings[top] = strings[seek]; strings[seek] = temp; } } char * s_gets(char * st, int n) { char * ret_val; int i = 0; ret_val = fgets(st, n, stdin); if (ret_val) { while (st[i] != 'n' && st[i] != '0') i++; if (st[i] == 'n') st[i] = '0'; else // must have words[i] == '0' while (getchar() != 'n') continue; } return ret_val; } 我们用一首童谣来测试该程序：
Input up to 20 lines, and I will sort them.
To stop, press the Enter key at a line's start.
O that I was where I would be,
Then would I be where I am not;
But where I am I must be,
And where I would be I can not.
Here's the sorted list:
And where I would be I can not.
But where I am I must be,
O that I was where I would be,
Then would I be where I am not;
看来经过排序后，这首童谣的内容未受影响。
1 排序指针而非字符串
该程序的巧妙之处在于排序的是指向字符串的指针，而不是字符串本身。我们来分析一下具体怎么做。最初，ptrst[0]被设置为input[0]，ptrst[1]被设置为input[1]，以此类推。这意味着指针ptrst[i]指向数组input[i]的首字符。每个input[i]都是一个内含81个元素的数组，每个ptrst[i]都是一个单独的变量。排序过程把ptrst重新排列，并未改变input。例如，如果按字母顺序input[1]在intput[0]前面，程序便交换指向它们的指针（即ptrst[0]指向input[1]的开始，而ptrst[1]指向input[0]的开始）。这样做比用strcpy()交换两个input字符串的内容简单得多，而且还保留了input数组中的原始顺序。图11.6从另一个视角演示了这一过程。
Sorting string pointers
2 选择排序算法
我们采用选择排序算法（selection sort algorithm）来排序指针。具体做法是，利用for循环依次把每个元素与首元素比较。如果待比较的元素在当前首元素的前面，则交换两者。循环结束时，首元素包含的指针指向机器排序序列最靠前的字符串。然后外层for循环重复这一过程，这次从input的第2个元素开始。当内层循环执行完毕时，ptrst中的第2个元素指向排在第2的字符串。这一过程持续到所有元素都已排序完毕。
现在来进一步分析选择排序的过程。下面是排序过程的伪代码：
for n = first to n = next-to-last element, find largest remaining number and place it in the nth element具体过程如下。首先，从n = 0开始，遍历整个数组找出最大值元素，那该元素与第1个元素交换；然后设置n = 1，遍历除第1个元素以外的其他元素，在其余元素中找出最大值元素，把该元素与第2个元素交换；重复这一过程直至倒数第2个元素为止。现在只剩下两个元素。比较这两个元素，把较大者放在倒数第2的位置。这样，数组中的最小元素就在最后的位置上。
这看起来用for循环就能完成任务，但是我们还要更详细地分析“查找和放置”的过程。在剩余项中查找最大值的方法是，比较数组剩余元素的第1个元素和第2个元素。如果第2个元素比第1个元素大，交换两者。现在比较数组剩余元素的第1个元素和第3个元素，如果第3个元素比较大，交换两者。每次交换都把较大的元素移至顶部。继续这一过程直到比较第1个元素和最后一个元素。比较完毕后，最大值元素现在是剩余数组的首元素。已经排出了该数组的首元素，但是其他元素还是一团糟。下面是排序过程的伪代码：
for n - second element to last element, compare nth element with first element; if nth is greater, swap values看上去用一个for循环也能搞定。只不过要把它嵌套在刚才的for循环中。外层循环指明正在处理数组的哪一个元素，内层循环找出应存储在该元素的值。把这两部分伪代码结合起来，翻译成C代码，就得到了程序清单11.29中的stsrt()函数。顺带一提，C库中有一个更高级的排序函数：qsort()。该函数使用一个指向函数的指针进行排序比较。