数据结构笔记.pdf

《数据结构笔记.pdf》由会员分享，可在线阅读，更多相关《数据结构笔记.pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、/2018/5/23/2018/5/23数据结构概述：数据结构概述：预备知识模块一：线性结构模块一：线性结构连续存储连续存储 数组数组 离散结构离散结构 链表链表 线性结构的两种常见应用之一线性结构的两种常见应用之一栈堆栈栈堆栈线性结构的两种常见应用之二线性结构的两种常见应用之二队列队列专题：递归专题：递归 1.1+2.+100 的和模块二：非线性结构模块二：非线性结构树图模块三：查找和排序模块三：查找和排序折半查找排序：冒泡插入选择快速排序补录：补录：JavaJava 中容器和数据结构相关知识中容器和数据结构相关知识 Iterator 接口 Map 哈希表严蔚敏-高一凡高一凡-黄国瑜归并排序

2、/2018/5/24/2018/5/24数据结构概述数据结构概述定义定义我们如何把现实中大量而复杂的问题以特定的数据类型特定的数据类型和特定的存储结构特定的存储结构保存到主存储器内存中，以及在此基础上为实现某个功能比方查找或删除某个元素，对所有元素进行排序而执行的相应操作，这个相应操作叫做算法。特定的数据类型特定的数据类型:个体如何保存个体如何保存特定的存储结构特定的存储结构:个体与个体的关系如何保存个体与个体的关系如何保存数据结构数据结构=个体的存储个体的存储+个体关系的存储个体关系的存储算法狭义算法狭义=对存储数据的操作对存储数据的操作算法：即解题的方法和步骤衡量算法的标准1.时间复杂度重

3、要大概程序要执行的次数，而非执行的时间2.空间复杂度重要算法执行过程中大概所占用的最大内存3.难易程度4.健壮性数据结构的地位数据结构是软件中最核心的课程。程序=数据的存储+数据的操作+可以被电脑执行的语言预备知识：预备知识：指针指针结构体结构体动态内存的分配和释放动态内存的分配和释放指针：指针：指针的重要性:表示一些复杂的数据结构快速的传送数据使函数返回一个以上的值能否直接访问硬件能够方便的使用数组和字符串是理解面向对象语言中引用的基础指针是指针是 C C 语言的灵魂语言的灵魂定义地址内存单元的编号从 0 开始的非负整数范围 0-FFFFFFFF【0 到 4G-1】注：无论一个变量有多大，其

4、地址只用第一个字节的地址表示，均只占四个字节。指针指针就是地址指针就是地址地址就是指针地址就是指针指针变量就是存放内存单元地址的变量指针本质上就是一个操作受限的非负整数分类1、基本类型指针【略】基本概念int i=10;int*p=&i;/等价于 int*p;p=&i;详解这两部操作：1p 存放了 i 的地址，所以我们说 p 指向了 i2p 和 i 是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值3p p 指向指向 i i，*p*p 就是就是 i i 变量本身变量本身。更形象的说所有出现*p 的地方都可以换成 i，所有出现 i 的地方都可以换成*p4int*p，不是定义了

5、*p 的参数，而是定义了一个变量p，为 int*类型。总结：1、如何一个指针变量(假定为 p)存放了某个普通变量(假定为 i)的地址，那我们就可以说：“p 指向了 i”，但 p 与 i 是两个不同的变量，修改 p 的值不影响 i 的值，修改 i 的值不影响 p 的值.2、*p 等价于 i 或者说*p 可以与 i 在任何地方互换3、如果一个指针变量指向了某个普通变量，则*指针变量就完全等价于该普通变量注意：指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址普通变量前不能加*常量和表达式前不能加&如何通过被调函数修改主调函数中普通变量的值 实参为相关变量的地址 形参为以该

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

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

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

9、须加数据类型*,表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。如：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*型的地址，更准确的说是把第一个字节的地址转化为 8

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

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

12、：分类：变量名：变量名：frontfront头部头部和和 rear rear尾部尾部链式队列链式队列-用链表实现静态队列静态队列-用数组实现注：在队首的位置删除元素，然后队首指针指向下一个元素在队尾的位置添加元素，然后队尾指针指向下一个元素【重点】【重点】RearRear 指向的是队列最后一个元素的下一个元素指向的是队列最后一个元素的下一个元素【重点】【重点】FrontFront 指向的是队列的第一个元素指向的是队列的第一个元素队列算法：队列算法：入队出队队列的具体应用：队列的具体应用：所有和时间及有关的操作都有队列的影子。静态队列：静态队列：注：将数组的部分功能给去掉，然后再加入一些功能。静

13、态队列通常都必须是循环队列。静态队列通常都必须是循环队列。问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。循环队列的讲解：循环队列的讲解：1.1.静态队列为什么必须是循环队列静态队列为什么必须是循环队列问题问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用只能被使用一次而不能重复被使用。只能增不能减。解决方法解决方法：当 front 和 rear 移动到顶部队尾时，下一次移动时可以让它再

14、移动到底部队首，首尾相连，这实际就是循环队列。2.2.循环队列需要几个参数来确定循环队列需要几个参数来确定需要两个参数来确定 front front rear rear3.3.循环队列各个参数的含义循环队列各个参数的含义这两个参数在不同场合有不同的含义建议初学者先记住，然后慢慢体会1 1）队列初始化队列初始化front 和 rear 的值都是 02 2）队列非空队列非空Front 代表的是队列的第一个元素Rear 代表的是队列的最后一个有效元素的下一个元素3 3）队列空队列空front 和 rear 的值相等，但不一定为 04.4.循环队列入队伪算法讲解循环队列入队伪算法讲解两步完成，详解见图

15、5.5.循环队列出队伪算法讲解循环队列出队伪算法讲解6.6.如何判断循环队列是否为空如何判断循环队列是否为空如果 front 和 rear 的值相等，则该队列就一定为空。7.7.如何判断循环队列是否为满如何判断循环队列是否为满预备知识：预备知识：front 的值可能比 rear 大，也完全有可能比 rear 小，当然也可能相等。两种方式：两种方式：2.少用一个元素【通常使用第二种元素通常使用第二种元素】队列中有 n 个元素，只要放到 n-1 个元素，即认为队列已满。/2018/5/21/2018/5/21专题：递归专题：递归定义：一个函数自己直接或间接调用自己递归满足的三个条件：递归满足的三个

16、条件：1.递归必须得有一个明确的终止条件2.递归的值可以是递增的，但所处理的数据规模必须在递减n-n-1-n-23.这个转化必须是可解的循环和递归循环和递归所有的循环都可以用递归实现，所有的循环都可以用递归实现，但所有的递归不一定都可以用循环实现。但所有的递归不一定都可以用循环实现。递归：递归：循环：循环：易于理解不易理解速度慢速度快存储空间大步骤麻烦存储空间小n-n-1-n-2-1举例：举例：1.求阶乘2.1+2+100 的和3.汉诺塔4.走迷宫递归的应用：递归的应用：树和森林就是以递归的方式定义的树和图的很多算法就是以递归来实现的很多数学公式就是以递归的方式定义的(例如：斐波拉切数列)线性

17、结构总复习：线性结构总复习：逻辑结构逻辑结构线性 数组链表栈和队列是一种特殊的线性结构，算线性结构的应用非线性 树图物理结构物理结构/2018/5/22/2018/5/22模块二：非线性结构模块二：非线性结构树树定义：定义：专业定义：专业定义：1.有且只有一个称为根的节点2.有假设干个互补相交的子树，这些子树本身也是一棵树通俗定义：通俗定义：1.树是由节点和边组成2.每个节点只有一个父节点但可以有多个子节点3.但有一个节点例外，该节点没有父节点，此节点成为根节点。专业术语专业术语节点节点父节点父节点子节点子节点子孙子孙堂兄弟堂兄弟深度深度：从根节点到最底层节点的层数称之为深度根节点是第一层叶子

18、节点叶子节点：没有子节点的节点。非终端节点非终端节点：实际就是非叶子节点。度度：子节点的个数成为度。分类：分类：一般树：任意一个节点的子节点的个数都不受限制二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改。分类：一般二叉树满二叉树完全二叉树的特例在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树完全二叉树用数组存储树时，必须是完全二叉树如果只是删除了满二叉树最底层最后边的连续假设干个节点，这样形成的二叉树就是完全二叉树。优点优点森林：n 个互不相交的树的集合树的存储：树的存储：二叉树的存储连续存储将二叉树补充为完全二叉树以数组的形式存储时，如果根据只保存有效节

19、点的形式，无法推出全树的样子。优点：查找某个节点的父节点和子节点也包括判断有没有父节点和子节点速度很快。缺点：耗用空间内存过大链式存储一般树的存储双亲表示法求父节点方便把每一个节点编号，然后在每一个节点后标记出其父节点的编号孩子表示法求子节点方便把每一个子节点都写在每一个节点之后。双亲孩子表示法求父节点和子节点都方便把每一个节点编号，然后在每一个节点后标记出其父节点的编号，再把每一个子节点写在之后。二叉树表示法把一个普通树转化为二叉树来存储。具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子左指针域指向它的第一个孩子右指针域指向它下一个兄弟右指针域指向它下一个兄弟只要满足此条件，就

20、可以把一个普通树转化为二叉树一个普通树转化成的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再将二叉树存储先把森林转化为二叉树，再将二叉树存储具体转换方法：其他树的根节点其他树的根节点当成第一颗树根节点的第一颗树根节点的兄弟兄弟左指针域指向它的第一个孩子左指针域指向它的第一个孩子右指针域指向它下一个兄弟右指针域指向它下一个兄弟只要满足此条件，就可以把一片森林转化为二叉树操作：操作：遍历先序遍历先访问根节点中左右中左右先访问根节点根节点再先序访问左子树左子树再先序访问右子树右子树中序遍历中间访问根节点左中右左中右中序遍历左子树再访问根节点再中序遍历右子树后序遍历最后访问根节点左右中先后序遍

21、历左子树再后序遍历右子树再访问根节点只知道一颗二叉树的一种遍历方式是无法复原二叉树的原貌的。只知道一颗二叉树的一种遍历方式是无法复原二叉树的原貌的。已知两种遍历序列求原始二叉树先中可以中后可以先后不可以必须有一个中序必须有一个中序已知先序和中序求后序例 1：先序：ABCDEFGH中序：BDCEAFHG求后序讲解：先序中第一个出现的一定是根节点，即 A；所以中序中根节点 A 左边的BDCE 是左子树，右边的 FHG 是右子树；然后在先序序列中看左子树 BDCE 中哪个先出现，先出现的为根节点，即 B；因为中序中 DCE 在 B 的右侧，所以 DCE是 B 的右子树，哪个在先序中先出现为根节点，即

22、 C；中序中，C 左侧是 D，右侧是 E，即为 C 的左右子节点；A 右子树方法类同。方法总结：由先序找到根节点先出现为根节点，由先序找到根节点先出现为根节点，由中序找到根节点的左右子树左侧左子树，右侧右子树。由中序找到根节点的左右子树左侧左子树，右侧右子树。后序：DECBHGFA例 2:先序:ABDGHCEFI中序:GDHBAECIF求后序:GHDBEIFCA已知中序和后序求先序已知中序和后序求先序例：中序：BDCEAFHG后序：DECBHGFA求先序：讲解：后序中第一个出现的一定是根节点，即 A；所以中序中根节点 A 左边的BDCE 是左子树，右边的 FHG 是右子树；然后在后序序列中看左

23、子树 BDCE 中哪个后出现，后出现的为根节点，即 B；因为中序中 DCE 在 B 的右侧，所以 DCE是 B 的右子树，哪个在后序中后出现为根节点，即 C；中序中，C 左侧是 D，右侧是 E，即为 C 的左右子节点；A 右子树方法类同。方法总结：由后序找到根节点后出现为根节点，由后序找到根节点后出现为根节点，由中序找到根节点的左右子树左侧左子树，右侧右子树。由中序找到根节点的左右子树左侧左子树，右侧右子树。先序:ABCDEFGH/2018/5/23/2018/5/23应用：应用：树是数据库中数据组织一种重要形式。操作系统子父进程的关系本身就是一棵树。面对对象语言中类的继承关系本身就是一棵树。赫夫曼树。