小甲鱼数据结构&算法教程学习笔记01

小甲鱼数据结构&算法教程学习笔记01

一、绪论

1. 程序设计=数据结构+算法

2. 数据结构：数据元素之间的一种或多种特定关系的集合

   1. 逻辑结构

      数据对象中数据元素间的相互关系

      • 集合结构
      • 线性结构
      • 树形结构
      • 图形结构

   2. 物理结构

      数据的逻辑结构在计算机中的存储形式

      存储器主要针对内存而言，硬盘/软盘/光盘等数据组织多是文件形式。

      数据元素存储结构

      • 顺序存储

        数据元素存放在地址连续的存储单元里，其数据间的逻辑关系与物理关系一致

      • 链式存储

        数据元素存储在任意的存储单元里，可以连续或不连续，其数据逻辑关系与物理存储关系并非一致，因此需要指针链接。

二、浅谈算法

1. 数据结构–>算法，好基友一辈子。

   等差数列求和的时候，公式计算算法VS逐步算法

2. 算法：解决特定问题求解步骤的描述；计算机中指令的有限序列；指令表示一个或多个操作。

3. 算法的5个特征

   • 输入：算法可有0个或多个输入。
   • 输出：至少有1个或多个输出。
   • 有穷性：执行有限步骤后，自动结束而不会无限循环。
   • 确定性：
     • 每个步骤都有确定含义，不会有歧义。
     • 一定条件下，只有一条执行路径，相同输入只能由唯一输出结果。
     • 每个步骤都应该被精确定义而无歧义
   • 可行性：
     • 每一步都必须是可行的，即每一步都能通过执行有限次而完成。

4. 算法设计要求

   同一问题的算法不唯一

   1. 正确性
      • 输入、输出、加工处理无歧义，正确反映问题需求和得到正确答案。
      • 设计层次
        1. 算法程序无预发错误。
        2. 对于合法输入产生满足需求的输出。
        3. 对非法输入产生满足规格的说明。
        4. 对于刁难测试有满足要求的输出结果。
   2. 可读性，便于阅读、理解、沟通
   3. 健壮性，Hold住异常
   4. 时间效率高、存储量低