缥缈峰

感谢Faust撰写C函数调用，Faust是我教研室的同学，签南京中兴。
-------------------------------------------------------------------------------------------------
作者：Faust ( wsgfaust_AT_163_DOT_com )

   C中采用了不同的调用方式来调用函数，这里的函数调用概念可能与我们通常所理解的函数调用有所不同，它们指的是处理器在处理函数上的差异。理解这些不同的方式有助于我们来调试程序和链接我们的代码。在此我想讨论一下主要的四种函数调用方法以及之间的区别，它们是__stdcall、__cdecl、__fastcall、thiscall。当然，还有一些更加不常用的函数调用方法比如naked call我也将顺便提及。


   不同的函数调用方法之间的主要有以下一些区别：
① 当参数个数多于一个时，按照什么顺序把参数压入堆栈函数调用后
② 谁来恢复堆栈
③ 编译后的修饰名规则


__stdcall：将参数压栈是按PASCAL语言的顺序（从右到左），通常用于WINAPI中。它是由被调用者将参数从栈中清除的,所以它的编译文件比__cdecl小。__stdcall是Windows API函数中默认的调用约定，被调函数自己在退出时清空堆栈。这种调用方式不能实现变参函数，因为被调函数不能事先知道弹栈数量，但在主调函数中是可以做到的，因为参数数量由主调函数确定。VC将函数编译后会在函数名前面加上下划线前缀，在函数名后加上"@"和参数的字节数。如函数int func(int a,  double b)的修饰名是_func@12。
编译选项/Gz。


注意：在创建DLL时，一般使用__stdcall调用（Win32 Api方式），采用__functionname@number命名规则，因而各种语言间的DLL能互相调用。也就是说，DLL的编制与具体的编程语言及编译器无关，只要遵守DLL的开发规范和编程策略，并安排正确的调用接口，不管用何种编程语言编制的DLL都具有通用性。


__cdecl：是C语言采用的默认调用方法，参数按从右到左的顺序压入栈，由调用者把参数弹出栈,它的优点是支持printf这样的可变参数调用。一般可变参数函数的调用都采用这种方式，比如int __cdecl scanf (const char *format,…)。对于"C"，修饰名是在函数名前加下划线,如函数void test(void)的修饰名是__test。除非声明为 extern "C"，否则 C++ 函数将使用不同的名称修饰方案。
    编译选项/Gd。


   注意：CC++中的main(或wmain)函数的调用约定必须是__cdecl,不允许更改。


__fastcall：__fastcall调用较快，它通过CPU内部寄存器传递参数。头两个DWORD类型或者占更少字节的参数被放入ECX和EDX寄存器，其他剩下的参数按从右到左的顺序压入栈。由被调用者把参数弹出栈，对于“C”函数或者变量，修饰名以“@”为前缀，然后是函数名，接着是符号“@”及参数的字节数，如函数int func(int  a, double b)的修饰名是@func@12。
编译选项/Gr，通常减少执行时间。


   注意：在对用内联程序集语言编写的任意函数使用__fastcall 调用约定时，一定要小心。您对寄存器的使用可能与编译器对它们的使用发生冲突。Microsoft 不保证不同编译器版本之间的 __fastcall 调用约定的实现相同。例如，16 位编译器与 32 位编译器的实现就不同。因此当使用 __fastcall 命名约定时，请使用标准包含文件。否则将获取无法解析的外部引用。


   thiscall： 函数体 this指针默认通过ECX传递,其它参数从右到左入栈。thiscall是唯一一个不能明确指明的函数修饰，因为thiscall不是关键字。它是C++类成员函数缺省的调用约定。由于成员函数调用还有一个this指针，因此必须特殊处理。3
thiscall意味着：参数从右向左入栈，如果参数个数确定，this指针通过ecx传递给被调用者；如果参数个数不确定，this指针在所有参数压栈后被压入堆栈。对参数个数不定的，调用者清理堆栈，否则函数自己清理堆栈。


   nakedcall：
这是一个很少见的调用约定，一般程序设计者建议不要使用。编译器不会给这种函数增加初始化和清理代码，更特殊的是，你不能用return返回返回值，只能用插入汇编返回结果。这一般用于实模式驱动程序设计。
讲到自右至左我想到了一个关于求值顺序的问题，巧合（？？?）的是，在C中求值顺序也是从右至左（不知道和压栈顺序是怎样的关系？）。我找到一个小例子。
void main()
{
int i=8;
printf("%dn%dn%dn%dn",++i,--i,i++,i--);
}
如按照从右至左的顺序求值。运行结果应为：
8
7
7
8
如对printf语句中的++i，--i，i++，i--从左至右求值，结果应为：
9
8
8
9
   应特别注意的是，无论是从左至右求值， 还是自右至左求值，其输出顺序都是不变的， 即输出顺序总是和实参表中实参的顺序相同。由于Turbo C现定是自右至左求值，所以结果为8，7，7，8。


转载请注明出处，谢谢！

     感谢Chris写的这个章节，另外更多的热心人正在帮助我完成Job Hunting系列技术文章的编写，再次对大家表示深深的感谢。
     如果您对我们写的文章有什么意见和建议，请告诉我们，谢谢。
-------------------------------------------------------------------------------------------------
作者：Chris. LGH (Blog: http://chris.turbozv.com)


     在一般的C教科书中，可以见到6种类型修饰符，分别是: auto, const, register, static, volatile, extern.
     局部变量除非显式指明为static, 否则默认为auto，所以一般不会在代码中使用类型修饰符auto.
     在后编译器时代，优化器可以合理的分配寄存器，所以一般不会在代码中使用类型修饰符register.
     extern只用于声明全局变量，用法单一。
     本节将主要介绍const, static和volatile.


1. const
     首先需要注意的是，const修饰的是在它前面的类型，如果它前面没有类型，那它修饰的是紧跟着它的那个类型。
例如：
(a)const int i = 0; 和 (b)int const i = 0; 是完全一样的。
在(a)中，const前面没有类型，它就修饰它后面的那个int类型。在(b)中，const修饰它前面的int类型，两者没有任何区别。
再看另一个稍复杂一点的例子，下面两条语句却不相同：
(c)const int *pi = 0;
/* 相当于int const *pi = 0; pi是一个指向const int的指针，复引用此运算符为得到一个const int的类型，该类型不能作为左值，在该语句后使用类似于*pi = 1的操作将导致编译错误。但该变量本身并不具备const属性，可以使用pi = &i的操作。可用于访问只读存储器。*/
(d)int* const pi = 0;
/* pi是一个指向int类型的const指针，复引用此运算符为得到一个int类型，该类型可以作为左值，在该语句可以使用类似于*pi = 1的操作，但该变量本身具备const属性，使用pi = &i的操作将导致编译错误。可用于访问固定位置的存储器。*/
再看一个更复杂的例子：
(e)const int* const pi = 0;
/* pi和*pi均不能作为左值。它只适合于读取某个固定位置的只读存储器 */

const还有下列典型用法:
     * 用于参数列表，通常修饰的是指针类型，表明该函数不会试图对传入的地址进行写操作。例如：
void *memcpy(void *, const void *, size_t);
     * 用于返回值，通常是一个指向只读区域的指针。例如：
const datatype_t *get_fixed_item(int index);
     * 给固定不变的数据(例如码表)加上只读属性，在某些情况下可以减小ram的开销。


2.static
     static用于全局变量声明和局部变量声明具有完全不同的语义，不得不说，这是C语言设计中的一个不合理之处。当static用于修饰全局变量声明(或函数声明，可以认为函数声明就是声明一个指向代码段的指针，该指针的值最后由链接时决定，从这个意义上说，函数声明也是一种全局变量声明)，它表示该变量具有文件作用域，只能被该源文件的代码引用，不能被其他源文件中的代码访问。在编译时引起的实际变化是被static修饰的变量不会被写入目标文件的输出节，在链接时解析其他模块中的未定义符号时不会被引用到。它的反义词是extern。
例如：
------main.c---
extern int a(void);
int main(){ return a(); }
------a.c------
/* link will fail unless remove “static” modifier */
static int a(void) { return 0; }



     当static用于修饰局部变量声明，它表示该变量不是分配在该函数的活动记录中，而是分配在全局的数据段(或bss段)中。简单的说，就是被static修饰的局部变量实际上并不是局部变量，而是具有函数作用域的全局变量，除了只能在定义它的函数内访问外(这是由C语法决定的)，它的运行时特征和全局变量完全一样，函数返回不会影响它的状态，它的初始化仅有一次，发生在程序的装载时，而不是在每次函数调用的时候初始化。它的反义词是auto。
例如, 下面这段函数返回自己被调用了多少次：
int callee(void) {
 static int times_called = 0;
 return (++ times_called);
}


3.volatile
     volatile修饰符的作用是告诉优化器不能优化这个变量的读写操作，一定要为这个变量的读写操作生成代码。
例如：
/* 延时操作 */
int foo(void) {
 /* 100次减法后返回 */
 volatile int i = 100; /*(a)*/
 while (i > 0) i--;  /*(b)*/
 return 0;
}
     在无volatile修饰的情况下，因为变量i的变化对上下文无影响，所以优化器很可能会省略掉对i操作的代码，而只生成return 0的代码，加上volatile可以保证编译器一定为语句(a)和(b)生成代码，达到延时的目的。

/* 设备状态判定 */
int uart_write_char(int c) {
 /* 向串口发送寄存器写入待发送字符 */
 *(volatile unsigned int *)UART_TX_REG = c;
 /* 判断是否已发送*/
 while ( (*(volatile unsigned int *)UART_STATUS_REG & TX_BIT) != 0); /*(c)*/
 return 0;
}
     在语句(c)中，如果不使用volatile，优化器可能会因为在两次读取UART_STATUS_REG之间没有对UART_STATUS_REG的写操作而将读取操作外提到循环体外而导致死循环。


转载请注明出处，谢谢！

计算机解决问题的本质就是搜索，说通俗一点就是尝试各种可能的情况，然后比较找出所需的解。我是从高一开始接触信息学竞赛的，竞赛和工程不一样，要求的是好的算法和在非常短的时间内实现，而工程要求的是稳定性可控和可测。说句实话，高二NOI'98(杭州)以后，我基本上没有再研究过搜索算法，很惭愧，这里贴出我高中的笔记，希望对大家有所帮助。


搜索算法分类：
1）盲目搜索：回溯法、广度优先、深度优先、双向广度优先、分支定界等
2）启发式搜索：A*、分段A*、博弈树等


回溯法：搜索算法的一种控制策略，亦是求解特殊性计数题或较复杂的枚举题中使用频率最高的一种算法，属基础算法，需优化后才能满足解题需要。

常用优化策略：
A）设定阀值，依次扩展节点
B）对处理过的节点不保留


广度优先、双向广度优先算法：解决最优化问题，盲目搜索无智力，一般都用双向广度优先算法。
需要注意的是：
A）双向广度优先算法，使用两头向中间扩展的队列
B）若产生重复节点的几率小，则可以取消判重
C）节点输出用递归：
void Print(int n)
{
   if (n > Queue[n]) printf("%dn", Queue[n].data);
   if (Queue[n] <> 0) Print(Queue[n].from);
   if (n < Queue[n]) printf("%dn", Queue[n].data);
}
单向输出： Print(F);
双向输出： Print(Queue[i].From); Print(i); // i为重合节点
D）扩展节点不是机械的按照正方向一层再逆方向一层，两个方向交替扩展的方法，而是选择节点个数较少的那个方向先扩展，这样就克服了两个方向节点生成速度不平衡的缺点（广度优先搜索的最大困难就是节点膨胀成指数级增长）


分支定界法：试题并未指定目标状态，而是给出约束条件和求某个目标函数的最小要求。
采用分支定界法题目的特点：
A）设置了一个下届prim－－目前为止的最优解。在分支定界中，每扩展一个节点，都要重新评估下界，若子节点中相关于目标函数的域值小于下界，才取该域值为新下界，并几下子节点信息
B）设定了一个界变量。在分支定界法中，必须按照目标函数的要求设计变量，作为分支标准，每扩展一个节点之前，都要根据当时已扩展情况计算界变量
C）搜索方式与广度搜索类似（队列）


A*算法：（这个内容好想Job Hunting的时候一般不会考察(游戏界人士除外)，所以不费口水了）
………………


各类搜索算法联系图
深度优先------------------>分支定界
         |---->启发式-->A*(修改A*)
广度优先------------------>双向广度


小结
>>深度优先（回溯法）：适用于求所有解或普通解，没有智力，对空间要求不大，是一种最自然的走迷宫方法
>>广度优先：适用于求最优解，没有智力，对空间要求很大（必须存储所有节点）
>>A*（修改A*）：是启发性搜索的最优化版本（不放弃“坏”节点），适用于求最优解
>>分支定界：是深度优先的最优化版本，是一种简单的求最优解的算法，逆同样可以将你的智慧放在剪枝函数>>中，它继承了深度优先的空间要求小的优点（完全放弃“坏”节点，类似“贪心法”）
>>双向广度：一定程度上降低了广度优先的空间要求大的弊端，尽管没有智力，也不失一种很好的求最优解算法


搜索算法的选择方法
A）根据题目要求和各类算法的适用范围，将不可行的算法抛弃
B）根据题目的规模，将某些不适用与大规模试题的算法抛弃
C）分析问题，找到问题的特点，如果找到了启发函数，就可以使用启发的解法解决
D）如果进一步找到更多关于问题的信息，也许可以使用数学算法（构造法）解决


转载请注明出处，谢谢！

线性表是《数据结构》正文第一部分的内容，是很简单的，也是很重要的基础知识。对于这部分知识大家应该记得滚瓜烂熟。
     线性表的实现分为顺序（数组）和链表，顺序实现过于简单，这里就不费口水了。
     链表实现有三种类型： 1)单向链表 2)循环链表 3)双向链表


链表的实现有几种形式：（主要是两种表示空节点的方式：NULL和DummyNode哑节点)

A)单链表，头节点NULL为空，尾节点NULL为空
初始化：head = NULL;
x节点后插入t节点：if (x == NULL) { head = t; } else { t->next = x->next; x->next = t;}
删除x后的节点：t = x->next; if (t) { x->next = t->next; free(t); }
遍历： t = head; while(t) { ...; t = t->next; }
是否为空：if (head == NULL) {...}


B)单链表，头节点哑节点为空，尾节点NULL为空
初始化：head = malloc(); head->next = NULL; // 浪费一个节点空间
x节点后插入t节点：t->next = x->next; x->next = t; // 少做一次判断
删除x后的节点：（同A）
遍历： （同A）
是否为空：if (head->next == NULL) {...}


C)单链表，头节点哑节点为空，尾节点哑节点为空 (这个很少用)
初始化：head = malloc(); z = malloc(); head->next = z; z->next = z; // 浪费两个节点空间
x节点后插入t节点：（同B）
删除x后的节点：（同B）
遍历： t = head->next; while (t != z) { ...; t = t->next; }
是否为空：if (head->next == z) {...}


D)循环链表
初始化：head = malloc(); head->next = head;
x节点后插入t节点：（同B）
删除x后的节点：（同B）
遍历： t = head; do { ...; t = t->next; } while (t != head);
是否为空：if (head->next == head) {...}


E)双向循环链表
初始化：head = malloc(); head->next = head->prev = head;
x节点后插入t节点：t->next = x->next; t->prev = x; x->next->prev = t; x->next = t;
删除x节点：x->prev->next = x->next; x->next->prev = x->prev; free(x);
遍历：（同D）
是否为空：（同D）



线性表应用：
1)单向链表
合并两个有序单向链表


逆转链表



2)循环链表
Josephus问题



转载请注明出处，谢谢！