思路：如果当前元素大于最大数 max，则让第二大数等于原来的最大数 max，再把当前元素的值赋给 max。如果当前的元素大于等于第二大数secondMax的值而小于最大数max的值，则要把当前元素的值赋给 secondMax。

解法一： 扫描一次数组找出最大值；再扫描一次数组找出最小值。 比较次数2N-2 转载请标明出处，原文地址： 解法二： 将数组中相邻的两个数分在一组， 每次比较两个相邻的数，将较大值交换至这两个数的左边，较小值放于右边。 对大者组扫描一次找出最大值，对小者组扫描一次找出最小值。 比较1.5N-2次，但需要改变数组结构   解法三： 每次比较相邻两个数，较大者与MAX比较，较小者与MIN比较，找出最大值和最小值。 方法如下：先将一对元素互相进行比较，然后把最小值跟当前最小值进行比较，把最大值跟当前最大值进行比较。因此每两个元素需要3次比较。如果n为奇数，那么比较的次数是3*(n/2)次比较。如果n为偶数，那么比较的次数是3n/2-2次比较。因此，不管是n是奇数还是偶数，比较的次数至多是3*(n/2)，具体的代码如下：

给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求： 1、排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变 2、不能使用额外存储空间 例子如下 输入 0、3、0、2、1、0、0 输出 0、0、0、0、3、2、1 分析 此排序非传统意义上的排序，因为它要求排序前后非0元素的相对位置不变，或许叫做整理会更恰当一些。我们可以从后向前遍历整个数组，遇到某个位置i上的元素是非0元素时，如果arr[k]为0，则将arr[i]赋值给arr[k]，arr[i]赋值为0。实际上i是非0元素的下标，而k是0元素的下标。

4、找出绝对值最小的元素

给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列 -5、-3、-1、2、8 则返回1。 分析：由于给定序列是有序的，而这又是搜索问题，所以首先想到二分搜索法，只不过这个二分法比普通的二分法稍微麻烦点，可以分为下面几种情况     如果给定的序列中所有的数都是正数，那么数组的第一个元素即是结果。     如果给定的序列中所有的数都是负数，那么数组的最后一个元素即是结果。     如果给定的序列中既有正数又有负数，那么绝对值的最小值一定出现在正数和负数的分界处。 为什么？因为对于负数序列来说，右侧的数字比左侧的数字绝对值小，如上面的-5、-3、-1，而对于整整数来说，左边的数字绝对值小，比如上面的2、8，将这个思想用于二分搜索，可先判断中间元素和两侧元素的符号，然后根据符号决定搜索区间，逐步缩小搜索区间，直到只剩下两个元素。 单独设置一个函数用来判断两个整数的符号是否相同

6、从长度为n的数组（元素互不相同）中任意选择m个数的所有组合。 DFS

7、从长度为n的数组（元素有可能相同）中任意选择m个数的所有组合。 先对数组进行排序，然后设置一个标记pre，记录前一个选择的数字，然后进行比较。

8、三色旗排序问题 一个字符串Color，其中每个元素值为‘R‘’G’‘B’三者之一，实现把数组中元素重新排列为红、绿、蓝的顺序，所有红色在前，绿色其后，蓝色最后，要如何移动次数才会最少，编写这么一个程序。 问题的解法很简单，您可以自己想像一下在移动旗子，从绳子开头进行，遇到红色往前移，遇到绿色留在中间，遇到蓝色往后移。 因为你最终的目的是为了让R、G、B成为有序排列，试想，如果第三步，gindex与bindex交换之前，万一bindex指向的是R，而gindex交换之后，gindex此刻指向的是R了，此时，gindex能动么？不能动啊，指向的是R，还得与rindex交换。

9、一个整型数组，含有N个数，将这N个数分成连续的M段，使得这M段每段的和中的最大值最小，输出最小值。（1<=N<=<=M<=N,每个数在1到10000之间）   POJ  3273 解题思路：不管分成多少段，每种分法和的最大值都在N个数的最大值和N个数的和之间，所求答案也在这之间。
我们可以以此为上下界，二分M段和的最大值进行尝试。对每次二分的值，将数组扫描累加。若当前和大于二分的这个值，则段数加一，由此统计出在当前值下，N个数能够分成的最小段数。若这个段数小于或等于M，则上界变为mid-1，并记下当前mid的值。否则，下界变为mid+1。继续二分，直到退出循环。最后记录的low值即为答案。

10、一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。 能否只用一个额外数组和少量其它空间实现。 分析：最原始的方法是检查每一个数 array[i] ，看是否左边的数都小于等于它，右边的数都大于等于它。这样做的话，要找出所有这样的数，时间复杂度为O(N^2)。 有了这样一个额外数组，当我们从头开始遍历原始数组时，我们保存一个当前最大值 max， 如果当前最大值刚好等于rightMin[i]， 那么这个最大值一定满足条件，还是刚才的例子。 第一个值是7，最大值也是7，因为7 不等于 2， 继续， 第二个值是10，最大值变成了10，但是10也不等于2，继续， 第三个值是2，最大值是10，但是10也不等于2，继续， 第四个值是6，最大值是10，但是10不等于6，继续， 第五个值是19，最大值变成了19，而且19也等于当前rightMin[4] = 19, 所以，满足条件。如此继续下去，后面的几个都满足。

+ .... + nk 状态表示：将n划分为k个数相加的组合方案数记为 q(n,k)。（相当于将n个苹果放入k个盘子） 状态转移： (1)若k>n，则盘子数大于苹果数，至少有k-n个空盘子，可以将其拿掉，对组合方案数无影响。 q(n,k) = q(n,n) (2)若k<=n，则盘子数小于等于苹果数，则分为两种情况 1.至少有一个盘子空着：q(n,k) = q(n,k-1)

12、整数的拆分问题 接着上一题，输出整数的所有划分方案

13、在数组中寻找和为给定值的组合 思路： 代码 14、字符串移动 字符串为*号和26个字母、阿拉伯数字的任意组合，把*号都移动到最左侧，把其他字母和数字都移到最右侧并保持相对顺序不变，返回字符*的个数，要求时间和空间复杂度最小。 第一种方法：跟上面的重排问题是一样的

时间复杂度O(N)，空间复杂度O(1) 15、求数组中两个元素差的最大值 后面的元素减去前面的元素（你可以认为你在炒股票，买入价格和卖出价格就是你的盈利），要求：O(N)时间复杂度，O(1)空间复杂度  思路：首先从包含两个元素的数组开始考虑问题，当这个包含两个元素的问题解决了，那么加一个新的元素会造成什么影响？要改变哪些值？每次都添加一个元素，每次都将这些可能的改变考虑进来，这样就能做到遍历整个数组的时候，问题就解决了。

16、求数组中两个元素差的最大值 前面的元素减去后面的元素，要求：O(N)时间复杂度，O(1)空间复杂度 思路：跟上一题的思路很相近

17、输入一个正数 n，输出所有和为 n 连续正数序列。  例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6 和 7-8。  方法一： 可以发现任意自然数序列其实是公差为1的等差数列，假设从i开始的连续k个数的和为n，即[i ,

方法二： 我们知道： 1+2 = 3； 4+5 = 9； 2+3+4 = 9。 等式的左边都是两个以上连续的自然数相加，那么是不是所有的整数都可以写成这样的形式呢？稍微考虑一下，我们发现，4和8等数不能写成这样的形式。 问题1：写一个程序，对于一个64位的正整数，输出它所有可能的连续自然数（两个以上）之和的算式。 问题2：大家在测试上面的程序的过程中，肯定会注意到有一些数字不能表达为一系列连续的自然数之和，例如32好像就找不到。那么，这样的数字有什么规律呢？能否证明你的结论？ 问题3：在64位正整数范围内，子序列数目最多的数是哪一个？这个问题要用程序蛮力搜索，恐怕要运行很长时间，能够用数学知识推导出来？ 问题1解答：对于任意的正整数n >=

由于账户到期或未成为会员，此博客已被关闭！

请移步 访问其他精彩内容。

如果你是此博客的主人(moocdaan1)，请及时联系我们充值

C语言中的数据类型分为：

• 构造类型：数组，结构体（struct），共用体（union）

C语言中没有字符串类型，字符串存放在字符数组中

gets() 类似于 getchar()，可以向缓冲区输入字符串和读取缓冲区中的字符串

使用 strcmp() 函数：可以比较两个字符串是否相等

比较规则：从左到右，依次比较各个字符的ASCII码大小

（1）初始化：可以直接赋值

3、改变习惯-字符数组赋值

5、两个搭配-字符数组赋值

1、函数返回值不是必须的，需要根据函数情况设置。

2、函数返回值需要是一个确定的类型，和定义的函数类型（默认是int类型）一致，以函数类型为准（不一致也可以，会以函数类型为准进行转换，可能会存在精度缺失问题）。

3、以 void 作为函数类型定义的函数，没有 return 语句，没有返回值

• 有参函数：有返回值；定义时必须指定参数数据类型（调用时传参要类型相同，或者相兼容–按照赋值规则进行转换）

VC++6.0调用顺序是自右向左

函数自己作为自己的参数

在主函数中调用自定义函数之前，需要先编写函数声明语句

如果自定义函数定义在main函数之前，调用时可以不添加声明语句
有参函数声明时，也可以不带参数

1、幂：n 的 m 次方计算函数

支持 int 类型数据

递归实现（递归效率低）

5、汉诺塔问题–递归——待运行，待思考

3.6 数组元素作参数

传递方式差异的本质原因：是否分配内存

• 前者的形参，会分配内存单元，形参与实参有着不同的内存单元
• 后者的形参，不会分配内存单元

注意：当参数为数组名时，不能获取数组长度，因为是地址传递，传来的参数相当于是指针，指向内存地址

1、局部变量、全局变量

在同一个程序中，局部变量和全局变量的变量名可以相同，系统会分配两个内存，二者并不冲突。

2、静态存储、动态存储

用户存储空间：程序区、静态存储区、动态存储区

static 变量（静态存储）不能做形参，动态存储可以做形参——auto/自动变量、形参 在内存的动态存储区

程序展示 static 变量值变化：

使用 extern 的情况：（和函数声明一样）

• 当全局变量定义在使用之后，可以通过 extern 关键字来进行声明
• 当全局变量定义在使用之前，不需要进行声明

4、多文件声明外部变量

希望外部变量只限于被本文件引用，而不能被其他文件引用——运行时会报错

6、内部函数、外部函数

使用 static 关键字定义的函数为内部函数，只能本文件内使用
使用 extern 关键字定义的函数为外部函数，可以省略该关键字（默认就是这个）【extern 关键字在函数内使用，而非全局使用】

指针：间接访问 | 存放地址

指针变量定义且初始化之后才能使用

5.1 取值操作符 *、取址操作符 &

指针变量：只能存放地址。若是将非地址赋值给指针变量，也会当成地址进行处理。
基类型：指针指向的变量的数据类型

二者优先级相同，但是结合方式：自右向左。

3、*、++ 优先级相同

++、* 优先级相同，结合方式：自左向右

• 数组和指针的指向都是地址
• 定义时，二者均分配了内存空间，但是指针的空间可以随时消除，数组空间不行
• 指针变量可以指向一个普通变量，也可以指向数组元素

引用一个数组元素，可以使用下标法、指针法

获取数组中的全部元素，有三种方法：

5.3 用数组名做参数

数组名作为实参时，要求形参的数据类型为指针类型——因为数组名作实参，传递的实际上是地址

指针作为实参时，要求形参的数据类型为指针类型

回顾：指针——地址，指针变量——存放地址的变量
关于 *pointer：在定义指针变量时，使用 *pointer；在取值时，也是用 pointer。此二者中， 的作用不同，前者是作为指针变量的标记符，后者是作为取值操作符。

作业——从10个数中取出最大、最小值（指针实现）

时间复杂度：O(n^2)，空间复杂度：O(0)

5.5【本章重点】小结

1-1 形参：数组名，实参：数组名

1-2 形参：数组名，实参：指针变量

2-1 形参：指针变量，实参：数组名

2-2 形参：指针变量，实参：指针变量

5.6【本章重点】多维数组、指针

二维数组：一个数组里面包含一个数组（A含有B）
三维数组：一个数组里面包含一个数组，被包含的数组里面又包含一个数组（A含有B，B含有C）

对于二维数组，地址如下：

对于二维数组，数值如下：

可以看出，第一行首地址和第二行首地址相差16字节（数组一行4个元素，一个元素4字节大小）

打印二维数组各个元素——指针实现

根据输入行数、列数，打印出该行该列对应的元素数值。

指针实现：明天实现代码

5.7【本章重点】字符串、指针

用字符串数组存放一个字符串，并输出该字符串。

1、数组存取字符串——用数组名指向首地址，获取字符串

用字符串数组存放一个字符串

疑问：定义数组的时候，是不是一定要指明长度？

2、指针存取字符串——用字符指针指向字符串

不定义字符数组，而是定义一个字符指针。使用字符指针指向字符串中的字符

指针方式存储字符串，实际上是两个步骤：
（1）存储字符串：存放在常量存储区，会分配一个内存单元
（2）将内存地址给指针变量
然后，就可以通过指针变量获取字符串数据了
这样一来，很明显，只能读不能写（因为常量存储区的不能修改）

3、获取字符串中的某个字符——下标法、指针法

将字符串A赋值给字符串B，得到A、B相同的结果。

5、字符指针变量做参数

将字符串A赋值给字符串B，得到A、B相同的结果。

字符串存放在常量存储区

通过汇编执行过程，可以看出二者的区别：*a = "string..." 实际上是将字符串在常量存储区的存储单元地址赋值给指针变量a（赋值的是地址）；后者不是赋值地址，而是真实的数据

8、【重要】字符指针变量、字符数组的讨论

函数指针：函数的入口地址

函数指针变量最常用的是把指针作为参数传递到其他函数，即函数指针变量作参数——传递的是函数入口地址

1、补充知识——预编译

# 代表预编译，宏概念

函数指针做其他函数的参数，可以方便业务管理。

如下图代码中，通过媒介process()函数控制三个函数（max()、min()、add()），方便管理

函数返回值可以是：void、整型、字符型、实型等，也可以是指针类型（即地址）

此类函数定义形式：类型名 *函数名(参数)

有若干个学生的成绩（每个学生4门课程），要求在用户输入学号之后，系统输出该学生的全部成绩。指针函数实现。

针对上例，找出有不及格课程的学生学号。

5、指针函数、函数指针

6、指针数组、指向指针的指针

例题2——指向指针的指针

从下面的汇编语句中，可以看出执行了4次偏移地址赋值：

（三）main() 函数的形参

main() 函数是由操作系统调用的，应用程序不会调用——main() 是应用程序的入口

指针数组做main()函数形参

main() 实际是有参数的：

运行结果：cmd 窗口运行

（五）指针运算（总结）

void：用于 函数返回值类型、函数参数类型，还可以用于指针类型。当参数类型为 void 时，可接收的参数类型任意
const：常量关键字，不能修改

（六）知识补充——memcpy

注意：第一个参数指向数据可读可写，第二个参数指向数据可读不可写

无参宏：宏名后不带参数

可用宏定义定义全局变量、定义数据类型

对输出格式进行宏定义，减少书写麻烦

对带参数的宏，调用时，需要进行：（1）宏展开；（2）实参代形参

注意：形参不分配内存单元，因此不要求定义数据类型；实参需要指定数据类型

值替换、值传递 的区别

9.3 宏定义替换表达式

由于替换时需要处理优先级问题，加大复杂性，还容易遗漏处理，因此不推荐使用宏定义替换表达式

注意：替换规则——直接替换，没有优先级处理

字符指针变量：分配内存

普通变量：指明数据类型；分配内存，值传递
指针变量：指明数据类型；分配内存？？不分配内存，值代替

函数的形参：分配内存，值传递
宏的形参：不分配内存，值代替

结构体：将不同数据类型的数据组合在一起

相当于面向对象语言中的 对象

1、定义结构体类型变量

• 获取结构体内的数据时，需要通过 . 属性获取每一个成员的数据：结构体变量名.成员名，而不能直接通过结构体变量名来获取
• 给结构体中的成员赋值时，也是上面的方式
• 如果成员本身也是结构体变量，那么进行取值和赋值的时候，也需要继续获取它的成员
• 可以引用结构体变量成员的地址、结构体变量的地址

结构体成员的操作类似 Object 对象

结构体数组：每一个数组元素都是一个结构体类型的。

和定义结构体变量一样，只需要指定变量为数组即可

例题：输入并输出三个学生的信息

3、【实战】：投票系统程序实现

10.3 结构指针：指向结构体类型数据 的指针

指向结构体类型数据 的指针：该结构体变量所占据的内存段的起始地址。

1、结构指针变量-赋值

把 结构体变量 的首地址赋值给指针变量

2、结构指针变量-访问成员

一般形式：pstr 为结构指针变量

1、【实战】：输出学生信息

题目：有一个结构体变量stu，内含学生学号、姓名、三门课程成绩。输出这些信息。

10.4 动态存储分配

C语言不允许动态定义数组长度

• 删除整个链表：直接将表头指针修改，就不能访问链表中其他结点，就相当于将链表消失了
• 删除某个元素：断开该元素前后指针连接，即可

【实战】-成绩管理系统

示例一：输入、输出学生信息
示例二：单链表中插入结点

10.2 共用体变量的引用

只有先定义了共用体变量，才能引用它。而且不能引用共用体变量，只能引用共用体变量中的成员。

10.3 共用体类型的特点

• 同一个内存段可以存放几种不同类型的成员
• 在每一瞬间，只能存放其中一种，而不是同时存放几种
  =>在共用体变量中，起作用的成员是最后一个存放的成员
• 共用体变量的地址、以及它的各个成员的地址，都是同一个地址
  =>因此，可以知道，共用体变量所占内存长度 = 占内存最大的成员的长度
• 不能对共用体变量名赋值，不能在定义共用体变量的时候对其初始化；也不能通过共用体变量名得到一个值
• 共用体变量不能做函数参数，也不能做函数返回值，但是可以使用指向共用体变量的指针
• 共用体类型可以出现在结构体类型的定义中
  结构体也可以出现在共用体类型的定义中
  数组也可以作为共用体的成员

10.4 【实战】-教务管理系统

第一行数据是学生的数据，第二行数据是教师的数据

当变量取值有限定的范围时，使用枚举类型更合适

• 应罗列出所有可用值，这些值叫“枚举元素”
• 枚举类型是一种基本数据类型，而不是构造类型（因为不可再分解）
• 在C语言中，枚举元素按照常量处理（枚举常量）：不能赋值。但是在编译时，会给枚举元素按照顺序赋值 0，1，2，3，4，5……
• 枚举值 可以比较（因为默认每个枚举值默认都有一个值，就上面的）
• 一个整数不能直接赋值给一个枚举变量？？？（本来不就是不能赋值吗）

不会有 j>LiLei（因为枚举范围最大是LiLei（4）），所以month[]中存储的是枚举元素

用typedef声明新的类型名，来代替已有的类型名

• typedef可以用来声明各种类型名，但是不能用来定义变量
• typedef声明类型时，只是声明了这个类型的一个别名，并不是创造新的类型
• 当不同源文件中都用到一个/些数据类型时，长用typedef声明这个/些数据类型，把它们单独放在一个文件中，然后在需要用的时候把这个文件通过#include命令包含进来

1、声明数据类型–就可以使用 数据类型 来定义变量了

2、声明结构类型–就可以使用 结构 来定义结构体类型变量了

3、声明数组类型–就可以使用 数组类型 来定义数组变量了

4、声明字符指针类型–就可以使用 字符指针类型 来定义字符指针了

5、声明指向函数的指针类型–

函数指针赋值和调用方式：

函数名、数组名都是首地址，可以直接作取地址用

（五）结构体、共用体 区别

（六）宏定义、typedef 区别

• #define可以定义全局变量，也可以声明数据类型

二者在声明数据类型上，作用相同，过程本质不同：

但是在声明指针类型时，有区别：

使用typedef，有利于程序的通用和移植