1. 第一课

面向对象：封装、继承、多态。模块与模块之间尽量解耦合

2. 递归

约瑟夫环问题（递归解法）

假设：

初始情况： 0, 1, 2 ……n-2, n-1 (共n个人)

第一个人(编号一定是(m-1)%n,设之为(k-1) ) 出列之后，

剩下的n-1个人组成了一个新的约瑟夫环（以编号为k==m%n的人开始）:

k k+1 k+2 … n-2, n-1, 0, 1, 2, …,k-3, k-2

现在我们把他们的编号做一下转换：

x -> x’ （x‘代表新编号，x代表原编号 k==m%n）

k –> 0
k+1 –> 1
k+2 –> 2
…
…

k-3 –> n-3

k-2 –> n-2

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x’是最终的胜利者，那么根据上面这个表把这个x’变回去不刚好就是n个人情况的解吗！
x’ ->ｘ？(这正是从n-1时的结果反过来推n个人时的编号！)
0 -> k

1 -> k+1

2 -> k+2

…

n-3 -> k-3

n-2 -> k-2

变回去的公式　x=(x’+k)%n

那么，如何知道(n-1)个人报数的问题的解？只要知道(n-2)个人的解就行了。(n-2)个人的解呢？只要知道(n-3)的情况就可以了 —- 这显然就是一个递归问题：

令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果就是f[n]

递推公式

f[1]=0;

f[n]=(f[n-1]+k)%n = (f[n-1] +m%n) % n = (f[n-1] + m) % n ; (n>1)

当然，当n==1时，直接返回0即可

public static int lastRemaining(int n, int m) {
    if (n == 1) {
        return 0;
    }
    return (lastRemaining(n - 1, m) + m) % n;
}

3. 链表

4.栈、队列

4.1 数组循环左移

假设数组a[7]={1,2,3,4,5,6,7}，向左移3个元素，输出结果为：4 5 6 7 1 2 3

对前3个元素逆序，变为{3,2,1,4,5,6,7}

对后4个元素逆序，变为{ 3,2,1,7,6,5,4 }

对所有元素逆序，变为{ 4,5,6,7,1,2,3 }

#include<stdio.h>

//[ster...end)，左边包含右边不包含
void reverse(int *a, int ster, int end)

{

    int temp;

    int s = end - 1;        //起始位置下标不变，终止位置-1

    while (ster < s)

    {

        temp = a[ster];

        a[ster] = a[s];

        a[s] = temp;

        ster++;

        s--;

    }

}

void main()

{

    int i, k, a[7] = { 1,2,3,4,5,6,7 };

    printf("先输入左移个数：\n");

    scanf("%d", &k);

    reverse(a, 0, k);

    reverse(a, k, 7);

    reverse(a, 0, 7);

    for (int i = 0; i < 7; i++)

    {

        printf("%d ", a[i]);

    }

}

4.2 表达式树

《数据结构》：中缀表达式转后缀表达式后缀表达式的计算

Irony's blog

数据结构与算法分析