先看一道例题，来自某公司招聘试题，如下：
`
在一场运动会中，共有n个国家的运动员参加比赛。
每个国家派出了5个运动员，所以一共有5n个运动员参加。
现在要求将他们排成一列纵队，但是要求每位运动员都能够挨着一个他的同胞而站。
你需要计算满足这样条件的排列方案数是多少。

Mooc距第一次听说已经过去4年了，在这过程中有不少好的课程（老师）令我受益匪浅，这次就做一个推荐吧。
1.程序设计入门——C语言
这门课算是我的启蒙课程，老师的思路非常清晰，完全像是给一个刚刚接触程序设计的小白讲的课程，非常容易上手。
2.C程序设计进阶
这门课程可以作为C语言的一门进阶课程。关于函数调用那一章地方讲的非常棒！到现在还记得老师上课时画的那只手。对指针的讲解也非常细致，完全是书本上接触不到的心法。
3.C++程序设计
见没见过一节课一瓶水的老师？就是他了。印象最深的是面向对象的设计方法中“表达A是B，使用派生。表达A有B，使用复合”。以及那句经典的“人中有狗，狗中有人，人狗合一”。哈哈真的是笑死了。
4.数据结构
在陈越姥姥的课上总是能给你惊喜，每次都是从一个问题开始，引发你的思考，从而一步又一部地刨析下去。当你以为找到解决办法的时候，姥姥就会告诉你“图样图森破”。
5.操作系统 李志军
生平中遇到的老师倒也不少，但是会讲人话的还真不多。老师讲课通俗易懂很地道，不时夹杂着几句方言很社会。课程定位很明确，不是为了研究生考试而准备，而是真正动手从一行行代码改起，从设计者的角度出发去剖析，真正实现自己的操作系统。

关于二叉树的遍历，往往会出这么几类题目：

1. 根据一种序列重建二叉树

分析：只给出一个输出序列会对应多种二叉树，因此这类题目的给定序列中往往包含有空节点，这时只需要反过来写递归程序便可：
例：1086 Tree Traversals Again (25)（25 分）
程：

int times = 0;                //计数变量
node * build()
{
    node * r = NULL;         //根节点指针
    if( times < 2*N )            //若输入N个数据，则二叉树有2*N个节点    
    {
        int tem;            
        cin >> tem;
        if( tem !=  -1 )        //若输入不是-1
        {
            r = new node;    
            r -> num = tem;    //建立根节点
            times++;
        }
        else
        {                    //若是-1
            times++;
            return NULL;    //返回空指针
        }
            r->left = build();        //递归调用 ,建立leftchild
            r->right = build();    //递归调用,建立rightchild
    }
    return r;                //返回建立好的二叉树(pre-order)
}

2.根据先序中序遍历

分析： 既然给出了两种序列，那么序列中一定不包含空节点的输出，对于这种问题其解题的核心在于找到根节点位置。
那么，如何找到根节点的位置呢？这就得利用中序遍历序列了。
例：1138 Postorder Traversal（25 分）
程：

void build(int root, int start, int end)
{
    if(start > end)
        return;
    int i = start;
    for(; inorder[i] != post[root]); i++);
    /************************
            do something
    ************************/
    build( root + 1,start,i-1);
    build( root + (i-start) + 1, i+1 , end);
}

析：
例如先序与中序分别是是:

1 2 3 4 5 6 7
2 3 1 5 4 7 6

根据先序序列，我们能够知道，根节点是1，那么2节点是1的左孩子(先序遍历的特性)。那么右节点在哪呢?
如果我们再看看中序序列，我们就可以清楚地发现树的结构是这样的：

           1
{2 3}          {5 4 7 6}

所以，先序序列的排布方式会是这样：

根 |   左   |      右 
 1  | 2   3  | 4   5   6   7

递归程序的接口设计为根节点的位置(先序)，树的范围(中序)。
根据中序序列确定子树的范围和子树的根节点位置。

3.根据先序后序遍历

例:1119 Pre-and Post-order Traversals（30 分）
程:

void build(int preStart, int preEnd, int postStart, int postEnd)
{       
        if(preStart == preEnd)
        {
                v.push_back(preorder[preStart]);        
                return ;
        }
        if(preorder[preStart] == postorder[postEnd])
        {
                int i = preStart + 1;
                for(; i < preEnd && preorder[i] != postorder[postEnd-1]; i++); // find the root of right child in preorder sequence
                if(i - preStart > 1)
                        build(preStart + 1,i-1,postStart,postStart+(i - preStart-1) - 1);
                else
                        unique = false;
                v.push_back(preorder[preStart]);
                build(i,preEnd,postStart + (i - preStart-1),postEnd - 1);
        }
}

析：首先需要说明的是，根据先序与后序而确定的二叉树并不唯一。
解决这个问题的核心在于树的划分。

关于system call 的调用过程本文不在此赘述，笔者只想在此说明如何在linux0.11内核的基础上添加系统调用。
要增加系统调用，分别需要在这7个地方进行改动，分别是内核代码中的：

1. include/unistd.h 中添加系统调用号
2. 在lib中增加用户接口源文件
3. include/linux/sys.h 中添加系统调用函数定义
4. kernel/system_call.s 修改系统调用总数
5. kernel中增加系统调用的具体实现
6. 修改Makefile 文件

以及usr/include/下的用户接口文件unistd.h
下面以增加一个系统调用hello()为例进行说明：

1. 添加内核系统调用号

打开源文件include/unistd.h，在132行处添加

#define __NR_hello      72

2. 增加用户接口源文件

进入lib目录，新建源文件hello.c

#define __LIBRARY__
#include<unistd.h>
_syscall0(int,hello)

3. 添加系统调用函数的定义

打开include/linux/sys.h，分别在73行和sys_call_table[]数组中添加

extern int sys_hello();

sys_hello

4. 修改系统调用总数

打开kernel/system_call.s ，将61行改为

nr_system_calls = 73

5.增加系统调用的具体实现

进入kernel目录，新建源文件sys_hello.c

int sys_hello()
{
        printk("Hello From kernel\n");
}

6.修改Makefile文件

进入kernel目录，打开Makefile,在OBJS 那一项后面添加

sys_hello.o

在最后一行添加

sys_hello.s sys_hello.o : sys_hello.c ../include/linux/kernel.h ../include/unistd.h

然后返回源文件根目录，make 编译内核。

7.添加编译器系统调用号

进入系统后，在/usr/include/unistd.h文件132行添加(与第一步不同)

#define __NR_hello      72

系统调用即添加完毕，新建hello.c文件进行测试:

#define __LIBRARY__
#include <unistd.h>
#include<stdio.h>
int errno;
_syscall0(int,hello)
int main()
{
    hello();
    return 0;
}

使用gcc 编译并运行，显示输出:

Hello From kernel

1.setup中获取扩展内存大小：

! Get memory size (extended mem, kB)

        mov     ah,#0x88
        int     0x15
        mov     [2],ax

返回：ax=从0x100000(1M)处开始的扩展内存大小

2.保护模式

setup切换保护模式位于[0x00090348] 9020:0148

        mov     ax,#0x0001      ! protected mode (PE) bit
        lmsw    ax              ! This is it!

此时CPU已经进入32位保护模式

jmpi    0,8             ! jmp offset 0 of segment 8 (cs)

这句话在16位实模式下解释如下:

CPU跳转至cs = 8,IP = 0 即0x80处开始执行

而到了32位,CS称为选择子。此时的寻址方式为：
通过选择子配合gdt表查到一个值，把这个值重新组合作为新的地址。
此时GDTR = 0x0009035b 意味着当前gdt表起始位置在内存中的0x0009035b处。cs=8代表，以GDTR位起始位置，偏移8个字节。也就是选择‘0x00090363’。存放的东西是什么呢？

0x00090363 <bogus+       8>:    0xff    0x07    0x00    0x00    0x00    0x9a    0xc0    0x00
p.s. 为了方便起见，将低地址放到低位，高地址放到高位于是乎:
0x00090363-0x00090371: 
00C09A00000007FF

上面的东西代表的是什么意思呢？其是，它是一段LDT(Local Descriptor Table)。一共64个bit，其解释方式如下图所示：

重点关心黑色字体部分:
00C09A00000007FF
前面的就是32位保护模式下的基址，后面的就是保护模式下的偏移地址。所以，接下来CPU就到了00:000000处。
用一张图概况保护模式下的寻址方式，一定就是这样了:

2018.10/27
为了加深理解，补充一张 GDT 的图片：

可以看到，除了 LDT 外，GDT 还包含有 TSS。而 TSS 却跟任务调度有着莫大的联系…

来源：赵炯《Linux 内核完全注释》

2019/2/2
可以这样理解，对于计算机来说，操作系统可以当作是一个庞大的进程。这个进程一方面处理用户交互（管理硬件），一方面用于支持其他的进程去运行。
分段机制让内存管理变得高效，但需要记录下来每个段的地址。这就需要有一份段表。
操作系统的段表就是 GDT，进程的段表就是 LDT

首先，BIOS有一段自检程序，其作用还不明确。总之，与我们有关的地方是内存中0x07c00
CPU到了0x07c00从这里开始进入bootsect.s

_start:
        mov     ax,#BOOTSEG
        mov     ds,ax
        mov     ax,#INITSEG
        mov     es,ax
        mov     cx,#256
        sub     si,si
        sub     di,di
        rep
        movw
        jmpi    go,INITSEG

而bootsect.s 一开始先是将自己拷贝到0x90000处
bootsect 本身只有512字节，因此才有了上述程序rep那里的内容.
256word= 512 byte
也就是从内存中0x07c00拷贝512字节到0x90000.
0x90000-0x9001ff 这里便是bootsect的新的位置.

这时候，如果你反汇编一下0x07c00 与 0x90000。你会发现二者相同，并且就是bootsect.S中的内容，因此验证猜想正确。

go:     mov     ax,cs          ! 此时cs=9000,IP = 0018
        mov     ds,ax
        mov     es,ax
! put stack at 0x9ff00.
        mov     ss,ax
        mov     sp,#0xFF00

执行完jmpi go,INITSEG后,CPU 便跳到了0x90018处，设置堆栈大小.并将ds,es设置为9000H.此时,cs=ds=es=ss=9000H.
接下来到了ok_load_setup

load_setup:
        mov     dx,#0x0000              ! drive 0, head 0
        mov     cx,#0x0002              ! sector 2, track 0
        mov     bx,#0x0200              ! address = 512, in INITSEG
        mov     ax,#0x0200+SETUPLEN     ! service 2, nr of sectors
        int     0x13                    ! read it
         jnc     ok_load_setup           ! ok - continue

这里的重点就是bios 13号中断.

功能描述：读扇区 
入口参数：AH＝02H 
AL＝扇区数 
CH＝柱面 
CL＝扇区 
DH＝磁头 
DL＝驱动器，00H~7FH：软盘；80H~0FFH：硬盘 
ES:BX＝缓冲区的地址 
出口参数：CF＝0——操作成功，AH＝00H，AL＝传输的扇区数，否则，AH＝状态代码

bios13号中断为基本的磁盘操作，根据ah不同选择不同功能。
上述ah = 02,al=SETUPLEN=2.
因此，其含义为
“从0柱面第二个扇区第0个磁头读4个扇区(2048B)到内存的0x90200处”
执行完第一个int 13后，我们查看0x90200内容。
会发现0x90200-0x90337共312字节

<bochs:29> u 0x90200 0x902ff
00090200: (                    ): mov ah, 0x03              ; b403
00090202: (                    ): xor bh, bh                ; 30ff
00090204: (                    ): int 0x10                  ; cd10
00090206: (                    ): mov cx, 0x0017            ; b91700
00090209: (                    ): mov bx, 0x0007            ; bb0700
0009020c: (                    ): mov bp, 0x014c            ; bd4c01
0009020f: (                    ): mov ax, 0x1301            ; b80113
00090212: (                    ): int 0x10                  ; cd10
00090214: (                    ): mov ax, 0x9000            ; b80090
00090217: (                    ): mov ds, ax                ; 8ed8
00090219: (                    ): mov ah, 0x03              ; b403
0009021b: (                    ): xor bh, bh                ; 30ff
0009021d: (                    ): int 0x10                  ; cd10
0009021f: (                    ): mov word ptr ds:0x0, dx   ; 89160000

正是后面setup.S中的内容。
如果成功，CF=0，跳转至ok_load_setup
若不成功得想办法补救，即重新读：

        mov     dx,#0x0000
        mov     ax,#0x0000              ! reset the diskette
        int     0x13
        j       load_setup

成功后，继续

ok_load_setup:

! Get disk drive parameters, specifically nr of sectors/track

        mov     dl,#0x00
        mov     ax,#0x0800              ! AH=8 is get drive parameters
        int     0x13

又是int 13.这次AH=08:

入口参数：AH＝08H 
DL＝驱动器，00H~7FH：软盘；80H~0FFH：硬盘 
出口参数：CF＝1——操作失败，AH＝状态代码，参见功能号01H中的说明，否则， BL＝01H — 360K 
＝02H — 1.2M 
＝03H — 720K 
＝04H — 1.44M 
CH＝柱面数的低8位 
CL的位7-6＝柱面数的该2位 
CL的位5-0＝扇区数 
DH＝磁头数 
DL＝驱动器数 
ES:DI＝磁盘驱动器参数表地址 

执行完int 13后，发现BL= 4代表读取软盘 大小为1.44M，CL =00010010B代表18个扇区 ，将CH置零后，cx = 0012H

      mov     ch,#0x00
        seg cs
        mov     sectors,cx
        mov     ax,#INITSEG
        mov     es,ax

接下来第2，3句为段超越，意思把cx内容移动到cs:[sectors]，此时sectors相当于一个变量，用于保存一个值，测试时发现sectors=0x13d。意味着将读取到的数据保存在内存cs:sectors处。
同时，int 13 改变了ES，将es再设回9000。然后，准备在屏幕上显示一些文字。

! Print some inane message

        mov     ah,#0x03                ! read cursor pos
        xor     bh,bh
        int     0x10

AH = 3
读光标位置
输入参数：BH = 页号
输出参数：
CH = 光标开始行
CL = 光标结束行
DH = 行
DL = 列

先读0页光标位置，ch=6,cl=7,dh=10,dl=0。

    mov     cx,#24                     !  cs:ip=0x00090056 
       mov     bx,#0x0007              ! page 0, attribute 7 (normal)
        mov     bp,#msg1
        mov     ax,#0x1301              ! write string, move cursor
        int     0x10

显示24个字符串。
接着将系统加载到内存起始0x10000处，代码如下

! ok, we've written the message, now
! we want to load the system (at 0x10000)

        mov     ax,#SYSSEG
        mov     es,ax           ! segment of 0x010000
        call    read_it

将段设置好后调用了读取函数：

read_it:
        mov ax,es
        test ax,#0x0fff
die:    jne die                 ! es must be at 64kB boundary
        xor bx,bx               ! bx is starting address within segment
rp_read:
        mov ax,es
        cmp ax,#ENDSEG          ! have we loaded all yet?
        jb ok1_read
        ret
ok1_read:...
ok2_read:...
.....

将一些东西准备就绪后，就要进入setup

    jmpi 0,SETUPSEG

跳转至0x90200。

庄子:
"吾生也有涯，而知也无涯。以有涯随无涯，殆已！已而为知者，殆而己也。"
胡适:
"怕什么真理无穷，进一寸有进一寸的欢喜。"

孔子:
“君子固穷，小人穷斯滥矣！”
管仲:
“仓廪实而知礼节，衣食足而知荣辱”

神秀：
“身是菩提树，心如明镜台，时时勤拂拭，勿使惹尘埃。”
惠能：
“菩提本无树，明镜亦非台，本来无一物，何处惹尘埃。”

霍普斯:
“一切人对一切人的战争”
克鲁泡特金
"人类发展的主旋律是和平，同情是合群生活的必然产物，同情来源于相似。"

程朱理学:
"格物致知,存天理灭人欲"
阳明心学:
"心即理，致良知、知行合一"

来源: 中国大学MOOC数据结构 陈越、何钦铭

注: 希尔排序中d取决于增量的选取，其可能小于2
基数排序中，B代表有多少个桶，P为收集的趟数

学习是一个过程。
大家通常所理解的学例如上课那样的不是学习，所做的只不过是浏览信息而已，什么是学习？
学习是一个动态的过程，是出现问题，寻找方法，解决问题这样一些列的过程。
就像通常意义上的“刷题”一样。“刷题“为什么高效？
出现不会做的难题，翻阅书本，查阅资料，寻找解决方法，最终解决问题。
这个过程不像所谓浏览信息一样的学习，浏览信息的整个过程中所看到的只是一个静态的信息，而上述定义的学习在其过程中，你与信息之间发生了关系，通过使用静态的信息将它与自己的知识网络缝合起来，这个过程叫学习。