读书笔记-数据结构（Java语言描述）其一

数据结构是国内计算机相关专业的基础课程，为了弥补没上大学时落下的差距，需要补一下数据结构的知识😅。

本书地址：数据结构（Java语言描述）

该书一共九个章节，所以读书笔记也分为九篇，希望自己能养成循序渐进并善于总结的读书习惯😄。

读书笔记中的脚注为本人自己简单粗暴的理解，由于水平有限难免有错的地方，如有大佬发现请指出，在此感谢😋。

本篇读书笔记为该系列的第一篇，对应该书的第一章。

第一章：概述

第一章比较简单，主要了解一些数据结构相关的概念和名称，难点是算法时间复杂度的计算。

相关知识点

• 相关术语：数据、数据元素、数据对象、数据结构
• 数据逻辑：集合、线性结构、树和图
• 数据的物理结构：顺序和非顺序结构
• 算法的五要素和时间复杂度及空间复杂度

学习重点

• 数据的逻辑结构和存储结构及其之间的关系
• 算法时间复杂度的计算

学习难点

• 算法时间复杂度的计算

1.1数据结构的作用和意义

数据结构这门课程研究的问题：

• 如何在计算机中方便高效的表示和组织数据
• 如何在计算机存储器中存储数据
• 如何对存储在计算机中的数据进行操作、对存储在计算机中的数据有哪些操作、如何实现这些操作并对同一问题不同操作方法进行评价
• 理解每种数据结构的性能特征，以便选择适合于某个特定问题的数据结构

数据结构主要描述的是数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算三个方面的内容，即数据的逻辑结构、存储结构和数据的操作集合。

1.1.1数据结构的作用

数据结构是前人在思索问题过程中想出的解决方法。

数据结构这门课程的目的：

• 学习常用的数据结构，作为程序员处理数据问题的基本工具
• 学习常用的算法，优化计算机的数据存储和运行效率
• 提高程序员的综合能力

1.1.2数据结构的意义

用计算机解决问题：分析问题->确定合适的数据模型->设计求解该数据模型的算法->编写程序->反复调试至得到正确结果

书中举了三个例子：

• 基于员工信息的管理系统-线性结构
  
• 计算机和人对弈问题-树形结构
  
• 田径比赛赛程安排问题-图状结构
  

1.2基本概念和术语

1.2.1基本概念和术语

1. 数据： 数据是信息的载体，凡能输入到计算机中并被计算机程序处理的符号都可称之为数据。如：整数、实数、字符、文字、声音、图像等都是数据。¹

2. 数据元素： 数据元素是数据的基本单位，在计算机处理和程序设计中通常作为独立个体。数据元素一般由一个或多个数据项组成，一个数据元素包含多个数据项时常称为记录、结点等。数据项也称为域、字段、属性、表目、项点。²

3. 数据对象： 数据对象是具有相同特征的数据元素的集合，是数据的一个子集，如一个整型数组、一个字符串数组都是一个数组对象。³

4. 数据结构： 简称DS（Data Structure），是数据及数据元素的组织形式。⁴

   数据结构包含两个方面内容：

   • 数据对象
   • 数据对象中数据元素之间的内在关系

   数据结构通常有四类基本形式：

   • 集合结构：数据元素除了同属于一个集合外，之间没有其它关系。各个数据元素平行，共同属性是同属于一个集合，类似于数学中的集合。
     
   • 线性结构：数据元素之间是一对一的关系。
     
   • 树型结构：数据元素之间是一对多的层次关系；树型结构中正关系是一对多，逆关系是一对一。
     
   • 图形结构或网状结构：数据元素是多对多的关系。
     

5. 数据类型： 一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合；如整数类型、字符类型等。每一种数据类型都有自身特点的一组操作方法，即运算规则。⁵
   数据类型可看作是简单的数据结构，数据的取值范围可看作是数据元素的有限集合，对数据进行操作的集合可看作数据元素之间关系的集合。

1.2.2数据的逻辑结构

数据的逻辑结构是从具体问题抽象出来的数学模型，和数据在计算机中的具体存储无关。1.2.1中的数据结构的定义就是数据的逻辑结构，它是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。
其中集合、树、图形结构都是非线性结构。

数据的逻辑结构有两个要素：

• 数据元素的集合，通常记为D
• 数据元素集合上的关系集，通常记为R；它反映了D中各数据元素之间前驱后继的关系。

一个数据结构可以表示成二元组B=(D,R)。

书中举了三个例子：

• 一年四季B1=(D1,R1)
  
• 某单位的管理关系B2=(D2,R2)
  
• A某的人际关系B3=(D3,R3)
  

<x,y>意为x和y之间存在【x领先于y】的次序关系，而(x,y)表示x和y之间没有次序上的关系。读到这儿我突然意识到我应该先去补习离散数学😥；不过还好查查资料勉强能看懂...

1.2.3数据的物理结构

数据的物理结构又称存储结构。
适用在内存结构中有数据存储结构有顺序结构和链式结构两种不同的方式。
顺序存储结构：
顺序存储结构通常用高级编程语言中的一维数组描述或实现，其特点是数据元素在存储器的相对位置来体现数据元素相互之间的逻辑关系。⁶

链式存储结构：
链式存储结构表现为可通过一组任意的存储单元来存储数据元素，这些存储单元可连续也可不连续。存储器中除了存放数据元素自身信息外，还要存放其它与该数据元素有关系的地址。

适用在外存与内存交互结构索引结构和散列结构两种不同的方式。
索引存储：
除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。

散列存储：
散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

1.3面向对象的数据结构表示

1.3.1Java面向对象基础

太基础了，就不总结了，除非失忆否则不可能忘吧....😑

• 类的声明与实例化
• 类的成员的定义与使用
• 抽象类
• 泛型类

1.3.2面向对象的抽象数据类型

抽象数据类型（Abstract Data Type，ADT）： 是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是描述数据结构的一种理论工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型的定义取决于它的一组逻辑特性，而与计算机内部如何表示无关。⁷

1.3.3使用Java语言描述数据结构的优势

优势：

1. 使用Java描述数据结构更加简单
2. Java的泛型机制更加适合数据结构的抽象表示
3. java.util提供多种数据结构，可以加速应用系统开发

1.4算法和算法分析

1.4.1算法的基本概念

算法： 是指在有限的时间范围内，为解决某一问题而采取的方法和步骤的准确完整的描述，它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。
算法的特征：

• 有穷性：一个算法应包含有限个操作步骤，即一个算法在执行若干个操作步骤之后应该能够结束，并且每一步都要在合理时间内完成。
• 确定性：算法中的每一个步骤必须有确切的含义，无二义性，在任何情况下，对于相同的输入只能得出相同的输出。
• 可行性：算法中的每一个步骤都应该能够通过已经实现的基本运算的有限次执行得以实现。
• 输入：输入指的是在算法执行时，从外界取得必要的数据。一个算法可以有一个或一个以上的输入，也可以没有输入。
• 输出：数据结构输出指的是算法对输入数据处理后的结果。一个算法可以有一个或一个以上的输出，没有输出的算法是无意义的。

1.4.2算法效率的度量

评价算法优劣的五个标准：

• 正确性：执行结果满足功能和性能需求，输入输出无歧义
• 可读性
• 健壮性：具有很强的容错能力
• 运行时间
• 占用空间

1.4.3算法效率分析

时间复杂度（Time Complexity）

大O符号表示法，算法的渐进时间复杂度：!$T(n)=O(f(n))$

n：问题规模的量；例如在排序问题中n就是所需排序元素的个数。
T(n)：问题规模n的算法运行所需的时间
O：数量级Order的首字母
f(n)：规模为n的算法重复执行基本操作的次数。

时间复杂度是估算的数量级，着重体现的是随着问题规模n增大算法执行时间的变化趋势。所以当T(n)为多项式时，可以省略系数并只取最高次幂；如：T(n)=8n^3^+15n^2^+3n+1可表示为T(n)=O(n^3^)。

一些常见的时间复杂度等级：
O(1)： 常数阶，基本操作执行次数为常数
O(logn)： 对数阶
O(n)： 线性阶
O(nlogn)： 线性对数阶
O(n^2^)： 平方阶
O(n^k^)： K方阶
O(x^n^)： 指数阶

一般情况下，对于足够大的n，常用的时间复杂性存在如下顺序：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<<O(2n^2^)<O(3n^2^)<...<O(n!)

空间复杂度（Space Complexity）

空间复杂度：!$S(n)=O(f(n))$
n：问题规模的量；例如在排序问题中n就是所需排序元素的个数。
S(n)：问题规模n的算法在计算机存储器内所占用的存储空间；主要分三部分：算法源码本身占用的存储空间、算法输入输出数据所占用的存储空间、算法运行过程中临时占用的存储空间
O：数量级Order的首字母
f(n)：规模为n的算法重复执行基本操作的次数。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

1.5习题

第一章的练习题
一、

1. 数据元素、数据间关系
2. 集合、线性结构、树形结构、图状结构或网状结构
3. 有穷性、可行性、确定性
4. 数据对象、数据关系、基本操作
5. 物理结构、逻辑结构、运算
6. 时间、空间

二、

1. B
2. C
3. C
4. A
5. C
6. C

三、

1. (n+3)(n-2)/2
2. n(n-1)/2
3. （1）. T(n)=O(n)
   （2）. T(n)=O(n^2^)

注：习题为自己做的，非答案，不保证其正确性；若有错误请大佬指出并提供解答思路，万分感谢✔️！