得鹿梦鱼 得鹿梦鱼
知识库 前端技能树 面试题 学习资料 关于本人

引言

数据结构的概念

数据结构主要研究数据（特别是非数值型数据）的组织、存储及运算方法

数据：是描述客观事物的数值、字符以及能输入计算机且能被处理的各种符号集合。
数据元素：是组成数据的基本单位。是数据集合的个体。
数据项是数据数据不可分割的最小单位。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
数据结构：是指相互之间存在一种或者多种特定关系的数据元素集合。
数据类型：是一组性质相同的值的集合，以及定义在这个值集合上的一组操作的总称。
抽象是对一种事物或一个系统的简化描述，它关注事物或系统的本质方面，而忽略非本质

抽象数据类型

抽象数据类型abstract data type ADT是指一个数学模型以及定义在该模型上的一组操作。

定义格式

ADT <ADT名称>
{
数据对象：<数据对象的定义>;
结构关系：<结构关系的定义>;
基本操作：<基本操作的定义>;
}ADT<ADT名称>

基本操作的定义格式

基本操作:参数表
操作前提：<操作前提描述>;
操作结果：<操作结果描述>;

例如：

ADT <Linear_list>
{
数据对象：所有a,属于同一个数据对象，i = 1,2,....n;
结构关系：所有数据元素a存在次序关系
基本操作：设L为linear_list:
InitialL：初始化空线性表
LengthL: 求线性表的表长
GetL,i：求取线性表的第i个元素
InsertL,i,b：在线性表的第i个位置插入元素b
DeleteL,i: 删除线性表的第i个元素
}ADT <Linear_list>

实现

抽象数据类型的实现需要借助于高级语言，并且其具体实现也依赖于所选择的高级语言的功能。

  1. 传统的面向过程的程序设计
  2. “包”“模型”的设计方法
  3. 面向对象的程序设计

数据结构的内容

数据的逻辑结构

数据的逻辑结构是指数据元素之间逻辑关系的描述。Data_Structure = D,R,其中D是数据元素的有限集，R是D上关系的有限集

集合结构：结构中的数据元素之间除了同属于一个结构的关系外，没有任何的其他关系
线性结构：结构中的数据元素之间存在着一对一的线性关系
树型结构：结构中的数据元素之间存在着一对多的层次关系
网状结构：结构中的数据元素之间存在着多对多的任意关系，如图

数据的存储结构

数据的逻辑结构是从逻辑上来描述数据元素之间的关系，是独立于计算机的。然而讨论数据结构的目的是在计算机中实现对它的操作，因此还需要研究数据元素和数据元素之间的关系如何在计算机中表示，这就是数据的存储结构

存储结构是逻辑关系的映像与元素本身的映像，是数据结构的实现；逻辑结构是数据结构的抽象

计算机的存储器由很多存储单元组成，每个存储单元有唯一的地址。数据元素在计算机中用若干个二进制“位串”表示。

数据元素之间的关系在计算机中有两种表示方法：顺序映像和非顺序映像，由此可得到两种不同的存储结构：顺序存储和链式存储。
顺序存储的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；
链式存储的特点是借助指针表示数据元素之间的逻辑

数据的运算

数据结构就是研究一类数据的表示及其相关的运算操作，包括插入、删除、更新、查找等操作

算法

算法就是解决特定问题而定义的的一系列操作步骤的集合（规则的有限集合）。

特性

  • 有穷性
  • 确定性
  • 可行性
  • 有输入
  • 有输出

评价标准

  1. 正确性：指算法能满足具体问题的要求，即对任何合法的输入，算法都会得出正确的结果
  2. 可读性：指算法被理解的难易程度。算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该更易于人的理解。另一方面，晦涩难读的程序易于隐藏较多错误而难以调试
  3. 健壮性（鲁棒性）：即对非法输入的抵抗能力
  4. 高效率与低存储量需求： 效率指的是算法执行时间，存储量指的是算法执行过程中所需的最大存储空间，两者均与问题的规模有关

描述

描述算法的工具可以是自然语言、框图或高级程序设计语言。用高级程序设计语言描述算法有严格、准确的特点，但缺点是语言细节过多，所以一般采用类语言描述

性能分析

一个算法的复杂性高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，则该算法的复杂性越高；反之，所需的资源越少，则该算法的复杂性越低。最重要的计算机资源是时间和空间资源。因此，算法的复杂性有时间复杂性和空间复杂性之分。

通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。事后统计法必须在计算机上实地运行程序，容易有其他因素掩盖算法本质；事前分析估算法则可以预先比较各种算法，以便均衡利弊而从中选出较优者。

时间复杂性

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数fnfn,算法的时间度量记作Tn=OfnTn=Ofn, 它表示随问题规模n的增大，算法执行时间的增长率和fnfn的增长率相同。称为算法的时间复杂度

OO的数学含义是，若存在两个常量C和n0n_0,当n>n0n > n_0时，
∣Tn∣≤C∣fn∣Tn \leq Cfn, 则记作Tn=OfnTn = Ofn
它表明算法的执行执行T是和fnfn"同数据量级"的，

原操作”**指的是固有数据类型的操作，显然每个原操作的执行时间和算法无关，相对于问题的规模是常
任何一个算法都是由一个控制结构和若干原操作组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和∑原操作i的执行次数∗原操作i的执行时间\sum原操作i的执行次数 * 原操作i的执行时间

let c = [];let a = [[1,2,3],[2,3,4], [3,4,5]]let b = [[4,5,6], [5,6,7], [7,8,9]]let n = 3;forlet i = 0; i < n; i++{                                // 执行n+1次    forlet j = 0; j < n; j++{                            // 执行nn+1次        c[i][j] = 0;                                       // 执行n*n次        forlet k = 0; k < n ; k++{                       // 执行n*n*n+1次            c[i][j] = c[i][j] + a[i][k] * b[k][j]          // 执行 n*n*n次        }    }}

上述代码总执行次数为Tn=2n3+3n2+3n+1Tn=2n^3+3n^2+3n+1, 该算法的时间复杂度为On3On^3

例【1-3】
程序，实现用一元人民币换成一分、两分、五分的硬币
分析：假设一分、两分、五分的硬币各为为x,y,zx, y,z则有
{x+y+z=501◯x+2y+5z=1002◯1-1\begin{cases}x + y +z = 50 \quad \textcircled 1\\x + 2y + 5z = 100 \quad\textcircled 2\end{cases}\quad\text{1-1}

代码实现三重循换

function main{    forlet x = 0; x <= 50; x++{        forlet y = 0 ; y <= 50; y++{            forlet z = 0; z <=50 ; z++{                ifx + y + z === 50 && x + 2*y + 5*z === 100{                    console.log`一分${x}个 二分${y}个 五分${z}个`                }            }        }    }}

代码实现二重循换

function main{    forlet z = 0; z <= 50; z++{        forlet y = 0 ; y <= 50; y++{            x = 50 - y - z;            ifx + 2*y + 5*z === 100{                console.log`一分${x}个 二分${y}个 五分${z}个`            }        }    }}

代码实现改进的二重循换

function main{    forlet z = 0; z <= 20; z++{        forlet y = 0 ; y <= 50; y++{            x = 50 - y - z;            ifx + 2*y + 5*z === 100{                console.log`一分${x}个 二分${y}个 五分${z}个`            }        }    }}

代码实现一重循换
由式1-1中的2◯−1◯\textcircled{2}-\textcircled{1}消除未知数xx得到y+4z=50y + 4z = 50, 由与y和z为整数，由此可知z最大为12y和z为整数，由此可知z最大为12

function main{    forlet z = 0 ; z < 13 ; z++{        let y = 50 - 4 * z;        let x = 50 - y - z;        console.log`一分${x}个 二分${y}个 五分${z}个`    }}

三重循环：循环次数51 51 51 = 132651 时间复杂度为On3On^3
二重循环：循环次数51 51 = 2601 时间复杂度为On2On^2
改进二重循环：循环次数21 51 = 1071 时间复杂度为On2On^2
单重循环：循环次数12 时间复杂度为O1O1

空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间，记作Sn=OfnSn = Ofn

算法执行期间所需要的存储空间包括三部分

  1. 算法程序所占用的空间
  2. 输入的初始数据所占的存储空间
  3. 算法执行过程中所需要的额外空间

事前分析估算法的相关因素

  • 算法采用的策略
  • 算法解决问题的规模
  • 编程采用的语言
  • 编译程序产生的机器代码的质量
  • 执行算法的计算机速度

结构化程序设计

是为了使程序具有合理的结构，以保证程序正确性而规定的一套程序设计的方法，是人们多年来研究和实践的结晶

目的： 通过设计结构良好的程序，以程序的静态良好程序结构保证程序动态执行的正确性，使程序易理解、易调试、易维护,以提高软件开发的效率，减少出错率

基本结构： 顺序、选择、重复， 共同特点（单入单出）

设计方法

  1. 自顶向下，逐步求精的设计思想
  2. 具有独立功能、单入单出的模块化结构
  3. 仅用三种基本控制结构的设计原则

引言
≡