数据结构和算法绪论

定义

简单来说，数据结构就是
—-> 程序设计 = 数据结构 + 算法
—-> 元素相互之间存在的一种或多种特定关系的集合

分层

数据结构分为逻辑结构和物理结构

  • 逻辑结构
    • 集合结构：
      • 集合结构中的数据元素除了同属于一个集合外，他们之间没有其他不三不四的关系。
      • image.png
    • 线性结构：
      • 线性结构中的数据元素之间是一对一的关系。
      • image.png
    • 树形结构
      • 树形结构中的树形元素之间存在一种一对多的层次关系
      • image.png
    • 图形结构
      • 图形结构的数据元素是多对多的关系
      • image.png
  • 物理结构
    • 物理结构是相对的，物理结构实际上研究的就是如何吧数据元素存储到计算机的储存器中。储存器是针对于内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。
    • 数据元素的存储结构形式有两种
      • 顺序存储结构
        • 把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。C语言中的数组结构就是这样。包括但不限于C语言。
        • image.png
      • 链式存储
        • 把数据放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
        • 链式存储结构的数据元素存储关系并不能反映起逻辑关系，因此需要用一个指针存放数据元素的地址，通过地址就可以找到相关数据元素的位置。一个元素在一个存储单元中，除了存放自己的值，还存放了一个指针。这个指针指向的就是下一个单元的地址。
        • image.png

算法

  • 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。—-摘抄自小甲鱼《数据结构和算法》
  • 换句话说，就是一个泡妞的技巧和方式。

  • 对于给定的问题，是可以用多种方式求解的。

    算法的五个基本特征

  • 输入

    • 定义：
      • 算法具有零个或多个输入 ```c // 无输入 void test(){ printf(“hello,world”); } // 一个输入 void test(int num){ printf(“%d\n”,num); } // 多个输入 void test(int name,int age){ printf(“%d\n%d\n”,num,age); }
  2. - 输出
  3.    - 定义
  4.       - 算法至少有一个或者多个输出
  5. - 有穷性 
  6.    - 定义
  7.       - 指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。一个永远都不会结束的算法有何用？
  8. - 确定性
  9.    - 定义
  10.       - 算法的每一个步骤都具有确定的含义，不会出现二义性
  11.       - 算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果
  12.       - 算法的每一个步骤都应该被精确定义而无歧义
  13. - 可行性
  14.    - 定义
  15.       - 算法的每一步都是可行的，也就是说每一步都能够通过执行有限次数完成
  16. <a name="Wt6sL"></a>
  17. ## 算法设计的要求
  19. - 正确性
  20.    - 定义：
  21.       - 算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。
  22.       - 四个层次
  23.          - 算法程序没有语法错误
  24.          - 算法程序对于合法输入能够产生满足要求的输出
  25.          - 算法程序对于非法输入能够产生满足规格的说明
  26.          - 算法程序对于故意刁难的测试输入满足要求的输出结果
  27. - 可读性
  28.    - 算法设计另一目的是为了便于阅读、理解和交流
  29.    - 一方面是为了让计算机执行，一方面为了便于他人阅读和自己日后阅读修改
  30. - 健壮性
  31.    - 当输入数据不合法时，算法也能做相关处理，而不是产生异常、崩溃或者莫名其妙的结果
  32. - 时间效率高和储存量低
  33. <a name="wb1Xs"></a>
  34. ## 算法初体验
  35. <a name="Aet78"></a>
  36. ### 计算1～n的累加和
  38. - 这个例子在编程中很常见到，在学习C语言for循环中的第一个例子就是利用for循环计算出1～100的累加和。如果是按照for循环的做法是这样的：
  39. ```c
  40. // 先定义函数
  41. int getSum(int start,int end){
  42.     int sum = 0;
  43.     for (int i = start; i <= end; i++) {
  44.         sum += i;
  45.     }
  46.     return sum;
  47. }
  48. int main(int argc, const char * argv[]) {
  49.     int sum = getSum(1,100);  // 调用
  50.     printf("%d\n",sum);
  51.     return 0;
  52. }
  53. // 输出5050

  • 分析一下这段代码，计算一个区间之内的累加和，在for循环中将会执行100次。也就是说 i 要后自增100次。如果换一个方式，我们可以吧将首尾数字相加，比如说1+100，2+99，3+98 ……，这样的话正好有总数的一半的对数和。所以可以有这样的代码：

    int getSum(int start,int end){
  int sum = 0;
  sum = (start + end) * end / 2;  // 仅仅只执行了一次
  return sum;
}
int main(int argc, const char * argv[]) {
  int sum = getSum(1,100);
  printf("%d\n",sum);
  return 0;
};
// 输出5050

  • 上面的代码对比刚才的那一段代码，仅仅只是执行了一次，就计算出了1～100的结果。如果是计算1～100或者1000或者10000，for循环还可以接受，如果是几千万，几个亿呢？这就是算法的独到之处。

    时间复杂度和空间复杂度

    算法效率的度量方法

  • 事后统计方法

    • 定义：
      • 主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低

  • 事前分析估算方法

    • 定义：
      • 在计算机程序编写前，依据统计方法对算法进行估算
        • 算法采用的策略、方案
        • 编译产生的代码质量
        • 问题的输入规模
        • 机器执行指令的速度

          算法举例

  • 函数的渐进增长

    • 1、判断下列两个算法A和B哪个更好？
      • 假设两个算法的输入规模都是n(也就是说A输入100次，B也输入100次)，算法A要做2n + 3次操作，可以这么理解：先执行n次的循环，执行完成后再有一个n次的循环，最后有三次运算。算法B要做3n+1次操作，理解同上。哪个更快？
        • 回答：
          • 图表解答示例
          • image.png
          • image.png
          • 当n=1的时候，算法A的效率不如B。当n=2的时候，算法A和算法B的效率是相等的。当n = 3的时候，算法A的效率高出了B。往后持续，可以看到A算法的效率很高。所以算法A的总体效率要比算法B要高。注意不是看值，而是比如说当n = 3时，算法A用了9次就完成了任务，而算法B用了10次才完成。而且在折线统计图中可以看到，后面的常数其实基本可以忽略掉。
      • 2、给定两个算法，C是4n + 8 D是2n^2 + 1
        • 图表解答示例
          • image.png
          • image.png
          • 可以发现，去掉和n相乘的常数，结果还是没有变，算法C2的次数随着n的增长，还是远小于算法D2
    • 结论：
      • 给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐进快于g(n)