第43题  插入排序法

在本题程序MODI1.C中,函数fun通过字符指针形参a接收一个字符串,采用插入法对串中字符从大到小进行排序。

例如:若接收字符串为:QETUOADGJLMBWCXZ

则从大到小排序后变成:ZXWUTQOMLJGEDCBA

请改正程序中的错误,使之得出正确结果。                                                                注意:不许改动 main函数,不许增行或删行,也不许更改程序结构。

MODI1.C:

MODI43-01

参考答案:

MODI43-02

运行结果:

MODI43-03

程序解析:

#include <stdio.h>
#include <string.h>

#define N 100

文件包含预处理指令#include <stdio.h>支持标准库函数printf、scanf的正常调用。程序要调用某个库函数,就必须包含与之对应的头文件。预处理指令通常位于源文件开头处,单独占一行,行尾无标点。#include <string.h>支持标准库函数strlen。

宏定义预处理指令#define N 100定义标识符N为字符序列100,在程序下文中,N的每次出现均被自动替换成字符序列100,这种标识符叫做符号常量或宏。例如:main中的char a[N];经替换变成char a[100];

程序从函数main开始执行。声明:

char a[N];

定义长度为N即100的字符型数组a,分配存储,不作初始化,用于从标准输入设备(通常是键盘)读取原始字符串。数组下标从0开始。凡未经初始化的变量,其初值无意义,仅反映新分配内存的当前随机性物理状态。至此,当前存储状态如下图所示,变量的无意义垃圾值以空白表示。

MODI43-04

首先,执行下列语句:

printf(″原始字符串:\n″);
gets(a);

printf语句在标准输出设备(通常是显示器)给出提示,gets语句从标准输入设备(通常是键盘)读取一行字符(以换行符′\n′结尾)、存储于字符数组a中、并以空字符′\0′取代换行符。至此,当前存储状态如下图所示。

MODI43-05

接着,执行下面函数调用语句:

fun(a);

以数组名a(自动转换为字符型常量指针)为实参调用函数fun,于是,main的执行被挂起(暂停),函数fun开始执行。首先,为形参变量a分配存储,完成参数传递:将main中的指针a的值(第0字符元素的地址)复制于fun的形参a,即让fun中的指针a指向main中的数组a的第0个字符元素,以便在函数fun中通过指针a来访问main中的数组a,即在fun中通过a[i]和在main中通过a[i]都将访问同一字符对象。

在函数fun中,声明:

int ch, n, i, j;

定义整型变量ch、n、i、j,分配存储,不作初始化,ch在排序过程中用于临时存放字符,n用于存放串a的长度,i、j均用于控制循环和充当访问数组a的下标。至此,当前存储状态如下图所示。形参a也是fun的局部变量。这时有两个变量a,同名同型,但不会冲突,因为它们分属函数fun和main,分别存在于不同的存储空间、各有自己的作用域。局部变量只能在自己的作用域中访问。

MODI43-06

在函数fun中,首先执行下面语句:

n = strlen(a);

调用库函数strlen,确定串a的长度(字符个数,不含空字符′\0′)并赋于变量n。至此,当前存储状态如下图所示:

MODI43-07

接着,执行下面语句:

for (i = 1; i < n; i++) {
­      ch = a[i];
­      j = i−1;
­      while ((j>=0) && (ch>a[j])) {
­            a[j+1] = a[j];
­            −−j;
­      }
­      a[j+1] = ch;
}

这是一个for循环(内嵌一个while循环),该语句用插入法对字符串a从大到小进行排序。以上图中的字符串为例,插入排序法的基本思想是:①首先把字符串看成两部分:只含一个字符Q的有序序列和其余字符E至Z组成的无序序列,如上图所示,有序序列用红色,无序序列用黑色。②将无序序列的首字符插入有序序列的适当位置,使得有序序列长度增1且依然有序,无序序列长度减1,如此重复,直到无序序列的字符全被插入,排序即告完成。这个反复插入的工作正是for循环的任务。循控变量 i 依次取值1,2,…,15,16(n)。当i取16时,循环因条件 i < n为假而终止。i 每取一值(16除外),均将无序序列的首字符a[i]插入有序序列中,当for循环终止后,排序即告完成。第1轮循环,字符a[1]即字符E插入后的效果如下图所示:

MODI43-08

第2轮循环,字符a[2]即字符T插入后的效果如下图所示:

MODI43-09

第6轮循环,字符a[6]即字符D插入后的效果如下图所示:

MODI43-10

下面具体分析,第7轮循环,字符a[7]即字符G插入的具体过程:在第7轮循环中,i 值为7,对应轮次,也对应当前待插字符的下标,当前待插字符是a[i]即a[7]即字符G。①执行语句ch = a[i];将当前待插字符G临时转储于变量ch,效果如下图所示:

MODI43-11

②执行语句j = i−1;将变量j定位于当前有序序列的尾字符A,效果如下图所示:

MODI43-12

③执行语句while,将当前待插字符G插入有序序列UTQOEDA中的适当位置,使得有序序列长度增1且依然有序。因为序列UTQOEDA由大到小有序,这个适当位置就是UTQOEDA之间,插入后变成UTQOGEDA,该位置特点是:左边序列UTQO均大于G,右边序列EDA均小于G。为了把G插入右序列EDA之前,必须将右序列EDA向右平移一个位置,先用A覆盖G、再用D覆盖A、后用E覆盖D,这样先后依次完成。因为这种平移会将G覆盖,所以预先将G临时转储于变量ch中保存起来。while语句正是完成右序列EDA向右平移一个位置的任务。因为右序列EDA均小于G,所以有限定条件(ch>a[j]),又因为在极端情况下,右序列等同于有序序列,即当前待插字符的适当位置是串首字符a[0]处,后面的字符X和Z的插入均属于这种情况,所以有限定条件(j>=0)。因为在当前待插字符前边(左边)同时满足这两个条件的字符构成右序列,所以采用逻辑与&&运算符将二者结合,构成右序列向后(向右)平移的while循环条件(j>=0) && (ch>a[j])。前面的定位语句j = i−1;将变量j定位于当前右序列的尾字符A,为while循环平移做好准备。当while循环终止后,右序列EDA向后平移一个位置完毕,效果如下图所示:注意:平移前,变量j定位于右序列尾字符A,每后移一个字符,j减1指示下一字符,在极端情况下,右序列等同于有序序列,即所有字符都要平移,当串首字符a[0]右移后,j减1变成−1,这时条件(j>=0)变为假,迫使while循环终止,平移完成。

MODI43-13

④执行语句a[j+1] = ch;用字符G覆盖字符E。因为在while循环平移过程中,先执行语句a[j+1] = a[j];实现向后平移一个位置,再执行−−j;,所以当右序列EDA的最后字符E后移动后,变量j再减1变成3,是左序列尾字符O的下标,因此字符ch即G应覆盖a[j+1]即a[4]即字符E,效果如下图所示:

MODI43-14

以此类推,第14轮循环,字符a[14]即字符X插入后的效果如下图所示:

MODI43-15

最后一轮,即第15轮循环,字符a[15]即字符Z插入后的效果如下图所示。至此,整个排序过程结束。注意:当字符X、Z插入后,j的值均为−1,表明循环条件中的(j>=0)为假,迫使while循环终止。

MODI43-16

由于这是函数fun的最后语句,随即fun返回函数main,但无返回值,同时收回函数fun的存储空间。fun通过其指针a访问main的数组a,其执行效果,也就是排序结果保留在main的数组a之中。至此,当前存储状态如下图所示:

MODI43-17

 

函数fun返回后,main从挂起点即语句fun(a);恢复继续执行。接着,执行下列语句:

printf(″由大到小排序后:\n″);
puts(a);

puts语句在标准输出设备输出字符数组a中的排序结果。

知识点:

① 程序执行是动态过程,语句不断执行,变量值不断变化,同时伴随函数局部变量(含形参变量)的创生与消亡。当函数进入时,局部变量因自动分配存储而创生;当函数返回时,因自动收回存储而消亡。形参变量经参数传递获得初值且有意义,非形参局部变量若未经显式初始化,则其初值无意义,称为垃圾值,仅反映新分配内存的当前随机性物理状态。参数传递发生在函数进入后、函数的语句开始执行前,实参表达式(含变量)的值被复制于形参变量之中,名曰″传值″。不同函数的局部变量可以同名,不会冲突,驻留各自的存储空间,只能被所属函数自己的语句访问,这就是局部变量的作用域。函数通过对形参指针的间接引用可以访问调用者函数内的变量,是函数之间双向通信的重要方式,既能从调用者接收数据,又能向调用者回送计算结果。函数通过非指针形参只能从调用者函数接收数据,通过函数返回值只能向调用者回送计算结果,都只是单向通信。

② 字符数组与字符串的关系。字符数组是用来存储字符数据的,每个元素可以存放机器字符集的任一字符。长度为n的字符串是长度为n+1的字符数组,最后一个字符必须是空字符′\0′,空字符′\0′不计入字符串长度,这是C语言的规定,供程序检测是否到达串尾之用。长度为n的字符数组,可以容纳n个任意字符,因此可以存储长度小于或等于n−1的任意字符串。

③  在C语言中,逻辑表达式的结果类型为int,结果值只取0或1,结果取0表示逻辑假,结果取1表示逻辑真。充当whileforif等语句的条件表达式,可以是任何数值型表达式,包括字符型、整型、实型,其值为0视为逻辑假,其值非0视为逻辑真。

④ 设有字符指针p,且已指向字符数组内某字符元素,那么,++p使p指向下一字符元素,而−−p使p指向上一字符元素。

⑤  设有字符指针变量p,且已指向某字符变量,则可通过∗p间接访问p所指的字符。MODI3-08在这种情形下,可通过∗p间接访问p所指的字符′A′,即字符变量∗p的值是′A′,注意:p和∗p是两个不同类型的变量,p的类型是字符指针类型,即char ∗类型,而∗p的类型是字符类型,即char类型。

⑥ 凡字符串处理程序,通常采用字符指针扫描字符串的方法解决问题。扫描终止的标志就是遇到串尾标记空字符′\0′,而空字符′\0′的机内码值的确为0。像′\0′、′\n′′a′等字符常量以及其它字符变量,当出现在表达式中时,自动转换为int类型。

⑦  库函数char  ∗gets(char  ∗s),需要头文件stdio.h支持。

从标准输入设备(通常是键盘),读取下一输入文本行于字符数组s中,并用空字符′\0′替代换行符′\n′,返回s。若遇文件尾或发生错误,则返回NULL。

⑧ 库函数int  puts(const  char  ∗s),需要头文件stdio.h支持。

向标准输出设备(通常是显示器),输出字符串s的内容之后,再输出换行符′\n′。若发生错误,则返回EOF,否则返回一个非负值。

⑨  void fun(char a[ ])等价于void fun(char ∗a),均声明形参a是字符型指针,可用来接收字符型数组。

练习题:

试改变代码行 while ((j>=0) && (ch>a[j])) 中的适当内容,为自己命新题,举一反三。

返回