搜索
数据结构资料-1-教材：《数据结构》严蔚敏吴伟民清华大学出版社《数据结构算法实现及解析》高一凡西安电子科技大学出版社第一部分数据结构概述一、定义（研究是数据结构的存储和数据的操作的）如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。数据结构=个体的存储（从某个角度而言，可忽略）+个体与个体之间关系的存储（核心）算法=对存储数据的操作二、算法解题的方法和步骤衡量算法的标准1.时间复杂度大概程序要执行的次数，而非执行的时间2.空间复杂度算法执行过程中大概所占用的最大内存3.难易程度（即可读性）4.健壮性三、数据结构的地位数据结构是软件中最核心的内容程序=数据的存储+数据的操作+可以被计算机执行的语言第二部分预备知识一、指针数据结构资料-2-指针的重要性：指针是C语言的灵魂定义地址：内存单元的编号从零开始的非负整数范围：0--FFFFFFFF（即0--4G-1）指针：指针就是地址，地址就是指针指针变量是存放内存单元地址的变量指针的本质是一个操作受限的非负整数（只能进行减运算）分类：1.基本类型的指针2.指针和一维数组的关系二、结构体为什么会出现结构体为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体结构体是用户根据实际需要自己定义的数据类型如何使用结构体两种方式：structStudentst={1000,zhangsan,20}structStudent*pst=&st;1.st.sid2.pst-sidpst所指向的结构体变量中的sid这个成员数据结构资料-3-注意事项结构体变量不能加减乘除，但可以相互赋值普通结构体变量和结构体指针变量作为函数传参问题三、动态内存的分配和释放假设动态构造一个int型的一位数组intlen；int*pArr=(int*)malloc(sizeof(int)*len);①本语句分配了两块内存，一块内存是动态分配的，总共len个字节；另一块是静态分配的，是pArr变量本身所占的内存，总共4个字节。②malloc只有一个int型的形参，表示要求系统分配的字节数③malloc函数的功能是请求系统分配len个字节的内存空间，如果分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL④malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此，malloc函数前面必须加强制类型转换（数据类型*），表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。⑤free（*pArr）表示把pArr所指向的内存给释放掉pArr本身的内存是静态的，不能有程序员手动释放，只能在pArr变量所在的函数运行终止时有系统自动释放⑥跨函数使用内存静态内存不可以跨函数使用：静态内存在函数执行期间可以被其它函数使用静态内存在函数执行完毕之后就不能在被其它函数使用数据结构资料-4-动态内存可以跨函数使用动态内存在函数执行完毕之后仍然可以被其它函数使用第三部分模块一：线性结构[把所有的结点用一条直线穿起来]一、连续存储[数组]1.什么叫做数组元素类型相同，大小相等2.数组的优缺点（相对于链表）优点：存取速度快缺点：实现必须知道数组的长度需要大块连续的内存块插入和删除元素很慢空间通常是有限制的二、离散存储[链表]1.定义N个结点离散分配彼此通过指针相连每个结点只有一个前驱结点，每个结点只有一个后续结点首结点没有前驱结点，尾结点没有后续结点专业术语：首结点：第一个存放有效数据的结点尾结点：最有一个存放有效数据的结点头结点：头结点的数据类型和首结点的类型是一样的首结点之前的结点头结点并不存放有效数据数据结构资料-5-加头结点的目的是为了方便对链表的操作头指针：指向头结点的指针变量尾指针：指向尾结点的指针变量确定一个链表需要几个参数：（如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的那些参数）一个参数，即头指针，因为我们通过头指针可以推算出链表的其它所有的信息2.分类单链表双链表：每一个结点有两个指针域循环链表：能通过任何一个结点找到其它所有的结点非循环链表3.算法遍历/查找/清空/销毁/求长度/排序/删除结点/插入结点插入结点：(伪算法)①r=p-pNext;p-pNext=q;q-pNext=r;②q-pNext=p-pNext;p-pNext=q;(这两行代码不能倒过来)删除结点：（伪算法）r=p-pNext;p-pNext=p-pNext-pNext;free(r);狭义的算法是与数据的存储方式密切相关广义的算法是与数据的存储方式无关泛型：利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的数据结构资料-6-同一种逻辑结构（包括线性结构和非线性结构，其中非线性结构包括树和图），无论该逻辑结构物理存储（包括数组和链表）是什么样子的，我们都可以对它执行相同的操作4.链表的优缺点（相对于数组）优点：空间没有限制插入和删除元素很快缺点：存取的速度很慢三、线性结构的两种常见应用之一栈1.定义：一种可以实现“先进后出”的存储结构栈类似于箱子2.分类静态栈：以数组为内核动态栈：以链表为内核3.算法出栈/入栈4.应用函数调用/中断/表达式求值/内存分配/缓冲处理/迷宫四、线性结构的两种常见应用之一队列1.定义：一种可以实现“先进先出”的存储结构队列类似于排队买票2.分类链式队列----用链表实现静态队列----用数组实现静态队列通常都必须是循环队列数据结构资料-7-循环队列的讲解：①静态队列为什么必须是循环队列普通队列的参数front和rear只增不减，导致内存浪费②循环队列需要几个参数来确定需要两个参数：front/rear③循环队列各个参数的含义两个参数在不同的场合有不同的含义①队列初始化front和rear的值都为零②队列非空front代表的是队列的第一个元素rear代表的是队列的最后一个有效元素的下一个元素③队列空front和rear的值相等，但不一定是零④循环队列入队伪算法讲解(在尾部入队)第一步：将值存入rear所指向的位置第二步：rear=(rear+1)%数组的长度⑤循环队列出队伪算法讲解（在头部出队）front=(front+1)%数组的长度⑥如何判断循环队列为空如果front与rear的值相等，则该队列一定为空⑦如何判断循环队列为满第一种方法：多增加一个标识参数，即数组的长度（常用）第二种方法：少用一个元素，如果front==(rear+1)%数组的长度，则数据结构资料-8-循环队列已满3.算法出队/入队4.应用所有和时间有关的操作都有队列的影子五、专题：递归（使用栈实现的）1、定义:一个函数自己直接或间接调用自己2、函数的调用当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：a、将所有的实际参数、返回地址等信息传递给被调函数保存b、为被调函数的局部变量（包括形参）分配存储空间c、将控制转移到被调函数的入口从被调函数返回主调函数之前，系统也要完成三件事：a、保存被调函数返回结果b、释放被调函数所占的存储空间c、依照被调函数保存的返回地址将控制转移到调用函数当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作；每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远都在栈顶位置。A函数调用A函数与A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已。数据结构资料-9-3、递归必须满足的三个条件：a、递归必须得有一个明确的终止条件b、该函数处理的数据规模必须在递减c、这个转化必须是可解的4、循环和递归之间的关系理论上循环能解决的问题，肯定可以转化为递归解决，但是这个过程是复杂的数学转化过程，递归能解决的问题不一定能转化为循环解决递归的优缺点：易于理解速度慢存储空间大循环的优缺点：不易理解速度快存储空间小5、举例：1.1+2+3+4+...+100的和2.求阶乘①使用for循环实现：求和求阶乘#includestdio.h#includestdio.hintmain(void)intmain(void){{longsum=0;longmult=1;数据结构资料-10-for（inti=1;i=100;i++）intval;sum=sum+i;printf(请输出整数：)printf(1到100的和是：%ld,sum);scanf(%d,&val);return0;for(inti=1;i=val;i++)}mult=mult*i;printf(%d的阶乘是%ld,val,mult);return0;}②使用递归实现：#includestdio.h#includestdio.hlongsum(intval)longmult(intval){{if(1==val)if(1==val)return1;return1;elseelsereturnval+sum(val-1);returnval*mult(val-1);}}intman(void)intmain(void){{printf(1到100的和是：%ld,sum(100));printf(请输出整数：)return0;scanf(%d,&val);}printf(%d的阶乘是%ld,val,mult(val));return0;}数据结构资料-11-3.汉诺塔伪算法：if（1==n）直接将盘子从A移动到Celse{（三步）第一步：将A上的前n-1个盘子借助B移动到C第二步：将A上的第n个盘子直接移动到C第三步：将B上的n-1个盘子借助A移动到C}4.走迷宫6、递归的应用树和森林就是以递归的方式定义的树和图的很多算法都是以递归来实现的很多数学公式就是以递归的方式定义的（例如：斐波拉契序列）第四部分模块二：非线性结构一、树1、定义（专业定义）有且只有一个称为根的结点；有若干个互不相交的子树，这些子树本身也是一棵树（通俗定义）树是由结点和边（即指针）组成；每一个结点只有一个父结点但可以有多个子结点；但是有一个结点例外，该结点没有父结点，此结点称为根结点专业术语数据结构资料-12-结点/父结点（只有一个）/子结点/子孙/堂兄弟深度:从根结点到最底层结点的层数（根结点是第一层）叶子结点：没有子结点的结点非终端结点：实际就是非叶子结点，即有子结点的结点度：子结点的个数2、分类一般树：任意一个结点的子结点的个数都不受限制二叉树：任意一个结点的子结点的个数最多两个，且子节点的位置不可更改二叉树的分类：一般二叉树满二叉树：在不增加树的层数的情况下，无法再多添加一个结点的二叉树就是满二叉树完全二叉树：如果只是删除满二叉树最底层最右边的连续若干个结点，这样形成的二叉树就是完全二叉树满二叉树是完全二叉树的特例，完全二叉树包含满二叉树森林：n个互不相交的树的集合3、存储（解决非线性结构用线性结构表示的问题）二叉树的存储连续存储[完全二叉树]一般二叉树要以数组的方式存储，要先转化成完全二叉树，因为如果只存有效节点（无论以哪种规则：先序，中序，后序），则无法知道这个树的原本样子。优点：查找某个结点的父结点和子结点（也包括判断有没有子结点）速度很快数据结构资料-13-缺点：耗用内存空间过大链式存储一般树的存储双亲表示法（求父结点方便）孩子表示法（求子结点方便）孩子双亲表示法（求父结点和子结点都方便）二叉树表示法把一棵普通树转化成二叉树来存储具体转化方法：设法保证任意一个结点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟一棵普通树转化为的二叉树一定没有右子树森林的存储先把森林转化为二叉树，再存储二叉树具体方式为：根节点之间