<![CDATA[我是程序员 -Shosh's Blog - C/C++]]> http://www.wscxy.com/shosh/ zh-cn PBlog2 v2.4 我是程序员 -Shosh's Blog http://www.wscxy.com/shosh/images/logos.gif http://www.wscxy.com/shosh/ 我是程序员 -Shosh's Blog http://www.wscxy.com/shosh/article.asp?id=126 <![CDATA[头文件的部分规则：重定义相关]]> shosh.zhu@qisda.com(shosh) Thu,28 Jan 2010 00:32:30 +0800 http://www.wscxy.com/shosh/default.asp?id=126 Site: http://www.wscxy.com

RULE1: 每个头文件都用以下宏包起来，防止被其他文件多次包含。
    #ifndef __FILENAME_H__
    #define __FILENAME_H__
    （……文件内容……）
    #endif //__FILENAME_H__

RULE2: 在定义一个宏的时候，考虑是否需要检测是否已经被定义过。
    #ifndef MACRO_NAME
    #define MACRO_NAME     MACRO_VALUE
    #endif

RULE3：头文件中不要去定义全局变量，也就是说头文件中的所有语句不能涉及实际内存的分配。

对于RULE1，基本上大家都会这么做，当然也可以用pragma once来代替，只是pragma once的通用性不好，所以大家大多选择比较麻烦一点的RULE1中的做法。RULE1不是我想说的重点。

RULE2主要是为了防止宏重定义。在同一个工程中，尤其是一较大的工程中，同一个名字的宏在多个文件被定义是很正常的，比如BREW中RELEASEIF往往在多处被定义。在VC的编译器中，即使重定义也不会报错，甚至连Warning都没有，但是TCC会作为Error来处理。
举例：a.h中定义了宏A，b.h中也定义了宏A，他们都没有用ifndef包起来。然后某个源文件同时包含了这两个文件。对于严格的编译器来说，会出现重定义的错误，而对于检查较松的编译器，后者的定义会覆盖前者的定义（有的时候不同地方对同一个宏的定义不同）。有的时候，某些头文件我们需要包含进来，但是我们不关心那些头文件有没有已经定义了自己想要定义的宏或者自己想要定义的宏名被那些头文件定义成了什么样子，我们可以先undef掉那个宏，然后再定义自己的宏，这样可以保证自己用的宏是自己想要的定义。用RULE2的做法确实存在这样一个问题，我们不能确定自己用的宏是什么样子的（和包含的头文件以及它们的顺序有关系，这意味着本来都正常的代码，忽然有一天你又把另外一个头文件包含进来，结果这个宏的定义可能就不再是原来的那个了）。如果需要确认，可以让编译器生成预处理后的文件查看，不过一般情况下不需要这么做。

今天有个同事碰到了这样一个问题，让我过去帮他看看：我看到的错误是说某个头文件的某个宏重定义了。据他描述是因为他在某个C源文件里包含了多个头文件导致的。可是这些被他包含进来的头文件中却没有那个提示出错的头文件，另外这个重定义的宏对他来说一点用也没有。当时我怎么也没想不明白，既然没有包含进那个出错的头文件，怎么会是因为加了这一堆头文件导致的，就算是有重定义的错误也该发生在这些被包含进来的头文件才对呀。原来这些被包含的头文件往往又会包含其它头文件，这样扩展开来是类似树状的结构，一种情况是那个出错的文件被这些头文件直接或间接地包含进来了一次，但是还有其他被比较或间接包含进来的进来的头文件也同时定义了这个宏，只是那个出错的文件被包含的顺序比较靠后一点，所以出错并提示该头文件的那个宏重定义；另一种情况是这个这个出错的头文件被间接地包含了多次，并且这个头文件没有用RULE1去做，当然这种可能性很小。解决该问题的方法是找到去找到被他包含进来的（包括间接包含进来的）的头文件哪里定义了这个宏，却没有用RULE2去定义的。但是这样找很多文件，即使使用Source Insight搜索到所有的包含该宏定义的头文件，也要去确认那些头文件是否属于被他包含的头文件之列，比较麻烦。如果使用#error通过二分法查找，需要不停地编译数次可以找到。另一种方法是在他的某处合适的头文件包含语句之间添加#undef那个宏的语句，可以解决掉这个问题（别人忽然看到可能会觉得奇怪，如果找到精确位置还是要一定功夫的，如果每个包含头文件语句之间都添加这样的语句，会显得很冗赘）。还有专门的工具可以生成文件包含关系，如果手头有这样的工具的话，找起来还是很方便的。

RULE3比较容易理解：如果没有遵循RULE3的头文件被多个源文件包含的时候，链接的时候编译器就会发现不知道该使用哪个符号了。

总结：RULE1 是作为预防头文件被重复的做法，虽然能够保证头文件不被重复包含，但是却不能预防宏的重定义。在多文件工程的头文件中，应该按此法去做。RULE2可以有效防止宏的重定义，但是某些检查较松的编译器如VC的CL是允许宏重定义的。RULE2可能会让你使用的宏的实际定义变得模糊，有的时候你可能只想使用自己定义的宏，但是你包含的其他头文件可能会已经包含了这个宏名，可以先undef掉。另外，我们应该尽量避免在不同头文件定义同名的宏，而比较公用的、可能会被多个其他文件包含的头文件应该使用RULE2去定义宏，以防止重定义。RULE3是必须遵循的。]]> http://www.wscxy.com/shosh/article.asp?id=119 <![CDATA[再说strcpy + 面试中的算法题笔试]]> shosh.zhu@qisda.com(shosh) Fri,06 Nov 2009 22:12:29 +0800 http://www.wscxy.com/shosh/default.asp?id=119 strcpy这个函数是很考验一个人的，其实很早（大二的时候）就看过林锐的《高质量C/C++代码》，里面对strcpy做了很详细的分析，以及哪些需要注意的地方。

其实C语言课上的时候，老师也分析过strcpy，甚至老师将该函数体的循环部分简化为一个语句。另外，本人也一直对自己的编码风格、C语言和一些比较常见的算法都很自信的，不过今天自己写了strcpy()这个函数，回来后发现自己还是载在了这个上面（其实也不是太影响面试结果）。反省一下！

当时写strcpy函数的时候，有几个没有记清的地方的：
1、strcpy会不会主动给strDest的末尾加上'\0'，当时当成不加了来处理。
2、参数是否该去检测NULL，因为strcpy作为比较常用的库函数，感觉程序员理应为主动为其保证正确性（现在想起来林锐当时好像用的是assert），不过我们写嵌入式的好像不怎么习惯用assert，也可能是我个人的情况。），即使可以保证指针为有效的地址值，也无法保证strDest分配的空间是足够的。不过这个判断语句还是写上了，因为写上去至少不会说是错。
3、其他错误（如果调试运行一下就可以发现）。

不怕丢脸，贴出我写的那个错误版本的strcpy函数：

  1. char* strcpy(char *strDest, const char *strSrc)
  2. {
  3.     char *p = strSrc;
  4.     if (NULL == strDest || NULL == strSrc)
  5.         return NULL;
  6.     while ('\0' != *p)
  7.     {
  8.         *strDest = *p;
  9.         strDest++;
  10.         p++;
  11.     }
  12.     return strDest;
  13. } 

函数中申请了临时变量p，不过没有用它来存放strDest。当初只想着把传入的strDest返回去就好了，结果忽略了过程中把它移动了。所以，其实这个是最大的错误，但是调试运行一下是很容易发现的。当时给strSrc设置了个变量的原因是因为const，其实我知道这里const修饰的是char*，也就是说地址strSrc指向的那片空间的数据在本函数中是不可以去修改的。但是当时也是为了“双保险”，就来了个char* p = strSrc; 。实际上这句话是有warning的，如果当时调试了，估计就把它删除掉了（因为我更讨厌强转，且这句话是非必须的）。

在讨论到要不要判断入参是否为NULL的时候，主考官的说法是：必须要，因为如果用户传入的是NULL，向0地址写数据，那会引起系统崩溃。本来是想和他说系统应该会有保护的，不过因为没有经过测试，也就只说了程序员在调用该函数的时候在调试过程会发现的。 所以晚上故意测试了一下，在windows上，这样做会导致程序本身不能运行，并不会导致系统崩溃，所以我那系统有保护的想法是正确的。其实这跟系统是否提供保护机制有关系。（不过肯定的是：对入参是应该进行有效性检测的）。而事实上，C库中的strcpy是不做检测的，所以事情不是那么绝对的。

其实第6到第11行可以简化为一行，不过因为不会提高执行效率，反而会降低可读性，所以就没那么写，同时也降低了出错的机率。

另外经过测试库函数strcpy发现：它是会给strDest的最后加上字符串结束符的（测试方法很简单，使用局部变量char str[n]，不要给他初始化就直接strcpy后输出，看后面是不是有乱码输出——这里必须使用局部变量，因为申请到的局部变量的初始值是随机的，而全局变量或静态变量是会被初始化为0的）。

最后本人修改函数如下：

  1. char* strcpy1(char *strDest, const char *strSrc)
  2. {
  3.     char *p = strDest;
  4.     if (NULL == strDest || NULL == strSrc)
  5.         return NULL;
  6.     while ('\0' != *strSrc)
  7.     {
  8.         *strDest = *strSrc;
  9.         strDest++;
  10.         strSrc++;
  11.     }
  12.     *strDest = '\0';
  13.     return p;
  14. } 

其实在这类函数中使用assert比判断指针是否为空更好，因为assert是用来调试的，而判断指针是否为空是防错性编程。在开发阶段，我们应该将问题尽量暴露出来，从而得到及时有效的修正，而assert刚好是最好的选择。所以第4行和第5行可以修改为：
assert(NULL != strDest && NULL != strSrc);
其实判断多个指针都不能为NULL，还可以优化为：if (NULL != p1 | p2 | p3 | ... | pn)，不过不推荐使用。其实这道题目考的不是算法，而是编程习惯，所以我在这题上的得分基本上是0分。

如果其他算法题目，大家在笔试的时候是不需要完全做正确的（当然了，如果能够完全正确是最好不过的），因为那个主要考的是你的思路，是你的逻辑思维能力，当然还有你的编码风格。之所以说不需要完全正确是因为，在不调试的情况下，如果算法不怎么简单，是很少有人一写就正确的。当然写好后最好再检查一遍（类似Code Review），这样可以发现一些笔误和一些简单的逻辑错误。但是还是可能会有一些错误是你一时发现不了的。

刚才我抽取了两道在展讯做的算法题，竟然发现没有错误，欣喜！
而运行了在今天面试的那家公司的排序算法题，其中方法一也没有错误，方法二有逻辑错误，少了一句break（其实是当时考虑遗漏的地方）。虽然这错误影响运行结果，这个break在该函数中的作用也是举足轻重的，但是我个人认为：这不算失败，在没有调试的情况下，一个较复杂的算法有这样一个未察觉的错误是正常的现象。

算了，想想还是把我做的这个题贴出来吧，反正也没有告诉大家这是哪家公司的题目：

  1. int *getASCArray(int srcArray[], int len)
  2. {
  3.     int i, j;
  4.     int *destArray = (int*) malloc(sizeof(int) * len);
  5.     if (NULL == destArray)
  6.         return NULL;
  7.     
  8.     destArray[0] = srcArray[0];
  9.     for (i = 1; i < len; i++)
  10.     {
  11.         if (srcArray[i] >= destArray[i - 1])
  12.         {
  13.             destArray[i] = srcArray[i];
  14.         }
  15.         else
  16.         {   
  17.             for (j = i - 1; j >= 0; j--)
  18.             {
  19.                 if (srcArray[i] >= destArray[j])
  20.                 {
  21.                     destArray[j + 1] = srcArray[i];
  22.                     break; //完成该数的插入
  23.                 }
  24.                 else
  25.                 {
  26.                     //直接把数据往后移一步
  27.                     destArray[j + 1] = destArray[j];
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     return destArray;
  33. } 

其中第22行的break是晚上调试后补充上的，其他代码是在笔试的时候做的。

]]> http://www.wscxy.com/shosh/article.asp?id=114 <![CDATA[C++中的多重继承]]> shosh.zhu@qisda.com(shosh) Fri,30 Oct 2009 01:36:27 +0800 http://www.wscxy.com/shosh/default.asp?id=114 和Java不同，C++允许多重继承。所谓多重继承，是指一个类可以同时继承自多个类，使其本身同时具有这些类的特征。这样就会有一个问题，如下面的继承关系：
A->B1->C1->D,  A->B2->C2->D，我们将这里的箭头看成是“派生出”，所以这里A派生出了B1和B2，B1派生出C1，B2派生出C2，而D同时继承自C1和C2，即D是从C1和C2多重继承出来的。我们知道，派生类是可以访问基类的数据成员的，那对于D的对象要访问间接基类A的成员，是访问第一条路线的A呢，还是访问第二条路线的A呢（两个A还不一样吗？不一样，因为在构造D的时候，会先去构造C1和C2，而在构造C1的时候，会先去构造B1，构造C2的时候会先去构造B2，而在构造B1的时候，会先去构造A，在构造B2的时候，也会先去构造A——这里说的构造X是指构造类X的对象。所以最后D中包含了两个A的对象）？也就是说，产生了二义性。如果你没有访问基类A的成员，没有关系，编译不会发现这个错误，但是如果有去访问A类的数据了，就会出错，因为编译器不能决定使用哪个对象的成员来编译。为了解决这个问题，C++使用虚基类的概念来解决这个问题的。即在指定派生类的直接基类的时候，使用virtual关键字指明该直接基类作为虚基类来继承。这里比较麻烦的是各级派生类的构造函数的写法。我们知道：对于没有不带参数的构造函数的基类（只提供带有参数的构造函数），其直接派生类的构造函数必须显式地调用其直接基类的构造函数（否则可以不用显示调用，编译器会默认帮你调用直接基类的无参构造函数），这个规则对于这里提到的多重继承也是适合的。不过这里又多了一条规则：如果派生类的各级基类包含有虚基类，该类的构造函数除了上一条规则提到的需要调用其直接基类的构造函数外，还需要调用虚基类的构造函数，如果虚基类的构造函数只提供带参数的构造函数，则必须显式调用，否则编译器也会帮助你调用虚基类的无参构造函数。


对于前面的例子：A->B1->C1->D,  A->B2->C2->D， 我编写了如下的测试代码：
//in header file(.h):
class A
{
public:
        A(int lv) : level(lv)
        {
                cout << "A" << endl;
        }
/*      A()
        {
                cout << "A" << endl;
                level = 0;
        }
*/
        void dispLevel(void)
        {
                cout << level << endl;
        }
       
private:
        int level;
};

class B1 : virtual public A
{
public:
        B1(void) : A(11)
        {
                cout << "B1" << endl;
        }
};
class B2 : virtual public A
{
public:
        B2(void) : A(12)
        {
                cout << "B2" << endl;       
        }
};
class C1 : public B1
{
public:
        C1(void) : B1(), A(21)
        {
                cout << "C1" << endl;
        }
};
class C2 : public B2
{
public:
        C2(void) : B2(), A(22)
        {
                cout << "C2" << endl;
        }
};
class D : public C1, public C2
{
public:
        D(void) : C1(), C2(), A(3)
        {
                cout << "D" << endl;
        }
};
//in source file(.cpp):
int main(void)
{
        D objD = D();
        objD.A::dispLevel();
        return 0;
}
 
如果将程序中类A的无参构造函数加上（去掉相应注释），则类B1,B2,C1,C2,D的构造函数都可以不必显式调用A的构造函数，这样会隐式调用A的无参构造函数，这样A::level = 0了（这里只是说在语法上可以这样做而已，效果上自然少了对level的自定义）。
 
上面的程序的运行结果如下：
A
B1
C1
B2
C2
D
3
 
可以看到只调用了一次A的构造函数，而不是两次，说明D的对象objD确实只包含一份A的对象，而不是两份，虚基类确实解决了多重继承容易出现的二义性问题。
 
为何objD.A::dispLevel();输出的结果是3而不是11？虽然在 D(void) : C1(), C2(), A(3)中，A(3)放在最后面，但是实际效果是和A(3)放在最前面是一致的。原因如下（派生类构造函数的调用次序三原则）：
(1)虚基类的构造函数在非虚基类之前调用;
(2)若同一层次中包含多个虚基类,这些虚基类的构造函数按它们说明的次序调用;
(3)若虚基类由非虚基类派生而来,按照先基类构造,再派生构造的顺序.
 
]]> http://www.wscxy.com/shosh/article.asp?id=83 <![CDATA[system函数让你的C程序功能强大且实用]]> shosh.zhu@qisda.com(shosh) Fri,23 Jan 2009 15:58:07 +0800 http://www.wscxy.com/shosh/default.asp?id=83 就本人来说，C语言是大二上学期开始学的，因为大一时自学过JavaScript，所以学期C语言比较轻松，加上当时上课认真听讲，上机课也独立完成作业，当时自认为学得不错（事实上也确实不错，只是工作后发现，C语言还有很多很精华的地方，大学时都没有接触到）。就拿system这个函数来说，上课的时候老师稍微提到过，就是让程序暂停执行的时候可以调用system("pause")或者需要清屏的时候可以调用system("cls")。当时只知道可以这样做，但是不明白这些参数是怎么来的，还可以用哪些。

工作后，曾经有位热心的同仁为了方便大家访问同仁之间的机器，做了一款to程序，将该程序放到system32目录后，用户在运行窗口输入"to 同仁英文名"后按回车就可以访问到所输入的英文名的同仁的机器了。当时看了该程序和我们在学校里写的一般小程序没什么两样，可是为什么它的功能那么“强大”，那么“实用”，而我们在大学里写的程序只能做些简单运算或简单输出呢？当然那个时候也没有细想是怎么实现的。

今天忽然想到程序间的调用方法的问题，想到之前我在bat里试图调用js成功，也看到过hta文件可以打开一些诸如notepad之类的程序，想用C语言来调用其他一些命令该怎么做。于是很自然地就想到了system函数。从最简单的开始，打开记事本。于是写了个简单的main函数，在里面调用:
system("notepad");
运行后，发现记事本打开了。
现在想明白了，这个函数的参数实际就是bat里的指令！
接着测试打开局域网中的o-2t9e这台机器。我们知道如果手工打开的话，都是通过运行"\\o-2t9e"来打开的。于是在main函数中加入如下代码：
system("\\o-2t9e");
出现提示：'\o-2t9e' 不是内部或外部命令，也不是可运行的程序或批处理文件。
对，这当然不对，因为“\\”转义成了“\”。于是将代码改为：
system("\\\\o-2t9e");
这样就可以转义成我们想要的“\\o-2t9e”了。
结果出现提示：文件名、目录名或卷标语法不正确。
一想这个是需要用资源管理器打开的，所以需要使用explorer.exe，于是修改使用如下代码：
system("explorer.exe \\\\o-2t9e");
嚯嚯，成功打开了。(想想：上面的命令才是bat里正确调用方式)
于是再试试打开http://www.wscxy.com这个网站，使用如下代码：
system("explorer.exe http:\/\/www.wscxy.com");
我那熟悉的网站首页出现在了我的显示屏幕上！
接着测试：
system("ping www.baidu.com");
都是正常的。

对，没有错，它的参数就是bat里的一条条指令！
知道这一点，如果你对bat有一定了解，你就可以使用C语言来写“功能强大且实用”的工具了！
 

]]> http://www.wscxy.com/shosh/article.asp?id=76 <![CDATA[定义全局变量时应尽量加static]]> shosh.zhu@qisda.com(shosh) Fri,12 Dec 2008 09:10:11 +0800 http://www.wscxy.com/shosh/default.asp?id=76 为什么定义全局变量时应尽量加static呢？
 
这是我在工程中碰到实际问题时才想到的。工程的编译阶段已经顺利通过，但是在链接时，发生了一些错误，其中的两条Error提示为：
Error: L6200E: Symbol gpListeners multiply defined (by OEMLogicalDisplayCfg.o and opc_history_store.o).
Error: L6200E: Symbol gpListeners multiply defined (by opc_history_store.o and OEMLogicalDisplayCfg.o).
明显是在两个文件里使用了同一个变量名。
我第一眼看到这个错误的时候，想到的是重复定义，使用的是同一个变量，应该用extern解决。不过找到相应代码仔细一看，发现它们的类型并不一致，才想起来，原来应该限定他们的作用域。
这两个变量都是只在文件内使用的，所以我给他们定义的前面都加了static，再编译链接，以上两条错误提示消去。
 
所以，如果要使用全局变量，且只在文件内使用，在定义时使用static限定其作用域，防止上述的错误发生。
如果有全局变量的适用范围不仅只在一个文件内部，则需要避免与其他文件使用同样的命名。
 
其实函数名也是如此，只是大家对待函数的习惯已经很好了，将只在文件内使用的函数都声明为static的了。
]]> http://www.wscxy.com/shosh/article.asp?id=65 <![CDATA[内联函数关键字辨析：inline, _inline和__inline]]> shosh.zhu@qisda.com(shosh) Thu,30 Oct 2008 08:55:08 +0800 http://www.wscxy.com/shosh/default.asp?id=65 在VC6编辑器上，输入inline,_inline,__inline可以发现它们都是蓝色的，说明它们都是关键字。

在MFC中，经常使用inline作为关键字。

在BREW上，却经常看到__inline作为关键字。

两者有何区别？另外，_inline呢？

在网上找了下答案，解释（主要部分）如下：

原文引用：
  1. The inline keyword is available only in C++. The __inline and __forceinline keywords are available in both C and C++. For compatibility with previous versions, _inline is a synonym for __inline.

 也就是说：

inline是C++的关键字，在C中是用不了的；

__inline和__forceinline（用于强制要求内联的关键字）是C和C++兼容使用的；

_inline则是为了保持和以前版本的兼容性而存在的，和__inline一样。

这样看来，__inline是最好的选择，因为，不管是在C中，还是在C++中，都可以使用。

]]> http://www.wscxy.com/shosh/article.asp?id=60 <![CDATA[C实现的一元多项式运算[2]--链表运算]]> shosh.zhu@qisda.com(shosh) Sun,28 Sep 2008 20:54:49 +0800 http://www.wscxy.com/shosh/default.asp?id=60 上一次《C实现的一元多项式运算》完成了一元多项式的基本操作，接上一次的工作，本次完成了乘法的运算和将多项式运算的过程输出到HTML文件的功能。另外定义了PRINTF_ARGL和FPRINTF_ARGL宏，用来同时向屏幕和文件输出。

因为多项式的表示是通过单向链表来完成的，多项式的运算也是通过链表的操作来完成的（结点动态申请），所以内存的分配和释放尤为重要。为检测分配和释放状况，代码统一使用宏Create_ENTITY和FREEIF来分配和释放，在宏中输出分配释放情况。

DEBUG_MEMORY宏值如果定义为0，则关闭输出链表结点输出的情况，定义为非0值（如1）则输出当前是在分配结点还是在释放结点，并输出分配或释放结点后剩余的结点数。所以当程序运行结束后，结点数为0则表示为链表分配的内存已经全部释放。

代码中的函数基础的放在前面，提供后面的函数使用，而没用使用函数原型声明，这样可以少贴几行到网页（实际编程时最好不要如此，以来很难控制函数的调用关系，二来如果将函数申明放在一起，用户可以很容易看到该源文件提供哪些函数，主要完成什么功能等）。

main函数被用来创建log文件，用户请在UserMain函数中编写代码。

头文件和源文件本应分开，为方便贴出，暂将其放在一块。

还少一个将字符串如“5y^3 + 3y^2 - 4y -1”parse成一个链表的函数，以后补上。等该功能完成后，可再增加命令行功能，如：“polynomial 5y^3+3y^2-4y-1 * 3y^4-4y-2”。

下载：
源文件
生成的log文件
生成的HTML文件（运算过程）

 

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. //You can set DEBUG_MEMORY to either 0 if do not wanna test whether there is
  6. //momery leak or 1(just other than 0) to check.
  7. #define DEBUG_MEMORY 1
  8. #define WRITE_SCREEN_TO_FILE 1
  9. //Write strings(written by PRINTF_ARGL) to the file besides the screen.
  10. //this is only used when WRITE_SCREEN_TO_FILE != 0
  11. #define SCREEN_LOG_FILE "D:\\PolyLog.txt"
  12.  
  13. #if defined NULL
  14.     #undef NULL
  15. #endif
  16. #define NULL 0
  17.  
  18. #define CHECK_NONNULL_POINT(p) assert(NULL != p)
  19. #define CHECK_SAME_VALUE(a,b) assert((a) == (b))
  20.  
  21. #define _ARGL(r) r##,
  22. #define _ARGLEND(r) r
  23.  
  24. //when use PRINTF_ARGL() or FPRINTF_ARGL(), please do not forget to add {}
  25. //even if there is only one statement in it, especially when it is after "if".
  26. #if WRITE_SCREEN_TO_FILE
  27.     FILE* gpLogFile = NULL;
  28.     #define PRINTF_ARGL(s) printf(s); \
  29.             if (NULL != gpLogFile) \
  30.                 fprintf(gpLogFile, s)
  31.     #define FPRINTF_ARGL(fp, s) printf(s); \
  32.             if (NULL != gpLogFile) \
  33.                 fprintf(gpLogFile, s); \
  34.             fprintf(fp, s)
  35. #else
  36.     #define PRINTF_ARGL(s) printf(s)
  37.     #define FPRINTF_ARGL(fp, s) printf(s); \
  38.             fprintf(fp, s)  
  39. #endif
  40.  
  41. //We can only create one Create_ENTITY in one area,
  42. //declaration of variables must be ahead of it.
  43. #if DEBUG_MEMORY
  44.     int gMemNodeNum = 0;
  45.     #define Create_ENTITY(type, name) \
  46.             type* name = (type*) malloc(sizeof(type)); \
  47.             assert(NULL != name); \
  48.             gMemNodeNum++; \
  49.             /* PRINTF("\n[Create_ENTITY: %d, 0x%p] ", ++gMemNodeNum, name)*/ \
  50.             PRINTF_ARGL(_ARGL("\n[Create_ENTITY: %d, 0x%p] ") \
  51.                         _ARGL(gMemNodeNum)_ARGLEND(name))
  52.  
  53.     #define FREEIF(p) \
  54.             if (NULL != p)  \
  55.             {               \
  56.                 gMemNodeNum--; \
  57.                 /* PRINTF("\n[FREE: %d, 0x%p] ", --gMemNodeNum, p); */ \
  58.                 PRINTF_ARGL(_ARGL("\n[FREE: %d, 0x%p] ") \
  59.                         _ARGL(gMemNodeNum)_ARGLEND(p)); \
  60.                 free(p);   \
  61.             }   \
  62.             p = NULL
  63. #else
  64.     #define Create_ENTITY(type, name) \
  65.             type* name = (type*) malloc(sizeof(type)); \
  66.             assert(NULL != name)                    
  67.  
  68.     #define FREEIF(p) \
  69.             if (NULL != p)  \
  70.             {               \
  71.                 free(p);   \
  72.             }   \
  73.             p = NULL    
  74. #endif
  75.  
  76.  
  77.  
  78. typedef unsigned int uint;
  79. typedef char BOOL;
  80. #define FALSE 0
  81. #define TRUE 1
  82.  
  83. typedef int QType; //use int to simplize
  84. typedef int IType;
  85.  
  86. //多项式中的项
  87. typedef struct _ItemNode ItemNode;
  88. struct _ItemNode
  89. {
  90.     ItemNode*   pNext;     //指向下一项
  91.     QType       quotiety;  //系数
  92.     IType       index;     //指数
  93. };
  94.  
  95. typedef struct _Polynomial
  96. {
  97.     ItemNode*   pHeader;   //多项式中的第一项
  98.     ItemNode*   pLast;     //多项式中的最后一项
  99.     char        pronumeral; //未知数名，如x,y,z
  100.     uint        ItemNum;   //项数
  101. } Polynomial;
  102.  
  103. //Create one empty polymonial
  104. Polynomial* CreateEmptyPolynomial(char name)
  105. {
  106.     Create_ENTITY(Polynomial, pPoly);
  107.     pPoly->pHeader = pPoly->pLast = NULL;
  108.     pPoly->pronumeral = name;
  109.     pPoly->ItemNum = 0;
  110.     return pPoly;
  111. }
  112.  
  113. //Create one polynomial with one item
  114. Polynomial* CreatePolynomial(char name, ItemNode* head)
  115. {
  116.     Polynomial* pPoly = CreateEmptyPolynomial(name);
  117.     pPoly->pHeader = pPoly->pLast = head;
  118.     pPoly->ItemNum = 1;
  119.     return pPoly;
  120. }
  121.  
  122. //Create one Item Node
  123. ItemNode* CreateItemNode(QType quotiety, IType index)//系数，指数
  124. {
  125.     Create_ENTITY(ItemNode, pItem);
  126.     pItem->quotiety = quotiety;
  127.     pItem->index = index;
  128.     pItem->pNext = NULL;
  129.     return pItem;
  130. }
  131.  
  132. //Duplicate an ItemNode
  133. ItemNode* DuplicateItemNode(ItemNode* pItem)
  134. {
  135.     Create_ENTITY(ItemNode, pNewItem);
  136.     pNewItem->index = pItem->index;
  137.     pNewItem->quotiety = pItem->quotiety;
  138.     pNewItem->pNext = pItem->pNext;
  139.     return pNewItem;
  140. }
  141.  
  142. void FreeItemNode(ItemNode* pItem)
  143. {
  144.     FREEIF(pItem);
  145. }
  146.  
  147.  
  148. void FreePolynomial(Polynomial* pPoly)
  149. {
  150.     ItemNode *temNode;
  151.     CHECK_NONNULL_POINT(pPoly);
  152.  
  153.     temNode = pPoly->pHeader;
  154.     while (NULL != temNode)
  155.     {
  156.         //we cannot simply use temNode = temNode->pNext after call FreeItemNode
  157.         //because the struct has been freed and we would not get proper value
  158.         //of temNode->pNext, although temNode isn't NULL
  159.         pPoly->pHeader = temNode->pNext;
  160.         FreeItemNode(temNode);
  161.         temNode = pPoly->pHeader;
  162.     }
  163.     FREEIF(pPoly);
  164. }
  165.  
  166. //Add one Item to polynomial,and return the ItemNode Num.
  167. int AddItemToPolynomial(Polynomial* pPoly, ItemNode* pItem)
  168. {
  169.     CHECK_NONNULL_POINT(pPoly);
  170.     CHECK_NONNULL_POINT(pItem);
  171.     if (NULL != pPoly->pLast) //this means pPoly->pHeader != NULL
  172.     {
  173.         if (NULL == pPoly->pHeader->pNext) //when there is only one item
  174.             pPoly->pHeader->pNext = pPoly->pLast;
  175.         pPoly->pLast->pNext = pItem;
  176.     }
  177.     else //the first item node
  178.     {
  179.         pPoly->pHeader = pItem;
  180.     }
  181.     pPoly->pLast = pItem;
  182.     pPoly->pLast->pNext = NULL;
  183.     return ++pPoly->ItemNum;
  184. }
  185.  
  186. //add one item to a formatted polynomial, and return the itemnode num.
  187. //please ensure that pPoly is formatted, namely its index is in Desc order.
  188. //pItem must be new built(is not a member of another polynomial)
  189. int AddItemToFormattedPolynomial(Polynomial* pPoly, ItemNode* pItem)
  190. {
  191.     CHECK_NONNULL_POINT(pPoly);
  192.     CHECK_NONNULL_POINT(pItem);
  193.     if (NULL == pPoly->pHeader)
  194.     {
  195.         pPoly->pHeader = pPoly->pLast = pItem;
  196.     }
  197.     else
  198.     {
  199.         ItemNode* pTemItem = pPoly->pHeader;
  200.         ItemNode* pLastValidItem = pTemItem; //this cannot be NULL
  201.         while (NULL != pTemItem && pTemItem->index > pItem->index)
  202.         {
  203.             pLastValidItem = pTemItem;
  204.             pTemItem = pTemItem->pNext;
  205.         }
  206.         if (NULL == pTemItem) //insert it to the end
  207.         {
  208.             pLastValidItem->pNext = pItem;
  209.             pPoly->pLast = pItem;
  210.         }
  211.         else if (pTemItem->index == pItem->index) //no insert it
  212.         {
  213.             pTemItem->quotiety += pItem->quotiety;
  214.             //remember to free pItem, for we have not added it to the pPoly
  215.             FreeItemNode(pItem);
  216.         }
  217.         else //insert it normally
  218.         {
  219.             pLastValidItem->pNext = pItem;
  220.             pItem->pNext = pTemItem;
  221.         }
  222.     }
  223.  
  224.     pPoly->pLast->pNext = NULL;
  225.     return ++pPoly->ItemNum;
  226. }
  227.  
  228. //Create a Formatted Polynomial from a non-formatted polynomial by index DESC
  229. Polynomial* CreateFormattedPolynomial(Polynomial* pPoly)
  230. {
  231.     Polynomial* pFmtPoly;
  232.     ItemNode* pTemNode;
  233.     CHECK_NONNULL_POINT(pPoly);
  234.     pFmtPoly = CreateEmptyPolynomial(pPoly->pronumeral);
  235.     pTemNode = pPoly->pHeader;
  236.     while (NULL != pTemNode)
  237.     {
  238.         AddItemToFormattedPolynomial(pFmtPoly, 
  239.                 DuplicateItemNode(pTemNode));
  240.         pTemNode = pTemNode->pNext;
  241.     }
  242.     return pFmtPoly;
  243. }
  244.  
  245. //Create a Formatted Polynomial and delete the old one
  246. Polynomial* CreateFormattedAndDelOldPolynomial(Polynomial* pPoly)
  247. {
  248.     Polynomial* pFmtPoly;
  249.     ItemNode* pTemNode;
  250.     ItemNode* pCurNode;
  251.     CHECK_NONNULL_POINT(pPoly);
  252.     pFmtPoly = CreateEmptyPolynomial(pPoly->pronumeral);
  253.     pTemNode = pPoly->pHeader;
  254.     while (NULL != pTemNode)
  255.     {
  256.         //it is the defference between this function and
  257.         //CreateFormattedPolynomial concerning the freedom of pTemNode.
  258.         pCurNode = pTemNode->pNext;
  259.         AddItemToFormattedPolynomial(pFmtPoly, pTemNode);
  260.         pTemNode = pCurNode;
  261.     }
  262.     FREEIF(pPoly);
  263.     return pFmtPoly;
  264. }
  265.  
  266. //Create a new ItemNode with quotiety and index first,
  267. //and then insert the node to pPoly at the tail(non-formatted).
  268. int AddItemToPolynomialEx(Polynomial* pPoly, QType quotiety, IType index)
  269. {
  270.     return AddItemToPolynomial(pPoly, CreateItemNode(quotiety, index));
  271. }
  272.  
  273. /***************************** + - * operations ******************************/
  274. //pLeftPoly and pRightPoly can be either formatted or non-formatted in these
  275. //three functions, but the new created polynomial(return value) is formatted.
  277. //+: pLeftPoly + pRightPoly
  278. Polynomial* PolynomialAdd(Polynomial* pLeftPoly, Polynomial* pRightPoly)
  279. {
  280.     Polynomial* pOutPoly;
  281.     CHECK_NONNULL_POINT(pLeftPoly);
  282.     CHECK_NONNULL_POINT(pRightPoly);
  283.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  284.     //pOutPoly = CreateEmptyPolynomial(pLeftPoly->pronumeral);
  285.     //just link two polynomials to simplize the actions.
  286.     pLeftPoly->pLast->pNext = pRightPoly->pHeader;
  287.     //calculating pLeftPoly->ItemNum is not needed,
  288.     //just for further consideration
  289.     pLeftPoly->ItemNum += pRightPoly->ItemNum;
  290.     pOutPoly = CreateFormattedPolynomial(pLeftPoly);
  291.     //set back
  292.     pLeftPoly->ItemNum -= pRightPoly->ItemNum;
  293.     pLeftPoly->pLast->pNext = NULL;
  294.     return pOutPoly;
  295. }
  296.  
  297. //-: pLeftPoly - pRightPoly
  298. Polynomial* PolynomialSubtract(Polynomial* pLeftPoly, Polynomial* pRightPoly)
  299. {
  300.     Polynomial* pOutPoly;
  301.     ItemNode* pTemNode;
  302.     ItemNode* pNewNode;
  303.     CHECK_NONNULL_POINT(pLeftPoly);
  304.     CHECK_NONNULL_POINT(pRightPoly);
  305.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  306.     pOutPoly = CreateFormattedPolynomial(pLeftPoly);
  307.     pTemNode = pRightPoly->pHeader;
  308.     while (NULL != pTemNode)
  309.     {
  310.         pNewNode = DuplicateItemNode(pTemNode);
  311.         pNewNode->quotiety = -pNewNode->quotiety;
  312.         AddItemToFormattedPolynomial(pOutPoly, pNewNode);
  313.         pTemNode = pTemNode->pNext;
  314.     }
  315.     return pOutPoly;
  316. }
  317.  
  318. //*: pLeftPoly * pRightPoly
  319. Polynomial* PolynomialMultiply(Polynomial* pLeftPoly, Polynomial* pRightPoly)
  320. {
  321.     Polynomial* pOutPoly;
  322.     ItemNode *pCurLeft;
  323.     ItemNode *pCurRight;
  324.     ItemNode *pOutItem;
  325.     CHECK_NONNULL_POINT(pLeftPoly);
  326.     CHECK_NONNULL_POINT(pRightPoly);
  327.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  328.     
  329.     pCurLeft = pLeftPoly->pHeader;
  330.     pOutPoly = CreateEmptyPolynomial(pLeftPoly->pronumeral);
  331.     while (pCurLeft)
  332.     {
  333.         pCurRight = pRightPoly->pHeader;
  334.         while (pCurRight)
  335.         {
  336.             pOutItem = CreateItemNode(
  337.                 pCurLeft->quotiety * pCurRight->quotiety,
  338.                 pCurLeft->index + pCurRight->index);
  339.             AddItemToFormattedPolynomial(pOutPoly, pOutItem);
  340.             pCurRight = pCurRight->pNext;
  341.         }
  342.         pCurLeft = pCurLeft->pNext;
  343.     }
  344.     return pOutPoly;
  345. }
  346.  
  347. /********************Write Processes to HTML File in Detail*******************/
  348. BOOL HTMLItemNode(FILE* pHTMLFile, ItemNode* pItem, char cPronum, BOOL bHead)
  349. {
  350.     CHECK_NONNULL_POINT(pItem);
  351.     CHECK_NONNULL_POINT(pHTMLFile);
  352.     if (0 == pItem->quotiety)
  353.         return FALSE;
  354.     if (bHead)
  355.     {
  356.         if (1 == pItem->quotiety)
  357.         {
  358.         }
  359.         else if (-1 == pItem->quotiety)
  360.         {
  361.             FPRINTF_ARGL(pHTMLFile, "-");
  362.         }
  363.         else
  364.         {
  365.             FPRINTF_ARGL(pHTMLFile, _ARGL("%d")_ARGLEND(pItem->quotiety));
  366.         }
  367.     }
  368.     else
  369.     {
  370.         if (1 == pItem->quotiety)
  371.         {
  372.             FPRINTF_ARGL(pHTMLFile, " + ");
  373.         }
  374.         else if (-1 == pItem->quotiety)
  375.         {
  376.             FPRINTF_ARGL(pHTMLFile, " - ");
  377.         }
  378.         else
  379.         {
  380.             QType quot = pItem->quotiety;
  381.             char op = '+';
  382.             if (quot < 0)
  383.             {
  384.                 quot = - quot;
  385.                 op = '-';
  386.             }
  387.             FPRINTF_ARGL(pHTMLFile, _ARGL(" %c %d")_ARGL(op)_ARGLEND(quot));
  388.         }
  389.     }
  390.     if (0 != pItem->index)
  391.     {
  392.         FPRINTF_ARGL(pHTMLFile, _ARGL("%c")_ARGLEND(cPronum));
  393.         if (1 != pItem->index)
  394.         {
  395.             FPRINTF_ARGL(pHTMLFile,
  396.                     _ARGL("<sup>%d</sup>")_ARGLEND(pItem->index));
  397.         }
  398.     }
  399.     return TRUE;
  400. }
  401.  
  402. BOOL HTMLPolynomial(FILE* pHTMLFile, Polynomial* pPoly)
  403. {
  404.     ItemNode* pItem;
  405.     BOOL bEmpty = TRUE;
  406.     CHECK_NONNULL_POINT(pPoly);
  407.     pItem = pPoly->pHeader;
  408.     
  409.     //print first item node
  410.     while (NULL != pItem)
  411.     {
  412.         if (HTMLItemNode(pHTMLFile, pItem, pPoly->pronumeral, TRUE))
  413.         {
  414.             bEmpty = FALSE;
  415.             pItem = pItem->pNext;
  416.             break;
  417.         }
  418.         pItem = pItem->pNext;
  419.     }
  420.     //print other item node
  421.     while (NULL != pItem)
  422.     {
  423.         HTMLItemNode(pHTMLFile, pItem, pPoly->pronumeral, FALSE);
  424.         pItem = pItem->pNext;
  425.     }
  426.     
  427.     //pPoly is empty
  428.     if (bEmpty)
  429.     {
  430.         FPRINTF_ARGL(pHTMLFile, "0");
  431.         return FALSE;
  432.     }
  433.     return TRUE;
  434. }
  435.  
  436. Polynomial* HTMLPolynomialAdd(FILE* pHTMLFile,
  437.             Polynomial* pLeftPoly, Polynomial* pRightPoly)
  438. {
  439.     Polynomial* pTemPoly;
  440.     ItemNode* pTemNode;
  441.     CHECK_NONNULL_POINT(pHTMLFile);
  442.     CHECK_NONNULL_POINT(pLeftPoly);
  443.     CHECK_NONNULL_POINT(pRightPoly);
  444.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  445.     // (a + b) + (c + d)
  446.     FPRINTF_ARGL(pHTMLFile, "\n<hr><b>&nbsp;&nbsp;(");
  447.     HTMLPolynomial(pHTMLFile, pLeftPoly);
  448.     FPRINTF_ARGL(pHTMLFile, ") + (");
  449.     HTMLPolynomial(pHTMLFile, pRightPoly);
  450.     FPRINTF_ARGL(pHTMLFile, ")</b>");
  451.     //=ac + ad + bc +bd(formatted)
  452.     pTemPoly = CreateEmptyPolynomial(pLeftPoly->pronumeral);
  453.     pTemNode = pLeftPoly->pHeader;
  454.     while (NULL != pTemNode)
  455.     {
  456.         AddItemToFormattedPolynomial(pTemPoly, DuplicateItemNode(pTemNode));
  457.         pTemNode = pTemNode->pNext;
  458.     }
  459.     pTemNode = pRightPoly->pHeader;
  460.     while (NULL != pTemNode)
  461.     {
  462.         AddItemToFormattedPolynomial(pTemPoly, DuplicateItemNode(pTemNode));
  463.         pTemNode = pTemNode->pNext;
  464.     }
  465.     FPRINTF_ARGL(pHTMLFile, "<br>\n<b>=</b>&nbsp;");
  466.     HTMLPolynomial(pHTMLFile, pTemPoly);
  467.     return pTemPoly;
  468. }
  469.  
  470. Polynomial* HTMLPolynomialSubtract(FILE* pHTMLFile,
  471.                               Polynomial* pLeftPoly, Polynomial* pRightPoly)
  472. {
  473.     Polynomial* pTemPoly;
  474.     ItemNode* pTemNode;
  475.     CHECK_NONNULL_POINT(pHTMLFile);
  476.     CHECK_NONNULL_POINT(pLeftPoly);
  477.     CHECK_NONNULL_POINT(pRightPoly);
  478.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  479.     // (a + b) - (c + d)
  480.     FPRINTF_ARGL(pHTMLFile, "\n<hr><b>&nbsp;&nbsp;(");
  481.     HTMLPolynomial(pHTMLFile, pLeftPoly);
  482.     FPRINTF_ARGL(pHTMLFile, ") - (");
  483.     HTMLPolynomial(pHTMLFile, pRightPoly);
  484.     FPRINTF_ARGL(pHTMLFile, ")</b>");
  485.     //=ac + ad - bc - bd
  486.     FPRINTF_ARGL(pHTMLFile, "<br>\n<b>=</b>&nbsp;");
  487.     pTemPoly = CreateEmptyPolynomial(pLeftPoly->pronumeral);
  488.     pTemNode = pLeftPoly->pHeader;
  489.     while (NULL != pTemNode)
  490.     {
  491.         AddItemToPolynomial(pTemPoly, DuplicateItemNode(pTemNode));
  492.         pTemNode = pTemNode->pNext;
  493.     }
  494.     pTemNode = pRightPoly->pHeader;
  495.     while (NULL != pTemNode)
  496.     {
  497.         ItemNode* pDupItem = DuplicateItemNode(pTemNode);
  498.         pDupItem->quotiety = -pDupItem->quotiety;
  499.         AddItemToPolynomial(pTemPoly, pDupItem);
  500.         pTemNode = pTemNode->pNext;
  501.     }
  502.     HTMLPolynomial(pHTMLFile, pTemPoly);
  503.     //format, pTemPoly(out) != pTemPoly(in)
  504.     pTemPoly = CreateFormattedAndDelOldPolynomial(pTemPoly);
  505.     FPRINTF_ARGL(pHTMLFile, "<br>\n<b>=</b>&nbsp;");
  506.     HTMLPolynomial(pHTMLFile, pTemPoly);
  507.     return pTemPoly;
  508. }
  509.  
  510. Polynomial* HTMLPolynomialMultiply(FILE* pHTMLFile,
  511.                             Polynomial* pLeftPoly, Polynomial* pRightPoly)
  512. {
  513.     Polynomial* pOutPoly;
  514.     ItemNode *pCurLeft;
  515.     ItemNode *pCurRight;
  516.     ItemNode *pOutItem;
  517.     CHECK_NONNULL_POINT(pHTMLFile);
  518.     CHECK_NONNULL_POINT(pLeftPoly);
  519.     CHECK_NONNULL_POINT(pRightPoly);
  520.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  521.     
  522.     // (a + b) * (c + d)
  523.     FPRINTF_ARGL(pHTMLFile, "\n<hr><b>&nbsp;&nbsp;(");
  524.     HTMLPolynomial(pHTMLFile, pLeftPoly);
  525.     FPRINTF_ARGL(pHTMLFile, ") * (");
  526.     HTMLPolynomial(pHTMLFile, pRightPoly);
  527.     FPRINTF_ARGL(pHTMLFile, ")</b>");
  528.  
  529.     //= ac + ad + bc + bd
  530.     pCurLeft = pLeftPoly->pHeader;
  531.     pOutPoly = CreateEmptyPolynomial(pLeftPoly->pronumeral);
  532.     while (pCurLeft)
  533.     {
  534.         pCurRight = pRightPoly->pHeader;
  535.         while (pCurRight)
  536.         {
  537.             pOutItem = CreateItemNode(
  538.                 pCurLeft->quotiety * pCurRight->quotiety,
  539.                 pCurLeft->index + pCurRight->index);
  540.             AddItemToPolynomial(pOutPoly, pOutItem);
  541.             pCurRight = pCurRight->pNext;
  542.         }
  543.         pCurLeft = pCurLeft->pNext;
  544.     }
  545.     FPRINTF_ARGL(pHTMLFile, "<br>\n<b>=</b>&nbsp;");
  546.     HTMLPolynomial(pHTMLFile, pOutPoly);
  547.     //format
  548.     pOutPoly = CreateFormattedAndDelOldPolynomial(pOutPoly);
  549.     FPRINTF_ARGL(pHTMLFile, "<br>\n<b>=</b>&nbsp;");
  550.     HTMLPolynomial(pHTMLFile, pOutPoly);
  551.     return pOutPoly;
  552. }
  553.  
  554. /*****************************************************************************/
  555. //print pItem, this function should be changed if the type of
  556. //pronumeral or index changs
  557. BOOL PrintItemNode(ItemNode* pItem, char cPronum, BOOL bHead)
  558. {
  559.     CHECK_NONNULL_POINT(pItem);
  560.     if (0 == pItem->quotiety)
  561.         return FALSE;
  562.     if (bHead)
  563.     {
  564.         if (1 == pItem->quotiety)
  565.         {
  566.         }
  567.         else if (-1 == pItem->quotiety)
  568.         {
  569.             PRINTF_ARGL("-");
  570.         }
  571.         else
  572.         {
  573.             PRINTF_ARGL(_ARGL("%d")_ARGLEND(pItem->quotiety));
  574.         }
  575.     }
  576.     else
  577.     {
  578.         if (1 == pItem->quotiety)
  579.         {
  580.             PRINTF_ARGL(" + ");
  581.         }
  582.         else if (-1 == pItem->quotiety)
  583.         {
  584.             PRINTF_ARGL(" - ");
  585.         }
  586.         else
  587.         {
  588.             QType quot = pItem->quotiety;
  589.             char op = '+';
  590.             if (quot < 0)
  591.             {
  592.                 quot = - quot;
  593.                 op = '-';
  594.             }
  595.             PRINTF_ARGL(_ARGL(" %c %d")_ARGL(op)_ARGLEND(quot));
  596.         }
  597.     }
  598.     if (0 != pItem->index)
  599.     {
  600.         PRINTF_ARGL(_ARGL("%c")_ARGLEND(cPronum));
  601.         if (1 != pItem->index)
  602.         {
  603.             PRINTF_ARGL(_ARGL("^%d")_ARGLEND(pItem->index));
  604.         }
  605.     }
  606.     return TRUE;
  607. }
  608.  
  609. // print the Polynomial
  610. BOOL PrintPolynomial(Polynomial* pPoly)
  611. {
  612.     ItemNode* pItem;
  613.     BOOL bEmpty = TRUE;
  614.     CHECK_NONNULL_POINT(pPoly);
  615.     pItem = pPoly->pHeader;
  616.  
  617.     //print first item node
  618.     while (NULL != pItem)
  619.     {
  620.         if (PrintItemNode(pItem, pPoly->pronumeral, TRUE))
  621.         {
  622.             bEmpty = FALSE;
  623.             pItem = pItem->pNext;
  624.             break;
  625.         }
  626.         pItem = pItem->pNext;
  627.     }
  628.     //print other item node
  629.     while (NULL != pItem)
  630.     {
  631.         PrintItemNode(pItem, pPoly->pronumeral, FALSE);
  632.         pItem = pItem->pNext;
  633.     }
  634.     
  635.     //pPoly is empty
  636.     if (bEmpty)
  637.     {
  638.         PRINTF_ARGL("Empty Polynomial!!!");
  639.         return FALSE;
  640.     }
  641.     return TRUE;
  642. }
  643.  
  644. //user function to code
  645. int UserMain(int argc, char *argv[])
  646. {
  647.     Polynomial* pPoly = CreateEmptyPolynomial('x');
  648.     Polynomial* pPoly1;
  649.     Polynomial* pPoly2;
  650.     FILE* pHTMLFile = fopen("D:\\test.html", "a+");
  651.     CHECK_NONNULL_POINT(pHTMLFile);
  652.     AddItemToPolynomialEx(pPoly, -1, 5);
  653.     AddItemToPolynomialEx(pPoly, -3, 0);
  654.     AddItemToPolynomialEx(pPoly, +5, 2);
  655.     AddItemToPolynomialEx(pPoly, -33, -1);
  656.     AddItemToPolynomialEx(pPoly, -31, 2);
  657.     
  658.     PRINTF_ARGL("\npPoly: \n");
  659.     PrintPolynomial(pPoly);
  660.     PRINTF_ARGL("\n");
  661.     pPoly1 = CreateFormattedPolynomial(pPoly);
  662.     PRINTF_ARGL("\nFormatted pPoly1: \n");
  663.     PrintPolynomial(pPoly1);
  664.     PRINTF_ARGL("\n");
  665.  
  666.     AddItemToPolynomialEx(pPoly1, 4, 0);
  667.     AddItemToPolynomialEx(pPoly1, 0, 2);
  668.     AddItemToPolynomialEx(pPoly1, 0, 0);
  669.     AddItemToPolynomialEx(pPoly1, 1, 1);
  670.     PRINTF_ARGL("\nnew pPoly1: \n");
  671.     PrintPolynomial(pPoly1);
  672.     PRINTF_ARGL("\n");
  673.     //+
  674.     pPoly2 = PolynomialAdd(pPoly, pPoly1);
  675.     PRINTF_ARGL("\nAdd pPoly2: \n");
  676.     PrintPolynomial(pPoly2);
  677.     PRINTF_ARGL("\n");
  678.     FreePolynomial(pPoly2);
  679.     //-
  680.     pPoly2 = PolynomialSubtract(pPoly, pPoly1);
  681.     PRINTF_ARGL("\nSub pPoly2: \n");
  682.     PrintPolynomial(pPoly2);
  683.     PRINTF_ARGL("\n");
  684.     FreePolynomial(pPoly2);
  685.     //*
  686.     pPoly2 = PolynomialMultiply(pPoly, pPoly1);
  687.     PRINTF_ARGL("\nMulti pPoly2: \n");
  688.     PrintPolynomial(pPoly2);
  689.     PRINTF_ARGL("\n");
  690.     FreePolynomial(pPoly2);
  691.     //HTML +
  692.     pPoly2 = HTMLPolynomialAdd(pHTMLFile, pPoly, pPoly1);
  693.     FreePolynomial(pPoly2);
  694.     //HTML -
  695.     pPoly2 = HTMLPolynomialSubtract(pHTMLFile, pPoly, pPoly1);
  696.     FreePolynomial(pPoly2);
  697.     //HTML *
  698.     pPoly2 = HTMLPolynomialMultiply(pHTMLFile, pPoly, pPoly1);
  699.     FreePolynomial(pPoly2);
  700.     FreePolynomial(pPoly);
  701.     FreePolynomial(pPoly1);
  702.     return 0;
  703. }
  704.  
  705. int main(int argc, char *argv[])
  706. {
  707.     int runRslt;
  708. #if WRITE_SCREEN_TO_FILE
  709.     gpLogFile = fopen(SCREEN_LOG_FILE, "w+");
  710. #endif
  711.  
  712.     runRslt = UserMain(argc, argv);
  713.  
  714. #if WRITE_SCREEN_TO_FILE
  715.     fclose(gpLogFile);
  716. #endif
  717.     return runRslt;
  718. } 
]]> http://www.wscxy.com/shosh/article.asp?id=59 <![CDATA[C实现的一元多项式运算]]> shosh.zhu@qisda.com(shosh) Thu,25 Sep 2008 22:55:07 +0800 http://www.wscxy.com/shosh/default.asp?id=59 　　 昨晚回宿舍看到书上说链表可以用来表示一员多项式，可以用一个结构体来表示多项式中的一项。虽然书上的描述只有五六行100字左右，并没有给出任何代码，当时我只是觉得言之有理，也没多在意。

　　其实昨晚上床的时间还是挺早的，23:00多一点，宿舍里的其他两人都还没睡，所以拿起《操作系统原理》看了起来。快到24:00的时候感觉想睡觉了，于是就将书收起，睡觉。没过多久，宿舍就熄灯了，大家都上床睡觉了。

　　可是闭上眼睛，脑子里便始终想着那一元多项式的实现问题，我可以实现两个多项式加减乘操作，除实现不了，除非被除的多项式只有一项。基本上也可以实现二元的，三元的，但是有点麻烦。当然想得还有很多，包括如何读入多项式（将字符串parse成链表），如何输出多项式（将链表组织成字符串），因为dos窗口显示得会很不直观，可以考虑生成网页等……想了很多很多，基本上在大脑里已经形成了该功能的设计文档了，只是无法将它用文件保存下来。

　　实在该睡觉了，宿舍里的其他两位睡得香着呢。手机已经自动关机了（设置为00:30自动关机的），打开一看，已经凌晨一点一刻了。有关掉手机，强制自己睡觉。不知道过了多久（感觉没多久，估计01：30左右睡着了吧），就睡着了。

　　下午15：30去上了Protocal Team的课，关于通话方面的。讲课的同仁本希望17:00讲完的，不过因为ppt准备得太多太详细了，结果将到18:10分左右才完成。回来后发现食堂还有饭，就随便吃了一下，回到电脑前开始去写用于实现一元多项式的代码。（为了方便贴出来，所以就全部写在一个文件里。另外写出来的函数是假设供别人调用的，所以并不是所有的函数都能够在文件中找到调用的地方的）。

　　——对了，昨晚还想了招聘的时候面试的问题，很多面试之前都需要做一个笔试，笔试的内容多是C或C++的一些很基础的、很细节的甚至很偏的，实际写代码中往往是很少用甚至不用的，并且还是一些选择填空题，感觉像是学校里的考试，很没有意义的，感觉很不科学的。我想技术面试就应该提供一台电脑，可以上网，甚至提供函数的使用帮助文档，允许考试者检索各种资料，方面外面连一台电脑监视考试房间内电脑的桌面。给考试着2-3小时，写一个中等程度复杂的编程题（最好出几道，让考试者选择完成其中的一两道题目），这样才真的比较全面考验，同时也可以看出考试者的编程习惯的好坏等。否则只是考考概念性的，即使不会编程的，临考前多看几分样卷，或许还能够考得不错。——希望以后会有公司采用这样的技术面试的方法吧。

　　晚上到现在已经把轮廓完成了，乘法还没有实现，读入和输出部分也没有做（简单写了一个PrintPolynomial函数，用来测试能否链表是否正确，因为负数能输出"-"号，而正数不能够输出"+"号，所以请先用负数测试，或完善该函数后再使用整数测试），也没有测试后面的代码。先贴上，明天继续……

 后续补充代码：《C实现的一元多项式运算[2]--链表运算》

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. #if defined NULL
  6.     #undef NULL
  7. #endif
  8. #define NULL 0
  9.  
  10. #define Create_ENTITY(type, name) \
  11.         type* name = (type*) malloc(sizeof(type)); \
  12.         assert(NULL != name)                    
  13.  
  14. #define CHECK_NONNULL_POINT(p)  \
  15.         assert(NULL != p)
  16. #define CHECK_SAME_VALUE(a,b)   \
  17.         assert((a) == (b))
  18.  
  19. #define FREEIF(p) \
  20.         if (NULL != p)  \
  21.         {               \
  22.             free(p);   \
  23.             p = NULL;  \
  24.         }
  25.  
  26. typedef unsigned int uint;
  27. typedef float QType;
  28. typedef int IType;
  29. //多项式中的项
  30. typedef struct _ItemNode ItemNode;
  31. struct _ItemNode
  32. {
  33.     ItemNode*   pNext;     //指向下一项
  34.     QType       quotiety;  //系数
  35.     IType       index;     //指数
  36. };
  37.  
  38. typedef struct
  39. {
  40.     ItemNode*   pHeader;   //多项式中的第一项
  41.     ItemNode*   pLast;     //多项式中的最后一项
  42.     char        pronumeral; //未知数名，如x,y,z
  43.     uint        ItemNum;   //项数
  44. } Polynomial;
  45.  
  46. //Create one empty polymonial
  47. Polynomial* CreateEmptyPolynomial(char name)
  48. {
  49.     Create_ENTITY(Polynomial, pPoly);
  50.     pPoly->pHeader = pPoly->pLast = NULL;
  51.     pPoly->pronumeral = name;
  52.     pPoly->ItemNum = 0;
  53.     return pPoly;
  54. }
  55.  
  56. //Create one polynomial with one item
  57. Polynomial* CreatePolynomial(char name, ItemNode* head)
  58. {
  59.     Polynomial* pPoly = CreateEmptyPolynomial(name);
  60.     pPoly->pHeader = pPoly->pLast = head;
  61.     pPoly->ItemNum = 1;
  62.     return pPoly;
  63. }
  64.  
  65. //Create one Item Node
  66. ItemNode* CreateItemNode(QType quotiety, IType index)//系数，指数
  67. {
  68.     Create_ENTITY(ItemNode, pItem);
  69.     pItem->quotiety = quotiety;
  70.     pItem->index = index;
  71.     pItem->pNext = NULL;
  72.     return pItem;
  73. }
  74.  
  75. //Duplicate an ItemNode
  76. ItemNode* DuplicateItemNode(ItemNode* pItem)
  77. {
  78.     Create_ENTITY(ItemNode, pNewItem);
  79.     pNewItem->index = pItem->index;
  80.     pNewItem->quotiety = pItem->quotiety;
  81.     pNewItem->pNext = pItem->pNext;
  82.     return pNewItem;
  83. }
  84.  
  85. void FreeItemNode(ItemNode* pItem)
  86. {
  87.     FREEIF(pItem);
  88. }
  89.  
  90.  
  91. void FreePolynomial(Polynomial* pPoly)
  92. {
  93.     ItemNode *temNode;
  94.     CHECK_NONNULL_POINT(pPoly);
  95.  
  96.     temNode = pPoly->pHeader;
  97.     while (NULL != temNode)
  98.     {
  99.         //we cannot simply use temNode = temNode->pNext after call FreeItemNode
  100.         //but use this method, because the struct has been freed and we would
  101.         //not get proper value of temNode->pNext.
  102.         pPoly->pHeader = temNode->pNext;
  103.         FreeItemNode(temNode);
  104.         temNode = pPoly->pHeader;
  105.     }
  106.     FREEIF(pPoly);
  107. }
  108.  
  109. //Add one Item to polynomial,and return the ItemNode Num.
  110. int AddItemToPolynomial(Polynomial* pPoly, ItemNode* pItem)
  111. {
  112.     CHECK_NONNULL_POINT(pPoly);
  113.     CHECK_NONNULL_POINT(pItem);
  114.     if (NULL != pPoly->pLast) //this means pPoly->pHeader != NULL
  115.     {
  116.         if (NULL == pPoly->pHeader->pNext) //when there is only one item
  117.             pPoly->pHeader->pNext = pPoly->pLast;
  118.         pPoly->pLast->pNext = pItem;
  119.     }
  120.     else //the first item node
  121.     {
  122.         pPoly->pHeader = pItem;
  123.     }
  124.     pPoly->pLast = pItem;
  125.     pPoly->pLast->pNext = NULL;
  126.     return ++pPoly->ItemNum;
  127. }
  128.  
  129. //add one item to a formatted polynomial, and return the itemnode num.
  130. //please ensure that pPoly is formatted, that is its index is in Desc order.
  131. //pItem must be new built(not is a member of another polynomial)
  132. int AddItemToFormattedPolynomial(Polynomial* pPoly, ItemNode* pItem)
  133. {
  134.     CHECK_NONNULL_POINT(pPoly);
  135.     CHECK_NONNULL_POINT(pItem);
  136.     if (NULL == pPoly->pHeader)
  137.     {
  138.         pPoly->pHeader = pPoly->pLast = pItem;
  139.     }
  140.     else
  141.     {
  142.         ItemNode* pTemItem = pPoly->pHeader;
  143.         ItemNode* pLastValidItem = pTemItem; //this cannot be NULL
  144.         while (NULL != pTemItem && pTemItem->index > pItem->index)
  145.         {
  146.             pLastValidItem = pTemItem;
  147.             pTemItem = pTemItem->pNext;
  148.         }
  149.         if (NULL == pTemItem) //insert it to the end
  150.         {
  151.             pLastValidItem->pNext = pItem;
  152.             pPoly->pLast = pItem;
  153.         }
  154.         else if (pTemItem->index == pItem->index) //no insert it
  155.         {
  156.             pTemItem->quotiety += pItem->quotiety;
  157.             //remember to free pItem, for we have not add it to the pPoly
  158.             FreeItemNode(pItem);
  159.         }
  160.         else //insert it normally
  161.         {
  162.             pLastValidItem->pNext = pItem;
  163.             pItem->pNext = pTemItem;
  164.         }
  165.     }
  166.  
  167.     pPoly->pLast->pNext = NULL;
  168.     return ++pPoly->ItemNum;
  169. }
  170.  
  171. //Create a Formatted Polynomial from a non-formatted polynomial by index DESC
  172. Polynomial* CreateFormattedPolynomial(Polynomial* pPoly)
  173. {
  174.     Polynomial* pFmtPoly;
  175.     ItemNode* pTemNode;
  176.     CHECK_NONNULL_POINT(pPoly);
  177.     pFmtPoly = CreateEmptyPolynomial(pPoly->pronumeral);
  178.     pTemNode = pPoly->pHeader;
  179.     while (NULL != pTemNode)
  180.     {
  181.         AddItemToFormattedPolynomial(pFmtPoly, 
  182.                 DuplicateItemNode(pTemNode));
  183.         pTemNode = pTemNode->pNext;
  184.     }
  185.     return pFmtPoly;
  186. }
  187.  
  188. //Create a Formatted Polynomial and delete the old one
  189. Polynomial* CreateFormattedAndDelOldPolynomial(Polynomial* pPoly)
  190. {
  191.     Polynomial* pFmtPoly;
  192.     ItemNode* pTemNode;
  193.     ItemNode* pCurNode;
  194.     CHECK_NONNULL_POINT(pPoly);
  195.     pFmtPoly = CreateEmptyPolynomial(pPoly->pronumeral);
  196.     pTemNode = pPoly->pHeader;
  197.     while (NULL != pTemNode)
  198.     {
  199.         //it is the defference between this function and
  200.         //CreateFormattedPolynomial concerning the freedom of pTemNode.
  201.         pCurNode = pTemNode->pNext;
  202.         AddItemToFormattedPolynomial(pFmtPoly, pTemNode);
  203.         pTemNode = pCurNode;
  204.     }
  205.     FREEIF(pPoly);
  206.     return pFmtPoly;
  207. }
  208.  
  209. //Create a new ItemNode with quotiety and index first,
  210. //and then insert the node to pPoly at the tail(non-formatted).
  211. int AddItemToPolynomialEx(Polynomial* pPoly, QType quotiety, IType index)
  212. {
  213.     return AddItemToPolynomial(pPoly, CreateItemNode(quotiety, index));
  214. }
  215.  
  216. /***************************** + - * operations ******************************/
  217. //pLeftPoly and pRightPoly can be either formatted or non-formatted in these
  218. //three functions, but the new created polynomial(return value) is formatted.
  219.  
  220. //+: pLeftPoly + pRightPoly
  221. Polynomial* PolynomialAdd(Polynomial* pLeftPoly, Polynomial* pRightPoly)
  222. {
  223.     Polynomial* pOutPoly;
  224.     CHECK_NONNULL_POINT(pLeftPoly);
  225.     CHECK_NONNULL_POINT(pRightPoly);
  226.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  227.     //pOutPoly = CreateEmptyPolynomial(pLeftPoly->pronumeral);
  228.     //just link two polynomials to simplize the actions.
  229.     pLeftPoly->pLast->pNext = pRightPoly->pHeader;
  230.     //calculating pLeftPoly->ItemNum is not needed,
  231.     //just for further consideration
  232.     pLeftPoly->ItemNum += pRightPoly->ItemNum;
  233.     pOutPoly = CreateFormattedPolynomial(pLeftPoly);
  234.     //set back
  235.     pLeftPoly->ItemNum -= pRightPoly->ItemNum;
  236.     pLeftPoly->pLast->pNext = NULL;
  237.     return pOutPoly;
  238. }
  239.  
  240. //-: pLeftPoly - pRightPoly
  241. Polynomial* PolynomialSubtract(Polynomial* pLeftPoly, Polynomial* pRightPoly)
  242. {
  243.     Polynomial* pOutPoly;
  244.     ItemNode* pTemNode;
  245.     ItemNode* pNewNode;
  246.     CHECK_NONNULL_POINT(pLeftPoly);
  247.     CHECK_NONNULL_POINT(pRightPoly);
  248.     CHECK_SAME_VALUE(pLeftPoly->pronumeral, pRightPoly->pronumeral);
  249.     pOutPoly = CreateFormattedPolynomial(pLeftPoly);
  250.     pTemNode = pRightPoly->pHeader;
  251.     while (NULL != pTemNode)
  252.     {
  253.         pNewNode = DuplicateItemNode(pTemNode);
  254.         pNewNode->quotiety = -pNewNode->quotiety;
  255.         AddItemToFormattedPolynomial(pOutPoly, pNewNode);
  256.         pTemNode = pTemNode->pNext;
  257.     }
  258.     return pOutPoly;
  259. }
  260.  
  261. //*: pLeftPoly * pRightPoly
  262. Polynomial* PolynomialMultiply(Polynomial* pLeftPoly, Polynomial* pRightPoly)
  263. {
  264.     CHECK_NONNULL_POINT(pLeftPoly);
  265.     CHECK_NONNULL_POINT(pRightPoly);
  266.     return NULL;//not finished, just for avoiding warnings.
  267. }
  268.  
  269.  
  270. /*****************************************************************************/
  271. // print the Polynomial, this function should be changed if the type of
  272. // pronumeral or index changs
  273. void PrintPolynomial(Polynomial* pPoly)
  274. {
  275.     ItemNode* pItem;
  276.     CHECK_NONNULL_POINT(pPoly);
  277.     pItem = pPoly->pHeader;
  278.     while (NULL != pItem)
  279.     {
  280.         printf("%.2f%c^%d", pItem->quotiety, pPoly->pronumeral, pItem->index);
  281.         pItem = pItem->pNext;
  282.     }
  283. }
  284.  
  285. int main()
  286. {
  287.     Polynomial* pPoly = CreateEmptyPolynomial('c');
  288.     Polynomial* pPoly1;
  289.     Polynomial* pPoly2;
  290.     AddItemToPolynomialEx(pPoly, -2, 5);
  291.     AddItemToPolynomialEx(pPoly, -3, 1);
  292.     AddItemToPolynomialEx(pPoly, -5, 2);
  293.     AddItemToPolynomialEx(pPoly, -33, 1);
  294.     AddItemToPolynomialEx(pPoly, -31, 2);
  295.  
  296.     printf("set up poly:\n");
  297.     PrintPolynomial(pPoly);
  298.     printf("\ncreate formatted one:\nold: ");
  299.     pPoly1 = CreateFormattedPolynomial(pPoly);
  300.     PrintPolynomial(pPoly);
  301.     printf("\nnew: ");
  302.     PrintPolynomial(pPoly1);
  303.     printf("\ncreate formatted one and delete the old:\nold: ");
  304.     pPoly2 = CreateFormattedAndDelOldPolynomial(pPoly);
  305. //  PrintPolynomial(pPoly); //should be NULL
  306.     printf("\nnew: ");
  307.     PrintPolynomial(pPoly2);
  308.     printf("\n");
  309.     FreePolynomial(pPoly1);
  310.     FreePolynomial(pPoly2);
  311.     return 0;
  312. } 
]]> http://www.wscxy.com/shosh/article.asp?id=51 <![CDATA[C语言实现的从1到N的出现M的次数算法]]> shosh.zhu@qisda.com(shosh) Tue,26 Aug 2008 20:07:13 +0800 http://www.wscxy.com/shosh/default.asp?id=51 下面的代码仅取了特殊值，根据需要去修改。函数名命名不直观，不过还好，有注释说明。

网上也有用C++的模板类实现的，不过我不熟悉，有兴趣的朋友自己去搜索一下。

  1. #include <stdio.h>
  2. unsigned long func(int a, int n)//求组合c(a,n) 
  3. {
  4.     unsigned long result = 1, temp = 1;
  5.     int i;
  6.     for (i = n;i > n-a; i--)
  7.     {
  8.         result *= i;
  9.     }
  10.     
  11.     for (;a > 0; a--)
  12.     {
  13.         temp *= a;
  14.     }
  15.     if (temp != 0)
  16.         result /= temp;
  17.     return result;
  18. }
  19.  
  20. unsigned long fun(int a, int n)//求a^n
  21. {
  22.     int result;
  23.     if (n == 0)
  24.     {
  25.         result = 1;
  26.     }
  27.     else
  28.     {
  29.         result = a;
  30.     }
  31.     
  32.     for (;n > 1;n--)
  33.     {
  34.         result *= a;
  35.     }
  36.     return result;
  37. }
  38.  
  39. unsigned long _findm(unsigned long a)//a位数，包含m的情况有多少
  40. {
  41.     unsigned long i, result = 0;
  42.     for (i = 1; i <= a; i++)
  43.     {//有i个m的情况
  44.         result += (func(i, a)*fun(9, a-i));
  45.     }
  46.     return result;
  47. }
  48.  
  49. unsigned long findm(unsigned long arg, unsigned long m)//0～arg之间有多少个含有m的整数
  50. {
  51.     unsigned long n = 0, a = 1;//arg是n+1位数，第一位数字是a，其余位都是0
  52.     unsigned long result;
  53.     a = arg;
  54.     while (a > 10)
  55.     {
  56.         a /= 10;
  57.         n++;
  58.     }
  59.     result = _findm(n);
  60.     if (a < m)
  61.     {
  62.         result *= a;
  63.     }
  64.     else 
  65.     {
  66.         result *= (a-1);
  67.         result += (arg/a);
  68.     }
  69.     return result;
  70. }
  71.  
  72. unsigned long group(unsigned long n, unsigned long a)//将n分组，起点是a，返回终点
  73. {
  74.     unsigned long result;
  75.     int i = 0;
  76.     n -= a;
  77.     while (n > 10)
  78.     {
  79.         n /= 10;
  80.         i++;
  81.     }
  82.     result = fun(10, i);
  83.     result *= n;
  84.     return result;
  85. }
  86.  
  87. unsigned long calc(unsigned long n, unsigned long m)//计算从1到N之间的整数有多少个含有数字m
  88. {
  89.     unsigned long a = 0, b, result = 0;
  90.     do
  91.     {
  92.         b = group(n, a);
  93.         result += findm(b, m);
  94.         a += b;
  95.     } while (b != 0);
  96.     return result;
  97. }
  98.  
  99. void main()
  100. {
  101.     unsigned long result, n, m;
  102.     //    printf("Input N:");scanf("%d", &n);
  103.     //    printf("Input M:");scanf("%d", &m);
  104.     n = 2008080808;
  105.     m = 7;
  106.         result = calc(n, m);
  107.     if (m == 0)
  108.         result--;
  109.     printf("共有%d个整数含有7\n", result);
  110. } 

不过，其实这已经是数学的问题了，先归纳出通项式，然后实现该通项式的算法即可。所以看来没多少意义了。

/////分析过程如下：（计算有多少个1）

只到个位最大数9时，即0~9　只有1个1
    即A1 = 1
到十位最大数99时，即0~99　有　10　+　10 = 20个
　　这里第一个10是01，11，21…91　共10个，第二个10是　10，11，12，13，…19共10个
    即A2 = A1*10 + 10^1
到百位最大数999时，有（10 + 10）* 10 + 10

]]> http://www.wscxy.com/shosh/article.asp?id=47 <![CDATA[C语言类型修饰符]]> shosh.zhu@qisda.com(shosh) Sun,10 Aug 2008 13:45:33 +0800 http://www.wscxy.com/shosh/default.asp?id=47      在一般的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的写操作而将读取操作外提到循环体外而导致死循环。
 

]]>