基本概念

数据的定义：

对客观对象的符号化表示,是计算机能偶输入的，可以被计算机处理的的符号总称

数据元素：

数据的基本单位,由多个数据项构成，数据项是构成数据元素的最小单位

数据对象

相同的数据元素集合，是数据的一个子集

数据结构

对于数据相互之间关系的描述

数据结构方向划分

数据逻辑结构

1、基本定义：逻辑上是相关的，但是在物理上的存储是无关的
2、常见的逻辑结构
线性：表、栈、队列
非线性：数、图、集合
我所理解的线性与非线性的差距在于元素间是否是一一对应的关系

数据结构物理（存储）结构

1、基本定义
2、常见的存储结构：
顺序
链式
索引
散列

数据的运算

运算的定义：
运算的实现：

线性结构

线性表：

定义：含有n个相同数据类型的数据元素的有限序列
数据元素间的关系：一对一的关系

存储结构：

1、顺序存储结构：顺序表、数组
顺序表：线性表的顺序存储结构表示
数组：顺序存储的一种方式
2、链式存储结构：单链表、双向链表、循环链表

栈

定义：就是被限定在尾进行插入和删除的线性表

基本操作规则

PUSH(入栈)、POP(出栈)
1、FIFO(先进先出)
2、LOLO(后进后出)

存储结构

1.顺序存储:顺栈,就是利用一组地址存储单元自栈低向栈顶存储,同时有指针(top)指示栈顶元素的当前位置
2.链式存储:链栈,一个链栈由一个顶指针唯一的确定，同时不存咋栈满的情况

栈的应用

括号表达式：用于编译
表达式求值：实现算法

队列

定义：数据元素属于同一类型，数据元素之间的关系为线性关系

基本操作规则

队尾（rear）、队头(front)
1、FIFO(先进先出)
2、LOLO(后进后出)

存储结构

顺序存储

1、队列存储结构：一块链接的存储空间存储队列的元素、并设立front指针指向队头位置,rear指针指向队尾
2、循环结构：把队列元素的表从逻辑上看成一个环

链式存储

一个列有头指针和尾指针，分别指向队头和队尾

串

就是由0或者多个字符组成的有限序列

非线性结构

集合

就累始与Java中的“对象”拥有某一共同属性的统称

树形结构

数据元素的关系

树

树是n个结点的有限集,n=0时为空树
结点：树的结点包含一个数据元素以及若干指向其子树的分支
节点的度：结点拥有的子树的个数
树的度：所有节点中度最大的值
叶子节点：度为0的结点
分支节点：度不为0的结点,或者非终端节点
树的深度：树中节点的最大层次
树的高度：以叶子结点为第一层，向上数有多少层

二叉树

定义：由多个结点组成，每个结点的子结点数小于2，同时左右结点不可以互换

常见分类：

1、普通二叉树
2、满二叉树:
定义：深度为K,有n个结点的二叉树,当且仅当其每一个结点与深度为K的满二叉树
特点：每一层上的结点数都是最大结点、除最后一层外的所有叶子节点以外的所有结点的度均为2
3、完全二叉树
定义：深度为K,有n个节点，当且仅当每一个结点与深度为K的满二叉树编号一一对应时，就称为完全二叉树
特点：叶子节点只可能在层次最大的两层、至多出现一个度为一的结点、当i$\ge \frac{n}{2}$时,结点i的分支节点,否者就是叶子结点

性质：

1、满二叉树的第i层最多有$2^i-1(i\ge 1)$个结点
2、深度(高度)是为K的二叉树最多有$2^k-1(k\ge 1)个结点$
3、非空的二叉树的叶子节点树比度为2的结点数多1个,就是n(o)=2n+1
4、具有完全子结点的完全二叉树的深度为$lo{g}_{2}2n=+lo{g}_2(n+1)$
5、对于一棵完全的二叉树,从上到下从左到右的编号依次为1、2、3…
当i=1时，结点i时二叉树的根i$gep1$那么它的双亲结点为$\frac{i}{2}$
但2i>n时，结点无左子节点，否者左子节点为2i+1
如果2i+1>n,那么该结点无左子结点，否者左子节点为2i+1
结点i所在的层次为$lo{g}_2+1$

遍历二叉树：

1、前序遍历（先序）：根$\to$左$\to$右
2、中序遍历：左$\to$根$\to$右
3、后序遍历：左$\to$右$\to$根

存储结构：

顺序存储结构:用一组地址连续的存储单元存储二叉树的数据元素就是二叉树的顺序存储
链式存储结构：设计不同的结点构成不同的链式存储结点，一般而言包含三个域,及数据域、和左右指针域

网状图

定义 图G由顶点集V边集E组成

数据元素的关系

多对多

矩阵

稀疏矩阵：

就是0元素远远多于非0元素，同时还要求非0元素排列时要有规律的

稠密矩阵:

同稀疏矩阵的定义相反

广义表

定义：具有n（n>=0）个数据元素的序列
1、n=0那么是个空表，长度为0
2、n=（a） 仅有一个单位元素，长度为1
3、n=(q,(d,e)) 长度为2,子元素分别为q和（d,e）