文档章节

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

idreamo
 idreamo
发布于 2016/08/27 06:02
字数 1423
阅读 42
收藏 0

我们来解决一个把字符串按字母表顺序排序的问题。准备花名册、建立索引以及很多其他情况下都会用到字符串排序。这个程序的一个主要工具就是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中的函数。

© 著作权归作者所有

idreamo
粉丝 18
博文 139
码字总数 224743
作品 0
青岛
产品经理
私信 提问
C Primer Plus 第11章 字符串和字符串函数 11.2 字符串输入

11.2.1 创建存储空间 要做的第一件事是建立一个空间以存放读入的字符串。 最简单的办法就是在声明中明确指出数组的大小: char name[81] ; 现在的name是一个已经分配81字节存储块的地址。另一...

idreamo
2016/08/19
23
0
C Primer Plus 第11章 字符串和字符串函数 11.5 字符串函数

C库提供了许多处理字符串的函数:ANSI C 用头文件string.h给出这些函数的原型。下面是一些最有用和最常用的函数:strlen() 、strcat()、strncat() 、strcmp() 、strncmp() 、strcpy()、 strn...

idreamo
2016/08/25
45
0
C Primer Plus 第11章 11.8 命令行参数

现代的图形界面出现之前是命令行界面。Dos和Unix就是例子。命令行(command line)是在一个命令行环境下,用户输入的用于运行程序的行。假定有一个程序在名为fuss 的文件中,那么在UNIX下运行该...

idreamo
2016/08/27
44
0
C Primer Plus 第11章 11.7 ctype.h字符函数和字符串

第7章“C控制语句 分支和跳转”介绍了ctype.h系列字符相关的函数。这些函数不能被 应用于整个字符串,但是可以被应用于字符串中的个别字符。程序清单11.26定义了一个函数,它把toupper( )函数...

idreamo
2016/08/27
52
0
【书评:Oracle查询优化改写】第五至十三章

【书评:Oracle查询优化改写】第五至十三章 一.1 BLOG文档结构图 一.2 前言部分 一.2.1 导读 各位技术爱好者,看完本文后,你可以掌握如下的技能,也可以学到一些其它你所不知道的知识,~O(∩...

技术小胖子
2017/11/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Replugin借助“UI进程”来快速释放Dex

public static boolean preload(PluginInfo pi) { if (pi == null) { return false; } // 借助“UI进程”来快速释放Dex(见PluginFastInstallProviderProxy的说明) return PluginFastInsta......

Gemini-Lin
58分钟前
4
0
Hibernate 5 的模块/包(modules/artifacts)

Hibernate 的功能被拆分成一系列的模块/包(modules/artifacts),其目的是为了对依赖进行独立(模块化)。 模块名称 说明 hibernate-core 这个是 Hibernate 的主要(main (core))模块。定义...

honeymoose
今天
4
0
CSS--属性

一、溢出 当内容多,元素区域小的时候,就会产生溢出效果,默认是纵向溢出 横向溢出:在内容和容器之间再套一层容器,并且内部容器要比外部容器宽 属性:overflow/overflow-x/overflow-y 取值...

wytao1995
今天
4
0
精华帖

第一章 jQuery简介 jQuery是一个JavaScript库 jQuery具备简洁的语法和跨平台的兼容性 简化了JavaScript的操作。 在页面中引入jQuery jQuery是一个JavaScript脚本库,不需要特别的安装,只需要...

流川偑
今天
7
0
语音对话英语翻译在线翻译成中文哪个方法好用

想要进行将中文翻译成英文,或者将英文翻译成中文的操作,其实有一个非常简单的工具就能够帮助完成将语音进行翻译转换的软件。 在应用市场或者百度手机助手等各大应用渠道里面就能够找到一款...

401恶户
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部