黑马程序员技术交流社区

标题: 【太原校区】数据结构（第一部分） [打印本页]

作者: miaohangbo 时间: 2018-12-5 15:18
标题: 【太原校区】数据结构（第一部分）
本帖最后由 miaohangbo 于 2018-12-6 17:56 编辑

涉及内容主要有：
1、数据结构（基本概念）
2、数据结构与其他语言关系
3、数据结构与算法关系
4、数据结构包含的内容
5、数据结构具体实现

目录：
第一部分：基本概念

第一部分(基本概念)

1、数据结构
1.1基本概念
数据：描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。数值类型（整型、实型等）和非数值类型（字符、声音、图像等）。
数据对象（记录）：是性质相同数据元素的集合，是数据的子集。
数据元素：组成数据的、有一定含义的基本单位，在计算机中通常作为整体处理。
数据项：一个数据元素由若干个数据项组成。数据项是数据不可分割的最小单位。

数据、数据对象、数据元素、数据项之间关系

1.2数据结构
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。（数据元素+关系）
（程序设计 = 数据结构 + 算法）
逻辑结构：是指数据对象中数据元素之间的相互关系。（四种：集合、线性、树形、图形）
集合结构：集合结构中的数据元素同属一个集合外，他们没有其他关系。元素是平等的。

线性结构：数据元素是一对一的关系。(对应前后)

树形结构：数据元素之间存在一种一对多的层次关系。

图形结构：数据元素多对多关系。

物理（存储）结构：是指数据的逻辑结构在计算机中的存储形式。两种：链式存储，顺序存储。
顺序存储结构：是把元素存放在地址连续的存储单元里，其数据之间的逻辑关系和物理关系是一致的。

链式存储结构：数据元素存放在任意的存储单元中，这组存储单元可以是连续的也可以是不连续的。需指针存储地址。

数据类型：是指一组性质相同的值的集合及定义在此集合上的一组操作的总称。
抽象数据类型：是指一个数学模型及定义在该模型上的一组操作。（主要指的是逻辑上的，抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性）

数据结构

2、与其他语言的关系
数据结构本身与语言无关。（java\c\python等等）
例如：勾股定理。

3、算法
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令都表示一个或多个操作。此处算法是为了更好地理解数据结构。（包含算法特征、设计要求等）

例子：1+2+3+....+100
方法一、普通计算
int sum=0;
for(int i=1,n=100;i<=n;i++){
sum+=i;
}
System.out.println(sum);
方法二、等差数列
int sum=0,n=100;
sum=(1+n)*n/2;
System.out.println(sum);

时间复杂度：在进行算法分析时，语句总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n变化情况确定T(n)的数量级。
空间复杂度：计算算法所需的存储空间。

常见时间复杂度比较：

大小关系