数据结构

1、绪论

基础概念

• 数据：描述客观事物的数值、字符、以及能输入机器且能被处理的各种符号集合
• 数据元素：组成数据的基本单位，是数据集合的个体
• 数据项：独立含义的最小单位
• 数据对象：性质相同的数据元素的集合
• 数据结构：相互之间存在一种或多种特定关系的数据元素集合
• 数据类型：一种性质相同的值集合以及定义在这个值集合上的一组操作的总称

数据类型

• 原子类型：不可再分；如：整型、实型、字符型、指针等
• 结构类型：由其他成分组成，可以再分

抽象数据类型

• 本质：抽取反映问题的本质点，而忽略非本质的细节
• 特点：数据抽象和信息隐蔽

数据元素间相互关系

• 数据的逻辑结构
  • 集合结构
  • 数据元素之间只属于同一个集合
  • 线性结构
  • 结构中数据元素之间存在着一对一的线性关系
  • 树状结构
  • 数据元素之间存在这一对多的关系
  • 图状或网状结构
  • 存在多对多的关系
• 数据的物理结构
  • 顺序存储结构
  • 非顺序存储结构
• 数据的运算集合

面向对象

• 组成
  • 对象
  • 类
  • 继承
  • 通信
• 特点
  • 封装性、继承性、多态性
• 变量作用域
  • 指该变量的作用域的最小范围
  • 全局变量
  • 程序中所有函数都可以访问的1变量
  • 局部变量
  • 只能在本函数中访问的量

2、线性表

结构特点：

• 第一个元素无直接前驱，最后一个元素无直接后继，中间元素，都有唯一直接前驱和后继

定义：

• 由n个类型相同的数据元素组成的有限序列

存储

• 顺序存储
  • 用一组地址连续的存储单元一次存储线性表中的各个元素
• 链式存储
  • 单链表
  • 用一组任意的存储单元存放线性表的结点
  • 结点信息
    • 数据域
    • 存储结点的值
    • 指针域
    • 数据元素的直接后继的地址
  • 每个结点只有一个next指针域
  • 设一个头指针H指向第一个结点
  • 最后一个结点的指针域为空（NULL）
  • 循环链表
  • 首尾相连的链表，最后一个结点的指针域由NULL改为指向表头结点
  • 双链表
  • 在每个结点增加一个指向其直接前驱的指针域prior

3、限定性线性表--栈与队列

栈

• 定义：
  • 插入和删除操作仅在表的一端操作（栈顶）
• 栈顶位置动态变化，有一个栈顶指针
• 操作
  • 插入和删除：进栈和出栈
  • 后进先出的原则（LIFO）
• 存储结构
  • 顺序栈
  • 用一组连续的存储单元依次存放自栈底到栈顶的数据元素
  • 设一个位置指针top（栈顶指针），通常top=-1表示空栈
  • 链栈
  • 带头结点的单链表来实现
  • 链表的表头指针就作为栈顶指针
• 递归
  • 在函数执行过程中直接或间接调用自己的函数称为递归函数
  • 使用条件
  • 原问题可以分解成类似的子问题
  • 子问题有直接解
  • 设计方法
  • 寻找分解方法：将原问题分解
  • 设计递归出口；确定递归终止的条件
  • 实现过程
  • 递归进层
    • 保留本层参数与返回地址
    • 为被调用函数的局部变量分配存储区，给下层函数赋值
    • 将程序转移到被调函数的入口
  • 递归退层
    • 保存被调函数的计算结果
    • 释放被调函数的数据区，恢复上层参数
    • 依照被调函数保存的返回地址，将控制转回调用函数
  • 特点
  • 分而治之，将复杂问题简单化
  • 算法的效率较低

队列

• 只允许在表的一端（队尾）插入元素，而在另一端（队头）删除元素
• 先进先出（FIFO）的特点
• 存储表示
  • 链队列
  • 带头结点的链表结构，并且设置一个队头指针和队尾指针，队头指针指向头结点，队尾指针指向最后一个元素
  • 循环队列
  • 用一组连续的存储单元依次存放队头到队尾的元素，设置front和rear指针

4、串

字符串

• 由零个或多个字符组成的有限序列
• 传值必须由引号括起来
• 主串
  • 包含子串的串
• 子串
  • 串中任一个连续的字符组成的子序列

存储实现

• 定长顺序串
  • 将串设计成一种静态结构类型，存储分配是在编译时完成的
  • 当串值序列长度超过最大长度时，将丢弃超出部分
• 堆串
  • 以一组地址连续的存储单元存放串中的字符，存储空间是在执行过程中动态分配的
  • 串名符号表
  • 所有的1串名存储映像构成一个符号表
  • 堆串存储表示
  • 利用堆的自由空间
• 块链串
  • 采用链式存储
  • 一个链表存放一个串值，每个结点存放多个或一个字符，结点称为块，加一个尾指针

5、数组与广义表

数组

• 定义
  • 一维数组即为线性表，二维数组可定义为其数据元素为一维数组的线性表
• 顺序存储
  • 按行序存储
  • 子主题 1
  • 按列序存储
  • 子主题 1
• 特殊矩阵的存储
  • 元素分布具有一定规律的矩阵
  • 三角矩阵
  • 上三角矩阵、下三角矩阵、对称矩阵
  • 稀疏矩阵
  • 矩阵中大多元素为0的矩阵
  • 只存储非零元素

广义表

• 定义
  • 由n个数据元素组成的有限序列，元素可以是单个元素，也可以是一个广义表
• 存储结构
  • 头尾链表存储结构
  • 每个元素由一个结点表示，表头和表尾可以确定惟一的一个广义表
  • 结点
    • 原子结点
    • 标志域
    • 值域
    • 子表结点
    • 标志域
    • 指向表头的指针域
    • 指向表尾的指针域
  • 同层结点链存储结构
  • 原子结点和表结点都由三个域构成

6、树与二叉树

树

• 定义
  • n个结点的有限集合T
• 结点树n
  • n=0：空树
  • n>0
  • 其中必须有一个根节点，它没有直接前驱，有零个或多个直接后继
  • 其余n-1个结点可以划分成m个互不相交的有限集，也称子树，都有一个直接前驱，零个或多个直接后继
• 相关术语
  • 结点
  • 包含一个数据元素及若干指向其他结点的分支信息
  • 结点的度
  • 一个结点的字数个数
  • 叶结点
  • 度为0的结点，即无后继的结点，也称终端结点
  • 分支节点
  • 度不为0的结点，也称非终端结点
  • 树的度
  • 树中所有结点的度的最大值
  • 树的高度
  • 树中所有结点的层次的最大值

二叉树

• 条件
  • 每个结点的度都不大于2
  • 每个节点的孩子结点次序不能任意颠倒
• 存储结构
  • 顺序存储结构
  • 完全二叉树方便，单支二叉树浪费
  • 链式存储结构
  • 设计每个结点至少包含三个域：数据域、左孩域和右孩域

7、图

定义

一种网状数据结构