2012年6月29日星期五

《c专家编程》笔记


第19页
关于类型不匹配的两个对比案例:
(1)
foo(const char **p) {}
main(int argc, char ** argv){
    foo(arvg);
}
(2)
char *cp;
const char *ccp;
ccp = cp;
例子(1)将提示警告“参数与原型不匹配”,例子(2)却是合法的。问题的症结在于“左边指针所指向的类型必须具有右边指针所指向类型的全部限定词”。按照这个规则,例子(2)因此是合法的。但例子(1)仍然不合法,因为指针p指向的是 const char*, 指针argv指向的是char*,这是两个不同的指针类型。


第23页
*关于隐式转换的规则
 ANSI C标准中,隐式转换可以通俗地表述为:

当执行算术运算时,操作数的类型如果不同,就会发生转换。数据类型一般朝着浮点精度更高,长度更长的方向转换,整型数如果转换为signed 不会丢失信息,就转换为signed,否则转换为unsigned。
对于隐式转换,K&R C则采用无符号优先原则,就是当一个无符号类型与int或更小的整型混合使用时,结果类型是无符号类型。
当然,现在的编译器一般都是符合ANSI C 标准的。下面的code,对于ANSI C 和 K&R C编译器中运行结果是不一样的。
main(){
    if(-1 < (unsigned char) 1)
        printf("-1 is less than (unsigned char)1 : ANSI semantics ");
    else
        printf("-1 NOT less than (unsigned char) 1: K&R semantics ");
}
-1的位模式是一样的,但是在K&R C 中,编译器将其解释为无符号数,也就是变成正数,所以“NOT less”。
那么,下面这段代码有问题么?
int array[] = {23,34,12,17,204,99,16};
#define TOTAL_ELEMENTS (sizeof(array)/sizeof(array[0]))
main(){
    int d = -1,x;
    /*...*/
    if(d <= TOTAL_ELEMENTS - 2)
        x = array[d+1];
   /*...*/
}

第30页
* switch 语句的误区

在这个位置上(指的是switch的左花括号之后)声明一些变量会被编译器很自然地接受,尽管在switch语句中为这些变量加上初始值是没有什么用处的,因为它绝不会被执行——语句从匹配表达式的case开始执行。
考虑下面这段代码:
int main(int argc, char *argv[])
{
    switch(4){
        int i = 3;
    case 1: printf("1\n");break;
    case 2: printf("2\n");break;
    case 3: printf("3\n");break;
    case 4: printf("4 %d\n",i);break;
    default: printf("default\n");break;
    }
    return 0;
}
程序将输出“4 0”(在我的机器上是输出0,实际上可能是任意值)。原因就在于switch语句直接跳到匹配位置的case处开始执行,所有的初始化并不会被执行。变量i是有定义的,i的可见范围为switch语句块,变量的声明是在编译期就可见,而初始化要等到运行时。可以说case语句就相当于goto。
另外要注意的是,上面的代码在g++编译是会出错的。c++ 与 c 的switch 语句不同?



第38页
*运算符优先级和求值顺序
书中讲了一个小八卦,关于& 和 && 的。Dennis Ritchie 发帖说在以前 & 不只是位操作符,而且承担逻辑操作符&&的作用(&&还没出生)。后来为了区分位操作符和逻辑操作符,重新加入了&&。因为已大量存在类似于 if(a == b & c == d)这样的表达式,由于这个“历史原因”,&的运算符优先级低于关系运算符。
优先级只是定义不同优先级间的计算顺序,但同一运算符内的多个操作数的计算顺序C是没有规定的(除了&&, ||, ?: 和,外)。类似的,C也没有指定函数各参数的求值顺序。
x = f() + g()*h()
上面的代码唯一可以确定的是乘法会在加法之前执行。但是操作数f(),g(),h()会以什么顺序执行并没有规定,可能f()会在乘法之前调用也可能在乘法之后调用,也可能在g()和h()之间调用。
类似地,
printf("%d %d\n",++n,power(2,n));
也认为上面代码是一种不良风格的代码,因为在不同的编译器中可能会得到不同的结果。
2012-06-20 22:03:14 回应


第46页
* maximal munch strategy(最大一口策略)
这个策略表示如果下一个标记有超过一种的解释方案,编译器将选取能组成最长字符序列的方案。所以,
z = y+++x;
将被理解为,而且只能被理解为
z = y++ + x;
但这种策略也会再次让人迷糊,比如,
z = y+++++x;
按照ANSI C 的策略,将被解析为,
z = y++ ++ +x;
所以会编译错误。虽然当理解做 z = y++ + ++x 时貌似是可行的,但按照策略,编译器并不会这么理解。
还有一个很鸡贼的错误。还能发现的出来的么?
ratio = *x/*y;
2012-06-20 22:27:47 回应



第117页
* 运行时数据结构
可执行文件a.out有三个段:文本段(text),数据段(data),bss段(bss)。text段为可执行文件的指令,data段保存初始化后的全局变量和静态变量。bss段这个名字原意是“Block Started By Symbol"的缩写,不知所云。有人更喜欢把它解释为“Better Save Space", 这更能体现bss的作用,它保存没有初始化的全局变量或静态变量。实际上它只是记录运行时所需要的bss段的大小记录,bss段(不像其他段)并不占据目标文件(就是a.out)的任何空间。当可执行文件由loader载入内存时,再按照bss段的记录申请空间。
譬如声明 int arr[1000] ; 的全局变量, bss段将增加 4000 Byte, a.out的大小并不会因此增加 4000 Byte。但如果声明的是初始化过的变量, int arr[1000] = {100}; (实验了一下,初始化为0效果跟没初始化一样), 则 bss段没有变化, data 段将增加4000 Byte, 另外 a.out 也会增加4000 Byte,说明data段是占用a.out的空间的。可以用 size 命令查看每个段的大小。
局部变量并不进入a.out,它们在运行时创建。
* 堆栈段(p122)

除了递归调用之外,堆栈并非必需。因为在编译时可以知道局部变量、参数和返回地址所需空间的固定大小,并可以将它们分配于bss段。BASIC,COBOL和FORTRAN的早期编译器并不允许函数的递归调用,所以它们在运行时并不需要动态的堆栈。允许递归调用意味着必须找到一种方法,在同一时刻允许局部变量的多个实例存在,但只有最近被创建的那个才能被访问,这很像栈的经典定义。
2012-06-23 11:06:58 回应



第170页
* 根据位模式构筑图形
在C语言中,典型的16x16的黑白图形可能如下:
static unsigned short stopwatch[] = {
0x07C6,
0x1FF7,
0x383B,
0x600C,
0xC006,
0xC006,
0xDF06,
0xC106,
0xC106,
0x610C,
0x610C,
0x3838,
0x1FF0,
0x07C0,
0x0000
};
正如所看到的那样,这些C语言常量并未提供有关图形实际模样的任何线索。这里有一个惊人的#define 定义的优雅集合,运行程序建立常量使它们看上去像是屏幕上的图形。
#define X   )*2+1
#define _   )*2
#define s   ((((((((((((((((0  /* 用于建立16位宽的图形 */
static unsigned short stopwatch[] = {
s _ _ _ _ _ X X X X X _ _ _ X X _,
s _ _ _ X X X X X X X X X _ X X X,
s _ _ X X X _ _ _ _ _ X X X _ X X,
s _ X X _ _ _ _ _ _ _ _ _ X X _ _,
s _ X X _ _ _ _ _ _ _ _ _ X X _ _,
s X X _ _ _ _ _ _ _ _ _ _ _ X X _,
s X X _ _ _ _ _ _ _ _ _ _ _ X X _,
s X X _ X X X X X _ _ _ _ _ X X _,
s X X _ _ _ _ _ X _ _ _ _ _ X X _,
s X X _ _ _ _ _ X _ _ _ _ _ X X _,
s _ X _ _ _ _ _ X _ _ _ _ X X _ _,
s _ X _ _ _ _ _ X _ _ _ _ X X _ _,
s _ _ X X X _ _ X _ _ X X X _ _ _,
s _ _ _ X X X X X X X X X _ _ _ _,
s _ _ _ _ _ X X X X X _ _ _ _ _ _,
s _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _,
};
千万不要忘了在绘图结束后清除这些宏定义,否则可能造成很大的麻烦。
2012-06-23 21:23:28 回应


第172页
* 整型提升
在C语言中,字符常量的类型为int 型。所以对于
printf("%d",sizeof 'A');

输出为4,不应该感到诧异。
但下面的语句有所不同:
char a = 'A';
char b = 'B';
printf ( " the size of the result of a+b :%d " ,sizeof( a+b) );
输出的结果也是 4(或许之前会认为应该输出1)。
这是由于发生了整型提升。两个操作数都不是三种浮点类型之一,它们一定是某种整值类型。在确定共同的目标提升类型之前,编译器将在所有小于int的整值类型上施加一个被称为整型提升(integral promotion)的过程。整型提升就是char、short int和位段类型(无论signed或unsigned)以及枚举类型将被提升为int, 前提是int 能够完整地容纳原先的数据,否则将被转换为unsigned int。wchar_t和枚举类型被提升为能够表示其底层类型(underlying type)所有值的最小整数类型。 一旦整型提升执行完毕,类型比较就又一次开始,也就是普通的算术类型转换。这在之前笔记有介绍过。
但是下面这个语句又会让人困惑:
char a = 'A';
char b = 'B';
printf ( " the size of the result of a++ :%d " ,sizeof( a++) );
或许你会认为,按照整型提升输出为4. 但实际上输出为 1。原因不详。
2012-06-23 22:55:21 回应


第281页
* 判断一个变量是有符号数还是无符号数
宏参数是个变量值时,大概可以这么做:
#define ISUNSIGNED(a) (a >=0 && ~a >= 0)
如果宏参数是类型时,可以这么做:
#define ISUNSIGNED(type) ((type)0 - 1 > 0)
其实,前一个代码由于整型提升的存在,并不能正常工作,比如 unsigned short us = 1 ,对us进行测试时就会得到错误答案。
我没有想出来怎么办,搜了一下,下面的代码可以工作:
#define ISUNSIGNED(a) ( a >= 0 && (a=~a,a >= 0? (a=~a,1):(a=~a,0)))
而对于第二个代码,我也觉得书上写得似乎有点不对,原因也在于整型提升,可以改为
#define ISUNSIGNED(type) ((type)- 1 > 0)
你认为呢?

* 从文件中随机提取一个字符串
只能顺序遍历文件,并且不能使用表格来存储所有字符串的偏移位置。书中给了一NB的方法。
2012-06-26 14:38:33 回应

2012年6月20日星期三

String Reduction

来源:Tristan's Collection of Interview Questions

Problem: A string that only contains three types of letters :"a", "b", "c". Our goal is to reduce the string. If two different letters are adjacent to each other, we can reduce the two letters into another letter. The rule is like this: if we encounter "ab" (or "ba"), we reduce to "c"; if we encounter "bc" (or "cb"), we reduce to "a"; if we encounter "ca" (or "ac"), we reduce to "b". If two adjacent letters are the same, we can't reduce them. We need to find an optimal way to reduce the string as much as possible.

For example, for string "acbb", if we try to reduce "ac"first, we get "bbb". But, if we reduce "cb" first, we get "aab" and we can further make "aab" => "ac" => "b". The latter approach gives us an optimal reduction.What is the smallest string which can result by applying this operation repeatedly?























Solution: Here what really matters is the numbers of letter "a", "b" and "c". Let us name them as num_a, num_b and num_c. If two of them are zero, we can't reduce that string. Otherwise, we can reduce the string into a string that has a length of 1 or 2. If num_a, num_b and num_c are all even or odd, we can reduce to a string with length 2; If not, we can reduce to a string with length 1.

Then how to do the reduction? The detail is as follow:
  1. if the string has a length of 3 and contains one "a", one "b" and one "c", whatever order of the three letter are in, we can only reduce the string into a string with length 2; if the string has a length of 2 and contains two different letters, we can only reduce the string into a string with length 1. Let us regard these two cases as base cases.

  2. for a general case, we have num_a "a" , num_b "b" and num_c "c". After every reduction, the sum of num_a, num_b and num_c will decrease by 1, since we substitue two letters with one letter.

  3. Then at each round, which two adjacent letters we choose to reduce? We try to find an adjacent pair that contains a letter which has the highest count. For example, if now, we have 3 "a", 4 "b" and 6 "c" in the string, we choose an adjacent pair that contains "c"since num_c = max(num_a, num_b, num_c) . Can we find such pair? definitely we can. If there are multiple such pairs, choose a random one. Then after we reduce this pair, num_c--, max(num_a, num_b, num_c) may decrease by 1, remain unchanged, or increase by 1. However, since max(num_a, num_b, num_c) is up-bounded by num_a + num_b + num_c. num_a + num_b + num_c is decreasing after every round, then max(num_a, num_b, num_c) will also decrease if we look at a long wrong. Therefore, by using our strategy, max(num_a, num_b, num_c) will eventually decrease to 1, which means we are encounter the base cases in step 1.

  4. Then when the string will be reduced to a length of 1 and when to a length of 2? We observe that is num_a, num_b and num_c are all even, then after one transformation, they will become all odd; similarly, if there are originally all odd, after one transformation, they will become all even. Then according to the analysis in step 3), we know at the end, the max(num_a, num_b, num_c) will eventually decrease to 1. But, they should still be all odd at that time (since "1" is odd). Therefore, at the very end, we will have num_a = 1, num_b = 1 and num_c =1, which will eventually lead to a string of length 2. It is easy to prove that if num_a, num_b and num_c are not all even or odd, the string will be reduced to length 1.

  5. if num_a, num_b and num_c are not all even or odd, there must be only two cases: a) two of the counters are odd and one is even b) two of the counters are even and one is odd. For example, if num_b is odd, num_a and num_c are both even. The string actually will eventually be reduced to "b".

  6. if num_a, num_b and num_c are all even or odd, there might be multiple different final forms.
if((a == 0 && b == 0 && c == 0) ||
   (a == 0 && b == 0 && c != 0) ||
   (a == 0 && b != 0 && c == 0) ||
   (a != 0 && b == 0 && c == 0))
   {
      result = a+b+c;
   }
else if(a != 0 && b != 0 && c != 0)
   {
      if((a%2 == 0 && b%2 == 0 && c%2 == 0) ||
         (a%2 == 1 && b%2 == 1 && c%2 == 1))
           result = 2;
      else
           result = 1;
   }
else if((a == 0 && b != 0 && c != 0) || 
        (a != 0 && b == 0 && c != 0) || 
        (a != 0 && b != 0 && c == 0))
   {
      if(a%2 == 0 && b%2 == 0 && c%2 == 0)
           result = 2;
      else
           result = 1;
   }

2012年6月14日星期四

树状数组

一个基本的问题:求数组中的逆序对数目?

这也是算法导论第一章的最后一道习题。按照算法导论中的提示,该问题可以通过修改合并排序在O(nlgn)内解决。另外一种方法,是使用一种特殊的数据结构称之为“树状数组”,也可以在O(nlgn)内解决。代码如下:

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std ;
#define MAXN 100002
#define MAX 1000002
int n,a[MAXN],c[MAX] ;
int main()
{
 int runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d",&n) ;
  for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
  long long ret = 1LL * n * (n - 1) / 2 ;
  memset(c,0,sizeof c) ;
  for(int i = 0;i < n;i++)
  {
   for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ;
   for(int j = a[i];j < MAX;j += j & -j) c[j]++ ;  
  }
  cout << ret << endl ;
 }
 return 0 ;
}


下面介绍下树状数组(Binary Indexed Tree)。如果搜一下,就会发现有很多文章详细介绍树状数组,比如这篇,所以这里不再赘述。 它能够高效地获取数组中连续n个数的和。概括说,树状数组通常用于解决以下问题:数组{a}中的元素可能不断地被修改,怎样才能快速地获取连续几个数的和? 传统数组(共n个元素)的元素修改和连续元素求和的复杂度分别为O(1)和O(n)。树状数组通过将线性结构转换成伪树状结构(线性结构只能逐个扫描元素,而树状结构可以实现跳跃式扫描),使得修改和求和复杂度均为O(lgn),大大提高了整体效率。 let the code talk.值得提一下的是,树状数组下标是从1开始的。




//求2^k
int lowbit(int t)
{
    return t & ( t ^ ( t - 1 ) );
}
 
//求前n项和
int sum(int end)
{
   int sum = 0;
   while(end > 0)
  {
     sum += in[end];
     end -= lowbit(end);
  }
 
  return sum;
}
 
//增加某个元素的大小
void plus(int pos, int num)
{
   while(pos <= n)
  {
     in[pos] += num;
     pos += lowbit(pos);
  }
}