数据结构和算法简介 以及 顺序表

数据结构和算法简介

一, 数据结构和算法的定义

数据结构的定义:

概述:

就是存储和组织数据的方式, 分为:线性结构和非线性结构.

算法的定义:

概述:

就是解决问题的思路和方法, 它具有独立性, 即,:它不依赖语言，而是解决问题的思路.Java能做Python也能做

特性:

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

二, 算法的时间效率衡量

时间复杂度的定义

时间复杂度表示一个算法随着问题规模不断变化的最主要趋势，通常用来衡量一个算法的优劣
懂俗点来说时间复杂制度可以衡量一个"算法的量级"

如何衡量算法的优劣

大0标记法, 即：将次要条件都省略掉，最终形成1个表达式.
主要条件：随着问题规模变化而变化的.
次要条件：随着问题规模变化而不变的.
图解:

最优和最坏时间复杂度

如非特殊说明，我们考虑的都是最坏时间复杂度，因为它是算法的一种保证
而最优时间复杂度是算法的最理想，最乐观的状况，没有太大的参考价值.

常见的时间复杂度如下

从最优到最坏分别是：
0(1) -> o(logn) -> o(n) -> o(nlogn) -> o(n²) -> o(n³)
常数阶 -> 对数阶 -> 线性阶 -> 线性对数阶 -> 平方阶 -> 立方阶

扩展:常见的空间复杂度如下

了解即可，因为服务器(内存)资源一般是足够的
从最优到最坏分别是：
o(1) -> o(logn) -> o(n) -> o(n²) -> o(n³)

三, 数据结构的分类

数据结构=存储，组织数据的方式，是算法解决问题时的载体

• 线性结构
  特点：每个节点都只能有1个前驱1个后继节点
  例如：栈, 队列
• 非线性结构
  特点：每个节点都可以有多个前驱，多个后继节点
  例如：树, 图

四, 线性结构存储数据的方式

(1)顺序表的存储方式

顺序表的定义

将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示
解释: 顺序表有 数据区 和 信息区 两部分组成.

特点

• 数据区和信息区在一起的 ->一体式存储(扩容时只能整体搬迁)

  • 图解:
    

• 数据取货和信息区分开存储的 ->分离式存储(可以直接让信息区指向新的 数据区即可, 不用整体搬迁 ).

  • 图解
    

顺序表扩容策略

思路1：每次增加固定的容量. 拿时间换空间

思路2：每次扩容，容量翻倍. 拿空间换时间

(2)链表的存储方式

略

五, 总结

• Q1:数据结构和算法的定义?
  • 数据结构的定义:就是存储和组织数据的方式, 分为:线性结构和非线性结构.
  • 算法的定义:就是解决问题的思路和方法, 它具有独立性, 即,:它不依赖语言，而是解决问题的思路.Java能做Python也能做
• Q2: 时间复杂度的定义?
  • 时间复杂度表示一个算法随着问题规模不断变化的最主要趋势，通常用来衡量一个算法的优劣.
  • 懂俗点来说时间复杂制度可以衡量一个"算法的量级"
• Q3: 数据结构的分类?
  • 线性结构
    特点：每个节点都只能有1个前驱1个后继节点
    例如：栈, 队列
  • 非线性结构
    特点：每个节点都可以有多个前驱，多个后继节点
    例如：树, 图
• Q3:线性结构存储数据的方式
  • 顺序表:
    • 将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示.
    • 解释: 顺序表有 数据区 和 信息区 两部分组成.
  • 链表：
    • 将元素存放在通过链接构造起来的一系列存储块中，存储区是非连续的