数据结构入门级

第一章绪论

什么是数据结构？什么是数据类型？

程序=数据结构+算法

一、基本概念：

1. 数据：指所有能被计算机处理的，无论图、文字、符号等。
2. 数据元素：数据的基本单位，通常作为整体考虑；由若干个数据项组成（数据项是数据最小的单位）。
3. 数据对象：是性质相同的数据元素的集合，数据的一个子集。（int类型、char类型...）

二、数据结构（三要素）：

1. 逻辑结构：指数据之间逻辑关系得整体，对数据之间关系的描述，与数据存储结构无关，与数据元素本身的内容和形式无关。
   • 集合：结构中数据元素除了“同属于一个集合”外，无其他关系；
   • 线性结构：元素都是一对一的关系；
   • 树形结构：元素存在一对多的关系；
   • 网状或图状结构：元素存在多对多的关系。

• 存储结构（物理结构）：描述数据具体在内存中的存储，可以理解为计算机的硬件设备，看得见摸得着；
  • 顺序存储：把逻辑上相邻的结点存储在物理位置上相邻的存储单位中，一般借助计算机程序设计语言（C/C++中的数组）来描述的；
  • 链式存储：不要求在逻辑位置相邻的结点在物理位置也相邻，结点之间的逻辑关系是用附加的指针（指向内存地址的工具）字段表示的（C/C++中的指针类型）。
  • 索引存储：建立附加索引表来标识结点地址；
    • 索引项形式<关键字,地址>，关键字：标识唯一一个结点；地址：指向结点的指针。
  • 散列存储：根据结点的关键字通过散列函数直接计算出该结点的存储地址，顺序存储的扩展。
• 数据运算：增删改查，建立和消除。 （数组没有插入和删除）
• PS：对于两种不同的数据结构来说，它们的物理结构和物理结构完全由可能相同，数据的运算不相同即可。

  三、算法与算法的评价

  1. 概念：算法是由基本运算及规定的运算顺序所构成的完成的解题步骤，是按照要求设计好的有限的确切的序列，简单来说就是问题求解步骤的描述。
  2. 算法的五个特性：
     • 有穷性：算法在执行有限的步骤（在可接受的时间内完成）之后，自动结束，不会出现无限循环；
     • 确定性：算法每一步具有确定的含义，不会出现二义性；
     • 可行性：算法中描述的操作都是通过已实现的基本运算执行有限次来实现。
     • 输入：一个算法有零个或多个输入；
     • 输出：一个或多个输出。
  3. 好算法的标准：
     • 正确性：应满足具体问题的需求；
     • 可读性：应容易阅读和交流，有助于理解和修改算法；
     • 健壮性：具有容错处理；
     • 通用性：具有一般性，对一般的数据集合都成立。
  4. 算法的设计要求：
     • 事后统计法：比较不同算法对同组输入数据的运行处理时间；
       • 缺陷：为获得不同算法的运行时间必须编写相应代码，实施困难且缺陷多；
       • 优点：非常直观。
     • 事前分析估算：一句统计方法对算法效率进行估算；
       • 影响效率因素：①算法采用的策略和方法；②问题的输入规模；③编译器所产生的代码；④计算机的执行速度。
  5. 算法效率的度量：
     • 时间复杂度（渐进时间复杂度）：通过算法中最基本语句执行次数得数量级来确定，常用最深层循环内的语句中的原操作的执行频度（重复的次数）来表示，指问题规模。
       • 例如：for(i = 0; i < 100; i++); 循环了100次；
       • 表示时间复杂度的阶：O(1)常见时间阶；O(n)线性时间阶；O(logn)对数时间阶；O(nlogn)线性对数时间阶；
       • 定理：A(n)=aₘnᵐ+aₘ₋₁nᵐ⁺¹+....+a₁n+a₀是一个m次多项式，则A(n)=O(nᵐ)；也就是只取最高次的；
       • 最坏复杂度、平均复杂度、最好时间复杂度；
       • 加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))，也就是取最大的，并列关系；
       • 乘法规则：T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O((f(n)*g(n)))，两相乘，嵌套关系；
       • 常见：O(1)<O(log₂n)<O(nlog₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)；
     • 空间复杂度：通过计算算法所需的存储空间实现；
       • 存储空间一般有：①指令常数变量所占的存储空间；②输入数据所占的存储空间；③辅助空间。
       • 一维数组a[n]：空间复杂度O(n);
       • 二维数组a[n][m]:空间复杂度O(n*m);
     • 算法的原地工作是指所需的辅助空间，是常量O(1)。
  6. 例题1：执行以下算法的时间复杂度为：O(log₂n)
     • void fun(int n){
     • int i = 1;
     • while(i <= n)
     • i = i * 2; 假设它执行m次，那么每次就是2ᵐ；2ᵐ<=n；即m<=log₂n
     • }
  7. 递归：程序调用自身的编程技巧称为递归，它在计算机中是借助栈来实现的，可以通过简单的函数调用来完成。
     • 如计算机阶乘的定义（5! = 5 * 4! ）；
     • 斐波那契数列：0，1，1，2，3，5，8...它后一个数是前两个数的和；
     • 递归思想：一个数是前两个数的和；
     • 递归表达式：f(n)=n n<=1；=f(n-1)+f(n-2) n>1;
  PS：算法和结构是不同的概念。