一、数据结构基本概念

1、数据:数据是信息的载体。客观事物的一种表现形式。万事万物都能用数据表示出来。

2、数据元素:数据元素是数据的基本单位,一个数据元素有若干个数据项组成

3、数据项:构成数据元素的不可分割的最小单元

理解:学java的可以这么理解,学生就是一个类,一个类里面有很多属性,比如学号,姓名和性别。
学生 = 类 = 数据元素
学号,姓名,性别=数据项。一个学生有多个数据项(学号,性别等等等)结合这个再读一遍概念就理解了.

4、数据对象:是具有相同性质的数据元素的集合,是数据对象的一个子集

理解,就是多个学生,多个相同的类 ,就是数据对象。

5、数据类型:是一个值的集合和定义在此集合上的一组操作的总称。主要分为:

  • 原子类型:值不能再分。如int bool 等。
  • 结构类型:值可以分解为若干个成分的数据类型。比如一个类,或者一个结构体
  • 抽象数据类型:就是数据组织与之相关操作。

6、数据结构:相互之间存在一种或多种特定关系的数据元素的集合。主要包括三个方面:逻辑结构存储结构数据的运算。也就ADT。

理解:现在有很多数据元素(学生),我们要把这些数据元素(学生)的关系的逻辑结构(三角恋关系,谈恋爱关系,各种抽象的关系),存储结构(在班里是怎么坐座位的)和如何运算(对学生进行删除,查找,添加等)结合在一起就形成了数据结构。也就是讲数据结构,不仅有数据,而且还要有数据之间的关系以及数据怎么存的方式结合起来

二、数据结构三要素

上面已经有数据结构概念,三要素就是对概念进行提炼。三要素包括:逻辑结构存储结构数据运算

  • 逻辑结构:考试一般就两种线性结构非线性结构。其中后面学的前几章都是线性结构(线性表,栈,队列,串,数组,广义表)。再往后都是非线性结构(树,图)
  • 存储结构:考试一般重点分为顺序存储链式存储。还有一些别的索引和散列。
  • 数据运算:主要针对逻辑结构。说白了,就是增删查
  • 总结:我们后面学的章节的开头,如,线性表,栈,队列,树,图都是学逻辑结构而每个逻辑结构里面都有顺序存储方式和链式存储方式。这是理解数据结构的一条线。

三、算法

1、算法概念

对特定问题的求解步骤描述,指令是有限序列,主要有5个特征:

  • 有穷性:步数和时间是有限的,不能没完没了。不能等人没了还没算出来。
  • 确定性:每条指令都必须有含义,不能没意义。
  • 可行性:对问题的描述能够转换为基本运算。
  • 输入:有零个或多个输入。
  • 输出:有一个或多个输出。

2、算法评价标准

一个好算法需要具备下面特点:

  • 确定性:正确的解决问题
  • 可读性:可以是伪代码,能读懂就OK。
  • 健壮性:对特殊问题能进行处理,不能老报错。
  • 效率和低存储量:时间要快,空间利用的要尽量小。也就是后面大家比较头疼的时间复杂度和空间复杂度。

3、时间复杂度

这个考试经常考,就是要用O(n)数量级把一个算法效率表示出来。

  • 注意几点:
    • 取较高的阶数,小的忽略
      O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n的三次方) < O(2的n次方) < O(n!) < O(n的n次方)
      口诀常对幂指阶

4、时间复杂度做题技巧

其实找规律就行,举几个例子:在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5、空间复杂度

完全可以用空间来换取时间,这个考的很少,一般记一些常用查找排序用的空间复杂度,,考试可能会考。

下一章:考研数据结构笔记——线性表(顺序表和链表必背代码及混淆点)

Logo

汇聚原天河团队并行计算工程师、中科院计算所专家以及头部AI名企HPC专家,助力解决“卡脖子”问题

更多推荐