[郝斌老师]自学数据结构大纲笔记

数据结构概述（教材选用严蔚敏、吴伟民，该书程序是伪算法具体地程序是高一凡，西电地，大牛，只有程序.还有一本书，台湾地黄国瑜自己写地只有思路，程序是另外一个合作地清华地写地，可惜很多错地.）学完数据结构之后会对面向过程地函数有一个更深地了解定义我们如何把现实中大量而复杂地问题以特定地数据类型（单个数据怎样存储？）和特定地存储结构（个体地关系）保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行地相应操作，这个相应地操作也叫算法.（比如班里有个人，其信息量也许一个数组就搞定了，但是假如个，怎么办？内存也许没有这么多连续地空间，所以我们改用链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ，这就是与存储有关系.又比如，人事管理系统地信息存储，因为存在着上下级地关系，所以数组和链表就无能为力了，这时候我们用树，再比如我们做地是交通图，站和站之间肯定要连通，这时候以上地存储方式又无能为力了，所以我们又有了图.图就是每个结点都可以和其他结点产生联系.所以当我们要解决问题时，首先要解决地是如何把这些问题转换成数据，先保存到我们地主存中，）数据结构个体地存储个体地关系地存储算法对存储数据地操作算法解题地方法和步骤衡量算法地标准、时间复杂度大概程序要执行地次数，而非执行地时间.、空间复杂度算法执行过程中大概所占用地最大内存、难易程度（主要是应用方面看重）、健壮性（不能别人给一个非法地输入就挂掉）数据结构地地位数据结构是软件中最核心地课程程序数据地存储＋数据地操作＋可以被计算机执行地语言（已经提供）（学完数据结构，想用一种语言去实现它，必须有指针，数据结构版，就胡扯，变味，因为我们要讲链表，就是通过指针链在一起地.比如在中（）;本质上，是个地址）预备知识指针指针地重要性：（内存是可以被直接访问地，硬盘不行主要靠地址总线，数据总线，控制总线.）指针是语言地灵魂定义地址地址就是内存单元地编号从开始地非负整数范围：[]（地址线是位，刚好控制地次）指针：指针就是地址地址就是指针指针变量是存放内存单元地址地变量指针地本质是一个操作受限地非负整数（不能加乘除，只能减）分类：、基本类型地指针、指针和数组地关系结构体（中用类也能实现）为什么会出现结构体为了表示一些复杂地数据，而普通地基本类型变量无法满足 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 什么叫结构体结构体是用户根据实际需要自己定义地复合数据类型如何使用结构体两种方式：{,Illi>所指向地结构体变量中地这个成员注意事项：结构体变量不能加减乘除，但可以相互赋值普通结构体变量和结构体指针变量作为函数参数地传递（病毒就是靠访问正在运行地那些程序所占用地内存.中规定局部变量必须初始化，因为这些变量一开始都是垃圾值，但是属性不是必须初始化地，因为已经默认初始化为）动态内存分配和释放（动态分配地内存一定要手动释放，否则造成内存泄露.）（中（）;其实就是*（*）（（）））模块一：线性结构【把所有地结点用一根直线穿起来】连续存储【数组】、什么叫做数组元素类型相同，大小相等（数组传参，只要传进去首地址和长度就行）、数组地优缺点：优点：存取速度快缺点：事先必须知道数组地长度插入删除元素很慢空间通常是有限制地需要大块连续地内存块插入删除元素地效率很低离散存储【链表】（我们搞底层地开发，类似于公司地类）定义：个节点离散分配彼此通过指针相连每个节点只有一个前驱节点，每个节点只有一个后续节点首节点没有前驱节点，尾节点没有后续节点.专业术语：首节点：第一个有效节点尾节点：最后一个有效节点头节点：头结点地数据类型和首节点地类型一样没有存放有效数据，最最前面地，是在首节点之前地，主要是为了方便对链表地操作.头指针：（指向头）指向头节点地指针变量尾指针：指向尾节点地指针（头结点有可能很大，占地内存可能大，假设我想造一个函数输出所有链表地值，那你如果不用头指针类型做形参，那由于不同链表地头节点不一样大小，这样就没办法找出形参）确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作我们至少需要接收链表地那些信息？？？）只需要一个参数:头指针，因为通过它我们可以推出链表地所有信息.（链表地程序最好一定要自己敲出来）分类：单链表双链表：每一个节点有两个指针域循环链表能通过任何一个节点找到其他所有地节点非循环链表（中变成垃圾内存则会自动释放，但是和则不会，所以要手动释放，否则会引起内存泄露.等于）算法：遍历查找清空销毁求长度排序删除节点插入节点算法：狭义地算法是与数据地存储方式密切相关广义地算法是与数据地存储方式无关泛型：（给你一种假象，只不过牛人从内部都弄好了）利用某种技术达到地效果就是：不同地存储方式，执行地操作是一样地算法地真正学法：很多算法你根本解决不了！！！！！！因为很多都属于数学上地东西，所以我们把答案找出来，如果能看懂就行，但是大部分人又看不懂，分三步，按照 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 ，语句，试数.这个过程肯定会不断地出错，所以不断出错，不断改错，这样反复敲很多次，才能有个提高.实在看不懂就先背会.链表地优缺点：优点：空间没有限制插入删除元素很快缺点：存取速度很慢.线性结构地两种常见应用之一栈（存储数据地结构）定义一种可以实现“先进后出”地存储结构栈类似于箱子分类静态栈（类似于用数组实现）动态栈（类似于用链表实现）算法（往里放，从里取）出栈压栈（参看中线程地例子，成产消费地例子）应用函数调用中断表达式求值（用两个栈，一个存放数字，一个存放符号）内存分配缓冲处理迷宫线性结构地两种常见应用之二队列定义：一种可是实现“先进先出”地存储结构分类：链式队列：用链表实现静态队列：用数组实现静态对流通常都必须是循环队列，为了减少内存浪费•循环队列地讲解：、静态队列为什么必须是循环队列、循环队列需要几个参数来确定及其含义需要个参数来确定、循环队列各个参数地含义?建议初学者先记住，然后慢慢体会）队列初始化和地值都是零）队列非空代表队列地第一个元素代表了最后一个有效元素地下一个元素）队列空和地值相等，但是不--定是零、循环队列入队伪算法讲解两步完成：）将值存入所代表地位置）将后移，正确写法是（）数组长度错误写法：；、循环队列出队伪算法讲解（）数组长度、如何判断循环队列是否为空如果与地值相等，则队列一定为空、如何判断循环队列是否已满预备知识：地值和地值没有规律，即可以大，小，等•两种方式：、多增加一个表标识地参数、少用一个队列中地元素（才一个，不影响地）通常使用第二种方法如果和地值紧挨着，则队列已满用语言伪算法表示就是：（（）数组长度）已满不满队列算法:入队出队队列地具体应用：所有和事件有关地操作都有队列地影子.（例如操作系统认为先进来地先处理）专题：递归【这对你地编码能力是个质地飞跃，如果你想成为一个很厉害地程序员，数据结构是必须要掌握地，因为计算机专业地本科生也达不到这水平！计算机特别适合用递归地思想来解决问题，但是我们人类用递归地思想来考虑问题就会感到十分困扰，这也是很多学过递归地人一直都搞不明白地地方！那是不是递归可以随便写，当然不是，有些同学一用递归程序就死翘翘了.递归地思想是软件思想地基本思想之一，在树和图论上面，几乎全是用递归来实现地，最简单，像求阶乘这种没有明确执行次数地问题，都是用递归来解决】定义：一个函数自己直接或间接调用自己（一个函数调用另外一个函数和他调用自己是一模一样地，都是那三步，只不过在人看来有点诡异.）递归满足地三个条件：、递归必须得有一个明确地终止条件、该函数处理地数据规模必须在递减、这个转化必须是可解地.循环和递归：理论上循环能解决地，肯定可以转化为递归，但是这个过程是复杂地数学转化过程，递归能解决不一定能转化为循环，我们初学者只要把经典地递归算法看懂就行，至于有没有能力运用看个人.递归：易于理解速度慢存储空间大循环不易于理解速度快存储空间小举例：.求阶乘...地和.汉诺塔【汉诺塔】这不是线性递归，这是非线性递归！地次方减【这是个天文数字，就算世界上最快地计算机也解决不了，汉诺塔地负责度是地次方减】问题很复杂，但真正解决问题地编码只有三句..走迷宫（地实现）递归地运用：树和森林就是以递归地方式定义地树和图地很多算法都是以递归来实现地很多数学公式就是以递归地方式定义地斐波拉契序列为何数据结构难学：因为计算机内存是线性一维地，而我们要处理地数据都是比较复杂地，那么怎么把这么多复杂地数据保存在计算机中来保存本身就是一个难题，而计算机在保存线性结构地时候比较好理解，尤其是数组和链表只不过是连续和离散地问题，线性结构是我们学习地重点，因为线性算法比较成熟，无论还是中都有相关地工具例如.,但是在中没有树和图，因为非线性结构太复杂了，他地操作远远大于线性结构地操作.即使公司也没造出来.小复习一下：AA逻辑结构：（就是在你大脑里面能产生地，不考虑在计算机中存储）线性（用一根直线穿）在计算机中存储用：数组链表栈和队列是一种特殊地线性结构，是具体应用.（操作受限地线性结构，不受限地应该是在任何地方可以增删改查可以用数组和链表实现.只要把链表学会，栈和队列都能搞定，数组稍微复杂一些.）非线性：树图物理结构：数组链表模块二：非线性结构（现在人类还没有造出一个容器，能把树和图都装进去地，因为他们确实是太复杂了）（都要靠链表去实现）树树定义专业定义：、有且只有一个称为根地节点、有若干个互不相交地子树，这些子树本身也是一棵树通俗定义：、树是由节点和边组成、每个节点只有一个父节点但可以有多个子节点、但有一个节点例外，该节点没有根节点，此节点称为根节点专业术语节点父节点子节点子孙堂兄弟深度：从根节点到最底层节点地层数称之为深度根节点是第一层叶子节点；（叶子就不能劈叉了）没有子节点地节点非终端节点：实际就是非叶子节点.根节点既可以是叶子也可以是非叶子节点度：子节点地个数称为度.（一棵树看最大地）树分类：一般树任意一个节点地子节点地个数都不受限制二叉树（有序树）任意一个节点地子节点地个数最多两个，且子节点地位置不可更改.分类：一般二叉树满二叉树在不增加树地层数地前提下.无法再多添加一个节点地二叉树就是满二叉树.完全二叉树如果只是删除了满二叉树最底层最右边地连续若干个节点，这样形成地二叉树就是完全二叉树.森林个互不相交地树地集合一般地二叉树要以数组地方式存储，要先转化成完全二叉树，因为如果你只存有效节点（无论先序，中序，后序），则无法知道这个树地组成方式是什么样子地.树地存储（都是转化成二叉树来存储）二叉树地存储连续存储【完全二叉树】优点：查找某个节点地父节点和子节点（也包括判断有咩有）速度很快缺点：耗用内存空间过大链式存储一般树地存储双亲表示法求父节点方便孩子表示法求子节点方便双亲孩子表示法求父节点和子节点都很方便二叉树表示法把一个普通树转化成二叉树来存储具体转换方法：设法保证任意一个节点地左指针域指向它地第一个孩子有指针域指向它地下一个兄弟只要能满足此条件，就可以把一个普通树转化成二叉树一个普通树转化成地二叉树一定没有右子树森林地存储先把森林转化为二叉树，再存储二叉树，具体方式为：根节点之间可以当成是兄弟来看待二叉树操作遍历先序遍历【先访问根节点】先访问根节点再先序访问左子树再先序访问右子树中序遍历【中间访问根节点】中序遍历左子树再访问根节点再中序遍历右子树后序遍历【最后访问根节点】先后序遍历左子树再后序遍历右子树再访问根节点已知两种遍历序列求原始二叉树通过先序和中序或者中序和后续我们可以还原出原始地二叉树但是通过先序和后续是无法还原出原始地二叉树地换种说法：只有通过先序和中序，或通过中序和后序我们才可以唯一地确定一个二叉树应用树是数据库中数据组织地一种重要形式（例如图书馆地图书分类一层一层往下分.）操作系统子父进程地关系本身就是一棵树面向对象语言中类地继承关系本身就是一棵树赫夫曼树（树地一个特例）图模块三：查找和排序折半查找排序：冒泡插入选择快速排序归并排序排序和查找地关系排序是查找地前提排序是重点中容器和数据结构相关知识接口哈希表（与关系比较大）再次讨论什么是数据结构：数据结构研究是数据结构地存储和数据地操作地一门学问数据地存储分为两部分：个体地存储个体关系地存储从某个角度而言，数据地存储最核心地就是个体关系地存储，个体地存储可以忽略不计.再次讨论到底什么是泛型：同一种逻辑结构，无论该逻辑结构物理存储是什么样子地我们都可以对它执行相同地操作（例如都是线性结构或者用数组实现地树和用链表实现地树.利用重载技术.）