数据结构笔记

//2018/5/23数据结构概述：预备知识模块一：线性结构连续存储[数组]离散结构[链表]线性结构的两种常见应用之一栈（堆栈）线性结构的两种常见应用之二队列专题：递归1.1+2......+100的和2.求阶乘3.汉诺塔4.走迷宫模块二：非线性结构树图模块三：查找和排序折半查找排序：冒泡插入选择快速排序归并排序补录：Java中容器和数据结构相关知识Iterator接口Map哈希表严蔚敏---高一凡---黄国瑜//2018/5/24数据结构概述定义我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找或删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应操作叫做算法。特定的数据类型:个体如何保存特定的存储结构:个体与个体的关系如何保存数据结构=个体的存储+个体关系的存储算法（狭义）=对存储数据的操作算法：即解题的方法和步骤衡量算法的标准1.时间复杂度[重要]大概程序要执行的次数，而非执行的时间2.空间复杂度[重要]算法执行过程中大概所占用的最大内存3.难易程度4.健壮性数据结构的地位数据结构是软件中最核心的课程。程序=数据的存储+数据的操作+可以被计算机执行的语言预备知识：指针结构体动态内存的分配和释放指针：指针的重要性:表示一些复杂的数据结构快速的传送数据使函数返回一个以上的值能否直接访问硬件能够方便的使用数组和字符串是理解面向对象语言中引用的基础指针是C语言的灵魂定义地址内存单元的编号从0开始的非负整数范围0-FFFFFFFF【0到4G-1】注：无论一个变量有多大，其地址只用第一个字节的地址表示，均只占四个字节。指针指针就是地址地址就是指针指针变量就是存放内存单元地址的变量指针本质上就是一个操作受限的非负整数分类1、基本类型指针【略】基本概念inti=10;int*p=&i;//等价于int*p;p=&i;详解这两部操作：1）p存放了i的地址，所以我们说p指向了i2）p和i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值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、如果一个指针变量指向了某个普通变量，则*指针变量就完全等价于该普通变量注意：指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址普通变量前不能加*常量和表达式前不能加&如何通过被调函数修改主调函数中普通变量的值Ⅰ实参为相关变量的地址Ⅱ形参为以该变量的类型为类型的指针变量Ⅲ在被调函数中通过*形参变量名的方式就可以修改主函数相关变量的值Eg:voidf(int*p)//II{*p=100;//III}intmain(void){inti=9;f(&i);//Iprintf(“i=%d\n”,i);}指针和数组的关系指针和一维数组数组名一维数组名是个指针常量，它存放的是一维数组第一个元素的地址，它的值不能被改变一维数组名指向的是数组的第一个元素下标和指针的关系a[i]==*(a+i)*a+3=a[0]+3假设指针变量的名字为p则p+i的值是p+i*(p所指向的变量所占的字节数)指针变量的运算指针变量不能相加，不能相乘，不能相除如果两指针变量属于同一数组，则可以相减指针变量可以加减一整数，前提是最终结果不能超过指针允许指向的范围p+i的值是p+i*(p所指向的变量所占的字节数)p-i的值是p-i*(p所指向的变量所占的字节数)p++==p+1p--==p-1举例如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】两个参数存放数组首元素的指针变量存放数组元素长度的整型变量所有的指针变量只占4个子节用第一个字节的地址表示整个变量的地址动态内存分配和释放：[程序在运行过程中可以动态的增加或减少内存分配]动态构造一维数组假设动态构造一个int型数组int*p=(int*)malloc(intlen);1、malloc只有一个int型的形参，表示要求系统分配的字节数2、malloc函数的功能是请求系统len个字节的内存空间，如果请求分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL3、malloc函数能且只能返回第一个字节的地址，所以我们需要把[类型不一样。即所占的字节数也不确定]这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此malloc前面必须加（数据类型*）,表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。如：int*p=(int*)malloc(50);表示将系统分配好的50个字节的第一个字节的地址转化为int*型的地址，更准确的说是把第一个字节的地址转化为四个字节的地址，这样p就指向了第一个的四个字节，p+1就指向了第2个的四个字节，p+i就指向了第i+1个的4个字节。p[0]就是第一个元素，p[i]就是第i+1个元素double*p=(double*)malloc(80);表示将系统分配好的80个字节的第一个字节的地址转化为double*型的地址，更准确的说是把第一个字节的地址转化为8个字节的地址，这样p就指向了第一个的8个字节，p+1就指向了第2个的8个字节，p+i就指向了第i+1个的8个字节。p[0]就是第一个元素，p[i]就是第i+1个元素free（p）：动态分配的内存，必须free()释放，系统不会自动释放。释放p所指向的内存，而不是释放p本身所占用的内存【重点：动态分配数组内存】int*pArr=(int*)malloc(sizeof(int)*len);(最后一个*代表了乘分配了4*len个字节)模块一：线性结构【把所有的结点用一根直线穿起来】连续存储[数组]1.什么叫数组元素类型离散结构[链表]线性结构中两种常用应用之一栈定义一种可以实现“先进后出”的存储结构只能从栈尾（栈顶）进和出。栈类似于箱子，局部变量都是在栈中存储的。分类静态栈【以数组为内核】动态栈【以链表为内核】算法出栈pTop向下移一个，pBottom不变压栈（入栈）pTop向上移一个，pBottom不变应用函数调用中断表达式求值（例如计算器的编写）内存分配缓冲处理//2018/5/20线性结构中两种常用应用之二队列定义：一种可以实现“先进先出”的存储结构分类：变量名：front（头部）和rear（尾部）链式队列---用链表实现静态队列---用数组实现注：在队首的位置删除元素，然后队首指针指向下一个元素在队尾的位置添加元素，然后队尾指针指向下一个元素【重点】Rear指向的是队列最后一个元素的下一个元素【重点】Front指向的是队列的第一个元素队列算法：入队出队队列的具体应用：所有和时间及有关的操作都有队列的影子。静态队列：注：将数组的部分功能给去掉，然后再加入一些功能。静态队列通常都必须是循环队列。问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。循环队列的讲解：1.静态队列为什么必须是循环队列问题：如果按照普通的数组来存储队列的话。每次删掉一个元素，头部指针都会指向下一个元素，会造成原来元素的位置空间浪费，只能被使用一次而不能重复被使用。只能增不能减。解决方法：当front和rear移动到顶部（队尾）时，下一次移动时可以让它再移动到底部（队首），首尾相连，这实际就是循环队列。2.循环队列需要几个参数来确定需要两个参数来确定frontrear3.循环队列各个参数的含义这两个参数在不同场合有不同的含义建议初学者先记住，然后慢慢体会1）队列初始化front和rear的值都是02）队列非空Front代表的是队列的第一个元素Rear代表的是队列的最后一个有效元素的下一个元素3）队列空front和rear的值相等，但不一定为04.循环队列入队伪算法讲解两步完成，详解见图5.循环队列出队伪算法讲解6.如何判断循环队列是否为空如果front和rear的值相等，则该队列就一定为空。7.如何判断循环队列是否为满预备知识：front的值可能比rear大，也完全有可能比rear小，当然也可能相等。两种方式：1.多增加一个标志位参数2.少用一个元素【通常使用第二种元素】队列中有n个元素，只要放到n-1个元素，即认为队列已满。//2018/5/21专题：递归定义：一个函数自己直接或间接调用自己递归满足的三个条件：1.递归必须得有一个明确的终止条件2.递归的值可以是递增的，但所处理的数据规模必须在递减（n-n-1-n-2……）3.这个转化必须是可解的循环和递归所有的循环都可以用递归实现，但所有的递归不一定都可以用循环实现。递归：循环：易于理解不易理解速度慢速度快存储空间大（步骤麻烦）存储空间小n-n-1-n-2-……-1举例：1.求阶乘2.1+2……+100的和3.汉诺塔4.走迷宫递归的应用：树和森林就是以递归的方式定义的树和图的很多算法就是以递归来实现的很多数学公式就是以递归的方式定义的(例如：斐波拉切数列)线性结构总复习：逻辑结构线性{数组链表}栈和队列是一种特殊的线性结构，算线性结构的应用非线性{树图}物理结构//2018/5/22模块二：非线性结构树定义：专业定义：1.有且只有一个称为根的节点2.有若干个互补相交的子树，这些子树本身也是一棵树通俗定义：1.树是由节点和边组成2.每个节点只有一个父节点但可以有多个子节点3.但有一个节点例外，该节点没有父节点，此节点成为根节点。专业术语节点父节点子节点子孙堂兄弟深度：从根节点到最底层节点的层数称之为深度（根节点是第一层）叶子节点：没有子节点的节点。非终端节点：实际就是非叶子节点。度：子节点的个数成为度。分类：一般树：任意一个节点的子节点的个数都不受限制二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改。分类：一般二叉树满二叉树（完全二叉树的特例）在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树完全二叉树（用数组存储树时，必须是完全二叉树）如果只是删除了满二叉树最底层最后边的连续若干个节点，这样形成的二叉树就是完全二叉树。优点：1.根据节点编号可以知道在第几层2.可以知道父节点和子节点森林：n个互不相交的树的集合树的存储：二叉树的存储连续存储[将二叉树补充为完全二叉树]以数组的形式存储时，如果根据只保存有效节点的形式，无法推出全树的样子。优点：查找某个节点的父节点和子节点（也包括判断有没有父节点和子节点）速度很快。缺点：耗用空间内存过大链式存储一般树的存储双亲表示法（求父节点方便）把每一个节点编号，然后在每一个节点后标记出其父节点的编号孩子表示法（求子节点方便）把每一个子节点都写在每一个节点之后。双亲孩子表示法（求父节点和子节点都方便）把每一个节点编号，然后在每一个节点后标记出其父节点的编号，再把每一个子节点写在之后。二叉树表示法把一个普通树转化为二叉树来存储。具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子右指针域指向它下一个兄弟只要满足此条件，就可以把一个普通树转化为二叉树一个普通树转化成的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再将二叉树存储具体转换方法：1.设法保证其他树的根节点当成第一颗树根节点的兄弟2.设法保证其他任意一个节点的左指针域指向它的第一个孩子右指针域指向它下一个兄弟只要满足此条件，就可以把一片森林转化为二叉树操作：遍历先序遍历[先访问根节点][中左右]先访问根节点再先序访问左子树再先序访问右子树中序遍历[中间访问根节点][左中右]中序遍历左子树再访问根节点再中序遍历右子树后