1.STL 源码剖析:sort
2.c语言中预处理命令都有哪些
3.c语言编程题打印出所有的案例“水仙花数”所谓“水仙花数”是指一个三位数其各位数字立方和等于该数本身
STL 源码剖析:sort
我大抵是太闲了。
更好的源码源代阅读体验。
sort 作为最常用的码案 STL 之一,大多数人对于其了解仅限于快速排序。案例
听说其内部实现还包括插入排序和堆排序,源码源代于是码案armadillo源码下载很好奇,决定通过源代码一探究竟。案例
个人习惯使用 DEV-C++,源码源代不知道其他的码案编译器会不会有所不同,现阶段也不是案例很关心。
这个文章并不是源码源代析完之后的总结,而是码案边剖边写。不免有个人的案例猜测。而且由于本人英语极其差劲,源码源代大抵会犯一些憨憨错误。码案
源码部分sort
首先,在 Dev 中输入以下代码:
然后按住 ctrl,鼠标左键sort,就可以跳转到头文件 stl_algo.h,并可以看到这个:
注释、模板和函数参数不再解释,我们需要关注的是函数体。
但是,中间那一段没看懂……
点进去,是一堆看不懂的#define。
查了一下,最牛网站源码感觉这东西不是我这个菜鸡能掌握的。
有兴趣的 戳这里。
那么接下来,就应该去到函数__sort 来一探究竟了。
__sort
通过同样的方法,继续在stl_algo.h 里找到 __sort 的源代码。
同样,只看函数体部分。
一般来说,sort(a,a+n) 是对于区间 [公式] 进行排序,所以排序的前提是 __first != __last。
如果能排序,那么通过两种方式:
一部分一部分的看。
__introsort_loop
最上边注释的翻译:这是排序例程的帮助程序函数。
在传参时,除了首尾迭代器和排序方式,还传了一个std::__lg(__last - __first) * 2,对应 __depth_limit。
while 表示,当区间长度太小时,不进行排序。
_S_threshold 是一个由 enum 定义的数,好像是叫枚举类型。
当__depth_limit 为 [公式] 时,也就是王者传奇游戏源码迭代次数较多时,不使用 __introsort_loop,而是使用 __partial_sort(部分排序)。
然后通过__unguarded_partition_pivot,得到一个奇怪的位置(这个函数的翻译是无防护分区枢轴)。
然后递归处理这个奇怪的位置到末位置,再更新末位置,继续循环。
鉴于本人比较好奇无防护分区枢轴是什么,于是先看的__unguarded_partition_pivot。
__unguarded_partition_pivot
首先,找到了中间点。
然后__move_median_to_first(把中间的数移到第一位)。
最后返回__unguarded_partition。
__move_median_to_first
这里的中间数,并不是数列的中间数,而是三个迭代器的中间值。
这三个迭代器分别指向:第二个数,中间的数,最后一个数。
至于为什么取中间的数,暂时还不是很清楚。
`__unguarded_partition`
传参传来的序列第二位到最后。
看着看着,我好像悟了。
这里应该就是刷赞的源码实现快速排序的部分。
上边的__move_median_to_first 是为了防止特殊数据卡 [公式] 。经过移动的话,第一个位置就不会是最小值,放在左半序列的数也就不会为 [公式] 。
这样的话,__unguarded_partition 就是快排的主体。
那么,接下来该去看部分排序了。
__partial_sort
这里浅显的理解为堆排序,至于具体实现,在stl_heap.h 里,不属于我们的讨论范围。
(绝对不是因为我懒。)
这样的话,__introsort_loop 就结束了。下一步就要回到 __sort。
__final_insertion_sort
其中某常量为enum { _S_threshold = };。
其中实现的函数有两个:
__insertion_sort
其中的__comp 依然按照默认排序方式 < 来理解。
_GLIBCXX_MOVE_BACKWARD3
进入到_GLIBCXX_MOVE_BACKWARD3,是一个神奇的 #define:
其上就是move_backward:
上边的注释翻译为:
__unguarded_linear_insert
翻译为“无防护线性插入”,应该是指直接插入吧。
当__last 的值比前边元素的值小的时候,就一直进行交换,最后把 __last 放到对应的位置。
__unguarded_insertion_sort
就是可视源码篇辑直接对区间的每个元素进行插入。
总结
到这里,sort 的源代码就剖完了(除了堆的那部分)。
虽然没怎么看懂,但也理解了,sort 的源码是在快排的基础上,通过堆排序和插入排序来维护时间复杂度的稳定,不至于退化为 [公式] 。
鬼知道我写这么多是为了干嘛……
c语言中预处理命令都有哪些
我们可以在C源程序中插入传给编译程序的各中指令,这些指令被称为预处理器指令,它们扩充了程序设计的环境。现把常用的预处理命令总结如下:
1. 预处理程序
按照ANSI标准的定义,预处理程序应该处理以下指令:
#if #ifdef #ifndef #else #elif
#endif
#define
#undef
#line
#error
#pragma
#include
显然,上述所有的个预处理指令都以符号#开始,,每条预处理指令必须独占一行。
2. #define
#define指令定义一个标识符和一个串(也就是字符集),在源程序中发现该标识符时,都用该串替换之。这种标识符称为宏名字,相应的替换称为宏代换。一般形式如下:
#define macro-name char-sequence
这种语句不用分号结尾。宏名字和串之间可以有多个空白符,但串开始后只能以新行终止。
例如:我们使用LEFT代表1,用RIGHT代表0,我们使用两个#define指令:
#define LEFT 1
#define RIGHT 0
每当在源程序中遇到LEFT或RIGHT时,编译程序都用1或0替换。
定义一个宏名字之后,可以在其他宏定义中使用,例如:
#define ONE 1
#define TWO ONE+ONE
#define THREE ONE+TWO
宏代换就是用相关的串替代标识符。因此,如果希望定义一条标准错误信息时,可以如下定义:
#define ERROR_MS “Standard error on input \n”
如果一个串长于一行,可在行尾用反斜线”\”续行,如下:
#define LONG_STRING “This is a very very long \
String that is used as an example”
3. #error
#error指令强制编译程序停止编译,它主要用于程序调试。#error指令的一般形式是:
#error error-message
注意,宏串error-message不用双引号包围。遇到#error指令时,错误信息被显示,可能同时还显示编译程序作者预先定义的其他内容。
4. #include
程序中的#include指令要求编译程序读入另一个源文件。被读入文件的名字必须用双引号(“”)或一对尖括号(<>)包围,例如:
#include “stdio.h”
#include <stdio.h>
都使C编译程序读入并编译头文件以用于I/O系统库函数。
包含文件中可以包含其他#include指令,称为嵌套包含。允许的最大嵌套深度随编译器而变。
文件名被双括号或尖括号包围决定了对指定文件的搜索方式。文件名被尖括号包围时,搜索按编译程序作者的定义进行,一般用于搜索某些专门放置包含文件的特殊目录。当文件名被双括号包围时,搜索按编译程序实时的规定进行,一般搜索当前目录。如未发现,再按尖括号包围时的办法重新搜索一次。
通常,绝大多数程序员使用尖括号包围标准的头文件,双引号用于包围与当前程序相关的文件名。
5. 条件编译指令
若干编译指令允许程序员有选择的编译程序源代码的不同部分,这种过程称为条件编译。
5.1#if、#else、#elif #endif
条件编译指令中最常用的或许是#if,#else,#elif和#endif。这些指令允许程序员根据常数表达式的结果有条件的包围部分代码。
#if的一般形式是:
#if constant-expression
Statement sequence
#endif
如#if后的常数表达式为真,则#if和#endif中间的代码被编译,否则忽略该代码段。#endif标记#if块的结束。
#else指令的作用与C语言的else相似,#if指令失败时它可以作为备选指令。例如:
#include <stdio.h>
#define MAX
Int main(void)
{
#if MAX>
printf(“Compiled for array greater than .\n”);
#else
printf(“Complied for small array.\n”);
#endif
return 0;
}
注意,#else既是标记#if块的结束,也标记#else块的开始。因为每个#if只能写一个#endif匹配。
#elif指令的意思是“否则,如果”,为多重编译选择建立一条if-else-if(如果-否则-如果链)。如果#if表达式为真,该代码块被编译,不测试其他#elif表达式。否则,序列中的下一块被测试,如果成功则编译之。一般形式如下:
#if expression
Statement sequence
#elif expression1
Statement sequence
#elif expression2
Statement sequence
.
.
.
#elif expression
Statement sequence
#endif
5.2#ifdef和#ifndef
条件编译的另一个方法是使用编译指令#ifdef和#ifndef,分别表示“如果已定义”和“如果未定义”。#ifdef的一般形式如下:
#ifdef macro-name
Statement sequence
#endif
如果macro-name原先已经被一个#define语句定义,则编译其中的代码块。
#ifndef的一般形式是:
#ifndef macro-name
Statement sequence
#endif
如果macro-name当前未被#define语句定义,则编译其中的代码块。
我认为,用这种,可以很方便的开启/关闭整个程序的某项特定功能。
#ifdef和#ifndef都可以使用#else或#elif语句。
#inlucde <stdio.h>
#define T
Int main(void)
{
#ifdef t
Printf(“Hi T\n”);
#else
Printf(“Hi anyone\n”);
#endif
#ifndef M
Printf(“M Not Defined\n”);
#endif
Return 0;
}
6. #undef
#undef指令删除前面定义的宏名字。也就是说,它“不定义”宏。一般形式为:
#undef macro-name
7. 使用defined
除#ifdef之外,还有另外一种确定是否定义宏名字的方法,即可以将#if指令与defined编译时操作符一起使用。defined操作符的一般形式如下:
defined macro-name
如果macro-name是当前定义的,则表达式为真,否则为假。
例如,确定宏MY是否定义,可以使用下列两种预处理命令之一:
#if defined MY
或
#ifdef MY
也可以在defined之前加上感叹号”!”来反转相应的条件。例如,只有在DEBUG未定义的情况下才编译。
#if !defined DEBUG
Printf(“Final Version!\n”);
#endif
使用defined的一个原因是,它允许由#elif语句确定的宏名字存在。
8. #line
#line指令改变__LINE__和__FILE__的内容。__LINE__和__FILE__都是编译程序中预定义的标识符。标识符__LINE__的内容是当前被编译代码行的行号,__FILE__的内容是当前被编译源文件的文件名。#line的一般形式是:
#line number “filename”
其中,number是正整数并变成__LINE__的新值;可选的“filename”是合法文件标识符并变成__FILE__的新值。#line主要用于调试和特殊应用。
9. #pragma
#pragma是编译程序实现时定义的指令,它允许由此向编译程序传入各种指令。例如,一个编译程序可能具有支持跟踪程序执行的选项,此时可以用#pragma语句选择该功能。编译程序忽略其不支持的#pragma选项。#pragma提高C源程序对编译程序的可移植性。
. 预处理操作符#和##
有两个预处理操作符:#和##,它们可以在#define中使用。
操作符#通常称为字符串化的操作符,它把其后的串变成用双引号包围的串。例如:
#include <stdio.h>
#define mkstr(s) #s
int main(void)
{
Printf(mkstr(I like C));
Return 0;
}
预处理程序把以下的语句:
Printf(mkstr(I like C));
变成
Printf(“I like C”);
操作符##把两个标记拼在一起,形成一个新标记。例如:
#include <stdio.h>
#define concat(a,a) a##b
int main(void)
{
Int xy = ;
Printf(“%d”,concat(x,y));
Return 0;
}
预处理程序把以下语句:
Printf(“%d”,concat(x,y));
变成
Printf(“%d”,xy);
操作符#和##主要作用是允许预处理程序对付某些特殊情况,多数程序中并不需要。
. 预定义宏
C规范了5个固有的预定义宏,它们是:
__LINE__
__FILE__
__DATE__
__TIME__
__STDC__
__LINE__和__FILE__包含正在编译的程序的行号和文件名。
__DATE__和内容形如month/day/year(月/日/年)的串,代表源文件翻译成目标码的日期。
__TIME__中的串代表源代码编译成目标码的时间,形如hour:minute:second(时:分:秒)
如果__STDC__的内容是十进制常数1,则表示编译程序的实现符合标准C。
c语言编程题打印出所有的“水仙花数”所谓“水仙花数”是指一个三位数其各位数字立方和等于该数本身
打印出所有的“水仙花数”,所谓“水仙花数”是指一个三位数,其各位数字立方和等于该数
本身。例如:是一个“水仙花数”,因为=1的三次方+5的三次方+3的三次方。
1.程序分析:利用for循环控制-个数,每个数分解出个位,十位,百位。
2.程序源代码:
main()
{
int i,j,k,n;
printf("'water flower'number is:");
for(n=;n<;n++)
{
i=n/;/*分解出百位*/
j=n/%;/*分解出十位*/
k=n%;/*分解出个位*/
if(i*+j*+k==i*i*i+j*j*j+k*k*k)
{
printf("%-5d",n);
}
}
printf("\n");
}