关于数据结构的泛谈

关于数据结构的泛谈1. 数据结构狭义：数据结构是专门研究数据存储问题的数据的存储包含两个方面：个体的存储 + 个体关系的存储从某个角度而言，数据存储最核心的问题是对个体关系的存储，个体的存储可以忽略不计广义：数据结构既包含数据的存储也包含对数据的操作对存储的数据的操作就是算法2. 算法狭义：算法和数据的存储方式密切相关广义：算法和数据的存储结构无关（也就是泛型的思想：对于同一种逻辑结构，无论该逻辑结构的物理存储是什么样子的，我们都可以对它执行相同的操作）3. 数据结构的分类逻辑结构线性数组链表栈和队列是特殊的线性结构（操作受限）非线性树图物理结构线性一维的连续单元（内存）4. 数据的存储结构线性连续存储（数组）优点存取速度很快缺点插入、删除操作效率很低事先必须知道数组的长度需要大块连续的内存块离散存储（链表）优点空间没有限制（不需要一块连续的内存）插入、删除操作效率很高缺点存取速度很慢线性结构的应用 1 栈定义一种可以实现“先进后出”的存储结构分类静态栈动态栈算法出栈压栈应用函数调用（函数的嵌套）中断表达式求值内存分配缓冲处理迷宫线性结构的应用 2 队列定义一种可以实现“先进先出”的存储结构分类链式队列用链表实现静态队列用数组实现，静态队列通常都是循环队列算法入队出队具体应用所有和时间有关的操作都有队列的影子【专题】递归定义一个函数自己直接或间接调用自己栈与递归的实现1. 当在一个函数运行期间，调用另一个函数时，在运行被调函数之前，系统需要完成 3 件事：将所有实参、返回地址等信息传给被调函数保存给被调函数的局部变量（包括形参）分配存储区域将控制转移到被调函数的入口2. 从被调函数返回调用函数之前，系统也需要完成 3 件工作：保存被调函数的返回结果释放被调函数所占的存储空间依照被调函数保存的返回值地址，将控制转移给调用函数PS：当多个函数迭代调用时，按照“后调用先返回”（后进先出）的规则进行，上述函数之间的传递和控制转移必须借助栈来实现，所以，系统将整个程序运行所需的存储区域安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区域，每当从一个函数退出时，就释放它的存储区域，则当前运行的函数的数据区域必须在栈顶。3. 递归需要满足的 3 个条件1） 递归必须要有一个明确的终止条件2） 该函数所处理的数据规模必须在递减3） 这个转化必须是可解的4. 循环和递归的关系所有的循环都可以转化成递归，但用递归可以解决的问题不一定能用循环解决递归易于理解速度慢所需存储空间大循环不易理解速度快所需存储空间小例子求阶乘求 1+ 2 + 3 + 4 + + 100 的和汉诺塔问题走迷宫应用树和森林就是以递归方式定义的树和图的很多算法都是用递归来实现的很多数学公式就是以递归的方式定义的（如斐波那契数列）非线性树定义专业定义（递归定义）1. 有且只有一个称为根的节点2. 有若干个互不相交的子树，这些子树本身也是一棵树通俗定义1. 树由节点和边组成2. 每个节点只有一个父节点，但可以有多个子节点3. 但有一个节点例外，该节点没有父节点，该节点称为根节点专业术语深度从根节点到最底层节点的层数称为深度（根节点是第一层）度某一节点的度是该节点下子节点的个数分类一般树任意一个节点的子节点的个数都不受限制二叉树任意一个节点的子节点的个数最多两个，且子节点的位置不可更改分类一般二叉树满二叉树在不增加树的层数的前提下，无法再添加一个节点的二叉树完全二叉树如果只删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树森林n 个互不相交的 树的集合存储二叉树的存储连续存储（完全二叉树，把一般二叉树补成完全二叉树）优点查找某个节点的父节点和子节点（判断有没有父、子节点）速度很快缺点耗用内存空间过大链式存储一般树的存储双亲表示法（数组）孩子表示法（边链表）双亲孩子表示法（数组加边链表）二叉树表示法（把一般树转换成二叉树来存储）森林的存储先把森林转换为二叉树，再存储二叉树操作遍历（遍历实质上是把非线性结构转化为线性结构的一种方式，以下三种遍历是三种不同的转化方式，并没有本质区别）先序遍历（根、左、右）中序遍历（左、根、右）后序遍历（左、右、根）已知两种遍历序列，求原始二叉树（已知任意一种序列不能推出原始二叉树，已知先中或者中后可以推出，已知先后不行）具体方法参见视频 71、72 两节，在此不加详述应用树是数据库中数据组织的一种重要形式操作系统子、父进程的关系本身就是一棵树面向对象语言中类的继承关系本身就是一棵树赫（哈）夫曼树图（略）5. 排序排序冒泡排序（相邻位置比较交换，每趟找出一个）插入排序（2 和 1 比插入形成长度为 2 的序列 A，3 和比插入形成长度为的序列，直至结束）选择排序（找出最大（小）的，与第一个位置的元素互换，在找出剩余元素中最大（小）的，与第二个位置的元素互换，直至结束）快速排序（先找出某一元素（一般取第一个元素）的最终位置，这时无序数列被分为两块，再分别对两块继续这样进行排序（递归），直至分成的两块长度为）示例：，-，（需要两个指针、和一个中间变量 temp = 9（第一个元素） ，假定指向，指向,先比较 H 所指向值与temp， H 值大则向前移动 H，直至 H 值小于 temp 时赋值：L 值 = H 值，H 值视为垃圾数字，用“ * ”表示，若 H 值始终大于temp，则当 L 与 H 指向同一元素时一趟排序停止）第一步：,，-,，（7 ，-,（0 temp，赋值：H 值 = L 值，下一步移动 H）第三步：,，-，,（13 > temp，移动 H，2 ,(-5 < temp，移动 L，L 与 H 重合，得到 temp 的最终位置，赋值：L 值（H 值） = temp，一趟排序结束)PS：上述结果是一趟排序的结果（一趟结束条件：L 与 H 重合） ，下一趟对 7,0,8,2，-5 用同样的方法排序（递归） ，下下一趟对 13,10 排序，直至所有待排序的无序列长度为 1 时，排序完成。H 与 L 的移动规则：（本次）谁变（下一次）移谁归并排序（个个比，个个比，个个比，直至结束）排序和查找的关系排序是查找的前提（也就是说排序是重点）