一、线性表

顺序表

在物理空间中存储为连续。
静态数组:

• data[maxsize]

动态分配

• 使用malloc和free

  特点

• 随机访问

• 存储密度高
• 插入与删除不方便

插入与删除

顺序表当中的基本操作

插入

• 在第 i 个位置插入，需要将 i 和 i 往后移动

平均时间复杂度 O(n)

删除操作

平均时间复杂度 O(n)

随机查找

O(1)

一、数组

地址的计算

一维数组

二维数组

• 行优先

• 列优先

数组的压缩

对称矩阵

• 下三角压缩

三角矩阵

二、树

最小生成树

Kruskal算法

• 算法总结，做题技巧##

1. 将所有的边，按照权从小到大排序
2. 按顺序连接回去
   • 判断是否为环
     • 是，则舍去
     • 否，则加入
3. 重复步骤，知道构成n-1条边。

   Prim算法

三、查找

查找长度: 就是在查找当中，对比多少次关键字
平均查找长度: 所有查找过程当中的平均值。

• 静态查找
  • 不进行操作
• 动态查找
  • 进行除查找以外的操作

顺序查找