1.考试时如何写代码

①在变量的定义处告知该变量是做什么的；
②在使用伪代码处和函数调用处告知这部分实现哪些功能；
③代码逻辑复杂的地方告知是做什么的。

2.复杂度问题

2.1时间复杂度

循环次数

（1)对于多层for循环，如果每一层的变量都是自增1，则直接把每层执行次数相乘
   for (i=0;i<n;i++)
      for (j=0;j<n;j++)
          for (k=0;k<n;k++)
             if (A[i][j]>A[i][k]+A[k][j])
                 A[i][j]>A[i][k]+A[k][j];
他的每一层都是变量自增，且变量都是从0~n-1共n次，所以总次数是n^3，时间复杂度是O(n^3)。

（2)对于多层for循环，如果每一层的变量都是自增1，但第二三层变量取值范围和第一层变量有关
   for (i=0;i<n;i++)
      for (j=0;j<i;j++)
          for (k=0;k<j;k++)
             if (A[i][j]>A[i][k]+A[k][j])
                 A[i][j]>A[i][k]+A[k][j];
时间复杂度和第①种一样，但不用考虑具体次数，时间复杂度是O(n^3)。

（3)对于两层循环，变量不是自增1（这种情况主要针对小题）
   for (i=1;i<n;i*=2)            //22考研真题
      for (j=0;j<i;j++)
          sum++;
需要讨论第一层变量i取不同值时，j的取值有x种，然后对x求和。比如本题，i=1, 2, 4, 8…2k(2k<n≤2k+1)时，第二层j有i个取值，所以总次数是对i求和，即T=1+2+4+2k=2k+1-1，n<T<2n，时间复杂度就是O(n)。

递归次数

递归总次数和时间复杂度有关，而最大递归层数和空间复杂度有关。
对于树中序遍历的递归写法，每个节点都会调用一次所以总共调用次数是O(n)级别的，时间复杂度是O(n)，而递归使用的层数最多是树高h，空间复杂度是O(h)。
    void inorder(BTNode *p){
          if (p==NULL) return;
          inorder(p->lchild);
          visit(p);                           //对p节点的访问等
          inorder(p->rchild);
      }

2.2空间复杂度

算额外空间开销，不考虑题目中已经给出的数据所占的空间，比如题目中给出了一个数组，这个数组是不计入空间复杂度的。

* 定义的数组、链表
单个定义的变量都不需要考虑，但定义的数组中元素个数以及链表中节点个数都要计入空间复杂度中。

* 递归层数
是在递归栈中最多出现多少个过程函数，层数和总次数比较见时间复杂度的递归次数。

2.3注意题目关于复杂度的要求

共有五种情况：
1)时间上尽可能高效：表示只要求时间复杂度，对空间复杂度不做要求
2)时间和空间两方面都尽可能高效：时间和空间复杂度都要求尽量小，时间复杂度小优先。
3)尽可能高效：要求同（2）。
4)空间复杂度为O(1)且时间上尽可能高效的算法：要求算法的空间复杂度是O(1)，时间复杂度尽可能小。
5)没有描述：只要能做出来就行，不要求复杂度是多少，常见于树中

3.顺序表

* 推荐流程：想出暴力解法->分析暴力解法复杂度->在暴力解法基础上思考优化

3.1 暴力破解

枚举法

*  枚举法是最容易想到的方法，把所有可能的情况都考虑到，然后从中选出符合题目要求的情况，通常使用for循环遍历。

对无序数组排序

    对于一个无序的数组可以先通过排序把他变成有序再处理，排序使用快速排序。考试直接默写快速排序，然后注意调整参数
    快速排序是一种分治思想，每一轮快排分为两个步骤：①选择枢值key。②枢值移动到他的最终位置，左右划分为两个区间，左
边区间的所有元素都小于枢值，右边区间的所有元素都大于枢值。然后对左右区间分别进行快排，不断重复直到当前处理区间元
素个数小于等于1（即L>=R）。
    快速排序的平均时间复杂度是O(nlogn)，平均空间复杂度是O(logn)，是考试中最快的不稳定排序算法，一般要用到排序时都
使用快速排序。快速排序的最坏时间复杂度是O(n^2)，最坏空间复杂度都是O(n)，但我们只需要加一个小优化就能避免最坏情况
：即随机选择一个元素作为枢值。优化后最坏时间复杂度O(nlogn)，最坏空间复杂度O(logn)。

代码如下

    void Qsort(int A[],L,R){    //a数组保存数据,L和R是边界
    if(L>R) return; //当前区间元素<=1 则退出
    int pivot,i=L,j=R;  //i和j是左右两个数组下标移动
    把A[L~R]中随机一个元素和A[L]互换    //快排优化，使得基准值的选取随机
    pivot=A[L]
    while(i<j&&A[j]>pivot)
    j--
  while (i<j && A[i]<=pivot)
     i++;
     if (i<j)
     swap(A[i], A[j]);          //交换A[i]和A[j]
}
swap(A[L], A[i]);           //将基准值放入他的最终位置
/*此时A[L~i-1]<=A[i]<=A[i+1~R]*/
Qsort(A, L, i-1);       //递归处理左区间
Qsort(A, i+1, R);       //递归处理右区间
 }

3.2思考优化的方向

    主要是三个方向：
①有没有条件没有使用到，如有序性，那如何利用这个条件？
②有没有超额完成题目中没有要求的任务？
③除了暴力的思考方向，还有没有别的方向？

3.3进阶需要掌握的算法

利用有序性——折半查找

 在线性表中如果需要查找权值为x的元素，时间复杂度是O(n)，也就是说不管什么线性表，查找元素的复杂度下界是O(n)。如果要实现查找的时间复杂度是O(logn)，
 因为待查找元素可能出现在任意位置，那需要每次查找都能够排除一半情况，这就是折半查找的逻辑。
 折半查找前提：
 ①数列必须是有序的，升序或者降序；
 ②只能是顺序表（数组），不能是链表。
       考试中当我们看到出现了一个有序数组（如果是链表一定不能使用）的时候，首先想想是否需要查找，能不能使用折半查找。
       折半查找，也叫二分查找，
       假设我们在升序数组A[L~R]中查找x，L和R是上下界（即Left和Right），mid=(L+R)/2，每次把x与A[mid]比较：如果x>A[mid]，说明x一定不会出现在A[L~mid]，只可能出现在A[mid+1~R]，更新L=mid+1；
       而如果x<=A[mid]，说明x一定不会出现在A[mid+1~R]，只可能出现在A[L~mid]，更新R=mid。重复比较——更新过程，直到L==R，此时A[L]就是我们要找的元素，如果A[L]不等于x说明x不在数组A中。

  eg:
  ①书写折半查找，最怕当只有两个元素的出现死循环，书写完后一定要带入只有两、三个元素的时候试一下是否有问题；
  ②如果是题目中返回查找成功时的下标可以直接使用这段代码，否则需要调整最后一个if语句。

int Binary_Search(int A[], L, R, x){ //A[]和x不一定是int型
  int mid;
  while (L<R){  //如果L>R则范围错误
     mid=(L+R)/2;   //mid取中间数，向下取整
     if (x<=A[mid])
             R=mid;
        else L=mid+1;   //更新查找范围
  }
  if (A[L]==x) return L;    //查找成功，返回数组下标L
     else return -1;    //查找失败
}

设置多指针后移

多指针后移常用于有序线性表（顺序表和链表都可以），如果考试中给出有序的线性表，优先考虑这种方式。
这种方式可以用于合并多个有序线性表、查找第k个元素等等，归并排序就是用到了这种思想。

归并两个升序数组（理解+应用），代码如下：

int C[n+m];     /*习惯将新数组设为全局变量*/
void Merge(int A[], n, B[], m){ //数组A、B长度分别为n、m
  int i=j=k=0;     //i、j作为遍历A、B的下标
  while (i<n && j<m)      //直到有一个数组遍历完
     if (A[i]<B[j])         //将小的那个数存入C数组
        C[k++]=A[i++];
     else C[k++]=B[j++];
  for (; i<n; i++)
     C[k++]=A[i];      //将A中剩余的数存入C数组
  for (; j<m; j++)
     C[k++]=B[j];      //将B中剩余的数存入C数组
}

3.4分析复杂度

分析所用算法的时间和空间复杂度，
常见时间复杂度：O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。
到这一步我们仍然只是思考还未进行书写，下一步开始书写。

3.5书写

先思考清楚整个算法需要做哪些事情已经对应流程，分析完复杂度再开始写。
* 第一小问：设计思想
主要介绍逻辑，告诉老师你用了什么，比如快速排序，重要的是让老师知道用的方法是什么。

* 第二小问：描述算法
注释要详实，用来介绍变量、过程的作用，提示老师。对于快速排序和折半查找（注意是否查找成功）可以直接默写，过程函数不需要改动，注意调用的参数即可。

* 第三小问：求时间和空间复杂度
直接写复杂度，不用过程，要检验是否符合代码。

4.链表

    做题推荐流程：和顺序表一样，
    想出暴力解法->分析暴力解法复杂度->在暴力解法基础上思考优化。

4.1需要注意的地方

4.1.1 特点

1)是线性表。线性表能用的方法他都能用，比如归并两个有序序列，所以数组指针后移的方法也可以用到链表中。
2)无法随机访问。如果一个方法需要利用随机访问的特性，那就不能用在链表上，比如说折半查找和快速排序。
3)只能向后查找，无法回头。比如要求倒数第k个结点，无法从最后一个结点往前查，得转化成正数第x个结点，从前往后查，或
者采用前后指针固定间距。

4.1.2 题目的要求

1)如果题目要求空间复杂度是O(1)，这就意味着不能额外设置数组，不能将链表先用数组保存然后再进行处理。
2)如果题目要求不可修改链表结构，意思是我们不能随意的对链表元素顺序进行修改以及随意的插入和删除。

4.1.3 考察结构

 题目中经常会有如下描述：
      根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
     我们可以提前记忆模板，然后考试中根据题目要求进行改动（仔细审题）：
单链表（data是该节点的权值，一般可以定义成int；next是指向下一个节点的指针，保存的是下一个节点的位置）：
    typedef struct LNode{
         Elemtype data;     //该节点的权值
        struct LNode *next;    //next指向下一个节点
     }LNode;

双链表（不需要特别记忆，只是比单链表多一个prior指针而已）：
    typedef struct LNode{
         Elemtype data;     //该节点的权值
        struct LNode *prior,*next;    //prior指向上一个节点
    }LNode;

4.2暴力解法

枚举法，直接处理

    链表的一些题目可以先采用最直接易想的方法，比如要改变链表元素顺序的话，可以将需要重排的元素一个一个拆下来重新‘
插入。这些方法一般看起来比较憨，但是容易想到。

将链表用数组保存，再处理

    可以使用数组保存链表中的结点地址或者直接保存数据，然后再按照数组的做题方法操作即可。注意：
    ①如果题目中求的是处理后的链表；
    ②如果题目要求空间复杂度为O(1)；
    这两种情况都不能使用数组保存链表的结点。

4.3 适用于链表的优化算法

设置多指针后移

类似于前面的数组多指针后移，在链表中也可以使用这种方法，
在数组中每次后移是i++，而链表中则是p=p->next，本质上都是一样的。
归并两个带头节点的升序链表（理解+应用），代码如下：

void Merge(LNode *L1, *L2){       //数组A、B长度分别为n、m
   LNode *p=L1->next, *q=L2->next;    //p、q指向L1、L2第一个元素
   LNode *r=L1;      //新链表头节点为L1，r指向末尾
   LNode *pn, *qn;    //用来暂存p->next和q->next
   while (p!=null && q!=null)      //直到有一个链表遍历完
      if (p->data<q->data){        //将小的那个数存入新链
          pn=p->next;         //pn为p下一个元素
          r->next=p;  //p插入到r后面
          p->next=null;      //这是新链最后一个元素
          r=p;         //尾指针r指向最后一个元素
          p=pn;         //p指向p下一个元素
      }
      else{ 
          qn=q->next;     //qn为q下一个元素
          r->next=q;     //q插入到r后面
          q->next=null;     //这是新链最后一个元素
          r=q       //尾指针r指向最后一个元素
          q=qn;       //q指向q下一个元素
      }
   if (p!=null)
      r->next=p;      //将剩余部分连到r后面
   if (q!=null)
      r->next=q;        //将剩余部分连到r后面
   /*L1是合并后的升序链表，注意此时r已经不是指向尾元素的指针了*/
}

4.4一些基本操作

只要把所有涉及到的结点都事先用指针保存下来就不可能断链。
如下图，我们可以实现自己约定好当前删除结点就用指针p指向，
前一个结点就用pre指向，后一个就用post指向。代码的顺序可以改变

4.4.1 取出/删除p指向的结点

//取出p指向的结点
pre->next=post
p->next=null; //不写也没关系
//删除p指向的结点:
pre->next=post;
free(p); //不写也可以

4.4.2 将p结点插入到per结点后面

//p插入pre后面的结点
p->next=post;
pre->next=p;

4.4.3 头插法插入p

//需要将p插入到L和post=L->next之间
p->next=post;
L->next=p;

4.4.4 遍历链表

对于线性表（数组+链表）的遍历，如果表中元素个数确定就用for循环，否则用while循环。在遍历过程中访问指针p每次都需要后移即p=p->next，不要忘记。
已知元素个数n：
Node* p=L->next;
for (int i=0; i<n; i++){
  visit(p);     //访问p结点
  p=p->next;
}

不知道元素个数：
Node* p=L->next;
while (p!=null){
  visit(p);     //访问p结点
  p=p->next;
}

5.树

5.1需要珠的地方

5.1.1 题目的要求

树的题目一般不会特别要求复杂度，如果没有特别要求的话，考试中只要做出来就可以直接写，不用考虑优化问题。一般都会考察树的遍历，除非特别说明，否则遍历就用递归写，不要写非递归。

5.1.2 考察结构

* 树和森林(孩子兄弟表示法)
 firstchild是指向该节点第一个儿子节点的指针，nextbro是指向下一个兄弟节点的指针
  typedef struct TNode{
         Elemtype  data; //每个节点的权值
        struct TNode *firstchild, *nextbro;
     }TNode; //树节点
* 树和森林（结点用双亲表示法存储，常用于并查集）
树和森林（节点用双亲表示法存储，常用于并查集）
一般采用数组表示，data数组保存每个节点的权值，father数组保存每个节点的父亲节点在数组中的下标：
  int father[maxsize];  //保存每个节点的父亲节点在数组中的下标
  Elemtype data[maxsize];   //保存每个节点的权值
也可以
  typedef struct TNode{
     Elemtype  data;  //每个节点的权值
     struct TNode *father; //father是指向该节点父亲节点的指针
     }TNode;   //树节点

二叉树（左右孩子表示）
   typedef struct BTNode{
     Elemtype  data; //每个节点的权值
    struct BTNode *lchild,*rchild;  //指向左右孩子节点的指针
     }BTNode; //二叉树节点

5.2 树的遍历（递归）

 树的遍历是408代码题的常考点
 前中后序的递归遍历时间复杂度为O(n)，空间复杂度为O(h)，n是总节点数，h是树高。
前序（根左右）：
 void preorder(BTNode *p){
     if (p==NULL) return;
     visit(p);  //对p节点的访问等
     preorder(p->lchild); 
     preorder(p->rchild);
     /*这三条语句，visit在先就是先序，在中就是中序，在后就是后序*/
     }
中序（左根右）：
  void inorder(BTNode *p){
     if (p==NULL) return;
     inorder(p->lchild);
     visit(p);  //对p节点的访问等
     inorder(p->rchild);
   }
后序（左右根）：
  void postorder(BTNode *p){
     if (p==NULL) return;
    postorder(p->lchild);
     postorder(p->rchild);
     visit(p);   //对p节点的访问等
  }

5.3可能考察的电

对平衡二叉树、二叉排序树的判断
哈夫曼树的遍历、计算和判断