1、/2018/5/23数据结构概述：预备知识模块一：线性结构 连续存储数组 离散结构链表 线性结构的两种常见应用之一 栈（堆栈） 线性结构的两种常见应用之二 队列 专题：递归 1.1+2.+100的和 2.求阶乘 3.汉诺塔 4.走迷宫模块二：非线性结构 树 图模块三：查找和排序 折半查找 排序：冒泡 插入 选择 快速排序 归并排序补录：Java中容器和数据结构相关知识 Iterator接口 Map 哈希表严蔚敏-高一凡-黄国瑜/2018/5/24数据结构概述 定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删
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是完全不同的两个变量，修改其
4、中的任意一个变量的值，不会影响另一变量的值3）p指向i，*p就是i变量本身。更形象的说所有出现 *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+
6、i) *a+3 = a0+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 *型的地址，更准确的说是把第一个字节的地址转化为8个字节的地址，这样p就指向了第一个的8个字节，p+1就指向了
9、第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（尾部） 链式队列-用链表实现 静态队列-用数组实现 注：在队首的位置删除元素，然后队首指针指向下一个元素在队尾的位置添加元素，然后队尾指针指向下一个元素 【重点】Rear指向的是队列最后
11、一个元素的下一个元素【重点】Front指向的是队列的第一个元素队列算法：入队出队队列的具体应用： 所有和时间及有关的操作都有队列的影子。静态队列：注：将数组的部分功能给去掉，然后再加入一些功能。静态队列通常都必须是循环队列。问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。循环队列的讲解：1. 静态队列为什么必须是循环队列问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。解
12、决方法：当front和rear移动到顶部（队尾）时，下一次移动时可以让它再移动到底部（队首），首尾相连，这实际就是循环队列。2. 循环队列需要几个参数来确定需要两个参数来确定 front rear3. 循环队列各个参数的含义这两个参数在不同场合有不同的含义建议初学者先记住，然后慢慢体会1） 队列初始化front和rear的值都是02） 队列非空Front代表的是队列的第一个元素Rear代表的是队列的最后一个有效元素的下一个元素3） 队列空front和rear的值相等，但不一定为04. 循环队列入队伪算法讲解两步完成，详解见图5. 循环队列出队伪算法讲解6. 如何判断循环队列是否为空如果fron
13、t和rear的值相等，则该队列就一定为空。7. 如何判断循环队列是否为满预备知识：front的值可能比rear大，也完全有可能比rear小，当然也可能相等。两种方式：1.多增加一个标志位参数 2.少用一个元素【通常使用第二种元素】队列中有n个元素，只要放到n-1个元素，即认为队列已满。/2018/5/21专题：递归 定义：一个函数自己直接或间接调用自己递归满足的三个条件：1. 递归必须得有一个明确的终止条件2. 递归的值可以是递增的，但所处理的数据规模必须在递减（n-n-1-n-2）3. 这个转化必须是可解的循环和递归所有的循环都可以用递归实现，但所有的递归不一定都可以用循环实现。递归： 循环
14、：易于理解 不易理解速度慢 速度快存储空间大（步骤麻烦） 存储空间小n - n-1 - n-2 - - 1举例：1. 求阶乘2. 1+2+100的和3. 汉诺塔4. 走迷宫递归的应用： 树和森林就是以递归的方式定义的 树和图的很多算法就是以递归来实现的 很多数学公式就是以递归的方式定义的(例如：斐波拉切数列)线性结构总复习： 逻辑结构 线性 数组 链表 栈和队列是一种特殊的线性结构，算线性结构的应用 非线性 树 图 物理结构/2018/5/22模块二：非线性结构 树定义： 专业定义：1. 有且只有一个称为根的节点 2. 有若干个互补相交的子树，这些子树本身也是一棵树 通俗定义：1. 树是由节点
15、和边组成2. 每个节点只有一个父节点但可以有多个子节点3. 但有一个节点例外，该节点没有父节点，此节点成为根节点。专业术语 节点 父节点 子节点 子孙 堂兄弟深度：从根节点到最底层节点的层数称之为深度（根节点是第一层）叶子节点：没有子节点的节点。非终端节点：实际就是非叶子节点。度：子节点的个数成为度。分类：一般树：任意一个节点的子节点的个数都不受限制二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改。 分类： 一般二叉树 满二叉树（完全二叉树的特例）在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树 完全二叉树（用数组存储树时，必须是完全二叉树） 如果只是删除了
16、满二叉树最底层最后边的连续若干个节点，这样形成的二叉树就是完全二叉树。 优点：1.根据节点编号可以知道在第几层 2.可以知道父节点和子节点森林：n个互不相交的树的集合树的存储：二叉树的存储 连续存储将二叉树补充为完全二叉树 以数组的形式存储时，如果根据只保存有效节点的形式，无法推出全树的样子。 优点：查找某个节点的父节点和子节点（也包括判断有没有父节点和子节点）速度很快。 缺点：耗用空间内存过大 链式存储一般树的存储 双亲表示法（求父节点方便） 把每一个节点编号，然后在每一个节点后标记出其父节点的编号 孩子表示法（求子节点方便） 把每一个子节点都写在每一个节点之后。 双亲孩子表示法（求父节点和
17、子节点都方便） 把每一个节点编号，然后在每一个节点后标记出其父节点的编号，再把每一个子节点写在之后。 二叉树表示法 把一个普通树转化为二叉树来存储。 具体转换方法： 设法保证任意一个节点的 左指针域指向它的第一个孩子 右指针域指向它下一个兄弟 只要满足此条件，就可以把一个普通树转化为二叉树 一个普通树转化成的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再将二叉树存储 具体转换方法： 1.设法保证其他树的根节点当成第一颗树根节点的兄弟 2.设法保证其他任意一个节点的 左指针域指向它的第一个孩子 右指针域指向它下一个兄弟 只要满足此条件，就可以把一片森林转化为二叉树 操作：遍历先序遍历先访
18、问根节点中左右 先访问根节点 再先序访问左子树 再先序访问右子树中序遍历中间访问根节点左中右 中序遍历左子树 再访问根节点 再中序遍历右子树后序遍历最后访问根节点左右中 先后序遍历左子树 再后序遍历右子树 再访问根节点只知道一颗二叉树的一种遍历方式是无法还原二叉树的原貌的。已知两种遍历序列求原始二叉树先中（可以） 中后（可以） 先后（不可以） 必须有一个中序已知先序和中序求后序例1：先序：ABCDEFGH 中序：BDCEAFHG 求后序讲解：先序中第一个出现的一定是根节点，即A；所以中序中根节点A左边的BDCE是左子树，右边的FHG是右子树；然后在先序序列中看左子树BDCE中哪个先出现，先出现
19、的为根节点，即B；因为中序中DCE在B的右侧，所以DCE是B的右子树，哪个在先序中先出现为根节点，即C；中序中，C左侧是D，右侧是E，即为C的左右子节点；A右子树方法类同。方法总结：由先序找到根节点（先出现为根节点），由中序找到根节点的左右子树（左侧左子树，右侧右子树）。后序：DECBHGFA例2:先序: ABDGHCEFI中序: GDHBAECIF求后序: GHDBEIFCA已知中序和后序求先序例：中序：BDCEAFHG 后序：DECBHGFA 求先序：讲解：后序中第一个出现的一定是根节点，即A；所以中序中根节点A左边的BDCE是左子树，右边的FHG是右子树；然后在后序序列中看左子树BDCE中哪个后出现，后出现的为根节点，即B；因为中序中DCE在B的右侧，所以DCE是B的右子树，哪个在后序中后出现为根节点，即C；中序中，C左侧是D，右侧是E，即为C的左右子节点；A右子树方法类同。方法总结：由后序找到根节点（后出现为根节点），由中序找到根节点的左右子树（左侧左子树，右侧右子树）。先序: ABCDEFGH/2018/5/23应用： 树是数据库中数据组织一种重要形式。 操作系统子父进程的关系本身就是一棵树。 面对对象语言中类的继承关系本身就是一棵树。赫夫曼树。
