Skip to content

Latest commit

 

History

History
1200 lines (379 loc) · 27.4 KB

数据结构与算法.md

File metadata and controls

1200 lines (379 loc) · 27.4 KB
Raw

数据结构与算法

解决问题方法的效率，跟数据的组织方式有关。

循环和递归

解决问题方法的效率，跟空间的利用效率有关。

image-20210818161452286

image-20210818162018882

解决问题方法的效率，跟算法的巧妙程度有关

数据结构

数据对象在计算机中的组织方式

  • 逻辑结构：线性结构和树结构、图结构
  • 物理存储结构：数组、链表

数据对象必定与一系列加在其上的操作相关联

完成这些操作所用的方法就是算法

抽象数据类型(Abstract Data Type)
  • 数据类型
    • 数据对象集
    • 数据集合相关联的操作集
  • 抽象：描述数据类型的方法不依赖于具体实现
    • 与存放数据的机器无关
    • 与数据存储的物理结构无关
    • 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集是什么，并不涉及如何做到的问题

抽象

image-20210818163548512

算法
  • 一个有限指令集
  • 接收一些输入（有些情况下不需要输入）
  • 产生输出
  • 一定在有限步骤之后终止
  • 每一条指令必须
    • 有充分明确的目标，不可以有歧义
    • 计算机能处理的范围之内
    • 描述应不依赖与任何一种计算机语言以及具体的实现手段

image-20210818164049310

什么是好算法
  • 空间复杂度sn

根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

  • 时间复杂度Tn

根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

递归的时候会占用内存，因为递归下一层的时候要暂存上一层的结果

Sn = C*N

image-20210818164648695

加减比乘除算的快

image-20210818164842726

在分析一般算法的效率时，我们经常关注下面两种复杂度

  • 最坏情况复杂度T worst(n)
  • 平均复杂度T avg(n)

基本上就是第一种：最坏情况复杂度

image-20210818165255964

image-20210818165445992

image-20210818165457903

image-20210818165643710

image-20210818165759487

image-20210818191956566

image-20210818193405280

image-20210818193945679

image-20210818194726647

什么是线性表
多项式表示问题的启示
  1. 同一个问题可以有不同的表示（存储）方法
  2. 有一类共性问题：有序线性序列的组织和管理
线性表

由同类型数据元素构成有序序列的线性结构

  • 表中元素个数成为线性表的长度
  • 线性表没有元素时，称为空表
  • 表起始位置称表头，表结束位置称表尾

image-20210818195144256

链式存储实现

image-20210818200032485

广义表
  • 广义表是线性表的推广
  • 对于线性表而言，n个元素都是基本的单元素
  • 广义表中，这些元素不仅可以是单元素也可以是另一个广义表

image-20210818201230986

多重链表

多重链表：链表中的节点可能同时隶属于多个链

  • 多重链表中结点的指针域会有多个，如前面例子包含了netx和sublist两个指针域
  • 但包含两个指针域的链表并不一定是多重链表，比如在双向链表不是多重链表

多重链表有广泛的用途：

基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储

堆栈

image-20210818203628155

堆栈stack ：具有一定操作约束的线性表

  • 只有一端（栈顶，top）做插入、删除
  • 插入数据：push入栈
  • 删除数据：pop出栈
  • 后入先出：LIFO

image-20210818203949646

image-20210818204030156

中缀表达式转成后缀表达式

image-20210818210009984

堆栈的其他应用：

  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法

队列及实现

队列：queue具有一定操作约束的线性表

  • 插入和删除操作：只能在一端插入，而在另一端删除
  • 数据插入 入队列 AddQ
  • 数据删除 出队列DeleteQ
  • 先来先服务
  • 先进先出 FIFO

image-20210819200815843

image-20210819200925663

image-20210819201437552

image-20210819201758339

image-20210819202139270

image-20210819202326934

image-20210819203439780

image-20210819203707397

什么是树

分层次组织在管理上具有更高的效率

数据管理的基本操作之一：查找

如何实现有效率的查找

searching

image-20210819205601090

image-20210819205951769

二分查找

image-20210819210521234

image-20210819211054628

image-20210819212247115

image-20210819212402458

image-20210819212620945

image-20210819212737409

image-20210819213128752

image-20210819213227642

image-20210819213322280

image-20210819213454497

image-20210819214643681

image-20210819214812719

image-20210819215245013

image-20210819215345900

image-20210819215519052

image-20210819220012636

DBEFAGHCI

image-20210819220312388

DEFBHGICA

image-20210819220547376

路线是一样的， 第一次碰到就输出的叫做先序、第二次的叫做中序、第三次的叫做后序

image-20210819220744178

image-20210822092825462

image-20210822093926951

​ image-20210822094347290

image-20210822094920689

image-20210822095028474

image-20210822095125615

image-20210822095254235

image-20210822095400071image-20210822095400133

image-20210822095600852

image-20210822095753944

image-20210822095955430

image-20210822100108869

image-20210822100248441

判断同构

image-20210822100435562

image-20210822100843208

image-20210822101301912

判断有没有哪个节点没有被指向 哪个节点就是根

例如231被指向了,那么意思就是0这个节点是根节点

image-20210822101644943

image-20210822101656356

image-20210822102023363

使用check来判断根节点

image-20210822102155154

image-20210822102200845

image-20210822102407846

image-20210822102550689

image-20210822102618697

image-20210822102638201

image-20210822102736696

尾递归可以用循环实现

image-20210822102824536

查找的效率决定于树的高度

image-20210822102911459

image-20210822102930132

image-20210822103127572

image-20210822103450196

​ image-20210822103701343

image-20210822103721215

image-20210822103850804

image-20210822104154455

image-20210822104407357

image-20210822104658392

image-20210822105311867

image-20210822105726331

所以走台阶问题我大概懂了

只能一次走一阶台阶或者一次走两阶台阶

一阶台阶有1种走法

二阶台阶有2种走法

那么三阶台阶无非就是1阶台阶的走法+走2阶的走法(2)

或者2阶台阶的走法+走1阶的走法(1)

那么四阶台阶无非就是2阶台阶的走法+走2阶的走法(2)

或者3阶台阶的走法+走1阶的走法(1)

所以也就是斐波那契数列的性质

F(n)=F(n-1)+1+F(n-2)+2

image-20210822110716637

image-20210822111522588

image-20210822112334232

image-20210822112657646

必须保证是查找树 也就是左边小右边大

image-20210822113538123

image-20210822113732802

image-20210822113938703

image-20210822114002650

image-20210822114101318

image-20210822114324854

image-20210822114521287

image-20210822114826316

image-20210822115039320

image-20210822151804901

image-20210822151947780

image-20210822152334294

image-20210822152933725

image-20210822153108950

image-20210822153304689

image-20210822153425949

image-20210822153713250

image-20210822153929001

实现堆用完全二叉树

根节点是最大的完全二叉树

image-20210822154053219

image-20210822154254474

image-20210822154337334

image-20210822154516519

image-20210822154705009

image-20210822154842548

i/2就是完全二叉树的父节点

image-20210822155046618

image-20210822155243748

因为是完全二叉树,所以要用最后一个元素替补删除掉的那个元素,才能满足完全二叉树的性质

image-20210822155357876

时间复杂性就是树的高度 log2n

image-20210822160108019

image-20210822160408516

image-20210822160720461

从倒数第二层开始建立堆,建完之后逐层往上建立,

image-20210822160834924

image-20210822160855127

image-20210822161110159

image-20210822161247647

image-20210822161303788

如何根据节点不同的查找效率构造更有效的搜索树

image-20210822161422536

image-20210822161529534

image-20210822161639103

image-20210822161818080

image-20210822161934722

由于度为1的节点就是只有一个儿子的节点

没有度为1的节点

那么就是n2+n1+n0=n0-1+0+n0=2n0-1

image-20210824222513996

image-20210824222657220

第二种的意思是, 我用2的三次方也就是8种不同的符号来表示7个字符绰绰有余

image-20210824222809811

image-20210824222844586

当所以的值都在叶节点上的时候就不可能出现一个字符的编码是另一个字符的前缀

image-20210824223228402

image-20210824223351755

image-20210824223520102

image-20210824223656627

用数组实现

image-20210824223823443

image-20210824224033563

image-20210824224257684

image-20210824224312615

这样做会导致一边倒,会让高度增加 find操作很难效率查

可以尝试把集合小的挂到集合大的下面

image-20210824224547703

image-20210824225642477

image-20210824230108245

image-20210824230311976

直接简化成把值为3对应为下标为3的数组中的,数组里存的值是他的父节点

image-20210824230758030

image-20210824231016070

image-20210824231230324

image-20210824231506693

image-20210824231623358

image-20210824232012169

image-20210824232158793

image-20210824232344637

image-20210824232443313

image-20210824232956745

image-20210824233747366

image-20210824233929998

image-20210827150052047

image-20210827150132906

image-20210827150336396

无向图 对称 那么会不会空间浪费呢

image-20210827151040590

image-20210827161401937

image-20210827161523060

image-20210827161721941

image-20210827161814110

image-20210827162026003

访问完所有的之后一定是原路返回

image-20210827162605593

利用堆栈

image-20210827163115572

明白为啥是深度优先了

image-20210827163414973

会走的比较深

一圈一圈的搜索

image-20210827163440795

image-20210827163728923

image-20210827163907704

image-20210827164150229

image-20210827164252208

image-20210827164800507

image-20210827165034266

image-20210827165238415

六度空间

image-20210827165619918

image-20210827165905518

image-20210901201200926

image-20210901201946320

image-20210901202237726

image-20210901202455949

image-20210901202622869

image-20210901202955801

![image-20210901203454720](数据结构与算法.assets/image-20210901203454720.png)

image-20210901203704206

image-20210901204828636

即根据先序遍历和中序遍历得到后序遍历

image-20210901205043619

image-20210901205101295

image-20210901205633120

image-20210901210114855

image-20210901210901643

image-20210901211233423

image-20210901212050929

image-20210901213024875

image-20210901213318714

image-20210901213830771

image-20210901214248906

image-20210901214943497

image-20210901215356706

image-20210901215508437

image-20210916200459764

image-20210916201013775

image-20210916201156749

image-20210916201648114

image-20210916201722454

image-20210916202319076

image-20210916202644505

image-20210916202953711

image-20210916203505922

image-20210916203805137

image-20210916204118520

image-20210916204625137

image-20210916204737766

image-20210916205117277

image-20210916205411212

image-20210916205506700

image-20210916205817371

image-20210917210409882

image-20210917210520371

image-20210917210637360

image-20210917211045499

image-20210917211223048

image-20210917211229224

image-20210917211536128

image-20210917211830438

image-20210917211946976

image-20210917212207839

image-20210917212505662

image-20210917212706862

image-20210917212839699

image-20210917213446655

image-20210917213740614

image-20210917213907565

image-20210917214142032

image-20210917214318206

image-20210917214748170

image-20210917215109213

image-20210917215516864

image-20210917215959866

image-20210917220307185

image-20210917220439313