2023-08-04 05:24来源：m.sf1369.com作者：宇宇
宁波大学的数据结构建议，按照王道408中的数据结构进行复习，可以不断地练习和代码记忆数据结构，不是很难。
第一章：数据结构概述
一、什么是数据结构
1、作者开篇谈到：
一般来说解决一个具体的问题时，大致需要经过下列几个步骤：首先要从具体的问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编写出程序代码，进行测试、调整直至得到最终的解决方案。
总结为：现实中具体的问题—>数学模型—>算法程序—>解决方案
动作为：抽象提取、设计编码、测试调整
2、数学角度阐述：
寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。
3、定义数据结构：
描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构，因此，简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科，用一句话来说就是，数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
研究对象：1、集合2、线性结构3、树形结构4、图状结构（网状结构）
结构分类：1、数据的逻辑结构2、数据的物理结构（存储结构）
关系表示：1、顺序映像2、非顺序映像，两者分别对应为顺序存储结构、链式存储结构
二、算法和算法分析
1、算法的五个特性：有穷性、确定性、可行性、输入和输出
2、算法设计的要求：正确性、可读性、健壮性以及效率与低存储量需求
3、算法的度量：时间复杂度和空间复杂度
总结：编写代码设计算法时候首先先考虑算法的正确性，确保程序能够满足要求，在正确性的前提下再进一步考虑算法的可读性、健壮性、拓展性以及算法的效率等。
第二章：线性表
一、线性表的定义
线性结构的特点是：在数据元素的非空有限集中（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中每个数据元素均只有一个前驱；（4）除最后一个元素之外，集合中每个数据元素均只有一个后继。
线性表是最常用并且最简单的一种数据结构，简单来说，一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，既可以是一个数也可以是一个符号等等。
二、线性表的操作
线性表是一个相当灵活的数据结构，它的长度可根据需要增长或者缩短，即对线性表的数据元素不但可以进行访问，还可以进行插入和删除等操作。线性表存储方式有两种，顺序存储和链式存储，下面通过代码进行简单模拟操作。
第三章：栈和队列
栈和队列是两种重要的线性结构，从数据结构的角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限制的线性表，因此可以称为限定性的数据结构。
一、栈的定义
栈是限定在表尾进行插入或删除操作的线性表，栈的特定是先进后出。栈的存储方式有两种，一种是顺序栈另外一种是链式栈，下面只通过代码简单模拟栈的操作。
二、栈的应用
栈的应用主要有数制转换、括号匹配的检验、迷宫问题求解以及表达式求值。另外栈递归实现的经典例子有八皇后问题、汉诺塔问题等。
三、队列的定义
队列和栈有点不同，队列是一种先进先出得线性表，它只能够在表的一端进行插入另外一头进行删除操作。队列在程序设计中比较常见的例子是操作系统中的作业排队。双端队列、循环队列有时间再进一步演进，暂时先了解些基本概念。
第四章：串
一、串的定义
计算机上的非数值处理的对象基本上都是字符串数据。串是由零个或多个字符组成的有限序列。串中字符的数目成为字符串的长度，零个字符的串成为空串。串的模式匹配算法经典的是KMP算法。
第五章：数组和广义表
一、数组和广义表定义
数组是读者已经很熟悉的一种数据类型，几乎所有的程序设计语言都把数组类型设为固有的类型。数组的应用中涉及到一个比较重要的数学知识，矩阵的压缩存储问题。广义表是线性表的推广，在java开发中好像用得不多，有时间再进一步学习。
第六章：树和二叉树
一、树的定义和基本操作
1、树的特点
树是一个结点n的有限集，在任意一颗树非空树中：1、有且只有一个根结点，2、当n>1时，其余结点分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，叫做根的子树。
关键词组：有限集、唯一性、对称性、递归性。
基本术语：结点、度、叶子、分支结点、孩子、双亲、兄弟、层次以及深度等。
基本操作：构造初始化树、取得左子树或右子树、插入结点、删除结点、树的遍历等等。
2、线性结构VS树结构
线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。
二、二叉树的定义
1、二叉树的特点
每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能颠倒。
关键词组：对称、次序
2、二叉树的具体实例
满二叉树、完全二叉树、平衡二叉树等，具体区别参考书籍教材详解。
3、二叉树的存储结构
主要分为两种方式，一类是顺序结构（可使用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素），另外一类是链式存储结构，这两种存储方式各有利弊，具体要看实际操作的场合。
4、二叉树的遍历方式
遍历方案有先序遍历、中序遍历、后序遍历，具体的算法实现有递归的算法和非递归的算法。二叉树线索化初步了解，待有需要再进一步编码实战。
三、树的应用实例
1、树和森林
树的存储表示方式主要有三种：双亲表示法、孩子表示法以及孩子兄弟法。树和森林之间的相互转换也比较简单，不过多分析。
2、树的应用
（1）树的等价问题：离散数学中引入的等价和等价类的概念
（2）赫夫曼树及其应用（赫夫曼树又叫最优二叉树）
（3）回溯法与树的遍历
（4）树的计数
四、代码实战参考题目
1、构造/初始化一颗二叉树
2、递归/非递归中序遍历该二叉树
3、二叉树和森林的相互转换模拟实现 //具体看存储的方式，比如孩子兄弟法
4、对平衡二叉树进行增加、删除结点操作
补充：参考学习资料： 赫夫树、赫夫曼编码实现
