《数据结构和算法分析—C语言描述》读书笔记

  第一章主要讲的是数学知识的复习，指数，级数什么的，最后，浅层次的谈了一下递归。

  当一个函数用它自己来定义时就称为是递归（recursive）的，C语言是允许递归的。但重要的是要记住，C提供的仅仅是遵循递归思想的一种企图。不是所有的数学递归函数都能有效地或者正确地由C的递归模拟来实现。

  举个递归的小例子：
  int x

  F(int X)

  {

      if(0 == X)

      return 0;

      else

      return 2*F(X-1)+X*X;

  }

  关于递归，有几个重要并且可能会被搞混的地方。一个常见的问题是：它是否就是循环逻辑？答案是：虽然我们定义一个函数用的是这个函数的本身，但是我们并没有用函数本身定义该函数的一个特定的实例。换句话话说，通过使用F（5）来得到F（5）的值才是循环的。通过使用F（4）得到F（5）的值不是循环的，除非F（4）的值又要用到对F(5)的计算。

  递归的前两个基本法则：

  1.基准情形：你必须总要有某些基准的情形，它们不用递归就能求解

  2.不断推进：对于那些需要递归求解的情形，递归调用必须总能朝着生产基准情形的方向推进。

  给大家讲一个简单易懂的例子：

  我们考虑一本大字典，词典中的词都是用其他的词定义的。当我们查一个单词时候，我们不理解对该词的解释，于是我们不得不再查一些解释中的词。而对这些词的解释中某些词我们有不理解，因此我们还要继续搜索。因为词典是有限的，所以实际上，要么我们最终查到一处，明白这个地方所有解释的意思，从而理解这里的解释，并按照查找到的路径回头理解其它多于的解释；要么我们发现这些解释形成一个循环，无法明白其中的意思，或者在解释中需要我们解释某个不在这本词典中的词。

  3.设计法则：假设所有的递归调用都能运行。这是一条重要的法则，我们之后会考虑递归的效率问题

  第二章讲的是一些算法的分析

  这一章开始讲的是各种语句索要消耗的时间和几种算法

  对分查找，也就是传说中的二分法吧

  欧几里得算法，定理：如果M>N,则M mod N

  高效率的取幂运算

  我把看到最深刻一个算法写一下，是讲最大子序列和问题的，就是比如6个数字，要计算最大加起来是那种情况，要是连续的，不能1.3.5，只能123 或者 45 这样。

  刚开始看到觉得这道题目蛮复杂的，但最后看到笔者的算法真是超级简单

 int MaxSubsequenceSum(const int A[],int N)

{

int ThisSum,MaxSum,J;

ThisSum = MaxSum = 0;

for(j = 0; j

{

ThisSum += A[j];

if(ThisSum > MaxSum)

MaxSum = ThisSum;

else if(ThisSum <0 )

ThisSum = 0;

}

return MaxSum;

}

我感觉写的不错，给函数变量命名都很好，不错不错！