数据结构-郝斌

数据结构的概述定义我们如何把现实中大量而反复的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此根底上为实现某个功能〔比方查找某个元素，删除某个元素，对所有元素进行排序〕而执行的相应的操作，这个相应的操作也叫做算法。数据结构=个体+个体的关系算法=对存储数据的操作狭义：数据结构是专门研究数据存储的问题数据的存储包含两方面：个体的存储+个体关系的存储广义：数据结构既包含数据的存储也包含数据的操作对存储数据的操作就是算法算法狭义：算法是和数据的存储方式密切相关广义：算法和数据的存储方式无关，这就是泛型思想衡量算法的标准：时间复杂度大概程序要执行的次数，而并非是执行的时间〔因为同一程序在不同机器上执行的时间是不一样的，有差异〕空间复杂度算法执行过程中大概所占用的最大内存难易程度健壮性数据结构的地位：数据结构是软件中最核心的课程程序=数据的存储+数据的操作+可以被计算机执行的语言泛型对于同一种逻辑结构，无论该逻辑结构的物理存储是什么样子的，我们可以对它执行相同的操作。数据的存储有几种：线性：连续存储：【数组】优点：存取速度快缺点：事先必须知道数组的长度插入删除元素很慢空间通常是有限的需要大块连续的内存块离散存储【链表】优点：空间没有限制插入删除元素很快缺点：存取速度很慢栈和队列是一种特殊的线性结构，是连续存储或离散存储的一种应用线性结构的应用------栈定义：一种可以实现“先进后出“的存储结构，类似于箱子分类：静态栈动态栈算法：出栈压栈应用：函数调用中断表达式求值内存分配缓冲处理迷宫intmain(void){intp;int*m=(int*)malloc(100);}如静态变量p和m是在栈中分配，有操作系统自动分配和释放。而(int*)malloc(100);执行后，将在堆中分配一块100字节的内存，由程序员手动分配。栈的示意图pToppToppBottom33无效数据nullNulNULL3333线性结构的应用------队列定义：一种可以实现“先进先出”的存储结构分类：链式队列：-----用链表实现〔比拟简单〕静态队列：-----用数组实现静态队列通常都必须是循环队列应用：所有和时间有关的事件都有队列的影子循环队列的讲解〔1〕静态队列为什么必须是循环队列665第四个4第三个3第二个2第一个10Frontrear现在如果一个数组里面存了四个元素，那么front就只想第一个有效元素，而real指向最后一个元素的下一个元素，当增加元素时，只能在rear一端增加，即rear向上移。删除元素时，只能在front一端删除元素，即front向上移。但是如果一直增增删删，那么就会造成rear端溢出，而front端浪费，所以对于这种情况，可以采用循环队列的形式，即当rear已经指向数组最后一个元素时，那么就可以转而将rear指向数组的第一个空出来的空间。〔2〕循环队列需要几个参数来确定需要2个参数来确定：front和rear〔3〕循环队列各个参数的含义：2个参数在不同场合有不同的含义队列初始化front和rear的值都为零队列非空front代表的是队列的第一个元素rear代表的是队列的最后一个有效元素的下一个元素队列为空front和real的值相等，但不一定为零〔4〕循环队列入队伪算法讲解：两步完成：将值存入rear所代表的位置错误的写法：rear=rear+1;正确的写法是：rear=(rear+1)%数组的长度〔5〕循环队列出队伪算法讲解Front=〔front+1〕%数组的长度(6)如何判断循环队列是否为空如果front与rear的值相等，那么该队列就一定为空〔7〕如何判断循环队列是否已满因为front的值可能比rear大，也可能比他小，也可能相等所以有两种方式:多增加一个标识是否满的参数少用一个元素【通常用此种方式】如果front和rear的值相差1，且front>rear,那么证明队列已满。用C语言伪算法表示为：if((rear+1)%数组长度==front)已满else未满专题：递归：知识点一：函数的调用当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：将所有的实际参数，返回地址等信息传递给被调函数。为被调函数的局部变量〔也包括形参〕分配存储空间将控制转移到被调函数的入口从被调函数返回主调函数之前，系统也要完成三件事：保存被调函数的返回结果释放被调函数所占的存储空间依照被调函数保存的返回地址将控制转移到调用函数当有多个函数相互调用时，按照“后调用先返回”的原那么，上述函数之间信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，将在栈顶分配一个存储区，进行压栈操作，每当一个函数退出时，就释放它的存储区，就进行出栈操作，当前运行的函数永远都在栈顶位置。A函数调用A函数和A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式比拟怪异而已。知识点二：递归必须满足的三个条件递归必须得有一个明确的终止条件该函数所处理的数据规模必须在递减这个转化必须是可解的知识点三：递归和循环的优缺点比拟递归：易于理解速度慢存储空间大循环不易理解速度快存储空间小知识点四：递归的应用树和森林就是以递归的方式定义的树和图的很多算法都是以递归来实现的很多数学公式就是以递归的方式定义的斐波拉契序列：12358132134非线性：树定义：专业定义：有且只有一个称为根的节点有假设干个互不相交的子树，这些子树本身也是一棵树。通俗的定义：树是由节点和边组成。每个节点只有一个父节点但可以有多个子节点但有一个节点例外，该节点没有父节点，此节点称为根节点。树相关的专业术语节点根节点父节点子节点有直接父子关系的才能叫子节点子孙节点堂兄弟节点其父节点是兄弟节点的为堂兄弟节点深度从根节点到对底层节点的层数称之为深度根节点是第一层叶子节点没有子节点的节点非终端节点实际就是非叶子节点度子节点的个数称为度，整个树的度就是所有节点的度数中，度数最大的那个为整个树的度数树的分类一般树任意一个节点的子节点的个数都不受限制，子节点的顺序可以更改也可以不能更改，能更改的树为无序一般树，不能更改的为有序一般树二叉树任意一个节点的子节点个数最多两个，且子节点的位置不可更改，即左子树和右子树的位置不可更改。分类：一般二叉树满二叉树在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树，及所有的节点都是两个度数〔两个子节点〕完全二叉树如果只是删除了满二叉树最底层最右边的连续假设干个节点，这样形成的二叉树就是完全二叉树。满二叉树只是完全二叉树的一个特例。森林n个互不相交的树的集合树的存储二叉树的存储连续存储用数组存储【适用于完全二叉树，不是完全二叉树的树补充为完全二叉树】优点:查找某个节点的父节点和子节点〔也包括判断有没有子节点〕方便快速缺点：耗用内存空间过大链式存储两个指针域分别指向两个子节点，没有子节点的为空优点：耗用内存空间小缺点：查找父节点不方便一般树的存储双亲表示法AABCDEFGACDEFGB-1006620此方法求父节点方便，但求子节点不方便。注意：此方法是用连续存储空间的数组来存储的，只不过数组的元素是C语言的struct或java和C++的对象，struct或对象里又有两个元素数值域父节点下标0123456孩子表示法AABCDEFGACDEFGB&B->&C->&DNULL&GNULLNULLNULL&E->&F此方法求子节点方便，但求父节点不方便。数值域子节点指针域链表0123456双亲孩子表示法ABABCDEFG&B->&C->&DNULL&GNULLNULLNULL&E->&F此方法求父节点和子节点都很方便，这也是用一块连续数组存储空间实现的数值域父节点下标子节点指针域链表0123456A-1C0D0E6

F6G2B0二叉树表示法(1)先把一个普通树转换为二叉树，再存储二叉树。具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子右指针域指向它的下一个兄弟只要能满足条件，就可以把一个普通树转化为二叉树。一个普通树转化成的二叉树一定没有右子树森林的存储〔1〕先把森林转化为二叉树，再存储二叉树具体转换方法：将森林中的每个树的节点当做兄弟存储；设法保证任意一个节点的左指针域指向它的第一个孩子,右指针域指向它的下一个兄弟只要满足条件，就可以把一个森林转化为二叉树AA

AE

AF

AI

AG

AH

AC

AB

AD

AK

AJ

A森林转化为二叉树为A

AF

AH

AD

AE

AC

AB

AJ

AG

AI

AK

A

二叉树的遍历：先序遍历【先访问根节点】方法：(1)先访问根节点(2)再先序访问左子树(3)再先序访问右子树AABCDEGFI先序遍历顺序：ABDGEHCFIH中序遍历【中间访问根节点】方法：(1)中序遍历左子树(2)再访问根节点(3)再中序遍历右子树AABCDEGFI中序遍历顺序：GDBHEACIFH后序遍历【最后访问根节点】方法：(1)先中序