1.绪论

数据三要素

逻辑结构

image-20251013220513002

  • 几何
  • 线性结构
  • 树形结构
  • 图/网状结构

存储结构

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

运算

算法的五个特性

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

2.线性表

2.1线性表的定义和基本操作

image-20251014204301673

2.2线性表的顺序表示

image-20251014204448258

  • 初始化
  • 插入
  • 删除
  • 按值查找

算法题：双指针满足条件移动！！

2.3线性表的链式表示

  • 单链表

    • 初始化
    • 求表长
    • 按序号找节点
    • 按值找节点
    • 插入节点
    • 删除节点
    • 头插法（倒序）
    • 尾插法

  • 双链表

    • 插入
    • 删除

  • 循环单链表

  • 循环双链表

  • 静态链表

注意头，尾节点，哨兵节点

快慢指针！！

使用头插法可实现原地倒序

快慢指针

哈希计数

3.栈，队列，数组

3.1栈

image-20251021100208663

3.2队列

3.3栈与队列的应用

3.4数组与特殊矩阵

4.串

4.1串的定义

4.2串的模式匹配

5.树与二叉树

5.1树的基本概念

image-20251017220730372

5.2二叉树的概念

二叉树与度为2的有序树的区别

image-20251020112832827

特殊的二叉树

image-20251020131508964

image-20251020131540533

二叉树的性质

image-20251020131630896

image-20251020132451956

image-20251020133105829

5.3二叉树的遍历和线索二叉树

5.4树，森林

image-20251021145037162

5.5树与二叉树的应用

6.图

6.1图的基本概念

image-20251022193804232

image-20251022193527330

image-20251022193603106

image-20251022193635781

image-20251022193707770

6.2图的存储及基本操作

邻接矩阵

image-20251022202940745

邻接表法

image-20251022203011825

十字链法

image-20251022203133077

临接多重表

image-20251022203254637

image-20251022203324517

总结

image-20251022203339285

6.3图的遍历

image-20251022222800561

image-20251022222823146

image-20251022222842436

6.4图的应用

最小生成树

image-20251023084557053

image-20251023084633266

Prim算法（基于点）

image-20251023085322534

image-20251023085353842

Kruskal算法（基于边）

image-20251023085829849

image-20251023085900551

最短路径

image-20251023090058240

Dijkstra算法（基于点）

image-20251023090132415

image-20251023090248736

image-20251023090725114

image-20251023090541818

Floyd算法

image-20251023090827765

image-20251023090944647

总结

image-20251023091339718

拓朴排序

image-20251023093223253

image-20251023093259523

image-20251023093454637

image-20251023093537818

关键路径

image-20251023095002848

image-20251023100244136

image-20251023100300581

总结

image-20251023100324888

7.查找

7.2顺序查找和折半查找

7.3树形查找

7.4B树与B+树

7.5散列表

8.排序

8.1排序的基本概念

8.2插入排序

直接插入排序

注意是从后往前比较，找到待插入位置

image-20251030110648682

image-20251030110628517

image-20251030110732771

折半插入排序

image-20251030111906894

希尔排序

image-20251030111959168

image-20251030112519242

image-20251030112541071

8.3交换排序

冒泡排序

image-20251030145501972

image-20251030145529324

image-20251030145613476

快速排序

image-20251030145709696

image-20251030145827785

image-20251030145932614

image-20251030145952808

image-20251030150018758

image-20251030150122353

8.4选择排序

简单选择排序

image-20251030150404915

堆排序

image-20251030153143855

image-20251030153212839

初始建堆

image-20251030153228640

堆的删除及调整

image-20251030153343752

image-20251030153410608

算法

image-20251030153536148

image-20251030153618690

堆的插入

image-20251030154311784

分析

image-20251030154343192

8.5归并排序，基数排序和计数排序

归并排序

image-20251030155009101

image-20251030155023118

image-20251030155106430

基数排序

image-20251030155344181

image-20251030155404779

image-20251030155418085

image-20251030155510309

image-20251030155551662

计数排序

image-20251030155615671

image-20251030155645527

image-20251030160439121

8.6内部排序的比较与应用

总结

image-20251030160536410

image-20251030160548387

image-20251030160558862

image-20251030160613300

image-20251030160653167

image-20251030160726114

image-20251030160752947

选择排序和插入排序的区别

选择排序是以某一规则在无序的元素中找到一个符合的元素排入到有序的队列中

插入排序，是直接在无序的元素中选择一个，在有序的队列中找到特定的位置再放入

进行n次操作，选择排序为前n个有序，插入排序为前n+1个有序（至少）

选择排序的比较次数与序列初始状态无关，插入排序则有关、

每次选择排序都会使一个元素处于最终的位置上

8.7外部排序

外部排序

image-20251030190519566

image-20251030190539007

多路归并与败者树

image-20251030190607240

image-20251030190623472

image-20251030190705474

置换-选择排序

image-20251030190731036

image-20251030190819739

最佳归并树

image-20251030190841160

image-20251030190856110

image-20251030190914743

image-20251030191015567