C Primer Plus 第11章 11.6 字符串例子:字符串排序

原创
2016/08/27 06:02
阅读数 156

我们来解决一个把字符串按字母表顺序排序的问题。准备花名册、建立索引以及很多其他情况下都会用到字符串排序。这个程序的一个主要工具就是strcmp( ),因为可以使用这个函数来决定两个字符串的顺序。一般的做法是读取一个字符串数组、对它们进行排序并输出。先前,我们给出一个读取字符串的方案,我们就按那个方案开始该程序。输出字符串不会有什么问题。程序使用的标准排序算法,后面会进行解释。我们在其中使用了一个小技巧,看您能否弄明白它。程序清单11.25给出了程序。

程序清单11.25  sort_str.c程序

/*sort_str.c 读进一些字符串并对它们排序*/
#include <stdio.h>
#include <string.h>
#define SIZE 81     /*字符串长度限制,包括'\0'  */
#define LIM 20      /*最多读取的行数  */
#define HALT " "    /*用空字符串终止结束  */
void stsrt(char *strings[],int num); /*字符串排序函数*/

int main(void)
{
    char input[LIM][SIZE];  /*存储输入的数组*/
    char *ptstr[LIM];  /*指针变量的数组*/
    int ct=0;  /*输入计数*/
    int k;  /*输出计数*/

    printf("Input up to %d lines,and I will sort them.\n",LIM);
    printf("To stop ,press the enter key at a line's start.\n");
    while(ct<LIM && gets(input[ct])!=NULL && input[ct][0]!='\0')
    {
        ptstr[ct]=input[ct];
        ct++;
    }
    stsrt(ptstr,ct);  /*调用字符串排序函数*/
    puts("\nHere's the sorted list: \n");
    for(k=0;k<ct;k++)
        puts(ptstr[k]);  /*排序后的指针*/

    return 0;
}
/*字符串-指针-排序函数*/
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;
    }
}

11.6.1  排序指针而不是字符串

程序的技巧部分在于它并不是重新安排字符串本身,而仅仅重新安排指向字符串的指针。

让我们解释一下。起初,ptrst[0]指向input[0],等待。这就是说指针ptrst[i]指向数组input[i]的第一个字符。每个input[i]都是一个含有81个元素的数组,而每个ptrst[i]都是一个变量。排序过程重新安排ptrst,而不改变input。例如,如果input[1]在字母表中先于input[0],程序就交换ptrst,使ptrst[0]指向input[1]的开始,使ptrst[1]指向input[0]的开始。这样比使用strcpy()来交换两个input字符串的内容简单多了。这种方法的优点在于保留了原始字符串顺序。

11.6.2  选择排序算法

我们使用了选择排序(selection sort)算法来进行指针排序。其思想是使用一个for循环把每个元素轮流与第一个元素比较。如果被比较元素在顺序上先于当前第一个元素,程序就将换这二者。程序执行到循环结束时,第一个元素包含的指针指向在机器编码顺序中排在第一个的字符串。然后外部的for循环重复这个过程,这次是以input的第二个元素作为开始元素。内部循环结束时,ptrst的第二个元素包含的指针就指向顺序排第二的字符串。这个过程一直继续下去,直到所有元素都已经排好序。

现在再仔细看一下选择排序。下面是用伪代码形式表示的纲要:

for n=first to n = nest-to-last element,
    find largest remaining number and place it in the nth element

流程是这样的:首先以n=0开始。扫描整个数组,找出最大的数,把它和第一个元素交换位置。然后设n=1,扫描数组第一个元素以外的其他元素,找出剩余数中最大数,并把它和第二个元素交换。继续这个过程,直到倒数第二个元素为止。现在只剩下两个元素,比较它们并把较大的一个放在倒数第二个位置上。最小的元素就放在最后一个位置上。

这看起来像是一个for循环可以完成的任务,但我们还必须更详细地描述这个查找和放置的过程。选择剩余最大值的一个办法就是比较剩余数组的第一和第二个元素。如果第二个元素大,就交换这两个数据。现在比较第一个和第三个元素。如果第三个大就交换这两个数据。每一次交换都把大的元素移到上面。继续这种方法,直到比较第一个和最后一个元素。完成以后,最大的数就在剩余数组的第一个元素中。此时,第一个元素已经排好序了,但是数组中的其他元素还很混乱。下面是该过程的伪代码:

for n-second element to last element 
    compare nth element with first element;if nth is greater ,swap values

这个过程看起来也像是一个for循环可以完成 的任务,它会被嵌套在第一个for循环中。外部循环表明要填充哪一个数组元素,内循环找出该数组元素中要放置的值。把这两部分的伪代码结合在一起,并翻译成C,我们就得到了程序清单11.25中的函数。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部