二级C语言考前复习资料（机试）

【解析】该类型主要考察学员对一个C程序的整体把握能力。首先须通读整个源程序，了解程序的功能后试着边填空边调试，分析输出结果，以找到正确答案。因此，不像程序修改题那么简单。

【程序填空题的特点和注意事项】

（1）程序填空的试题中通常包含三个空需要填写。

（2）试题中用"******found******/"来提示在下一行或下二行注明填空的位置及编号，如___1___。

（3）程序填空考核对程序的整体把握，出题点可能是：for循环语句的初始化或条件判断、函数返回值、if语句的条件判断、链表中指针如何移动、文件操作相关函数的参数等。

（4）特别要注意的是：只能在填空的位置填写语句或表达式，不要增行或删行，不要改动程序行的顺序，更不要改动程序的结构。

（1）首先仔细审题，了解试题的要求，看清题目给出的输入和输出例示，以便检验程序运行的结果是否正确。

（2）审视"/******found******/"所在函数，根据题义理解程序所采用的基本算法，做到心里有数。

（3）填好空后对测试程序进行检查是否有语法错误。当编译提示有语法错时，可参考编译提示来查找并改正错误。

（4）当不再出现语法错时，执行程序， 按照试题的示例给出的数据进行试算，若试算的结果与给出的输出结果相同时，该题就做对了；若试算的结果与给出的输出结果不同，就应进一步检查程序中的逻辑错误。

（5）修改完成，得到正确结果后，一定不要忘记把修改后的程序存盘。

【解析】该类型主要考察学员对C程序部分结构或算法的分析和理解能力。因此，对学员的知识把握能力要求不高，通常可以借助计算机帮我们改错（仅限语法错误）。若非语法错误，则需对程序边调试边找错，分析输出结果，找出错误所在并改正。

【程序填空题的特点和注意事项】

（1）上机改错的试题中通常包含两个(或三个)错误需要修改。

（3）错误的性质基本分语法错误和逻辑错误两种，也有些试题要求把语句添加在下划线处。

（4）特别注意：只能在出错的行上进行修改，不要改动程序行的顺序，更不要自己另编程序。

（1）首先仔细审题，了解试题的要求，看清楚试题给出的输入和输出例示，以便检验改错后程序运行的结果是否正确。

（2）审视"/******found******/"所在函数，根据题义理解程序所采用的基本算法，做到心里有数。

（3）先对测试程序进行检查是否有语法错误。当编译提示有语法错时，可参考编译提示来查找并改正错误。

（4）当不再出现语法错时，执行程序， 按照试题的示例给出的数据进行试算，若试算的结果与给出的输出结果相同时，该题就做对了；若试算的结果与给出的输出结果不同，就应进一步检查程序中的逻辑错误。

（5）当程序存在逻辑错误时，首先应当理解题意、读懂程序的算法，必要时可按步检查数据的流程，以便确定错误所在。例如，题目要求数据按由小到大排序，而结果数据是按由大到小进行了排序，问题可能出现在条件判断上。又如，输出的字符串比预期的短，就有可能字符串的结束标志放错了位置。再如做循环的时候数组上限下限错误了，下标是从0开始 而不是1开始的。修改程序中的逻辑错时，要求考生认真读懂程序代码。

（6）修改完成，得到正确结果后，一定不要忘记把修改后的程序存盘。

【解析】主要考察学员对C语言综合理解能力和上机实践能力，能够对所给问题，运用所学知识，按照程序设计的步骤独立编写出一段程序，学会用计算机语言描述日常生活中所见到的现象和拟题，通过实际上机操作积累经验，锻炼用C语言描述问题的逻辑思维能力。

（1）首先仔细审题，了解试题的要求，记下试题给出的输入和输出例示，以便检验在完成指定的函数后程序运行的结果是否正确。

（2）调出源程序后，应对照函数首部的形参，审视主函数中调用函数时的实参内容，以便明确在函数中需要处理的数据对象。

（3）理解试题的要求，审视主函数中调用函数的方式，若在表达式中调用函数(如把函数值赋给某个对象)，则要求有函数值返回，需注意函数的类型，并在函数中用return语句返回函数值；若主函数中仅用语句形式调用函数，则需要通过形参间接地返回所得结果。

（4）选择适当的算法进行编程，输入程序语句。不要忘记及时存盘！

（5）编译程序，直到没有语法错误。

（6）调试程序，利用试题中给出的例示数据进行输入(若要求输入的话)，运行程序，用示例的输出数据检验输出结果，直到结果相同。

　　 特别要注意：程序设计题要求完全设计正确才会给分，因此，要么是40分，要么是0分，不会给中间分。那么想通过机试，程序填空题和程序修改题通常来说必须全部正确才能容易通过，否则不容易通过。

上机填空、改错题重点题型归类分析

一、填空题（30分）两至三个空

注意：上机考试时要删除填空地方的数字和下划线

常见题型：加下划线的代码是可能考填空的！

1.累加求和，累乘求阶乘

2.素数的判断（除了1和其自身外，不能被任何数整数的数为素数）

判断整数2―n内的所有素数，并将素数输出，返回素数的个数

3.大小写转化或者大小写字母的判断

判断某一年是不是闰年，关键代码：

如果要求出年中的所有闰年，则需要在外层套一个for循环

【分析】判断闰年只需要考虑两种情况：（1）年份能被4整除但不能被100整除（2）年份能被400整除

5.求一组数的中的最大数和最小数

6.逆转（将字符串中的字符逆转或者把数组中的元素逆转）

（1）将左三角元素置0，将矩阵转置，求矩阵周边元素的值

此种类型的题目，只要获得了左下三角元素和右下三角元素，就容易求解了！

（2）将N×N矩阵主对角线元素中的值与反向对角线对应位置上元素中的值进行交换。N=3，有下列矩阵：

例如：求100――200内能别2整除不能被3整除的所有整数

【注意】此处一定是= =，在改错题中经常考

9.获取一个三位数的个位数，十位数，百位数

个位数：i=x%10;/*此方法对任何位数的整数都适用，必须熟记*/

其它位数：对于4位数，5位数，获取最高位的方法很多，不过最简单的方法是除以4位数，5位数的最小数即可

获取中间位数的数的方法也很多，/100,/10最后再对10求余都可以获得

10.排序算法――选择法排序(从小到大进行排序)

11.取子串，按要求取出长字符串中的子字符串，并统计子串的个数

12.统计：统计分数段的人数个数

统计字符串中数字或某一个字符出现的个数

例如：统计成绩在90分以上,80-90,70-80，60-70,60分以下各分数段人数个数，每个分数段的人数分别存放在数组b中

第一、二个数为1，后面的每一个数是前面两个数的和

例如：求第n位斐波纳契数

给定程序中,函数fun的功能是将带头节点的单向链表结点数据域中的数据从小到大排序。即若原链表结点数据域从头至尾的数据为：10、4、2、8、6，排序后链表结点数据域从头至尾的数据为：2、4、6、8、10。

给定程序中，函数fun的功能是：对形参s所指字符串中下标为奇数的字符按ASCII码大小递增排序，并将排序后下标为奇数的字符取出，存入形参p所指字符数组中，形成一个新串。

给定程序中，函数fun的功能是：判断形参s所指字符串是否是"回文"（Palindrome），若是，函数返回值为1；不是，函数返回值为0。"回文"是正读和反读都一样的字符串（不区分大小写字母）。21

给定程序中，函数fun的功能是：将形参n中，各位上为偶数的数取出，并按原来从高位到低位相反的顺序组成一个新的数，并作为函数值返回。

19.字符串中的字符与数字关系

给定程序中，函数fun的功能是: 将s所指字符串中的所有数字字符移到所有非数字字符之后，并保持数字字符串和非数字字符串原有的先后次序。例如，形参s所指的字符串为：def35adh3kjsdf7。执行结果为：defadhkjsdf3537。

20.数组中偶数下标与奇数下标

给定程序中,函数fun的功能是将形参给定的字符串、整数、浮点数写到文本文件中，再用字符方式从此文本文件中逐个读入并显示在终端屏幕上。

二、改错题（30分）两至三个错误

注意：对于基本的语法错误，可以直接通过编译找出来，但是对于逻辑错误，需要自己在看懂程序的基础上进行修改。把程序要实现的功能搞清楚，修改起来就容易些。

给定程序MODI1.C中函数fun的功能是：用递归算法计算斐波拉契数列中第n项的值。从第1项起，斐波拉契数列为：1、1、2、3、5、8、13、21、……

例如，若给n输入7，该项的斐波拉契数值为：13。请改正程序中的错误，使它能得出正确结果。

2.条件判断时，判断符合出错

3.赋值出错或没有赋值

（1）变量定义之前没有赋值

long k;而在之后的程序中使用到了k,此时必须对k初始化，如long k=0;

(2)赋值时类型不匹配

*p,*r才是表示内容，而r,p是表示地址

0;因为'\0'的ASCII码就是0，所以可直接用0进行赋值

给定程序MODI1.C中函数fun的功能是：将长整型数中每一位上为奇数的数依次取出，构成一个新数放在t中。高位仍在高位，低位仍在低位。

4.函数定义出错，常见错误如下：（考得非常频繁，请务必熟记）

（8）函数定义时有返回值类型，但程序中缺少return 语句

给定程序MODI1.C中函数 fun 的功能是：求S的值。

5.实现交换时赋值出错

给定程序MODI1.C中函数fun的功能是：通过某种方式实现两个变量值的交换,规定不允许增加语句和表达式。例如变量a 中的值原为8，b中的值原为3, 程序运行后a 中的值为 3，b中的值为8。

6.for循环的格式不对

7.++、- -与*结合问题，搞清楚什么时候应该加括号。搞清楚什么时候该加*号

++、- -和*是同一优先级，结合性是从右向左

*p++； 是指针p向后移动一个存储单元 然后取指针p所指变量的值。

（*p）++； 是将指针p所指变量的值自增1.

给定程序MODI1.C中函数fun的功能是: 比较两个字符串，将长的那个字符串的首地址作为函数值返回。

由N个有序整数组成的数列已放在一维数组中，给定程序MODI1.C中函数fun的功能是：利用折半查找算法查找整数m在数组中的位置。若找到，返回其下标值；反之，返回-1。

8.数组元素逆序存放问题（常考！）

实质就是将数组中首位元素依次互换，sl-i-1];(记住这个对应关系！)

给定程序MODI1.C中函数fun的功能是：先将s所指字符串中的字符按逆序存放到t所指字符串中，然后把s所指串中的字符按正序连接到t所指串的后面。

9、带参宏定义，参数要加括号

10、链表问题，关于链表的插入、删除操作要熟悉

给定程序MODI1.C是建立一个带头结点的单向链表, 并用随机函数为各结点数据域赋值。函数fun的作用是求出单向链表结点(不包括头结点)数据域中的最大值,并且作为函数值返回。

%k;根据具体题目要求来改，也是考点之一，有时候要反过来改，将% 改为 /

给定程序MODI1.C中函数fun 的功能是：用下面的公式求π的近似值，直到最后一项的绝对值小于指定的数（参数num ）为止：

给定程序MODI1.C中函数fun的功能是：输出M行M列整数方阵，然后求两条对角线上元素之和，返回此和数。

（10）浮点数不能比较大小，只能用绝对值来比较

给定程序MODI1.C中函数fun 的功能是：用下面的公式求π的近似值，直到最后一项的绝对值小于指定的数（参数num ）为止：

(11)条件判断时的符号不对（这种错误要根据具体的题意来修改）

给定程序MODI1.C中函数fun的功能是：找出一个大于形参m且紧随m的素数，并作为函数值返回。

给定程序MODI1.C中函数fun的功能是：根据整型形参m的值，计算如下公式的值。

以上是可能会出错的地方，基本上涵盖了考试中会出现的所有错误，在上机考试时，要多注意这些容易出错的地方！

1、给定程序MODI1.C中，函数fun的功能是：在任意给定的N个正整数中，从左到右依次逐个取三个数作为一组，按值大小找出该组数的中值，用该中值替换与该组数对应的原三个数中的中间位置的数。处理后原数列中首尾2个数不变。处理后数列在主函数中输出。例如，有10个正整数如下：

上机编程题重点题型归类分析（二十四章经）

题型二：累加、累乘求和

题型四：在一维数组中按指定条件筛选

题型五：一维数组最值求解

题型八：数组去掉值重复的元素

题型九：数组元素的查找

题型十：二维数组周边元素

题型十一：二维数组对角线、上三角和下三角元素的操作

题型十二：二维数组转一维数组

题型十三：二维数组转置问题（即行列互换）

题型十四：数字字符串转整数

题型十五：“回文”字符串

题型十六：字符串统计问题

题型十七：字符串指定字符删除

题型十八：字符串数组求最值

题型十九：字符串的逆置

题型二十：字符串的连接

题型二十一：结构体数组求最值

题型二十二：结构体数组排序

1、函数fun的功能是： 将a、b中的两个两位正整数合并形成一个新的整数放在c中。合并的方式是：将a中的十位和个位数依次放在变量c的百位和个位上，b中的十位和个位数依次放在变量c的千位和十位上。

请编写fun函数实现该功能：

【解题思路】本题主要考了以下几个知识点：

（1）如何获得一个二位数的个位和十位：

不管是几位数，获得个位数的方法：a%10即可获得个位

两位数获得十位的方法：a/10

（2）十进制中四位数的构成：

也就是说：只要知道该四位数的各位上的数码，通过以上组合的方式就可以组合成一个四位数。如：b的十位放在c的千位，b/10*1000就是c的千位上的数了，其它的依次类推

题型二：累加、累乘求和

2、编写函数fun，它的功能是计算下列级数和，和值由函数值返回。

【解题思路】将复杂的多项式拆分开，找出各项或其中一部分的规律

（1）计算表达式的值，应根据题目要求定义变量数据类型以及如何初始化，找出各项的共同点。

（2）本程序中a，b用来表示每项的分子与分母(即各项中的阶乘)，注意其初值都为1

3、请编写函数fun，函数的功能是：将大于形参m且紧靠m的k个素数存入xx所指的数组中。例如，若输入17, 5，则应输出：19, 23, 29, 31, 37。函数fun中给出的语句仅供参考。

【解题思路】素数是历年考试中的重点和难点，掌握素数的基本概念：即除了1和t本身外，不能被“其它数”整除，“其它数”应该是从2到t-1的范围，从而确定循环变量的起始值、终止值

（1）本题答案中粗体部分是判断一个整数t是否为素数，通过for循环语句;if语句;break语句,与if语句连在一起满足条件时跳出循环。

（2）外层的while循环将大于m且紧靠m，即从m+1开始向后逐一判定，当个数j的值等于k时结束循环

题型四：在一维数组中按指定条件筛选

4、请编写函数fun，它的功能是: 求出 1 到 1000 之间能被 7 或11整除、但不能同时被 7 和 11 整除的所有整数并将它们放在a所指的数组中，通过 n 返回这些数的个数。

解题思路：将指定条件的数值“依次”追加到数组，在这个过程中追加元素的个数从0开始计算，因此变量j作为下标的初值设为0，存到数组后j增1，即现已找到的个数为1，同时1也是下一次待存入元素的下标，依次类推

（1）if语句,但是又不能同时被7和11整除的数,在这里充分理解"逻辑与"和"逻辑或"的区别;注意:(i%7==0||i%11==0)两边必须要有小括号

题型五：一维数组最值求解

5、请编写函数fun，其功能是求出数组的最大元素在数组中的下标并存放在k所指的存储单元中。

【解题思路】求最值问题是数组应用的基本考核方式，具体方法：

（1）假设第一个元素为最大（小）值

（2）与之后的其他元素“依次”比较，若比假设值大（小），则将该值设为假设值，依次类推

6、函数fun的功能是:用选择法对数组中的n个元素按从小到大的顺序进行排序。

【解题思路】 题中所提到的是"从小到大"的顺序。这类题可以利用选择法,即从后N个比较过程中,选择一个最小的与第一个元素交换,依此类推,即用第二个元素与后N-1个进行比较,并进行交换。该题与我们常见的C语言排序题类似,也是改错和编程题中的重点,请参看同类试题,以便达到举一反三的目的。

7、请编写函数fun,对长度为7个字符的字符串,除首、尾字符外,将其余5个字符按ASCII码值升序排列。

【解题思路】本题考查利用循环来控制数组元素的操作,首尾元素除外,因此,数组的下标值要从1开始,用循环变量i来依次取得数组中的元素,用数组中的元素s[i]和s[j]进行比较,如果后一个元素的ASCII码值小于前一个元素的ASCII码值,则交换这两个数组元素的值。

8、请编写函数fun, 函数的功能是: 移动一维数组中的内容; 若数组中有n个整数, 要求把下标从0到p(含p,p小于等于n-1)的数组元素平移到数组的最后。

【解题思路】本题采用"循环左移"的算法,即从第2个字符开始以后的每个字符都依次前移一个字符,而原来的第1个字符放在串中的最后一个字符。当要平移p个字符时,则要进行p次的循环左移。

题型八：数组去掉值重复的元素

9. 请编写函数fun，该函数的功能是：删去一维数组中所有相同的数，使之只剩一个。数组中的数已按由小到大的顺序排列，函数返回删除后数组中数据的个数。

由于数组是已经排好序的，相同的指定在一起，所以从前往后比，只要发现一个不和前面相同，后面就不再会有和前面相同的了。

题目中把准备保存下来的数存着t中，然后他后面的数顺序与他比较，如果不相等，那么就把这个数存起来，此时数组下标用另一个j来表示，只要出现不相等的情况，j才++，同时t换成这个和他不相等的新数。

提示：如果没排好序的我们可以先排序然后进行上面的操作。

题型九：数组元素的查找

10.请编写函数fun，函数的功能是查找x在s所指数组中下标的位置作为函数值返回，若x不存在，则返回-1。

查找数组元素值为x的下标，只需要把数组的每个元素a[i]（i从0到N-1）与x比较，如果相等则返回i的值，否则返回-1。

注意：改错中还有一个二分查找法需要掌握。

题型十：二维数组周边元素

11.下列程序定义了的二维数组,并在主函数中赋值。请编写函数fun,函数的功能是:求出数组周边元素的平均值并作为函数值返回给主函数中的s。例如,若a数组中的值为:

该题采用逐一判断的方式,周边元素的下标一定有一个是0或N-1,所以只要下标中有一个为0或N-1,那么它一定是周边元素。计算周边元素个数的方式是当给av加一个值时,k也加1,k也可用2*N+2*N-4求得。

题型十一：二维数组对角线、上三角和下三角元素的操作

12．程序定义了N×N的二维数组，并在主函数中自动赋值。请编写函数fun（int a[][N],int n）,该函数的功能是：使数组左下半三角元素中的值乘以n。例如：或n的值为3，a数组中的值为

则返回主程序后a数组中的值应为：

针对二维数组元素a[i][j],如果i>=j，也即行号大于等于列号时，是对角线下半三角的元素，相反i<=j，也即行号小于等于列号时，是对角线上半三角的元素，而i==j，即行号等于列号时，正好是对角线上的元素。

题型十二：二维数组转一维数组

13、请编写函数fun, 函数的功能是: 将M行N列的二维数组中的数据,按行的顺序依次放到一维数组中, 一维数组中数据的个数存放在形参n所指的存储单元中。

【解题思路】我们可以用两个循环来处理问题,由于是按行的顺序取出,所以第1个循环用于控制行下标,第2个循环用于控制列下标;

若改成按列的顺序取出,则循环应改成：

题型十三：二维数组转置问题（即行列互换）

【解题思路】行列数相等的二维数组的转置就是行列互换,即转置后的第i行第j列正好对应原矩阵的第j行第i列。

（1）若要将矩阵a转置后还存入a中,可用程序:

注意,第2个循环的初值。

（2）若要将矩阵a转置后存入c中:

注意,数组c和a的下标。

题型十四：数字字符串转整数

15、请编写一个函数fun，它的功能是：将一个数字字符串转换为一个整数(不得调用C语言提供的将字符串转换为整数的函数)。例如，若输入字符串"-1234",则函数把它转换为整数值 -1234。函数fun中给出的语句仅供参考。

【解题思路】if( )的作用是判断它应该是正数还是负数，变量t为1或-1作为符号标示。while( )循环的作用是将字符串转成相应的整数。

注意: p[i]的值是一个字符(如'9'、'4'),并不是一个数,要将其转成相应的数字必须令其减去'0'(不是'\0')，即*p-'0' 就得到*p这个字符的相应数字，如'0'-'0'=0、'8'-'0'=8等。

题型十五：“回文”字符串

16、请编写函数fun, 函数的功能是: 判断字符串是否为回文?若是, 函数返回1，主函数中输出: YES, 否则返回0, 主函数中输出NO。回文是指顺读和倒读都一样的字符串。

题型十六：字符串统计问题

【解题思路】26个字母的个数在pp所指数组中为0-25，其中数组下标可以通过某一个字符的ASCII值减去97或直接减'a'也可以，就可以得出该字符出现次数存放的位置。例如：字符为b，那么位置为'b'-'a'=1，就是实际存放的位置。

18. 编写一个函数，该函数可以统计一个长度为2的字符串在另一个字符串中出现的次数。

主字符串从第一个字符开始，不断循环直到结束，在循环中让指针p指向主字符串的当前位置，而指针r每次都重新指向子字符串的首地址，比较p和r指向的值是否相等，如果相等，需要比较后面的是否还相等，故p和r同时++指向后面一个字符，如果到r指向的值为’\0’前面都相等，那么说明找到一个，n+1；如果其中出现不相等的情况，则进入下一次外层循环，主字符串从下一个字符开始重新比较。

19.请编写函数fun，该函数的功能是：统计一行字符串中单词的个数，作为函数值返回。一行字符串在主函数中输入，规定所有单词由小写字母组成，单词之间由若干个空格隔开，一行的开始和结束都没有空格。

单词以空格隔开，加上最后一个单词是字符串的结尾，所以只需要判断当前的下一个字符是不是空格或者’\0’,如果是说明前面是一个单词。

题型十七：字符串指定字符删除

20、假定输入的字符串中只包含字母和*号。请编写函数fun，它的功能是：删除字符串中所有的*号。在编写函数时，不得使用C语言提供的字符串函数。

【解题思路】（1）本题中是删除全部字符('*')，所以用循环从字符串的开始往后逐个进行比较，若不是要删除的字符(用if(a[i]!='*')来控制)则保留。注意在保存的时候，下标变量j要从0开始，最后还要加上字符串结束符'\0'。

（2）此类题可以多种形式出现，以字符串中第一个字母和最后一个字母为坐标，如：只删除前导*，只删除后面所有*，只删除中间部分的*等等。通用的方法是如何定位第一个字母和最后一个字母，以它们作为起始点，通过循环追加来完成。

21、假定输入的字符串中只包含字母和*号。请编写函数fun，它的功能是：使字符串中尾部的*号不得多于n个;若多于n个，则删除多余的*号;若少于或等于n个，则什么也不做, 字符串中间和前面的*号不删除。

【解题思路】（1）while()循环的作用是计算出字符串中前部星号的个数;

（2）if( )的作用是判断*号个数是否大于n个,若是则只保留n个星号,即从字符串前部的倒数第n个星号到最后一个字符都存入数组a中,最后记得在字符串末尾加上结束标志位。

题型十八：字符串数组最值

22.编写一个函数，从传入的num个字符串中找出最长的一个字符串，传回该串地址（用****作为结束标志）。

思路同一位数组求最值，先把第一个字符串当成要的最值，然后拿其他的和他进行比较，此处strlen是求字符串的长度，所以最后求出的是字符最长的字符串，如果用strcmp可以去比较字符串的大小。同样用这样的方法可以考虑字符串的排序。方法同一维数组。

23. 请编写一个函数fun(char *s),该函数的功能是把字符串中的内容逆置。

例如：字符串中原有的字符为abcdefg，则调用该函数后，串中的内容为gfedcba。

要把字符串逆置其实就是以中间元素为对称轴对调，只需要将第一个字符和最后一个字符交换，第二个字符和倒数第二个字符交换，以此类推，所以题目中将s[i]和s[m]交换，i是从0到整个长度的一半，m是从整个字符串的长度到整个长度的一半。

注意：这个循环的次数一定要限制为整个字符串长度的一半，如果为字符串的长度那么相当于掉了两次，最后又回到刚开始的情况。

题型二十：字符串的连接

24. 编写一个函数fun,它的功能是:实现两个字符串的连接(不使用库函数strcat),即把p2所指的字符串连接到p1所指的字符串后。

(1) 让指针p指向第一个字符串的最后，即’\0’的位置；

(2) 将第二个字符串的各个字符依次加在后面；

(3) 最后在加上’\0’代表字符串结束。

题型二十一：结构体数组求最值

25、学生的记录由学号和成绩组成，N名学生的数据已在主函数中放入结构体数组s中,请编写函数fun，它的功能是：把分数最高的学生数据放在b所指的数组中,注意：分数最高的学生可能不止一个，函数返回分数最高的学生的人数。

【解题思路】（1）对于如何找出数组中最大值的操作，前面涉及过，对结构体数组进行类似操作也可采用同样方法。

（2）第1个for语句的作用是找出最大值；第2个循环的作用是找出与max相等的成绩(即最高成绩)的学生记录，并存入b中。对于结构体类型的数组来说，每个元素均由两个成员组成，其中s是成绩，因此我们只需要对其中成绩成员s进行访问，如a[i].s

题型二十二：结构体数组排序

27、N名学生的成绩已在主函数中放入一个带头节点的链表结构中,h指向链表的头节点。请编写函数fun，它的功能是：求出平均分，由函数值返回。

【解题思路】（1）本题是考查链表问题,所以,一定要弄清表示初始指针变量p指向下一个"节点"的方法及表示结束的判断。

（2）因为"头结点"中没有数值，所以程序中让p直接指向"头节点"的下一个节点，使用语句STREC *p=h->next，当然也可将p一开始指向"头节点"，即STREC*p=h，然后再p=p->next。

28. 编写函数fun，它的功能是：求Fibonacci数列中大于t的最小的一个数，结果由函数返回。其中Fibonacci数列F(n)的定义为：

当前项等于前面两项之和，然后把前面的第二项改为当前的前面第一项，把当前项改为前面的第二项。如此循环。

提示：用递归写是不是更简单更好理解。

符号的有限集合 （是一个集合，既然是集合那么就是有限的）

符号: 可以互相区分的记号或元素 （每个符号都是不同的）

不同语言有不同的字母表 （不同的自然语言有着不同的符号集合）

Σ={0, 1}表示二进制数的字母表 （组成二进制的所有符号的集合）

Σ={a, b, c,…,z}表示英语的字母表 （26个英语字母是英语的基本符号）

字母表上的符号的有穷序列,也称为句子

空符号串ε不包含任何符号的符号串，是任何Σ上的符号串 （相当于1 ， i ，E 等基本单元）

（实数的基本单位，虚数的基本单位，矩阵的基本单位）

（引入连接的目的就是通过组合的方式增加可能的组合方式来拥有更多的含义）

符号串α、β的连接，是把β的符号写在α的符号之后得到的符号串αβ

注：εα = αε = α （空串和任何字符串拼接都不变）

符号串α自身连接n次得到的符号串αα…αα (n个α) 表示为 α^n （类比乘法的幂）（类比乘方）

表示符号串中包含符号的个数 (符号可以类比数值的绝对值)

（这里的| |符号就是求字符串中的元素个数）

符号串中的连续子序列 （强调一点，这个序列是连续的）

x=αβδ，则β是x的一个子串

删去符号串 s 尾部的大于等于0个 符号得到的符号串

删去符号串 s 头部的大于等于0 个 符号得到的符号串

删去多于零个字符(非空) （类比真子集的概念，就是必须要删除字符，不能一个字符也不删）

对于w=uv，u是前缀，v是后缀

一般的集合操作+ 和 \cdot （类比点乘）

（需要将符号组合在一起，形成符号串，来表示更多含义）

Σ*: 表示由字母表Σ中的符号组成的符号串集合

（先写出所有的符号串的长度，然后选取字母表中的任意可能的符号进行组合得到符号串）

Σ^* 和Σ^+ 分别称为Kleene（克莱因）闭包(星闭包)和(正闭包)

语言就是某个字母表上的符号串的集合

（是一个集合，集合的元素一个字母表中的符号串）

任何一个语言都是 Σ^* 的一个子集

（原因是Σ^*是所有可能字符串的全集，语言需要选取需要的，合法的字符串）

（想一想C 语言中的变量名不能以数字开始，可以含有下滑线，不可以包含 - 杠号）

既然语言是符号串的集合，那么符号串集合中的各种运算也可用于语言，如并、交、减

同样也可以定义语言上的连接、幂、闭包等

（ L^+是除去空字符串后的集合 ）

把L和D两个字母表看作是长度为1的字符串集合，即为两个语言，下列运算的结果是什么？

L ∪ D ： 类比求集合的并集 （排列组合中的加法）

LD ： 类比求集合的交集 （排列组合中的乘法）

• 如果语言是有穷的(只包含有穷个句子)，可以将所有的句子列出来 （有限个，可以全部列举出来）
• 如果语言是无穷的，则要找出语言的有穷表示 （找到最少的有限表示）

语言中的每个句子可以用严格定义的规则来构造 （类比英语中的语法） （根据规则直接生成）

用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，

若不属于，要么能停止并回答“不是”，要么永远继续下去 （停下，或者永远继续下去）

（给出所有的可能，判别“是”，还是 “不是”，挑选合法符号串的一个过程）

（筛选，通过已有的规范来识别）

（最大的语法单位 是句子）

V_N 是非终结符号集

(就是将词汇表拆成两个没有交集的部分)

P={α→β|α至少包含一个非终结符号}

（左边是更大的语法单元）

文法理论是乔姆斯基在上世纪50年代提出的，包含四类形式文法理论

在编译原理中，主要用到的是上下文无关文法和正规文法(也叫正则文法)

（一层一层的进行抽象）

（通过非终结符号以产生式规则来产生终结符号）

（开始符号就是最大的语法单元）

下面是一些十分抽象的定义 ：

（expression 是一个较大的语法单位：叫做开始符号）

（a*b+c*d 乘法和除法连接的一个单元叫做项，通过加法和减法连接的叫多项式）

（表达式是term 项组成的）

（因子可以通过括号括上一个表达式组成）

（因子可以由id 组成）

（—>就是变换的规则）

用文法“生成”语言的句子(符号串)

从开始符号S形成的串开始，对串中的每个子串α，如果在P中有规则α→β，则α可以替换为β，如此重复进行。

当串中的每个符号都是终结符号的时候，重写结束，称最后得到的串可以从文法生成。

向右的过程就是一种生成展开的过程

产生所有用+, * 运算和括号构成的算术表达式的文法(就是各种符号串的组合规则)

这个文法的好处是乘法的优先级比加法高(与example 1相比)

VT={所有的名词和动词}

(指把产生式的右部γ替换产生式的左部A)

推导 (0步或多步直接推导)

(推导的中间过程就是句型)

如果α是一个句型，并且 α∈V_T* ，则称α是一个句子，即只包含终结符号的句型

（推导到不能再替换了，就是一个句子）

（感觉在学英语语法。。。。）

文法产生的语言L(G)={α|α是G的句子}

（所有句子的集合就是语言）

以有限的规则描述无限的语言现象(语言的有穷描述)

有限：产生式集合、终结符集合、非终结符集合

无限：可以导出无穷多个句子(L也可是有穷)

如果文法中有递归，就可以用有限的文法产生无限的句子

通过有限规则把握无限句子，显示了乔姆斯基文法的威力，也从一个侧面证实了小孩可以容易学好语言

C++中的string类 翻译过来就是字符串类型 但是它可不是一个平平无奇的字符串 它具有像线性表一样的增删查改的功能 会自动扩容 还支持迭代器遍历 功能可谓十分齐全 下面就来实现它

以及目录中的相关方法、_str是字符指针指向一块用来存储字符串的空间 、_size是用来记录字符串的有效字符的个数、_capacity是用来记录当前空间可以存放多少个字符（容量）

上面介绍了string 类的成员变量 那么构造函数就要对其进行初始化咯

实参传过来的必须是字符串，所以用字符指针接收，细节一点，就是用const修饰一下*str这样实参就不能在构造函数中被改变

然后就用strlen函数计算出传过来的字符串的长度，让该类中的成员变量（属性）_size和_capacity都等于该长度，然后再开辟出比容量大一的空间来存储我们要所要构造的字符串。最后一步就是把实参的字符串拷贝到我们新开辟的空间中；这一波操作下来就构造好了一个string对象，该对象（字符串）的内容，空间大小，长度都是和我们初始化时给的参数一样的了

关于这里为什么要开辟_capacity+1个字符的空间，也不一定非得是这样，只要逻辑上走得通都可以；这里我定义的_capacity 是可以存储有效字符的个数，不包括\0在内，但是字符串是以\0 作为结尾标志的，所以要多开辟一个字节的空间用来存放\0。

二、拷贝构造函数（传统写法和现代写法）

拷贝构造函数就是拿一个已经创建了初始化好了的对象，去初始化新定义的对象。

注意：这里的拷贝够造必须是深拷贝（所有的内容相同，但是原来的和拷贝的是并不是同一个），不能是浅拷贝（光是值的拷贝）。（自身理解，若有考虑不周，还望体谅）

但是这里的拷贝构造有两种写法 传统写法及现代写法

思路：开辟空间，把用来构造的对象的数据一一复制给自己

以上面的例子为例说明：

思路：与传统方法不同，传统方法是自己一一去实现拷贝，但是现代方法比较懒，它调写好的构造函数去帮自己构造出一个与传过来的对象一样的对象，在将构造出来的对象的数据和自己交换。

注：代码中的三个swap可以合并成一个函数简化代码（标准库里也是这样的）：

这里需要注意的是自身的_str必须要初始化，不能是随机的！！！

因为利用构造函数构造出来的对象临时tmp出来作用域会自动销毁，那么就会去调用析构函数，但是这里我们把本身对象和临时对象的_str交换了，所以tmp调用析构函数的时候，就是去释放本身对象中_str指向的空间，那么如果本身对象的_str没有初始化指向的就是随机空间是野指针，释放野指针指向的空间是会报错的，所以必须初始化_str 为空指针，这样就不会出错了。

最后对两者进行对比一下：传统写法比较呆板，现代写法比较新颖，也比较简洁

析构函数就比较简单了 ，释放掉_str指向的空间，并将_str置空即可

这里的按下标访问或者修改就是运算符重载的知识了

利用[]的运算符重载即可实现按下标访问或者修改

一、访问的是非const对象

对于非const对象我们可读可写 那么就是返回的就是非const的引用类型

二、访问的是const对象

1、对于const对象，只能读，不能写，那么其[]的运算符重载函数就要用const修饰，const修饰的函数或者接口，修饰的是隐含的this指针指向的对象（*this），所指向对象的成员变量不可以通过该函数或接口改变，起到了保护作用。

2、既然是只读，而返回的是引用，但又不能通过返回的引用去改变对象成员变量，所以引用也要用const来修饰

五、赋值操作（传统写法和现代写法）

赋值操作可以实现可以拿对象赋值给对象

也分传统写法和现代写法，传统写法就是按部就班的走，现代写法就是借助构造函数构造对象在交换

思路：先释放原来的空间，在开辟新的空间，把str对象的_str里的数据拷贝到自己的_str里，再让_size和_capacity都与str对象的_size和_capacity相同

思路：让形参是一个值而不是引用，那么传参的时候编译器就会调用上面的拷贝构造（深拷贝）去构造出与实参有着相同属性的形参，绕后再让自身对象的各个成员变量（属性）一一交换就好了，并且不用去释放空间，因为形参是局部变量出来定义域会自动调用析构函数清理数据，而我们经过交换把自己的各个属性都给了形参，形参就会帮我们调用析构函数自动清理原来的数据了，很棒！

在字符串的尾部插入数据，可以是字符，也可以是字符串。

既然是插入单个字符就是先判断容量够不够，不够就进行扩容，再把结束标准\0设置好，最后把字符插入即可。

下标问题：这里的_size表示的是有效字符的个数，因为小标从0开始，所以最后一个有效字符即使_str[size-1]了，那么_str[_size]就是\0了。我们插入字符就要把\0往后挪一个字符的位置就是上面的 _str[_size + 1] = '\0'; 然后在\0原来的位置放我们插入的字符_str[_size]

注意：这里的扩容最好用strncpy 否则特定情况会出bug 下面会详细提到

实现一个尾插字符串的函数append(标准库也有的）

append函数的实现思路也是先判断是否需要扩容，然后把要插入的字符串拷贝到对象的_str中更新_size(插入数据的思路都是大同小异的)

七、加等字符和加等字符串操作

加等字符和加等字符串的操作是和上面的插入字符和字符串的操作一样的 就可以复用上面的pushback 和 append 来实现他们 只是函数名不同，内在的实现逻辑是相同的

因为string是类似线性表的，可以动态扩容，每次插入数据都需要判断是否需要进行扩容，上面那么多的插入，都需要判断是否需要扩容，那么就可以把扩容写成一个成员函数，需要扩容的时候调用它即可。

这里的reserve只是负责开辟空间，不负责初始化空间，只是_capacity会改变，_size是不会改变的

reserve这里就有细节值得扣了，就是上面讲的最好用strncpy不要用strcpy的原因所在

问题就是：当我们调用了resize之后如果没有个默认的初始化空间的字符，就是默认的'\0'；或者说我们自己给的初始化空间的字符就是‘\0’,之后再调用reserve就会出现bug了

与reserve不同的是，resize 是开空间并且初始化的，给一个字符，将开辟出来的多于的空间用给的字符填充，更新_size，更新_capacity.

这里是复用了reserve进行扩容然后用memset去初始化多余的空间，初始化空间的范围是

(_str + _size,ch, n-_size)，还有考虑缩容的情况，如果是n小于_capacity就是缩容了，直接在n下标对应的空间放上一颗零鸭蛋即可，最后更新_size

这个就比较简单了 直接写个成员函数，返回_size 即可

十一、获取成员变量_str的函数c_str()

这个也比较好实现 写个成员函数返回_str即可

随机插入也是string具有的功能，包括插入字符和字符串，插入的方法有三种。

通过对下标对数据进行挪动，在哪插入就从哪开始把数据往后挪动，空出位置来插入新数据

1.有缺陷的下标法 （不能是从下标为0的位置插入）

2.没有缺陷的下标法（可以在任意下标进行插入）

指针法就直接是对指针指向的数据进行操作了，就没有数的转化了，就不用担心-1的情况了。

这里的两种下标法只是四条代码不同,方法1 是让end等于_size下标（对应的\0），然后让

这样如果是从0开始插入数据，end最后就会变成0 ，最小的情况即使end变成0 ，是不会到-1去的，所以就很好地避开了-1的情况，就解决了缺陷；

具体步骤可以参考俺画的图（老费劲了）

下标法2是怎么解决下标法1的缺陷的具体图解（瞧一瞧吧）：

注意：这里也有细节要扣，end是用来记录原来字符串的\0 的位置的，这里的end的初始化要在判断是否扩容的后面进行，否则会出现野指针的问题。因为如果要扩容的话，就会开辟新的空间然后把原来的数据拷贝到新空间，然后把这块空间赋值给原来的_str，相当于是内容没有变，容量变了，空间地址也变了，扩容前后是两块不同的空间，如果在判断扩容之前就初始化了end，那么如果下面进行了扩容_str就会是另一块新的空间了，那么后面循环里对end进行的操作就是非法的了，为什么呢？

因为扩容后是_str指向的是新空间，end本应该新空间中数据中\0的位置的指针，但是在扩容前就初始化了end的话那么end就是扩容前空间中数据中'\0'位置的指针了，在扩容后end还是指向原来空间中\0的位置，但是原来的空间已经被释放了，你这个时候再用end去访问原来的空间就是非法的，这时的end指针就是大名鼎鼎的“野指针”了！！！

在写完随机插入字符的函数后，再写随机插入字符串的函数后，会有一个类比的思想，就是把在插入字符函数中的    _str[end] = _str[end - 1];基础之上想着，既然是插入字符串，那么就要从\0开始往前直到pos位置的数据全部往后挪动插入字符串的长度个位置，也就是

这里是不能想当然地写的，我们要知道把数据往后挪插入字符串长度个距离，两个方括号里的数据差就要是字符串的长度，_str[end+len] = _str[end - 1];中很明显差值不是len 而是len+1

删除数据的思路与插入数据的思路相似，也是通过挪动数据，对要删除的数据进行覆盖处理，这里是用的strcpy来实现数据的挪动

1.pos位置后剩下的字符个数小于要删除的字符个数

这种情况直接就把下标为pos的位置放上\0 即可，即使代表把pos位置之后的所有数据全部删除

2.pos位置之后剩下的字符个数大于要删除的字符个数

这种情况就是把从下标从pos+len的位置往后的字符全部拷贝到从pos下标位置开始往后的空间中

十四、查找单个字符和子串

这里用到了strstr函数来实现找子串的功能

遍历思想，如果找到了就返回下标，否则返回string中的npos （无符号整形的-1 ）

十五、简易迭代器遍历的实现

然后各自写两个函数begin（）和end（）作为迭代器的开始和结束

在函数中使用实现的简易的迭代器去遍历输出字符串

实现像比较数字一样比较类（字符串）的大小

这里用到了strcmp来实现

//比较两个字符串 可以用函数strcmp
 

 实现了大于小于等于，剩下的借口就可以复用他们来实现了 
 


 

 
 


 

十七、类的直接输入输出

 
 

 实现像基本类型一样直接输出string对象总的字符串
 
 

 
//ch++; 因为这里是范围for 所以不用自己写加加 他自己会自动加的
 

 这里要返回的是输出流的引用，使得可以连续地输出，out 是ostream的对象。
 
 

 
//如果是本来就有数据的字符串再输入 那就要把原来的数据清理掉 然后size变成0
 

  注意这里不能直接用in来输入，因为in遇到字符'\0'和字符'\n'就会自动忽略，然后程序就不动了，崩了。要用ostream类的in对象的get方法来接收输入的值，相当于C语言中的getchar（），可以接收\n 和 \0.除了EOF其他都可以接收。 
 
 

十八、标准库中getline简易的实现

 
 

 getline 是输入一个串 要包括空格在内 cin和cout 都是遇到\n 和 \0 就停止的，根据上面的输入可以改变一下条件实现输入的是一个可以包括空格的字符串，那就是把while里的ch！= '\0' 去掉就可以了。
 

好了 本文到此就结束了~

如果喜欢的话就留下你来过的痕迹吧！