思考：

我们如何用Python中的类型来保存一个班的学生信息？ 如果想要快速的通过学生姓名获取其信息呢？

  1.   实际上当我们在思考这个问题的时候，我们已经用到了数据结构。列表和字典都可以存储一个班的学生信息，但是想要在列表中获取一名同学的信息时，就要遍历这个列表，其时间复杂度为O(n)，而使用字典存储时，可将学生姓名作为字典的键，学生信息作为值，进而查询时不需要遍历便可快速获取到学生信息，其时间复杂度为O(1)。

我们为了解决问题，需要将数据保存下来，然后根据数据的存储方式来设计算法实现进行处理，那么数据的存储方式不同就会导致需要不同的算法进行处理。我们希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题，这就是数据结构。

在上面的问题中我们可以选择Python中的列表或字典来存储学生信息。列表和字典就是Python内建帮我们封装好的两种数据结构。

1、相关概念

1.1数据

  • 对客观事物记录及区分的符号，以及这些符号的组合，就是我们需要获取的信息；一个数字，一串英文等等都属于数据，数据也分多种类型，比如python中有int float str等。

1.2数据结构

  • 将数据以某种方式组织、存储起来的一种结构；
  • 或者说是一种数据元素相互之间存在一种或多种特定关系的集合。

Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。

2、数据结构分类

  • 分为逻辑结构和物理结构


2.1 逻辑结构

  • 逻辑结构：指在数据对象中，数据元素之间的关系
  • 重点研究对象，可分为四大类


2.2 物理结构

  • 指逻辑结构在计算机中的存储形式
  • 非重点研究对象


2.3 逻辑结构的分类

  • 集合结构：数据元素同属于一个集合
  • 线性结构：数据元素之间是一对一的关系
  • 树型结构：数据元素之间是一对多的层次关系
  • 图形结构：数据元素之间是多对多的关系


2.4 物理结构中的存储结构

  • 物理结构研究的是，如何将数据元素存储到计算机的存储器中


  • 存储器：主要是针对内存而言；像硬盘、光盘、U盘等这些存储设备通常用文件结构来描述


  • 数据元素的储存形式结构有两种：顺序储存和链式储存

    • 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的；例如编程语言中的数组结构就是典型的顺序存储结构。

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

3、数据结构与算法

  • 数据结构只是静态的描述了数据元素之间的关系。
  • 高效的程序需要在数据结构的基础上设计和选择算法。
  • 一个问题可以有多个算法解决，一个算法也不可能具有通解所有问题的能力
  • 算法是解决问题的一种思想、方法，数据结构是算法实现的载体，二者密切联系；
  • 程序=算法+数据结构

**