计算机基础 - 数据结构与算法 - 《前端知识体系》

第1章数据结构绪论
第2章算法
第三章线性表

第1章数据结构绪论

1.1 基本概念和术语

1.1.1 数据

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入计算机处理的符号集合
两个前提：

可以输入到计算机
能被计算机程序处理

1.1.2 数据元素

数据元素：是组成数据的、有一定意义的基本单元，在计算机中通常作为整体，也被称为记录

1.1.3 数据项

数据项：一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单元

1.1.4 数据对象

数据对象：是性质相同的数据元素的集合，是数据的子集

1.1.5 数据结构

数据结构：是相互之间存在一种或者多种特定关系的数据元素的集合

1.2 逻辑结构与物理结构

根据视角的不同，我们把数据结构分为逻辑结构和物理结构

1.2.1 逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系

集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系

线性结构：线性结构中的数据元素之间是一对一的关系

树形结构：树形结构中的数据元素存在一种一对多的层次关系

图形结构：图形结构的数据元素是多对多的关系

我们在示意图中表达数据的逻辑结构时，要注意两点

每一个数据元素看作一个节点，要用圆圈表示
元素之间的逻辑结构用节点之间的连线表示，如果这个关系是有方向的，则用带箭头的联系表示

1.2.2 物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式，分为以下两种

顺序存储结构

链式存储机构：是把数据元素存放在数据连续的存储单元里，其数据间的逻辑关系和物理关系是一致的

链式存储结构

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

逻辑结构是面向问题的，物理结构是面向计算机的，其基本的目的就是将数据及其逻辑关系存储在计算机内存中

1.3 抽象数据类型

1.3.1 数据类型

数据类型：是指一组性质相同的值的集合及定义再次集合上的一些操作的名称。

1.3.2 抽象数据类型

抽象数据类型：是指一个数学模型及定义在该模型上的一组操作，抽象的意义在于数据类型的数学抽象特性，抽象数据类型体现了程序设计中问题分解、抽象、信息隐藏的特性

第一章总结：

第2章算法

2.1 算法定义

算法：算法是描述解决问题的方法，是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每个指令表示一个或多个操作

2.2 算法的特性

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

输入：算法具有0个或者多个输入。
输出：算法至少有一个或多个输出。
有穷性：算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
确定性：算法的每一个步骤都有确定的含义，不会出现二义性
可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

2.3 算法设计的要求

正确性：算法的正确性是指算法至少应该在具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案，算法的正确答大体分为以下四个层次
1. 算法没有语法错误
2. 算法对于合法的输入数据能够产生满足要求的输出结果
3. 算法对于非法的输入数据能够得出满足规格说明的结果
4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果
可读性：算法设计的另一目的是为了便于阅读、理解和交流
健壮性：当输入数据不合法时，算法也能做出相关的处理，而不是产生异常或莫名其妙的结果
时间效率高和存储量低

2.4 算法效率的度量方法

事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机对不同算法编制程序的运行时间进行比较，从而确定算法效率的高低（缺陷多，不采纳）
事前分析评估方法：在计算机程序编制前，依据统计方法对算法进行评估
1. 算法采用的策略、方法（算法好坏的根本）
2. 编译产生的代码质量（软件支持）
3. 问题的输入规模
4. 机器执行指令的速度（硬件性能）

2.5 函数的渐进增长

函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n > N，f(n)总是比g(n)大，那么，我们说f(n)的渐近增长快于g(n)。
算法中，最好此项指数大的，函数随着n的增长，也会增长的特别快。判断一个算法的效率时，函数的常量和其他次要项常常可以忽略，而应该关注主项的阶数。某个算法，随着n的增大，他会越来越优于另一算法，或者越来越差于另一算法，这其实时时事前估算方法的理论依据，通过算法时间复杂度来评估算法时间效率

2.6 算法时间复杂度

定义：在进行算法分析时，语句总的执行次数T(n)时关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作T(n)=O(f(n))。他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数

大O记法：O()来一线算法的复杂度的记法

推导大O阶：

用常数1 取代运行时间中所有加法常数
再修改后的运行次数函数中，只保留最高项
如果最高阶项存在且不是1，则去除与这个项相乘的常数

常数阶：O(1)，用常数1 取代运行时间中所有加法常数
对数阶：O(logn)
线性阶：O(n)，循环体执行n次运算
nlogn阶：O(nlogn)
平方阶：O(n²)，循环的时间复杂度等于循环体的复杂度乘以该循环运算的次数
立方阶：O(n³)
指数阶：O(2^n）

2.7 最坏情况与平均情况

最坏情况：最坏运行时间是一种保证，那就是运行时加不能再坏了
平均情况：最坏运行时间时所有情况中最有意义的，因为他是期望的运行时间

2.8 算法空间复杂度

算法空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中n为问题的规模，f(n)为语句关于n所占存储空间的函数

第二章总结

第三章线性表

3.1 线性表的定义

线性表：零个或多个数据元素的有限序列

有限：元素个数有限
序列：元素之间存在顺序，若元素存在多个，则第一个元素无前驱，最后一个元素无后驱，其他每个元素都只有一个前驱和后驱

线性表的元素个数n（n≥0）定义为线性表的长度，当n=0时，称为空表
在复杂的线性表中，一个数据元素可以由若干个数据项组成

3.2 数据表的抽象数据类型

ADT 线性表（List） Data 线性表的数据结对象集合为{a1,a2,……,an}，每个元素的数据类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素。除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系时一对一的关系 Operation InitList(L)：初始化操作，建立一个空的线性表L ListEmpty(L)：若线性表为空，返回true，否则返回false ClearList(L)：将线性表清空 GetElem(L,i,e)：将线性表L中第i个位置元素返回给e LocateElem(L,e)：将线性表L中查找与定值e相等的元素，如果查找成功，返回该元素再表中序号，表示成功，否则，返回0表示失败 ListInsert(L,i,e)：在线性表L中的第i个位置插入新元素e ListDelete(L,i,e)：删除线性表中第i个未知元素，并用e返回其值 ListLength(L)：返回线性表L的元素个数 endADT

3.3 线性表的顺序存储结构

3.3.1 顺序存储的定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的元素

3.3.2 顺序存储方式

描述顺序存储结构需要的三个属性：

存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置
线性表的最大存储容量：数组长度MaxSize
线性表当前长度：length

3.3.3 数据长度和线性表长度的区别

数组长度：是存放线性表的存储空间的长度，存储分配后这个量一般是不会变的
线性表长度：是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的

3.3.4 地址计算方法

数组元素的序号和存放他的数组下标之间存在的对应关系：

地址：存储器中的每个存储单元都有着自己的编号，这个编号称为地址

线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示存储位置的函数，c是一个数据元素占用的存储单元）

LOC(a[i+1])=LOC(a[i])+c

对于第i个数据元素a[i]的存储位置可以有a[1]推算得出：

LOC(a[i])=LOC(a[1])+(i-1)*c

3.4 顺序存储结构的插入与删除

3.4.1 获得元素操作

const maxSize = 10;
const a = [1, 2, 3, 4, 5, 6, 7, 8, undefined];
const getElem = (list, i) => {
  if (list.length === 0 || i < 1 || i > list.length) {
    console.log('i不在范围内')
    return ;
  }
  return list[i-1]
};
const item=getElem(a,3)
console.log('item',item)

3.4.2 插入操作

// 插入算法的思路
// 1. 如果线性表的长度≥数组长度，则抛出异常或者动态增加容量
// 2. 如果插入的位置不合理，抛出异常
// 3. 从最后一个元素开始向前遍历到第i个位置，分别将他们向后移动一个位置
// 4. 将要插入元素填入位置i处
// 5. 表长+1
const maxSize =10 
const a=[1,2,3,4,5,6,7,8,undefined]
const listInsert=(list,i,e)=>{
let  k;
if(list.length===maxSize){
    console.log('顺序线性表已满')
    return ;
}
if(i<1||i>list.length+1){
    console.log('i不在范围内')
    return ;
}
if(i<=list.length-1){
    for(k=list.length-1;k>=i-1;k--){
      list[`${k+1}`]=list[k]
    }
    list[i-1]=e
    }
  console.log('list',list)
  return 
}
listInsert(a,1,'a')

3.4.3 删除操作

const a = [1, 2, 3, 4, 5, 6, 7, 8, undefined];
const listDelete=(list, index) =>{
  if(index<1||index>list.length){
    console.log('删除位置不正确')
    return ;
  }
  if(index<list.length){
    for(let i=index; i<list.length; i++){
      list[i-1]=list[i]
    }
  }
}
listDelete(a,3)

3.4.4 线性表顺序存储结构的优缺点

优点：

无须为表示表中的元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素

缺点：

插入和删除操作需要移动大量的元素
当线性表长度变化比较大时，难以确定存储空间的容量
造成存储空间的“碎片”

3.5 线性表的链式存储结构

特点：使用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置
为了表示每个数据元素a[i]与直接后继元素a[i+1]之间的逻辑关系，对数据元素a[i]来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。
数据域：存储信息元素的域
指针域：存储直接后继位置的域
指针（链）：指针域中存储的信息
结点：数据域和指针域这两部分信息组成数据元素a[i]的存储映像
线性表的链式存储结构：n个结点链结成的一个链表，因为此链表中每个节点只包含一个指针域，所以叫做单链表。单链表正式通过每个结点的指针域将线性表的数据元素按其扩及次序链接在一起

头结点：单链表第一个结点前附设一个节点。头结点的数据域可以不存储任何信息
头指针：链表中第一个结点的存储位置叫做头指针

数据结构与算法

第1章 数据结构绪论