诺西笔试小结

时间：2010-09-05 来源：zyd_cu

常量指针与指针常量

直接从语义上理解，看const限定那个范围。const int *p 其中的const在*p之前，也就是说*p是常量，不能改变。同样int *const p 其中的const在p之前，所以p是常量，不能改变。

位段的符号

struct test {
    int a:2; /*表示范围-2~1 */
    unsigned int b:2; /*表示范围0-3 */
};

int main()
{
    struct test t;
    t.a = 1;
    t.b = 1;
    t.a++;
    t.b++;
    printf("%d %d\n", t.a, t.b); //结果：-2， 2

    return 0;
}

反转整数的位（整型的长度不确定）

unsigned int reverse_bits(unsigned int value)
{
   unsigned int len = 8 * sizeof(int);
   unsigned int first = 1 << (len – 1); //整型长度不定，不能直接0x80000000
   unsigned int last = 1;

while(first > last) {

/* 如果两位相等，不需要做任何处理；

* 如果不相等与first，last做异或操作会改变对应的位

if((value & first) != (value & last)) {

   value = value ^ fisrt ^ last;
   }
   first >> 1;
   last << 1;
   }
   return value;

}

反转链表

typedef struct node {
    int key;
    struct node * next;
}node;
/* 反转链表，返回新链表的头指针 */

node *reverse_list(node *head)
{
    if(head == NULL)
        return NULL;

    node *nh = head;
    node *cur = head->next;
    node * tmp;

    while(cur != NULL) {
     tmp = p->next;
    p->next = nh;
    nh = p;
    p = tmp;
   }
   head->next = NULL;
   return nh;
}

划分集合为非空的两堆

/*
* 将数组元素分成非空的两个集合P, Q
* 打印所有可能的情况
*
* 根据C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n;
* 去掉空的集合，1到2^n-2的所有数的低n位位图即能标示集合
*
* 以6个元素为例
* 1的低6位为000001, 代表一个集合选了最后一个元素
* 3的低6位为000011, 代表一个集合选了最后两个元素
*
* 通过这种方式，可以以O(2^n)的复杂度求C(n, r)组合
* 从0到2^n-2逐个判断位图中1的个数，为r则符合条件
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void print(char *array, int num)
{
    int i;
    for(i = 0; i < num; i++)
        printf("%c ", array[i]);
    printf("\n");
}

void process(char *array, int cur, int num, char *p, char *q)
{
    int i;
    int b = 1 << (num - 1);
    int pi = 0;
    int qi = 0;
    for(i = 0; i < num; i++) {
        if(cur & b)
            p[pi++] = array[i];
        else
            q[qi++] = array[i];
        b >>= 1;
    }

    printf("Values in P: ");
    print(p, pi);
    printf("Values in Q: ");
    print(q, qi);
    printf("\n");
}

void partition(char *array, int num)
{
    int i;
    int last = (int)pow(2, num);
    char *p = (char*)malloc(sizeof(char) * num);
    char *q = (char*)malloc(sizeof(char) * num);

    for(i = 1; i < last - 1; i++) {
        process(array, i, num, p, q);
    }

    printf("Total = %d\n", last - 2);

    free(p);
    free(q);
}

int main()
{
    char array[] = "ABC";
    partition(array, 3);
    return 0;
}