数据结构补充.docx

《数据结构补充.docx》由会员分享，可在线阅读，更多相关《数据结构补充.docx（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构概述：预备知识模块一：线性结构连续存储数组 离散结构链表线性结构的两种常见应用之一栈（堆栈） 线性结构的两种常见应用之二队列专题：递归1.1+2+100 的和2. 求阶乘3. 汉诺塔4. 走迷宫模块二：非线性结构树图模块三：查找和排序折半查找排序：冒泡插入选择快速排序归并排序补录：Java 中容器和数据结构相关知识Iterator 接口Map 哈希表数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。特定的数据类型:个体

2、如何保存特定的存储结构:个体与个体的关系如何保存数据结构 = 个体的存储 + 个体关系的存储算法（狭义） = 对存储数据的操作算法：即解题的方法和步骤衡量算法的标准1. 时间复杂度重要大概程序要执行的次数，而非执行的时间2. 空间复杂度重要算法执行过程中大概所占用的最大内存3. 难易程度4. 健壮性数据结构的地位数据结构是软件中最核心的课程。程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言预备知识：指 针 结构体动态内存的分配和释放指针：指针的重要性:表示一些复杂的数据结构快速的传送数据使函数返回一个以上的值能否直接访问硬件能够方便的使用数组和字符串是理解面向对象语言中引用的基

3、础指针是 C 语言的灵魂定义地址内存单元的编号从 0 开始的非负整数范围 0-FFFFFFFF 【0 到 4G-1】注：无论一个变量有多大，其地址只用第一个字节的地址表示， 均只占四个字节。指针指针就是地址地址就是指针指针变量就是存放内存单元地址的变量指针本质上就是一个操作受限的非负整数分类1、基本类型指针【略】基本概念int i=10;int *p = &i; /等价于 int *p; p = &i;详解这两部操作：1）p 存放了 i 的地址，所以我们说 p 指向了 i2）p 和 i 是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值3）p 指向 i，*p 就是 i 变量

4、本身。更形象的说所有出现 *p 的地方都可以换成 i，所有出现 i 的地方都可以换成*p4）int * p，不是定义了*p 的参数，而是定义了一个变量 p，为 int *类型。总结：1、如何一个指针变量(假定为 p)存放了某个普通变量(假定为 i)的地址，那我们就可以说：“p 指向了 i”， 但 p 与 i 是两个不同的变量，修改 p 的值不影响 i 的值，修改 i 的值不影响 p 的值.2、*p 等价于 i 或者说*p 可以与 i 在任何地方互换3、如果一个指针变量指向了某个普通变量，则*指针变量 就完全等价于该普通变量注意：指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存

5、单元的地址普通变量前不能加*常量和表达式前不能加&如何通过被调函数修改主调函数中普通变量的值 实参为相关变量的地址 形参为以该变量的类型为类型的指针变量 在被调函数中通过 *形参变量名 的方式就可以修改主函数相关变量的值Eg:void f(int * p)/II*p = 100;/IIIint main(void)int i = 9; f(&i);/Iprintf(“i = %dn”, i);指针和数组的关系指针 和 一维数组数组名一维数组名是个指针常量，它存放的是一维数组第一个元素的地址， 它的值不能被改变一维数组名指向的是数组的第一个元素下标和指针的关系ai *(a+i)*a+3 = a0

6、+3假设指针变量的名字为 p则 p+i 的值是 p+i*(p 所指向的变量所占的字节数) 指针变量的运算指针变量不能相加，不能相乘，不能相除 如果两指针变量属于同一数组，则可以相减指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围p+i 的值是 p + i*(p 所指向的变量所占的字节数)p-i 的值是 p - i*(p 所指向的变量所占的字节数) p+p+1p-p-1举例如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】两个参数存放数组首元素的指针变量 存放数组元素长度的整型变量所有的指针变量只占 4 个子节用第一个字节的地址表示整个变量的地址动态内存分配和释放：

7、程序在运行过程中可以动态的增加或减少内存分配 动态构造一维数组假设动态构造一个 int 型数组int *p = (int *)malloc(int len);1、malloc 只有一个 int 型的形参，表示要求系统分配的字节数2、malloc 函数的功能是请求系统 len 个字节的内存空间，如果请求分配成功， 则返回第一个字节的地址，如果分配不成功，则返回 NULL3、malloc 函数能且只能返回第一个字节的地址，所以我们需要把类型不一样。即所占的字节数也不确定这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此 malloc 前面必须加（数据类型 *）, 表

8、示把这个无实际意义的第一个字节的地址转化为相应类型的地址。如：int *p = (int *)malloc(50);表示将系统分配好的 50 个字节的第一个字节的地址转化为 int *型的地址， 更准确的说是把第一个字节的地址转化为四个字节的地址，这样 p 就指向了第一个的四个字节，p+1 就指向了第 2 个的四个字节，p+i 就指向了第 i+1 个的 4 个字节。p0就是第一个元素， pi就是第 i+1 个元素double *p = (double *)malloc(80);表示将系统分配好的 80 个字节的第一个字节的地址转化为 double *型的地址，更准确的说是把第一个字节的地址转化

9、为 8 个字节的地址，这样 p 就指向了第一个的 8 个字节，p+1 就指向了第 2 个的 8 个字节，p+i 就指向了第 i+1 个的 8 个字节。p0就是第一个元素， pi就是第 i+1 个元素free（p）：动态分配的内存，必须 free()释放，系统不会自动释放。释放 p 所指向的内存，而不是释放 p 本身所占用的内存【重点：动态分配数组内存】int * pArr = (int *) malloc (sizeof(int) * len);(最后一个*代表了乘分配了 4 * len 个字节)模块一：线性结构【把所有的结点用一根直线穿起来】连续存储数组1. 什么叫数组元素类型离散结构链表线

10、性结构中两种常用应用之一栈定义一种可以实现“先进后出”的存储结构只能从栈尾（栈顶）进和出。栈类似于箱子，局部变量都是在栈中存储的。分类静态栈【以数组为内核】动态栈【以链表为内核】算法出栈pTop 向下移一个，pBottom 不变压栈（入栈）pTop 向上移一个，pBottom 不变应用函数调用中断表达式求值（例如计算器的编写）内存分配缓冲处理/2018/5/20线性结构中两种常用应用之二队列定义：一种可以实现“先进先出”的存储结构分类：变量名：front（头部）和rear（尾部）链式队列-用链表实现静态队列-用数组实现注：在队首的位置删除元素，然后队首指针指向下一个元素 在队尾的位置添加元素，

11、然后队尾指针指向下一个元素【重点】Rear 指向的是队列最后一个元素的下一个元素【重点】Front 指向的是队列的第一个元素队列算法： 入队出队队列的具体应用：所有和时间及有关的操作都有队列的影子。静态队列：注：将数组的部分功能给去掉，然后再加入一些功能。静态队列通常都必须是循环队列。问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。循环队列的讲解：1. 静态队列为什么必须是循环队列问题：如果按照普通的数组来存储队列的话。每次删掉一个元素， 头部指针都会指向下一个元素，会造成原来元素

12、的位置空间浪费， 只能被使用一次而不能重复被使用。只能增不能减。解决方法：当 front 和 rear 移动到顶部（队尾）时，下一次移动时可以让它再移动到底部（队首），首尾相连，这实际就是循环队列。2. 循环队列需要几个参数来确定需要两个参数来确定front rear3. 循环队列各个参数的含义这两个参数在不同场合有不同的含义建议初学者先记住，然后慢慢体会1）队列初始化front 和 rear 的值都是 0 2）队列非空Front 代表的是队列的第一个元素Rear 代表的是队列的最后一个有效元素的下一个元素3）队列空front 和 rear 的值相等，但不一定为 04. 循环队列入队伪算法讲解

13、两步完成，详解见图5. 循环队列出队伪算法讲解6. 如何判断循环队列是否为空 如果 front 和 rear 的值相等， 则该队列就一定为空。7. 如何判断循环队列是否为满预备知识：front 的值可能比 rear 大， 也完全有可能比 rear 小， 当然也可能相等。两种方式：1. 多增加一个标志位参数2. 少用一个元素【通常使用第二种元素】队列中有 n 个元素，只要放到 n-1 个元素，即认为队列已满。/2018/5/21专题：递归定义：一个函数自己直接或间接调用自己递归满足的三个条件：1. 递归必须得有一个明确的终止条件2. 递归的值可以是递增的，但所处理的数据规模必须在递减（n-n-1

14、-n-2）3. 这个转化必须是可解的循环和递归所有的循环都可以用递归实现，但所有的递归不一定都可以用循环实现。递归：循环：易于理解不易理解速度慢速度快存储空间大（步骤麻烦）存储空间小n - n-1 - n-2 - - 1举例：1. 求阶乘2. 1+2+100 的和3. 汉诺塔4. 走迷宫递归的应用：树和森林就是以递归的方式定义的树和图的很多算法就是以递归来实现的很多数学公式就是以递归的方式定义的(例如：斐波拉切数列)线性结构总复习：逻辑结构线性数组链表栈和队列是一种特殊的线性结构，算线性结构的应用非线性树图物理结构模块二：非线性结构树定义：专业定义：1. 有且只有一个称为根的节点2. 有若干个

15、互补相交的子树，这些子树本身也是一棵树通俗定义：1. 树是由节点和边组成2. 每个节点只有一个父节点但可以有多个子节点专业术语3. 但有一个节点例外，该节点没有父节点，此节点成为根节点。节点父节点子节点子孙堂兄弟深度：从根节点到最底层节点的层数称之为深度（根节点是第一层） 叶子节点：没有子节点的节点。非终端节点：实际就是非叶子节点。度：子节点的个数成为度。分类：一般树：任意一个节点的子节点的个数都不受限制二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改。分类：一般二叉树满二叉树（完全二叉树的特例）在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树完全二叉树（用

16、数组存储树时，必须是完全二叉树）如果只是删除了满二叉树最底层最后边的连续若干个节点，这样形成的二叉树就是完全二叉树。优点：1.根据节点编号可以知道在第几层2.可以知道父节点和子节点森林：n 个互不相交的树的集合树的存储：二叉树的存储连续存储将二叉树补充为完全二叉树以数组的形式存储时，如果根据只保存有效节点的形式，无法推出全树的样子。优点：查找某个节点的父节点和子节点（也包括判断有没有父节点和子 节点）速度很快。缺点：耗用空间内存过大链式存储一般树的存储双亲表示法（求父节点方便）把每一个节点编号，然后在每一个节点后标记出其父节点的编号孩子表示法（求子节点方便）把每一个子节点都写在每一个节点之后。

17、双亲孩子表示法（求父节点和子节点都方便）把每一个节点编号，然后在每一个节点后标记出其父节点的编号， 再把每一个子节点写在之后。二叉树表示法把一个普通树转化为二叉树来存储。具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子右指针域指向它下一个兄弟只要满足此条件，就可以把一个普通树转化为二叉树一个普通树转化成的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再将二叉树存储具体转换方法：1. 设法保证其他树的根节点当成第一颗树根节点的兄弟2. 设法保证其他任意一个节点的左指针域指向它的第一个孩子右指针域指向它下一个兄弟只要满足此条件，就可以把一片森林转化为二叉树操作：遍历先序遍历先访

18、问根节点中左右 先访问根节点再先序访问左子树再先序访问右子树三 竺I X花式 (Q) 帮 助(lj)F4一般树转化为二叉树的方法是设法保证任总一个节点的左指针域指向它的第右指针域指向它的下只要筋满足此条件，饮可森林的存储先把森林转化为 二叉树，再存储二叉树J 去：树操作遍历光序追历先访问根节点再先庄访闰左子树再凭序访问 右子树AB .DeEFu中序讷历后序遍历已知两种遍历序列求睬始二叉树J-m 1中文忡 邸 1叫11i1 浩振结构E .E_：过我旦已 L _.J志 “心 K 负 曜 235严 飞 （矿 括入（I广 格梦 立 妇?黔l 囡 生空 归 引.:.J 三严 L2 .:.J 下 且 迫

19、F 归 sM！ 3 ,五森；上：为 叉；“ 石 卢 心 飞 二叉树揉作迭ffj先序迭 历先访问根节点再先序访问 左千树再先序访问 右千树中序遇历后序迪历勹、气已知两种遍历序列求陌始 叉树应用）去 ! Ap cDE 一t心 M 伈sJIJ.查找和排序乍在找平I1! 汁因数和结构大 已F 我自己 先序遍历举，|中序遍历中间访问根节点左中右 中序遍历左子树再访问根节点再中序遍历右子树后序遍历最后访问根节点左右中 先后序遍历左子树再后序遍历右子树再访问根节点只知道一颗二叉树的一种遍历方式是无法还原二叉树的原貌的。已知两种遍历序列求原始二叉树先中（可以）中后（可以）先后（不可以）必须有一个中序已知先序和

20、中序求后序例 1：先序：ABCDEFGH中序：BDCEAFHG求后序讲解：先序中第一个出现的一定是根节点，即 A；所以中序中根节点 A 左边的BDCE 是左子树，右边的 FHG 是右子树；然后在先序序列中看左子树 BDCE 中哪个先出现，先出现的为根节点，即 B；因为中序中 DCE 在 B 的右侧，所以 DCE 是 B 的右子树，哪个在先序中先出现为根节点，即 C；中序中，C 左侧是 D，右侧是 E，即为 C 的左右子节点；A 右子树方法类同。方法总结：由先序找到根节点（先出现为根节点），由中序找到根节点的左右子树（左侧左子树，右侧右子树）。后序：DECBHGFA例 2:先 序 : ABDGH

21、CEFI 中 序 : GDHBAECIF 求后序: GHDBEIFCA已知中序和后序求先序例：中序：BDCEAFHG后序：DECBHGFA求先序：讲解：后序中第一个出现的一定是根节点，即 A；所以中序中根节点 A 左边的BDCE 是左子树，右边的 FHG 是右子树；然后在后序序列中看左子树 BDCE 中哪个后出现，后出现的为根节点，即 B；因为中序中 DCE 在 B 的右侧，所以 DCE 是 B 的右子树，哪个在后序中后出现为根节点，即 C；中序中，C 左侧是 D，右侧是 E，即为 C 的左右子节点；A 右子树方法类同。方法总结：由后序找到根节点（后出现为根节点），由中序找到根节点的左右子树（左侧左子树，右侧右子树）。先序: ABCDEFGH应用：树是数据库中数据组织一种重要形式。操作系统子父进程的关系本身就是一棵树。面对对象语言中类的继承关系本身就是一棵树。赫夫曼树。