动态链接使用共享库的一个主要目的就是允许多个正在运行的进程共享存储器中相同的库代码，因而节约资源。那么，多个进程是如何共享一个程序的一个拷贝的呢？一种比较好的方法就是编译库代码，使得不需要链接器修改库代码，就可以在任何地址加载和执行这些代码。这样的代码就叫做位置无关的代码（position-independent code, PIC）。

PIC的特点是，它被加载到任意地址空间都可以正确的执行，这点是显著区别于可重定向文件的。其原理是PIC对常量和函数入口地址的操作都是基于PC+偏移量的寻址方式。即使程序被移动，但是PC也变化了，而偏移量是不变的，所以程序仍然可以找到正确的入口地址或者常量。那些引用了绝对内存地址的指令（比如绝对跳转指令）必须被替换为PC相对寻址指令。这些间接处理过程可能导致PIC的运行效率下降，但是目前大多数处理器对PIC都有很好的支持，使得这效率上的这一点点下降基本可以忽略。下面具体说明。

链接（linking）就是将不同部分的代码和数据收集和组合成为一个单一文件的过程，在现代系统中，链接由叫做链接器（linker）的程序自动执行。典型的链接器把由编译器或汇编器生成的若干个目标模块整合成一个被称为载入模块或可执行文件的实体，其可以被操作系统直接执行。其中，某些目标模块是直接作为输入提供给链接器的；而另外一些目标模块则是根据链接过程的需要，从库文件中取得。

链接器使得分离编译（Separate Complication）成为可能，即若干个源程序可以在不同的时候单独进行编译，然后在恰当的时候整合到一起。下面我们主要来讨论下从源文件翻译成可执行目标文件的过程，随后再来讨论下静态链接和动态链接。

主要讨论C语言怎样组织正在运行的程序的数据结构的细节。

我们知道知道在UNIX操作系统中，一个C语言文件经过预处理（cpp），编译（cc1），汇编（as）和链接（ld）后可以得到可执行文件a.out。我们可以用size命令（或nm、dump）检查可执行文件，它会告诉你这个文件中的三个段（文本段.text，数据段.data，.bss段）的大小。文本段包含程序的指令。由于程序的文本内容和大小都不会变化，链接器把指令直接从文件拷贝到内存中，不再处理。数据段包含经过初始化的全局和静态变量以及它们的值。BSS段的大小从可执行文件中得到，然后链接器得到这个大小的内存块，紧跟在数据段之后。当这个内存区进入程序的地址空间后全部清零，通常是memset全部置0。通常把数据段和BSS段统一称为数据区。上面这些内容可以通过size命令很直观的查看与验证。除了上面提到的程序指令、全局和静态变量，我们还有局部变量等数据需要存储。这就引出了堆栈段（stack）和堆空间（heap）。下面将详细讨论数据区、堆栈段和堆空间。

C语言中数组与指针是不可分开而论的，下面先说说数组T a[n]。

1.数组的访问方式有两种：指针形式(a+i)和下标形式a[i]。而编译器对这两种方式的操作解析是一样：把a作为数组首元素的首地址，然后再加上i作为地址偏移，算出新的地址，然后从新的地址中取出值。而对于偏移的计算为isizeof(T)。如果计算过程反过来，也就是i[a]也具有同样的含义。

2.a表示什么？对于上面两种情况可以知道a表示数组首元素的地址。那么a还有其它的意义吗？当然，sizeof(a)=n*sizeof(T)。这里a表示数组的地址（把数组看成一个整体），而不是首元素的地址。实际上除了作为sizeof()的参数外，a都表示数组的首元素的地址。

这里所说的符号是大家不常用的，而且可能出错的符号。不仅仅是指运算符，具体有注释符号，反斜杠，自增自减操作符。

1.关于注释符号

[cce_cpp tab_size=”4”]
int/…/i;
y = x/*p;
[/cce_cpp]
编译器剔除注释不是简单的剔除，而是用空格代替原来的注释。所以第一个表达式是正确的。而第二个表达式则会被编译器认为p为注释的一部分。

2.反斜杠（\）
C语言里以反斜杠（\）表示断行。编译器会将反斜杠剔除掉，跟在反斜杠后面的字符自动连接到前面一行。但是注意：反斜杠之后不能有空格，反斜杠的下一行之前也不能有空格。

Struct与union作为C语言的关键字，定义与用法这里就不说了。下面主要针对几点进行说明。

1.Struct与内存对齐

先看一下下面三个结构体，在不实验的情况下能确定的说出他们的大小？

[cce_cpp]
struct test1
{
    char a;
    char c;
    short b;
};

struct test2
{
    char a;
    short b;
    char c;
};

struct test3
{
    char a;
    int b;
    char c;
};
[/cce_cpp]

编译器会自动进行成员变量的对齐，以提高运算效率。缺省情况下，编译器为结构体的每个成员按其自然对界（natural alignment）条件分配空间。各个成员按照它们被声明的顺序在内存中顺序存储，第一个成员的地址和整个结构的地址相同。

最近在实验室白天完全是不敢看dota视频，连dota视频网页都不敢打开，太显眼了，但是又想关注有没有精彩视频更新,怎么样才能在不打开网站的情况下知道视频情况呢？
想了想，还是尝试用python写个小助手。python以前只是简单的看过，小白阶段。但是python上手确实太快了。下面就是刚才利用2个小时写的脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import urllib
import re

def dotareplay(url):
    content = urllib.urlopen(url).read()
    content = content.decode('utf-8')
    matchtitle = re.findall(u'<li class="v_title"><a href=".*" charset="100344-18935-[1-9]-2" target="video" title=".*">', content)
    if matchtitle:
        for eachtitle in matchtitle:
            findeachtitle=re.search('<li class="v_title"><a href="(.*)" charset="100344-18935-[1-9]-2" target="video" title="(.*)">', eachtitle)
            print findeachtitle.group(2)
            print findeachtitle.group(1)

def main():
    dotareplay('http://game.youku.com/')

if __name__ == '__main__':
    main()

链表的结构比较简单，基本特性以及相关操作这里就不作介绍。如果有同学不自信的话，这有个pdf文档可以参考复习下。http://cslibrary.stanford.edu/103/如果有同学网络问题不给力的话，可以给我发邮件。下面来看几道常见的面试题。

1.链表倒置（两种方法）

这个应该也算比较简单的，直接上代码了。(两种：迭代、递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void reverse_iterate(struct node** head)
{
    struct node* result = NULL;
    struct node* current = *head;
    struct node* next;

    while(current != NULL)
    {
        next = current->next;

        current->next = result;
        result = current;
        current = next;
    }
    *head = result;
}

void reverse_recursive(struct node** head)
{
    struct node* first;
    struct node* rest;

    if(*head == NULL)
        return;

    first = head;
    rest = first->next;

    if(rest == NULL)
        return;

    reverse_recursive(& rest);

    first->next->next = first;
    first->next = NULL;

    *head = rest;
}

3sum问题就是3数求和问题，可以简单描述如下：给定数据集S找出数据集中的三个元素a,b,c，满足a+b+c=k。直接可能没什么思路，其实3数求和问题可以看成是下面这个问题的扩展：给定数据集S，找出所有数据对a,b，满足a+b=k。

其实对于原始问题的求解时间复杂度可以达到O(n)，如果数据集是已排好序的。分别在头部和尾部设置两个指针，求其和，如果大于K，则尾部的指针向头部移动，否则头部的指针向后移动。用C语言简单实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void find2sum(int dataSet[], int itemNum, int key)
{
    int left=0;
    int right = itemNum-1;

    while(left<right){
        if(dataSet[left]+dataSet[right] == key)
            printf("The pair (%d %d) bingo!", left, right);
        else if(dataSet[left]+dataSet[right] < key)
            left ++;
        else
            right --;
    }
}

对上面的方法进行扩展就可以得到3数求和问题的解答了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void find3sum(int dataSet[], int itemNum, int key)
{
    int i, left, right;
    sort(dataSet);
    for(i=0; i<itemNum-2; i++){
        left    = i+1;
        right   = itemNum-1;
        while(left<right){
            if(sum(i, left, right) == key)
                printf("triplet %d %d %d bingo!\n", i, left, right);
            else if(sum(i, left, right) < key)
                left ++;
            else
                right ++;
        }
    }
}

如果文章从这儿就结束了，那也没有写的必要了。

前面求解两数求和问题的时候提到了数组是排好序的，利用这一特性我们可是可以大做文章了。例如：如何求解两个已排序数组的公共子序列？

首先说明下，公共子序列和公共子串是不同的。公共子串是连续的，而公共子序列则没有这一限制。比如{1，2，3，4，5，6｝的子序列可以是｛1，3，6｝。

我们不妨设置两个数组分别为A，B，长度分别为m，n。结合上文，很容易可以得到时间复杂度为O(m+n)的解法。分别设置两个指针指向两个数组，然后比较，将较小的指针往前移动即可。

另外说到排序好的数组，一个自然反应应该就是二分查找了。对于数组A中的每个元素，对数组B进行二分查找，时间复杂度为O(mlgn)。其实这个讨论是有必要的，当m<<n时，这种方法明显优于上面的。

其实个人觉得效率还可以更高，只要将上面两种方法结合起来，定性描述如下。第一种方法的思想，当找到A[i]=B[j]的时候，下一次对B进行二分查找的时候，只需要查找B[j+1, n-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void commonSeq(int A[], int B[], int m, int n)
{
    int index_A, index_B, result;

    index_A = index_B = 0;
    while(index_A<m && index_B<n){
        result = bisearch(B, index_B, n, A[index_A]);
        if(-1 == result)    /*使没查找到时返回-1*/
            index_A ++;
        else{
            printf("%d\t", A[index_A]);
            index_A ++;
            index_B = result+1;
        }
    }
    printf("\n");
}

还有一些，以后再说吧！
see you!