Archive for category Programming

Thanks to Korek..

Posted by xiaokucha in Programming on May 3, 2008

 
Great thanks to those people who contributed and are still contributing to this project.  I will try to get this running in the small portable things like usb-wifi card(Phrack #65) or my ndsl or mobile linux phone, though not very useful(assuming people are using WPA).
 
It seems impossible to access this website in China, in that case try www.wirelessdefence.org.
 
btw, thanks to the great song "Ruled by Secrecy" from Muse, the piano makes me high..

Leave a comment

c++的几种cast zz

Posted by xiaokucha in Programming on April 12, 2007

先看看这篇文章，然后说一下问题:

 

一共四种cast。1、static_cast，支持子类指针到父类指针的转换，并根据实际情况调整指针的值，反过来也支持，但会给出编译警告，它作用最类似C风格的“强制转换”，一般来说可认为它是安全的；2、dynamic_cast，支持子类指针到父类指针的转换，并根据实际情况调整指针的值，和static_cast不同，反过来它就不支持了，会导致编译错误，这种转换是最安全的转换；3、reinterpret_cast，支持任何转换，但仅仅是如它的名字所描述的那样“重解释”而已，不会对指针的值进行任何调整，用它完全可以做到“指鹿为马”，但很明显，它是最不安全的转换，使用它的时候，你得头脑清醒，知道自己在干什么；4、const_cast，这个转换能剥离一个对象的const属性，也就是说允许你对常量进行修改。

 

这样回答即使得不了满分，拿个八九十分应该也没问题了，我后来还专门写了些测试程序来验证过，对于第一第二第三种转换都没什么问题，而const_cast却似乎不能正常工作，代码如下：

int main(int argc, char* argv[])

{

     const int ic=100;

     const_cast<int &>(ic)=200;

     printf("%dn", ic);

     return 0;

}

 

结果不是我期待的200，而是100，我一开始以为这是由于优化选项的问题，于是调整编译器选项，全部不优化，但还是一样的结果，我开始怀疑这是VC++的bug，于是使用Linux的g++来编译，结果一样，看来这和编译器没有关系，那我究竟做错了哪里呢？或者我对const_cast理解错了呢？我开始改进我的代码，我尝试不同的类型：

class CTest

{

public:

     CTest(int i){m_val = i;printf("construction [%d]n", m_val);};

     ~CTest(){printf("destructionn");};

     void SelfAdd(){m_val++;};

     int m_val;

};

 

int main(int argc, char* argv[])

{

     const CTest test(1000);

     CTest test2(1050);

     const_cast<CTest &>(test)= test2;

     printf("%dn", test.m_val);

     return 0;

}

 

这次总算得到了我想要得到结果，打印出了1050，说明const_cast并没有问题，但前一个程序为什么不能正常工作？我继续尝试了不同的类型，比如char，short，float，double等，发现了规律，凡是对结构体或类进行这个转换，都是成功的，但对char，short等基本类型的转换都没有成功。我进一步改进代码，为了查看它们的值是否真的已经被修改，我使用了指针：

int main(int argc, char* argv[])

{

     const int ic = 100;

     const int *pc=&ic;

     const_cast<int &>(ic)++;

     printf("%d,%dn", ic, *pc);

     return 0;

}

 

这次打印出来的结果是“100,101”，这就说明常量ic的值确实已经被改变了，但为什么直接打印ic就得不到正确的结果？那估计还是前边想到的“优化”的原因，可我一再确认我并没有使用优化编译选项，而且g++的表现也如此。看来只好使用最后一招了，直接查看printf究竟做了些什么，在printf处设置断点，调试程序，然后打开disassembly视图查看反汇编代码，一切真相大白。

 

原来虽然我没有使用优化，但系统还是对ic这个const进行了预编译般的替换，将它替换成“64h”（十六进制的64就是十进制的100），这究竟是不是C++的规范？我不知道，但我肯定这不是一般用户想要的结果，对我来说，算是个C++的bug吧。通过解决这个问题，我也学会了些东西，如果以后遇到类似这种表面上再显浅不过，但就是不能正常工作的代码片断，要学会查看反汇编代码，也许一切问题迎刃而解，另外使用const_cast的时候应该注意些什么东西，嗯，自己思考一下吧。Java没有const_cast，很多语言都没有，（我只知道C++有）既然已经被定义为常量，就是不希望它被改变，但现在又允许你改变它，这不是很可笑吗？但难道它不是C++强大又灵活的又一体现吗？不过话说回来要看你怎么用了。

 

好了，文章说的很清楚，const_cast可以修改常量，可以修改类，不过这里主要出现的问题就是编译器的处理。

试想如果这样写代码:

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])

{

     const volatile int ic = 100;//volatile

     const volatile int *pc=&ic;

     const_cast<int &>(ic)++;

     printf("%d,%dn", ic, *pc);
     system("pause");
     return 0;

}

程序就会输出101,101，因为volatile以后，跳过了编译器指定寄存器中的内容，直接取的内存中数值，所以文章中之所以总会出现ic原来的值，是因为寄存器中值的假象。手头没有vc++不知道debug模式下，const_cast之后,printf会不会调用内存值。而对于类，个人认为类每次取的值不可能在寄存器中，应该是每次取一次内存，所以不会出现假象

Leave a comment

huawei最后一道小题

Posted by xiaokucha in Programming on April 7, 2007

tree和forest的结构有些差别，tree包含data ,lchild ,rchild，而forest则是data,firstchild nextsibling;
 
 
typedef struct tnode{
        char tdata;
        struct tnode *lchild,*rchild;
        }tnode,*tree;
typedef struct fnode{
        char fdata;
        struct fnode *firstchild,*nextsibling;
        }fnode,*forest;
void foresttotree(forest a,tree b){
     if(a){
           if(!(b=(tnode *)malloc(sizeof(tnode))))
           exit(0);
           b->tdata=a->fdata;
           foresttotree(a->firstchild,b->lchild);
           foresttotree(a->nextsibling,b->rchild);
           }
           }
 
当时我写的用的也是递归，不过struct那里没有定义好，sb了，这段代码我看着好像有问题，看客望请指点，算是抛砖引玉。。。

Leave a comment

linus写的,貌似

Posted by xiaokucha in Programming on April 6, 2007

/*  
   2     *     linux/lib/string.c  
   3     *  
   4     *     Copyright   (C)   1991,   1992     Linus   Torvalds  
   5     */  
   6    
   7   /*  
   8     *   stupid   library   routines..   The   optimized   versions   should   generally   be   found  
   9     *   as   inline   code   in   <asm-xx/string.h>  
   10     *  
   11     *   These   are   buggy   as   well..  
   12     */  
   13      
   14   #include   <linux/types.h>  
   15    
   16   char   *   ___strtok   =   NULL;  
   17    
   18   char   *   strcpy(char   *   dest,const   char   *src)  
   19   {  
   20                   char   *tmp   =   dest;  
   21    
   22                   while   ((*dest++   =   *src++)   !=   ”)  
   23                                   /*   nothing   */;  
   24                   return   tmp;  
   25   }  
   26    
   27   char   *   strncpy(char   *   dest,const   char   *src,size_t   count)  
   28   {  
   29                   char   *tmp   =   dest;  
   30    
   31                   while   (count–   &&   (*dest++   =   *src++)   !=   ”)  
   32                                   /*   nothing   */;  
   33    
   34                   return   tmp;  
   35   }  
   36    
   37   char   *   strcat(char   *   dest,   const   char   *   src)  
   38   {  
   39                   char   *tmp   =   dest;  
   40    
   41                   while   (*dest)  
   42                                   dest++;  
   43                   while   ((*dest++   =   *src++)   !=   ”)  
   44                                   ;  
   45    
   46                   return   tmp;  
   47   }  
   48    
   49   char   *   strncat(char   *dest,   const   char   *src,   size_t   count)  
   50   {  
   51                   char   *tmp   =   dest;  
   52    
   53                   if   (count)   {  
   54                                   while   (*dest)  
   55                                                   dest++;  
   56                                   while   ((*dest++   =   *src++))   {  
   57                                                   if   (–count   ==   0)  
   58                                                                   break;  
   59                                   }  
   60                   }  
   61    
   62                   return   tmp;  
   63   }  
   64    
   65   int   strcmp(const   char   *   cs,const   char   *   ct)  
   66   {  
   67                   register   signed   char   __res;  
   68    
   69                   while   (1)   {  
   70                                   if   ((__res   =   *cs   –   *ct++)   !=   0   ||   !*cs++)  
   71                                                   break;  
   72                   }  
   73    
   74                   return   __res;  
   75   }  
   76    
   77   int   strncmp(const   char   *   cs,const   char   *   ct,size_t   count)  
   78   {  
   79                   register   signed   char   __res   =   0;  
   80    
   81                   while   (count)   {  
   82                                   if   ((__res   =   *cs   –   *ct++)   !=   0   ||   !*cs++)  
   83                                                   break;  
   84                                   count–;  
   85                   }  
   86    
   87                   return   __res;  
   88   }  
   89    
   90   char   *   strchr(const   char   *   s,char   c)  
   91   {  
   92                   for(;   *s   !=   c;   ++s)  
   93                                   if   (*s   ==   ”)  
   94                                                   return   NULL;  
   95                   return   (char   *)   s;  
   96   }  
   97    
   98   size_t   strlen(const   char   *   s)  
   99   {  
   100                   const   char   *sc;  
   101    
   102                   for   (sc   =   s;   *sc   !=   ”;   ++sc)  
   103                                   /*   nothing   */;  
   104                   return   sc   –   s;  
   105   }  
   106    
   107   size_t   strnlen(const   char   *   s,   size_t   count)  
   108   {  
   109                   const   char   *sc;  
   110    
   111                   for   (sc   =   s;   *sc   !=   ”   &&   count–;   ++sc)  
   112                                   /*   nothing   */;  
   113                   return   sc   –   s;  
   114   }  
   115    
   116   size_t   strspn(const   char   *s,   const   char   *accept)  
   117   {  
   118                   const   char   *p;  
   119                   const   char   *a;  
   120                   size_t   count   =   0;  
   121    
   122                   for   (p   =   s;   *p   !=   ”;   ++p)   {  
   123                                   for   (a   =   accept;   *a   !=   ”;   ++a)   {  
   124                                                   if   (*p   ==   *a)  
   125                                                                   break;  
   126                                   }  
   127                                   if   (*a   ==   ”)  
   128                                                   return   count;  
   129                                   ++count;  
   130                   }  
   131    
   132                   return   count;  
   133   }  
   134    
   135   char   *   strpbrk(const   char   *   cs,const   char   *   ct)  
   136   {  
   137                   const   char   *sc1,*sc2;  
   138    
   139                   for(   sc1   =   cs;   *sc1   !=   ”;   ++sc1)   {  
   140                                   for(   sc2   =   ct;   *sc2   !=   ”;   ++sc2)   {  
   141                                                   if   (*sc1   ==   *sc2)  
   142                                                                   return   (char   *)   sc1;  
   143                                   }  
   144                   }  
   145                   return   NULL;  
   146   }  
   147    
   148   char   *   strtok(char   *   s,const   char   *   ct)  
   149   {  
   150                   char   *sbegin,   *send;  
   151    
   152                   sbegin     =   s   ?   s   :   ___strtok;  
   153                   if   (!sbegin)   {  
   154                                   return   NULL;  
   155                   }  
   156                   sbegin   +=   strspn(sbegin,ct);  
   157                   if   (*sbegin   ==   ”)   {  
   158                                   ___strtok   =   NULL;  
   159                                   return(   NULL   );  
   160                   }  
   161                   send   =   strpbrk(   sbegin,   ct);  
   162                   if   (send   &&   *send   !=   ”)  
   163                                   *send++   =   ”;  
   164                   ___strtok   =   send;  
   165                   return   (sbegin);  
   166   }  
   167    
   168   void   *   memset(void   *   s,char   c,size_t   count)  
   169   {  
   170                   char   *xs   =   (char   *)   s;  
   171    
   172                   while   (count–)  
   173                                   *xs++   =   c;  
   174    
   175                   return   s;  
   176   }  
   177    
   178   char   *   bcopy(const   char   *   src,   char   *   dest,   int   count)  
   179   {  
   180                   char   *tmp   =   dest;  
   181    
   182                   while   (count–)  
   183                                   *tmp++   =   *src++;  
   184    
   185                   return   dest;  
   186   }  
   187    
   188   void   *   memcpy(void   *   dest,const   void   *src,size_t   count)  
   189   {  
   190                   char   *tmp   =   (char   *)   dest,   *s   =   (char   *)   src;  
   191    
   192                   while   (count–)  
   193                                   *tmp++   =   *s++;  
   194    
   195                   return   dest;  
   196   }  
   197    
   198   void   *   memmove(void   *   dest,const   void   *src,size_t   count)  
   199   {  
   200                   char   *tmp,   *s;  
   201    
   202                   if   (dest   <=   src)   {  
   203                                   tmp   =   (char   *)   dest;  
   204                                   s   =   (char   *)   src;  
   205                                   while   (count–)  
   206                                                   *tmp++   =   *s++;  
   207                                   }  
   208                   else   {  
   209                                   tmp   =   (char   *)   dest   +   count;  
   210                                   s   =   (char   *)   src   +   count;  
   211                                   while   (count–)  
   212                                                   *–tmp   =   *–s;  
   213                                   }  
   214    
   215                   return   dest;  
   216   }  
   217    
   218   int   memcmp(const   void   *   cs,const   void   *   ct,size_t   count)  
   219   {  
   220                   const   unsigned   char   *su1,   *su2;  
   221                   signed   char   res   =   0;  
   222    
   223                   for(   su1   =   cs,   su2   =   ct;   0   <   count;   ++su1,   ++su2,   count–)  
   224                                   if   ((res   =   *su1   –   *su2)   !=   0)  
   225                                                   break;  
   226                   return   res;  
   227   }  
   228    
   229   /*  
   230     *   find   the   first   occurrence   of   byte   ‘c’,   or   1   past   the   area   if   none  
   231     */  
   232   void   *   memscan(void   *   addr,   unsigned   char   c,   size_t   size)  
   233   {  
   234                   unsigned   char   *   p   =   (unsigned   char   *)   addr;  
   235    
   236                   while   (size)   {  
   237                                   if   (*p   ==   c)  
   238                                                   return   (void   *)   p;  
   239                                   p++;  
   240                                   size–;  
   241                   }  
   242                   return   (void   *)   p;  
   243   } 

Leave a comment

memcpy()&memmove()

Posted by xiaokucha in Programming on April 6, 2007

void * __cdecl memcpy (
        void * dst,
        const void * src,
        size_t count
        )

{
        void * ret = dst;
        /*
         * copy from lower addresses to higher addresses
         */
        while (count–) {
                *(char *)dst = *(char *)src;
                dst = (char *)dst + 1;
                src = (char *)src + 1;
        }
        return(ret);
}

void * __cdecl memmove (
        void * dst,
        const void * src,
        size_t count
        )
{
        void * ret = dst;
        if (dst <= src || (char *)dst >= ((char *)src + count)) {
                /*
                 * Non-Overlapping Buffers
                 * copy from lower addresses to higher addresses
                 */
                while (count–) {
                        *(char *)dst = *(char *)src;
                        dst = (char *)dst + 1;
                        src = (char *)src + 1;
                }
        }
        else {
                /*
                 * Overlapping Buffers
                 * copy from higher addresses to lower addresses
                 */
                dst = (char *)dst + count – 1;
                src = (char *)src + count – 1;
 
                while (count–) {
                        *(char *)dst = *(char *)src;
                        dst = (char *)dst – 1;
                        src = (char *)src – 1;
                }
        }
 
        return(ret);
}

今天huawei一个小题，如下:

char *str1="this is a string";

char *str2="this is a string";

memcpy(str1+4,str1,6);

memmove(str2+4,str2,6);

printf("%sn",str1);

printf("%sn",str2);

这段程序在现在的编译器比如dev-c++上compile会报错，就是因为在我以前写的潜规则中提到的char *定义赋值字符串问题，这种写法已经被淘汰了，因为char *现在一般用于定义指针而无内部类型，这里最好用char [20];

然后在tc2上编译了一下，发现自己sb了。。。

结果如下:

thisthisthstring

thisthis istring

不过在dev-c++上面将*改为[]后，发现结果如下

thisthis istring
thisthis istring

主要的问题就是Overlap(内存重叠),上面的CRT代码已经写出来了memcpy和memmove的区别，memcpy是memmove的子集，memmove可以对于重叠的内存操作进行逆序处理。。。memcpy对于重叠的copy会出现非所期望的结果，在copy的同时改变了src的内容，所以对于src，我们强调一定要const。。。根据上述结果可以猜测tc2里面的memcpy和memmove没有强调src的const，而现在的CRT应该是上面所ctrl+v的

对于旧的c标准，我是sb，同时，对于新的标准，这道题sb，以上。

1 Comment

volatile(zz from csdn)

Posted by xiaokucha in Programming on April 3, 2007

如果你懂一点点的编译器的知识我想你都会知道编译器在编译你的代码的时候，用进行自动优化的，用以产生优化指令。同上操作系统和一些线程同样也会对你所定义的一些变量做出一些你所不知道的更改。这样的更改我们称为，隐式修改，因为你不知道，编译器在什么情况下，在那里做出了优化，甚至你都不知道，或是不能肯定编译器到底有没有对你的代码做出优化。
直接点把你看看下面的例子
 
＃include <iostream>
void main()
{
int i=10;
int a = i;
printf("i= %dn",a);
__asm {
mov dword ptr [ebp-4], 50h
}
//下面汇编语句的作用就是改变内存中i的值，但是又不让编译器知道,来隐式的修改了变量。
int b = i;
printf("i= %dn",b);
}
然后，在调试版本(debug)模式运行程序，输出结果如下：
i = 10
i = 80
然后，在release版本模式运行程序，输出结果如下：
i = 10
i = 10
呵呵结果看到了吗？输出的结果明显表明，release模式下，编译器对代码进行了优化，第二次没有输出正确的i值。所以得出一个结论在VC中release模式编译代码时编译器会自动对你的代码来做起优化的。而调试版本(debug)模式下便不会。
废话说了好多啊呵呵　下面继续说说 volatile
下面，我们把 i的声明加上volatile关键字，看看有什么效果：
 
＃include <iostream>
void main()
{
 volatile int i=10;
 int a = i;
 printf("i= %dn",a);
 __asm {
  mov         dword ptr [ebp-4], 50h
 }
 int b = i;
 printf("i= %dn",b);
}
这下你再在调试版本和release版本运行程序，看看输出结果是不是都是：
i = 10
i = 32
估计大家看到这里便会明白了，volatile　这个关键字最最主要的意思是做什么的了。
在MSDN中volatile是一个限定符，也称为keyword或描述符，"volatile 关键字指示字段可由操作系统、硬件或并发执行的线程在程序中进行修改。"
当要求使用volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存。
一般说来，volatile用在如下的几个地方：
1、中断服务程序中修改的供其它程序检测的变量需要加volatile；
2、多任务环境下各任务间共享的标志应该加volatile；
3、存储器映射的硬件寄存器通常也要加volatile说明，因为每次对它的读写都可能由不同意义；
声明方式为　　volatile declaration
备注
系统总是在 volatile 对象被请求的那一刻读取其当前值，即使上一条指令从同一对象请求值。而且，该对象的值在赋值时立即写入。
volatile 修饰符通常用于由多个线程访问而不使用 lock 语句来序列化访问的字段。使用 volatile 修饰符能够确保一个线程检索由另一线程写入的最新值。
 
一个定义为volatile的变量是说这变量可能会被意想不到地改变，这样，编译器就不会去假设这个变量的值了。精确地说就是，优化器在用到这个变量时必须每次都小心地重新读取这个变量的值，而不是使用保存在寄存器里的备份。下面是volatile变量的几个例子：
1). 并行设备的硬件寄存器（如：状态寄存器）
2). 一个中断服务子程序中会访问到的非自动变量(Non-automatic variables)
3). 多线程应用中被几个任务共享的变量
回答不出这个问题的人是不会被雇佣的。我认为这是区分C程序员和嵌入式系统程序员的最基本的问题。嵌入式系统程序员经常同硬件、中断、RTOS等等打交道，所用这些都要求volatile变量。不懂得volatile内容将会带来灾难。
假设被面试者正确地回答了这是问题（嗯，怀疑这否会是这样），我将稍微深究一下，看一下这家伙是不是直正懂得volatile完全的重要性。
1). 一个参数既可以是const还可以是volatile吗？解释为什么。
2). 一个指针可以是volatile 吗？解释为什么。
3). 下面的函数有什么错误：
int square(volatile int *ptr)
{
return *ptr * *ptr;
}
下面是答案：
1). 是的。一个例子是只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。
2). 是的。尽管这并不很常见。一个例子是当一个中服务子程序修该一个指向一个buffer的指针时。
3). 这段代码的有个恶作剧。这段代码的目的是用来返指针*ptr指向值的平方，但是，由于*ptr指向一个volatile型参数，编译器将产生类似下面的代码：
int square(volatile int *ptr)
{
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由于*ptr的值可能被意想不到地该变，因此a和b可能是不同的。结果，这段代码可能返不是你所期望的平方值！正确的代码如下：
long square(volatile int *ptr)
{
int a;
a = *ptr;
return a * a;
}

Leave a comment

C Traps and Pit falls 之 Macro 预处理

Posted by xiaokucha in Programming on April 1, 2007

2007 NEC 笔试题:
 
#include <stdio.h>                 [1]
#define Method_1                  [2]
#define MAX(Num1,Num2)  (Num1>Num2)?Num1:Num2      [3]
#define Exchange(a,b)  a=a+b;b=a-b;a=a-b    [4]
int MIN (int Num1,int Num2)      
  {
   
     int ret;
     ret=Num1;
     if(Num1<Num2);else ret=Num2; [5]
     return ret;
  }
int  func(int x1,int x2,int *ret)
{
 
   int RetVal;
   if(*ret==NULL)                 [6]
      return(-1);
   if(x1<0||x1>9||x2<0||x2>9)     [7]
      return(-1);
 #ifdef Method_1         //方法一 [8]
    if(x1<x2) Exchange(x1,x2);
        RetVal=x1*10+x2;          [9]
 #else                    //方法二
    RetVal=MAX(x1,x2)*10+MIN(x1,x2);
 #endif
    ret=&RetVal;                  [10]
    return(0);
}
 
当然这道题，不光是Macro(宏)的问题，但是宏是重点，我们先把这个程序修改一下:
 
#include<stdio.h>                 //[1]
#define Method_1                //  [2]
#define MAX(Num1,Num2)  ((Num1)>(Num2)?(Num1):(Num2))     // [3]
#define Exchange(a,b)  {a=a+b;b=a-b;a=a-b;}   // [4]
int
MIN(int Num1,int Num2)      
  {
   
     int ret;
     ret=Num1;
     if(Num1<Num2);else ret=Num2;// [5]
     return ret;
  }
int 
func(int x1,int x2,int *ret)
{
 
   int RetVal;
   if(ret==NULL)                // [6]
      return(-1);
   if(x1<0||x1>9||x2<0||x2>9)     //[7]
      return(-1);
 #ifdef Method_1         //方法一// [8]
    if(x1<x2) Exchange(x1,x2);
        *ret=x1*10+x2;         // [9]
 #else                    //方法二
    RetVal=MAX(x1,x2)*10+MIN(x1,x2);
 #endif
    //ret=&RetVal;                // [10]
    //printf("test %dn",*ret);
    return(0);
}
int
main()
{
      int a=1,b=2;
      int *c;
      c=(int*)malloc(sizeof(int));
      func(a,b,c);
      printf("%dn",*c);
      system("pause");
      return 0;
}
上述代码在dev-c++ 4.9.9.2中调试通过，无错。。。先不说，为什么这么改，我先type一下C traps中的一章 预处理器
 
在严格意义上的编译过程开始之前，c语言预处理器首先对程序代码作了必要的转换处理。因此，我们运行的程序实际上并不是我们所写的程序。预处理器使得编程者可以简化某些工作，它的重要性可以有两个主要的原因说明(当然还有一些次要原因，这里不再赘述)。
 
第一个原因，当需要将某个特定数量在程序中出现的实例统统加以修改，我们希望能够通过在程序中只改动一处数值，然后重新编译就可以实现。我们只需要将这个数定义为显式常量(manifest constant)。
 
第二个原因，大多数c语言实现在函数调用时都会带来重大的系统开销，因此，我们也许希望有这样一种程序块，它看上去像是一个函数，但却没有函数调用的开销。举例来说，getchar和putchar经常被实现为宏，以避免在每次执行输入或者输出一个字符这样简单的操作时，都要调用相应的函数而造成系统效率的下降。
 
1,不能忽视宏中的空格
 
例如,下面的宏定义中f是否带了一个参数呢?
#define f (x) ((x)-1)
答案只可能有两种: f(x)或者代表((x)-1)或者代表(x)((x)-1)
上述定义中，第二个是正确的。因为f 和(x)中有一个space。所以如果希望f(x)为((x)-1)则要写成
#define f(x) ((x)-1)
这一规则不适用于宏调用，只对宏定义使用。因此，在上面完成宏定义后，f(3)和f (3)都等于2。
 
2,宏并不是函数
 
看看下面的两个宏:
#define abs(x) (((x)>=0)?(x):-(x))
#define max(a,b) ((a)>(b)?(a):(b))
 
宏定义中的括号的作用是预防引起与优先级有关的问题。例如，假设abs这样定义:
#define abs(x) x>0?x:-x
那么，对于abs(a-b)是怎样的结果?
 
abs(a-b)展开为a-b>0?a-b:-a-b
这里的-a-b并不是我们所想要得-(a-b)。而且，定义中整个结果的表达式也应该用括号括起来，防止当宏用于一个更大一些的表达式中可能出现问题，例如abs(a)+1展开为a>0?a:-a+1，结果变为了-a+1。。。
 
看一个例子:
biggest=x[0];
i=1;
while(i<n)
biggest=max(biggest,x[i++]);
 
由于在宏max中，如果a大于b，则a会被求值两次，一次是a和b比较时，另一次是计算max结果时
我们这样赋值:
x[0]=2;x[1]=3;x[2]=1;
则biggest=((biggest)>(x[i++])?(biggest):(x[i++]));首先biggest和x[i++]比较这时i=1,x[1]=3，而biggest的值为2，所以比较后结果为false，而这时由于i++，i已经变为2，所以赋给biggest的值为x[2]，即1。这时，又由于i++,i变成了3。(写到这里，想起了传说中的引用调用(值调用，结果调用，引用调用))
解决问题有两个方法:
biggest=x[0];
for(i=1;i<n;i++)
biggest=max(biggest,x[i])
或者不用max的宏，自己写一个比较的函数
对于这个宏#define putc(x,p)
(–(p)->_cnt>=0?(*(p)->_ptr++=(x)):_flsbuf(x,p))
虽然x是求了一次值，但是对于p缺是取了2次值，所以对于p参数，当我们操作的时候不能给带自增或自减的参量。类似的函数还有很多，例如，#define toupper(c) ((c)>’a’&&(c)<‘z’?(c)+(‘A’-‘a’):(c))
 
宏的另外一个问题是，展开后可能产生很大的表达式，例如，max(a,max(b,max(c,d)))
展开后是((a)>(((b)>(((c)>(d)?(c):(d)))?(b):(((c)>(d)?(c):(d)))))?(a):(((b)>(((c)>(d)?(c):(d)))?(b):(((c)>(d)?(c):(d))))))
就算是max(max(a,b),max(c,d))也是很大的，不如写成
 
biggest=a;
if(biggest<b)biggest=b;
if(biggest<c)biggest=c;
if(biggest<d)biggest=d;
 
3,宏并不是语句
 
这里，我们用assert宏做个例子:
#define assert(e) if(!e) assert_error(__FILE__,__LINE__)
这里的__FILE__和__LINE__是内建于c语言预处理器中的宏，他们会被扩展为所在文件的文件名和所处代码行的行号。
但是下面这段就显示出了错误:
if(x>0&&y>0)
                assert(x>y)
else assert(y>x)
展开后变为:
if(x>0&&y>0)
if(!(x>y))assert_error("foo.c",37);
else
if(!(y>x))assert_error("foo.c",39);
这样一看else相对的if就变了，所以我们可能会这样去尝试解决问题:
#define assert(e) {if(!e) assert_error(__FILE__,__LINE__);}
但是这样一来上面的展开后}后面就多了;(虽然是这样，但是对于dev-c++编译好像已经能自己修改这样的错误，并且正确编译)
再改:
#define assert(e) ((void)((e)||_assert_error(__FILE__,__LINE__)))(这个的确是高，实在是高)
 
4,宏不是类型定义
 
#define FOOTYPE struct foo
FOOTYPE a;
FOOTYPE b,c;
这里体现了宏的一个优点，可移植性，但是，我们最好还是使用类型定义:
typedef struct foo FOOTYPE;
因为，对于下面的代码:
 
#define T1 struct foo *
typedef struct foo *T2;
 
T1 a,b;
T2 a,b;
 
这里,T1只能成功定义a,对于b只是定义了一个struct foo而不是 struct foo *,而T2则能成功定义a,b为struct foo *。
 
如此，上面的问题也就很简单了，有错误的是3,4,6,9,10
 
3中宏没有加括号，会产生优先级问题
 
4中没有加大括号，会产生语句整体分离
 
6中*ret没有实在的空间只是一个指针，所以应该为ret
 
9这里不应该把计算结果赋给函数内变量因为函数返回后，函数内声明的变量所对应的数据栈也会释放，所以应该赋值给全局空间
 
10这里访问释放后的&retval会被认为非法
 
btw:在群硕技术面的时候，tech leader也提出过宏为什么要注意用++的问题，哎，当时头脑一热，空白了，还有shell中多线程实现的问题
 
也没有答好，基础啊基础。。。
 

1 Comment

Sequence

Posted by xiaokucha in Programming on April 1, 2007

运算符按照优先级大小由上向下排列，在同一行的运算符具有相同优先级。第二行是所有的一元运算符。
 

运算符

 解释

 结合方式

() [] -> .

括号（函数等），数组，两种结构成员访问

 由左向右

! ~ ++ — + – 

* & (类型) sizeof

否定，按位否定，增量，减量，正负号，

间接，取地址，类型转换，求大小

 由右向左

* / %

乘，除，取模

 由左向右

+ –

加，减

 由左向右

<< >>

左移，右移

 由左向右

< <= >= >

小于，小于等于，大于等于，大于

 由左向右

== !=

等于，不等于

 由左向右

&

按位与

 由左向右

^

按位异或

 由左向右

|

按位或

 由左向右

&&

逻辑与

 由左向右

||

逻辑或

 由左向右

? :

条件

 由右向左

= += -= *= /= 

&= ^= |= <<= >>=

各种赋值

 由右向左

,

逗号（顺序）

 由左向右

Leave a comment

knapsack problem

Posted by xiaokucha in Programming on March 14, 2007

From Gossip@caterpillar

Algorithm Gossip: 背包問題（Knapsack Problem）

說明

假設有一個背包的負重最多可達8公斤，而希望在背包中裝入負重範圍內可得之總價物品，假設是水果好了，水果的編號、單價與重量如下所示：

0

李子

4KG

NT$4500

1

蘋果

5KG

NT$5700

2

橘子

2KG

NT$2250

3

草莓

1KG

NT$1100

4

甜瓜

6KG

NT$6700

解法

背包問題是關於最佳化的問題，要解最佳化問題可以使用「動態規劃」（Dynamic programming），從空集合開始，每增加一個元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最後得到的就是最佳解。

以背包問題為例，我們使用兩個陣列value與item，value表示目前的最佳解所得之總價，item表示最後一個放至背包的水果，假設有負重量 1～8的背包8個，並對每個背包求其最佳解。

逐步將水果放入背包中，並求該階段的最佳解：

  • 放入李子
背包負重

1

2

3

4

5

6

7

8

value

０

０

０

4500

4500

4500

4500

9000

item

－

－

－

０

０

０

０

０

  • 放入蘋果
背包負重

1

2

3

4

5

6

7

8

value

０

０

０

4500

5700

5700

5700

9000

item

－

－

－

０

1

1

1

０
  • 放入橘子
背包負重

1

2

3

4

5

6

7

8

value

０

2250

2250

4500

5700

6750

7950

9000

item

－

2

2

０

1

2

2

０

  • 放入草莓
背包負重

1

2

3

4

5

6

7

8

value

1100

2250

3350

4500

5700

6800

7950

9050

item

3

2

3

０

1

3

2

3

  • 放入甜瓜
背包負重

1

2

3

4

5

6

7

8

value

1100

2250

3350

4500

5700

6800

7950

9050

item

3

2

3

０

1

3

2

3

由最後一個表格，可以得知在背包負重8公斤時，最多可以裝入9050元的水果，而最後一個裝入的水果是3號，也就是草莓，裝入了草莓，背包只能再放入7公斤（8-1）的水果，所以必須看背包負重7公斤時的最佳解，最後一個放入的是2號，也就是橘子，現在背包剩下負重量5公斤（7-2），所以看負重5公斤的最佳解，最後放入的是1號，也就是蘋果，此時背包負重量剩下0公斤（5-5），無法再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為9050元。

實作

  • C 
#include <stdio.h> 
#include <stdlib.h> 

#define LIMIT 8   // 重量限制 
#define N 5       // 物品種類 
#define MIN 1     // 最小重量 

struct body { 
    char name[20]; 
    int size; 
    int price; 
}; 

typedef struct body object; 

int main(void) { 
    int item[LIMIT+1] = {0}; 
    int value[LIMIT+1] = {0}; 
    int newvalue, i, s, p; 

    object a[] = {{"李子", 4, 4500}, 
                  {"蘋果", 5, 5700}, 
                  {"橘子", 2, 2250}, 
                  {"草莓", 1, 1100}, 
                  {"甜瓜", 6, 6700}}; 

    for(i = 0; i < N; i++) { 
        for(s = a[i].size; s <= LIMIT; s++) { 
            p = s - a[i].size; 
            newvalue = value[p] + a[i].price; 
            if(newvalue > value[s]) {// 找到階段最佳解 
                value[s] = newvalue; 
                item[s] = i; 
            } 
        } 
    } 

    printf("物品t價格n"); 
    for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) { 
        printf("%st%dn", 
                  a[item[i]].name, a[item[i]].price); 
    } 

    printf("合計t%dn", value[LIMIT]); 

    return 0; 
}

  • Java 
class Fruit {
    private String name;
    private int size;
    private int price;
    
    public Fruit(String name, int size, int price) {
        this.name = name;
        this.size = size;
        this.price = price;
    }
    
    public String getName() {
        return name;
    }

    public int getPrice() {
        return price;
    }

    public int getSize() {
        return size;
    }
}

public class Knapsack {
    public static void main(String[] args) {
        final int MAX = 8;
        final int MIN = 1;
        int[] item = new int[MAX+1]; 
        int[] value = new int[MAX+1];  

        Fruit fruits[] = {
                new Fruit("李子", 4, 4500), 
                new Fruit("蘋果", 5, 5700), 
                new Fruit("橘子", 2, 2250), 
                new Fruit("草莓", 1, 1100), 
                new Fruit("甜瓜", 6, 6700)}; 

        for(int i = 0; i < fruits.length; i++) { 
            for(int s = fruits[i].getSize(); s <= MAX; s++) { 
                int p = s - fruits[i].getSize(); 
                int newvalue = value[p] + 
                                   fruits[i].getPrice(); 
                if(newvalue > value[s]) {// 找到階段最佳解 
                    value[s] = newvalue; 
                    item[s] = i; 
                } 
            } 
        } 

        System.out.println("物品t價格"); 
        for(int i = MAX; 
            i >= MIN; 
            i = i - fruits[item[i]].getSize()) { 
            System.out.println(fruits[item[i]].getName()+ 
                    "t" + fruits[item[i]].getPrice()); 
        } 

        System.out.println("合計t" + value[MAX]);  
    }
}

Leave a comment

DataStructure chapter 1

Posted by xiaokucha in Programming on March 13, 2007

Chapter 1 List
 
 
List Insert
 
int ListInsert_L(LinkList &La,int i,ElemType b)
{
    LinkList *p=La;int j=0;
    while(p&&j<i-1)
    {p=p->next;++j;}
    if(!p||j>i-1)
    return 1;
    else
    {
    s= new LNode;//s=(LinkList)malloc(sizeof(LNode));
    s->data=b;
    s->next=p->next;
    p->next=s;
    return 0;
    }
}
 
List Delete
 
int ListDelete_L(LinkList &La,int i,ElemType &b)
{
    LinkList *p=La;int j=0; LinkList *q;
    while(p&&j<i-1)
    {p=p->next;++j;}
    if(!(p->next)||j>i-1)
    return 1;
    else
    {
    q=p->next;
    p->next=q->next;
    b=q->data;
    delete q;
    return 0:
    }
}
 
List Create
 
Void CreatList_L(LinkList &a,ElemType a[],int i)
{
    la=new LNode;la->next=NULL;
    for(i=n;i>=1;i–)
    {
    p=new LNode;
    p->data=a[i];
    p->next=la->next;
    la->next=p;
    }
}
 
List Intersect(with or without old space,both sequential list)
 
Void Intersect(LinkList &a,LinkList &b)  //use given
{
ap=a->next;bp=b->next;tp=a;
while(ap)
{
    if(!bp||ap->data<bp->data)
    {
    tp->next=ap->next;
    delete ap;
    ap=tp->next;}
    else if(ap->data=bp->data)
    {
    tp=ap;
    ap=ap->next;
    bp=bp->next;
    }
    else bp=bp->next;
}
}
 
Void Intersect(LinkList &c,LinkList a,LinkList b)  //copy node
{
    c= new LNode;
    ap=a->next;bp=b->next;cp=c;
    while(ap&&bp)
    {
    if(ap->data=bp->data)
    {
    tp=new LNode;
    tp->data=ap->data;
    cp->next=tp;cp=tp;
    ap=ap->next;
    bp=bp->next;
    }
    else if(ap->data<bp->data)
    ap=ap->data;
    else
    bp=bp->data;
    }
    cp->next=NULL;
}
 
List Complement
 
Void Complement(LinkList &a,LinkList &b)  //use given
{
     ap=a->next;bp=b->next;tp=a;
     while(ap&&bp)
     {
     if(!bp||ap->data<bp->data)
     {
     ap=ap->next;
     tp=tp->next;
     }
     else if(ap->data==bp->data)
     {
     tp->next=ap->next;
     delete ap;
     ap=tp->next;
     }
     else
     bp=bp->next;
     }
}
 
Void Complement(LinkList &c,LinkList a,LinkList b)   //copy node
{
     c=new LNode;
     ap=a->next;
     bp=b->next;
     cp=c;
     while(ap)
     {
     if(!bp)
     {
     tp=new LNode;
     cp->next=tp;cp=tp;cp->data=ap->data;ap=ap->next;
     }
     else if(ap->data<bp->data){
     tp=new LNode;cp->next=tp;cp=tp;cp->data=ap->data;ap=ap->next;
     }
     else if(ap->data==bp->data){
     ap=ap->next;bp=bp->next;
     }
     else bp=bp->next;
     }
     cp->next=NULL;
}
 
List Union
 
Void Union(LinkList &a,LinkList &b)   //use given
{
     ap=a->next;bp=b->next;tp=a;
     while(ap&&bp)
     {
     if(ap->data<bp->data)
     {tp->next=ap;tp=ap;ap=ap->next;}
     else if(ap->data>bp->data)
     {tp->next=bp;tp=bp;bp=bp->next;}
     else{
     tp->next=ap;tp=bp;bp=bp->next;
     delete tp;
     tp=ap;ap=ap->next;}
     }
     if(ap)tp->next=ap;
     else tp->next=bp;
     delete b;
}
 
void Union(LinkList &c,LinkList a,LinkList b)   //copy node
{
     c=new LNode;
     ap=a->next;bp=b->next;cp=c;
     while(ap||bp)
     {
     tp=new LNode;
     cp->next=tp;
     cp=tp;
     if(!ap)
     {cp->data=bp->data;bp=bp->next;}
     else if(!bp)
     {cp->data=ap->data;ap=ap->next;}
     else if(ap->data==bp->data)
     {cp->data=ap->data;ap=ap->next;bp=bp->next;}
     else if(ap->data<bp->data)
     {cp->data=ap->data;ap=ap->data;}
     else
     {cp->data=bp->data;bp=bp->data;}
     cp->next=NULL;
}

1 Comment