数据结构篇_知识点板块_第一章绪论

2022年05月11日 阅读数:2
这篇文章主要向大家介绍数据结构篇_知识点板块_第一章绪论,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 数据结构篇为本人考研时所写笔记,包括知识点和编程思想两大板块,笔记内容依据王道数据结构考研书所写,但比书本上知识更加生动形象,愿本篇章能对您有所帮助
  • 注意:数据结构篇为本人手动将Word文档修改为Markdown格式(由于网上修改的方法都会出现较多错误),故格式可能有时会不太整齐请见谅,阅读时请务必主要内容前的编号

1、绪论

  1. 基本概念:

① 数据元素:是数据的基本单位(由数据项构成)算法

② 数据项:一个元素由若干数据项组成,数据项是构成数据元素的不可分割的最小单位编程

③ 数据对象:具备相同性质的数据元素集合,是数据的一个子集数组

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

⑤ 数据类型:一个值的集合和定义在此集合上的一组操做的总称函数

⑥ 抽象数据类型(ADT):是指一个数学模型及定义在该模型上的一组操做,一个抽象数据类型的软件模块一般包含定义、表示和实现code

​ 三元组(D,S,P):数据对象,数据关系,基本操做对象

​ 二元组(D,R):数据元素的集合,D上关系的集合blog

  1. 数据的物理结构主要包括顺序存储结构和链式存储结构排序

  2. 逻辑结构:独立于计算机(数据逻辑结构独立于其存储结构),分为线性结构(一维数组是线性结构的,二维数组和多维数组不是线性结构的)和非线性结构(树型结构,网状结构,集合);例如栈是抽象数据类型,可采用顺序存储或链式存储,故为逻辑结构递归

存储结构:依赖于计算机,主要有顺序存储、链式存储、索引存储、散列存储

  1. 运算的定义是针对逻辑结构的,指出运算的功能

运算的实现是针对存储结构的,指出运算的具体操做步骤

  1. 在存储数据时,不只要存储数据元素的值,并且要存储数据元素之间的关系

  2. 程序=数据结构+算法

  3. 一个算法应该是问题求解的步骤描述

  4. 算法的特性:

① 有穷性

② 肯定性

③ 可行性

④ 输入

⑤ 输出

  1. 好的算法特性

① 正确性

② 可读性

③ 健壮性

④ 高效率与低存储需求

10. 时间复杂度计算(T(n),通常记为O(n)):

① 注意题目问到时平均时间复杂度仍是时间代价表达式

② 若为大题则必须写过程,不然可能不记分

③ T(n)=O(f(n))。通常地,若T(n)是有关n的一个多项式,则f(n)可由T(n)中的最高此项去掉系数所得,O(n)也是一个函数,它表示渐进时间复杂度

④ 多数状况是选择最深层循环内的语句中的原操做,计算该原操做的重复执行次数

⑤ 有时须要同时考虑几种原操做,多项相加保留最高阶的项,多项相乘都保留(空间复杂度同)

⑥ 有时算法的原操做重复执行次数还随问题的输入数据集不一样而不一样,对于这种状况通常采起计算平均值的办法(即平均时间复杂度)

⑦ 多数状况输入数据集的几率难以肯定,此时平均时间复杂度很差算,故通常讨论算法在最坏状况下的时间复杂度(即为上界)

 易错:很明显时间复杂度与n有关,故当程序中没有n的出现时,若一切都为肯定的数无论循环有多大,这个程序的运行都是和n无关的,故T(n)=O(1)


  1. (时间复杂度和空间复杂度经典排序)

补充:(2/3)^n < 2^100 < lg_n < n^1/2

  1. 空间复杂度(S(n))=递归调用的深度(每次递归调用所产生的空间复杂度同样的前提下(没有相似于a[n]这种数组建立和传入的相关的代码))

  2. 算法原地工做是指算法所需的辅助空间是常量,不是指不需辅助空间

  3. 算法中语句的频度不只与问题规模有关,还与输入实例中各元素取值相关,但在最坏的状况下,时间复杂度就是只与求解问题的规模有关的