数据结构详解

1“”数据结构12知识导入全程目标•数据结构的基本概念–逻辑结构–物理结构–运算结构•数据结构的基本实现–堆栈–队列–链表–二叉树23知识讲解3数据结构的基本概念•数据结构是相互之间存在一种或多种特定关系的数据的集合•数据结构是计算机存储、组织数据的方式•数据结构的选择直接影响计算机程序的运行效率(时间复杂度)和存储效率(空间复杂度)•计算机程序设计=算法+数据结构•数据结构的三个层次–抽象层——逻辑结构–结构层——物理结构–实现层——运算结构知识讲解4逻辑结构•集合结构(集)–结构中的数据元素除了同属于一个集合外没有其它关系知识讲解5逻辑结构•线性结构(表)–结构中的数据元素具有一对一的前后关系知识讲解6逻辑结构•树型结构(树)–结构中的数据元素具有一对多的父子关系知识讲解7逻辑结构•网状结构(图)–结构中的数据元素具有多对多的交叉映射关系知识讲解8物理结构•顺序结构–结构中的数据元素存放在一段连续的地址空间中知识讲解9物理结构•顺序结构–随机访问方便，空间利用率低，插入删除不方便知识讲解10物理结构•链式结构–结构中的数据元素存放在彼此独立的地址空间中–每个独立的地址空间称为节点–节点除保存数据外，还需要保存相关节点的地址知识讲解11物理结构•链式结构–插入删除方便，空间利用率高，随机访问不方便知识讲解12逻辑结构与物理结构的关系•每种逻辑结构采用何种物理结构实现，并没有一定之规，通常根据实现的难易程度，以及在时间和空间复杂度方面的要求，选择最适合的物理结构，亦不排除复合多种物理结构实现一种逻辑结构的可能数据结构表树图顺序顺序表(数组)顺序树链表数组链式链式表(链表)链式树知识讲解13运算结构•创建与销毁–分配资源、建立结构、释放资源•插入与删除–增加、减少数据元素•获取与修改–遍历、迭代、随机访问•排序与查找–算法应用知识讲解14数据结构的基本实现•堆栈–基于顺序表的实现–基于链式表的实现•队列–基于顺序表的实现–基于链式表的实现•链表–双向线性链表的实现•二叉树–有序二叉树(二叉搜索树)的实现知识讲解15堆栈•后进(压入/push)先出(弹出/pop)知识讲解16实现基于顺序表的堆栈•初始化空间、栈顶指针、判空判满知识讲解17实现基于链式表的堆栈•动态分配、栈顶指针、注意判空18知识讲解18队列•先进(压入/push)先出(弹出/pop)知识讲解19实现基于顺序表的队列•初始化空间、前弹后压、循环使用、判空判满知识讲解20实现基于链式表的队列•动态分配、前后指针、注意判空21知识讲解21链表•地址不连续的节点序列，彼此通过指针相互连接•根据不同的结构特征，将链表分为：–单向线性链表–单向循环链表–双向线性链表–双线循环链表–数组链表–链表数组–二维链表知识讲解22链表•单向线性链表知识讲解23链表•单向循环链表知识讲解24链表•双向线性链表知识讲解25链表•双向循环链表知识讲解26链表•数组链表知识讲解27链表•链表数组知识讲解28链表•二维链表知识讲解29实现双向线性链表•结构模型知识讲解30实现双向线性链表•插入节点知识讲解31实现双向线性链表•删除节点32知识讲解32二叉树•树形结构的最简模型，每个节点最多有两个子节点•每个子节点有且仅有一个父节点，整棵树只有一个根节点•具有递归的结构特征，用递归的方法处理，可以简化算法•三种遍历序–前序遍历：D-L-R–中序遍历：L-D-R–后序遍历：L-R-D知识讲解33二叉树•二叉树的一般形式–根节点、枝节点和叶节点–父节点和子节点–左子节点和右子节点–左子树和右子树–大小和高度(深度)知识讲解34二叉树•满二叉树–每层节点数均达到最大值–所有枝节点均有左右子树知识讲解35二叉树•完全二叉树–除最下层外，各层节点数均达到最大值–最下层的节点都连续集中在左边知识讲解36二叉树的存储结构•顺序存储–从上到下、从左到右，依次存放–非完全二叉树需用虚节点补成完全二叉树知识讲解37二叉树的存储结构•链式存储–二叉链表，每个节点包括三个域，一个数据域和两个分别指向其左右子节点的指针域知识讲解38二叉树的存储结构•链式存储–三叉链表，每个节点包括四个域，一个数据域、两个分别指向其左右子节点的指针域和一个指向其父节点的指针域知识讲解39实现有序二叉树•有序二叉树亦称二叉搜索树，若非空树则满足：–若左子树非空，则左子树上所有节点的值均小于等于根节点的值–若右子树非空，则右子树上所有节点的值均大于等于根节点的值–左右子树亦分别为有序二叉树•基于有序二叉树的排序和查找，可获得O(logN)级的平均时间复杂度