数据结构
基本概念
一、数据
1、数据（用计算机处理的事物）
描述客观事务的符号
计算机可操作的对象
能被计算机识别，并输入给计算机处理的符号集合
2、数据类型
数值类型：整型、浮点型
非数值类型：字符、声音、图像、视频
3、数据元素（一条记录，数据的基本单位）
组成数据的，有一定意义的基本单位
在计算机中通常作为整体处理
也被称为记录
数据是一个整体，数据元素是一个组成
例：植物中的杨树、柳树；餐具中的盘、碗
4、数据项（字段，构成数据元素的最小单位）
一个元素由若干个数据项组成
是数据不可分割的最小单位
例：树的粗细、高度、树龄；电脑的显示器、主机、键盘、鼠标
数据元素和数据项的的关系
a、数据项是数据元素的组成部分
b、数据元素是数据结构中建立数据模型的着眼点
5、数据对象
多个性质相同的数据元素的集合--》数据元素是数据对象的子集
是数据的子集
例：电脑都有：显示器、键盘、鼠标相同的数据项；动物都有：头、躯干、四肢相同的数据项
二、数据结构
结构是各个组成部分相互搭配和排列的方式
数据是数据对象的简称
数据结构指相互之间存在一种或多种特定关系的数据元素的集合
逻辑结构
一、概念
数据对象中数据元素之间的相互关系
人的思维--》分析数据
二、分类
1、集合结构（不研究，关系弱）
a、数据元素呈集合结构分布
b、数据元素除了属于一个集合外，数据元素之间没有任何关系
c、数据元素之间是平等的最松散的结构
2、线性结构
a、数据元素呈线性结构分布（一维：直线）
一维：数据1可以找到数据2，但是数据1必须通过数据2才能找到数据3
b、数据元素是一对一的关系
3、树形结构
a、数据元素呈树形结构分布
b、数据元素是一对多的关系
c、图例：
4、图形结构（网络结构）
a、数据元素呈图形结构分布
b、数据元素是多对多的关系
存储结构
一、概念
数据的逻辑结构在计算机中的存储方式
逻辑结构是人的思维便于分析数据；存储结构是计算机实际存储数据的方式
二、分类
1、顺序存储结构
数据元素存储在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
如：数组 可以通过地址的加减找到下一个数据元素
缺点
插入和删除时效率低下
2、链式存储结构
数据元素存储在任意的存储单元里。存储单元可以是连续的也可以不是连续的
缺点
插入、删除灵活，查找节点比较慢；
3、索引存储结构
应用：数据库
4、散列存储结构
神奇的结构--》添加、查询速度快
应用：哈希表
抽象数据类型ADT
一、数据类型
一组性质相同的值的集合及定义在此集合上的一些操作的总称
a、值：性质相同的值得集合（前提）
b、操作：对值进行的一些操作（如：算术运算等）
按照值得不同进行划分--》说明变量和表达式的取值范围和能进行的操作
如：数值型--》byte、short、int、long
二、数据类型分类
1、原子数据类型
不能再分的基本数据类型如：java中的8大基本数据类型
2、构造类型
若干原子类型或构造类型组合而成
三、抽象
一种思考问题的方式
抽取具体事物中具有的普通性的本质--》对具体事物的概括
四、抽象数据类型ADT
指一个数据模型（数据）及定义在该模型上的一组操作（数据及操作）
对数据类型的数学抽象表示
仅与逻辑结构有关（人的思维方式）；与存储结构无关
算法
一、算法定义
对解决特定问题的求解步骤的描述（解决问题的步骤）
在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
特定问题：没有通用的算法，只有专用的算法
有限序列：按照顺序的有限排列 不是无穷的。
指令：能被计算机执行的命令
一组命令：有限序列
可以是计算机语言，可以是平时的语言
二、算法的特性
1、输入特性
算法执行前，必须具备的先决条件
可以没有输入，及不需要先决条件
有一个输入，需要一个先决条件
有多个输入，需要多个先决条件
2、输出特性
算法执行后，得到的结果
必须有输出特性
输出可以是打印输出
也可以是返回一个或多个值
3、有穷性
不会出现死循环
算法在执行有限的步骤后自动停止
每个步骤都能在可接受的时间内完成
4、确定性
算法的每一个步骤都有确定的含义--》没有二义性（一个结果）
5、可执行性
算法的每一步都必须是可执行的
算法的每一步--》通过执行有限的次数完成
算法可以别转换成计算机程序执行，并得到执行结果
三、算法设计的要求
1、正确性
体现在：输入、输出、加工处理等方面
正确反映问题的需求
能得到问题的正确答案
无歧义（准确性）
2、正确性的4个层次
没有语法错误--》程序可以运行
对于合法的输入数据产生满足需求的输出结果
对于不合法的输入数据能产生满足规格说明的输出结果
对于精心准备的测试数据能产生满足要求的输出结果--》一般只要求到层次3
3、可读性
便于阅读、理解、交流
4、健壮性
输入不合法的值，算法能做出相关的处理
不会产生异常或莫名其妙的结果
5、时间效率高
算法的执行时间
对于同一问题，用时少的算法，时间效率高
6、存储量底
算法执行过程中所需要的内存空间
对于同一问题，存储空间小的算法，存储量低。
线性表List
一、线性表的定义
1、定义
零个或多个相同数据元素的有限序列
相同数据类型：在内存存储时，每个元素占用相同的内存空间，便于后续的查询定位；
序列：元素之间有顺序
有限：元素的个数是有限的
2、线性表的长度
数据元素的个数
3、数学定义（数据模型）
线性表逻辑表示：
a1 ，a2，a3……ai-1，ai，ai+1……an ；
ai-1位于ai前面，ai-1是ai的直接前驱；
ai+1位于ai后面，ai+1是ai的直接后继；
a1只有直接后继an只有直接后驱；
n为线性表的长度，若n = 0 时，线性表为空表；
二、线性表的抽象数据类型
ADT线性表
1、Data
a1 ，a2，a3……ai-1，ai，ai+1……an ；
2、Operation
|
序号 |
方法名 |
方法说明 |
|
1 |
InitList(L) |
初始化操作，建立一个空的线性表 |
|
2 |
ListEmpty(L) |
判断线性表若为空，返回true |
|
不为空，返回false |
||
|
3 |
ClearList(L) |
将线性表中的所有数据元素删除 |
|
4 |
GetElement(L , i) |
返回线性表L中下标为i的元素 |
|
5 |
LocateElement(L , e) |
在线性表L中查找指定元素e |
|
查找成功，返回e在L中的下标 |
||
|
不成功，返回-1 |
||
|
6 |
InsertList(L , i , e) |
在线性表L中下标为i的位置插入元素e |
|
7 |
DeleteList(L , i) |
将线限表L中下标为i 的元素删除 |
|
8 |
ListLength(L) |
返线性表L中元素的个数 |
三、顺序存储结构
1、顺序存储结构
用一段地址连续的存储空间；
依次存储数据表中数据元素（有序）；
2、示意图（内存）
|
A1 |
|
A2 |
|
... |
|
Ai-1 |
|
Ai |
|
Ai+1 |
|
... |
|
An |
3、数据长度
线性表中能保存数据元素最多个数；
是个固定值，定义时确定大小，不可变更；
4、线性表长度
线性表中已保存的数据元素的个数；
一个随时变化的值；
5、地址的计算方法（参照示意图）
地址：存储器中每个存储单元的编号；
顺序存储结构通过地址偏移量的计算找到下一个元素；
address（Ai）= address（Ai-1）+n
= address（A0）+n（i-1）
n：每个元素所占的字节数
Ai，Ai-1，A0表示数据表中数据元素的个数。0，i-1, i 表示下标。
下标（subscript）：数组中每个元素的编号
四、顺序存储结构的优缺点
优点：索引查询效率高；
缺点：增加、删除数据的时候操作的比较多，比较慢；
链表
一、链式存储结构
1、特点
用一组任意的存储单元存储线性表中的数据元素；
任意：存储单元可以是连续的，也可以不连续；
每个数据元素除了存储数据外，还要存储前驱、后继元素的地址；
顺序存储结构：通过地址偏移量的计算找到下一个元素
链式存储结构：通过next指针找到一下个元素
|
data（数据域） |
address（指针域） |
二、单链表
1、定义
n个节点按链式存储结构存储
每一个节点都只包含一个指针域
2、图例
|
A1 |
A2 |
A3 |
null |
3、Operation
主要是操作指针注意区分第一个，最后一个和中间的操作；
获取指定位置的元素；--》获取指针的位置position
获取链表的节点数getSize ( )；--》利用后驱指针的null属性
在链表中插入一个节点insert( )；--》更改前驱、后继指针的指向
单链表节点的删除erase( )；--》将后驱指针赋值为null
单链表的合并union ( )；--》第一链表，然后将最后的指针null更改为第二个链条的第一个
单链表的倒置reverse( )；--》第一个和最后的指针变化，中间指针指向前面一个循环
单链表的遍历trave ( )；--》获取节点数类似
三、单循环链表
1、定义
单链表中的最后一个指针域null改为指向第一个链表。形成一个环；
2、分类
只有一个节点；--》自己指向自己
多个节点
3、Operation
获取单循环链表的节点数getSize ( )；--》尾指针的next 等于头指针
获取指定位置的元素
插入节点insert ( )；
删除节点erase ( )；
栈
一、栈的定义
1、栈
限定仅在表尾进行插入和删除操作的线性表；
又称为后进先出(Last In First Out)线性表,简称LIFO
2、栈的相关概念
栈顶：进行插入和删除的一端；
栈底：不允许进行插入和删除的一端；
空栈：不含任何数据元素的栈；
3、栈的操作
进栈：又称压栈，在栈中增加一个元素；
出栈：又称弹栈，在栈中删除一个元素；
二、栈的抽象数据类型
ADT栈
1、Data
本质是一个线性表，限定了插入和删除的位置；
2、Operation
|
序号 |
方法名 |
作用 |
|
1 |
InitStack (s) |
初始化操作，建立一个空的栈 |
|
2 |
DestroyStack (s) |
销毁一个已存在的栈 |
|
3 |
ClearStack (s) |
清空一个栈 |
|
4 |
StackEmpty (s) |
若栈为空，返回true |
|
若栈中有元素，返回false |
||
|
5 |
GetTop (s, e) |
若栈存在且非空，返回栈顶元素 |
|
6 |
Push (s, e) |
在栈中压入一个元素 |
|
7 |
Pop (s ，e) |
在栈中弹出一个元素 |
|
8 |
StackLength (s) |
获取栈中的元素个数 |
三、顺序存储结构
1、栈的顺序存储结构
简称顺序栈；
和线性表类似，用一维数组来存储栈；
2、代码体现，内存分析
声明内存空间；
InitStack (s)；