数据结构笔记.doc

数据结构笔记基础：数据结构与算法（一） 数据结构基本概念数据（data）：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素（data element）：是数据的基本单位，在计算机中通常被当做一个整体进行考虑和处理数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合4类基本结构：集合、线性结构、树形结构、图形（网状）结构数据结构的形式定义为数据结构是一个二元组 Data Structure = （D,S），其中D是数据元素的有限集，S是D上关系的有限集数据结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构数据结构在计算机中的表示（映像）称为物理结构（存储结构）计算机中表示信息的最小单位是二进制中的一位，叫做 位（bit），一到若干位组成一个位串表示一个数据元素，这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种：顺序映像、非顺序映像，并由此得到两种存储结构：顺序存储、链式存储，前者运用相对位置表示数据元素间的逻辑结构，后者借助指针 任何一个算法的设计取决于数据（逻辑）结构，而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种：原子类型、结构类型，前者不可分解（例如int、char、float、void ），后者结构类型由若干成分按某种结构组成，可分解，成分既可以是非结构的也可以是结构的（例：数组）抽象数据类型（Abstract Data Type ）：是指一个数学模型及定义在该模型上的一组操作（P8）抽象数据类型格式如下：ADT抽象数据类型名数据对象：数据关系：数据操作：ADT抽象数据类型名基本操作格式如下：基本操作名（参数表）初始条件：操作结果：多形数据类型（polymorphic data type）：是指其值得成分不确定的数据类型（P9）抽象数据类型可由固有数据类型来表示和实现（二） 算法（概念）和算法分析（时、空性能）算法（algorithm）：对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1、有穷性：算法必须在可接受的时间内执行有穷步后结束2、确定性：每条指令必须要有确切含义，无二义性，并且只有唯一执行路径，即对相同的输入只能得相同输出3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入：一个算法有一到多个输入，并取自某个特定对象合集5、输出：一个算法有一到多个输出，这些输出与输入有着某些特定关系的量算法设计要求（好算法）：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求，并能有合理的处理方式。算法效率的度量：（1） 事后统计：程序运行结束后借助计算机内部计时功能，缺点一是必须先运行依据算法编制的程序，二是受限于计算机软硬件，导致掩盖了算法本身的优劣（2） 事前分析估计： 消耗时间影响因素：算法策略、问题规模、编程语言、编译程序产生的机器码质量、机器执行指令的速度撇开各种影响因素只考虑问题的规模（通常用整数量n表示），记为问题规模的函数算法时间取决于控制结构（顺序，分支，循环）和固有数据类型操作的综合效果书写格式：T（n）= O（f（n） f（n）为n的某个函数时间复杂度：算法的渐近时间复杂度（asymptotic time complexity），它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同以循环最深层原操作为度量基准频度：该语句重复执行的次数算法的存储空间需求：空间复杂度（space complexity）：算法所需存储空间度量，记作 S（n）= O（f（n），其中n为问题规模的大小一、线性表（一） 线性表基本概念线性表（linear_list）：n个数据元素的有限序列结构特点：存在唯一的被称作“第一个”、“最后一个”的数据元素，且除了第一个以外每个元素都有唯一前驱，除最后一个以外都有唯一后继在复杂线性表中存在：数据项-记录-文件，例如每个学生情况为一个记录，它由学号、性别.数据项组成，多个学生记录组成一个文件在形如（a1，.，ai-1，ai，ai+1，.，an）中，ai-1领先于ai，ai领先于ai+1，且形成直接前驱元素，直接后继元素关系元素个数n定义为线性表长度，n=0为空表相关操作算法见书（P20）（二） 线性表顺序存储结构和链式存储结构（1）线性表顺序表示和实现线性表顺序存储在一组连续的存储单元中，链式存储则不要求；顺序结构可以随机访问，链式结构可以无限扩容确定存储位置（计算公式）：第i个元素：LOC（ai）= LOC（a1）+（i-1）*L L是偏移量，即每个元素占用存储单元第ai+1个元素：LOC（ai+1）= LOC（ai）+L a1（起始地址或基地址）C语言下标从“0”开始，则表中第i个元素是L.elem i-1当对线性表进行操作时，被操作元素后面的元素角标会相应变化（前移、后移），算法（P24）（2）线性表链式表示和实现特点：用一组任意的存储单元存储线性表的数据元素（存储单元不一定连续）结点存储数据元素及直接后继的存储位置信息，两个域：数据域和指针域，指针域中存储的信息称为指针或链，仅含有一个指针域故又称线性链表或单链表链表的插入：先增加一条指针再修改原指针头指针指向第一个数据元素的存储位置，最后一个结点的指针为空（NULL）链表表示方法及算法（P28）单链表第一个结点前加一个头结点Head，其数据域可为空也可存储一些附加信息（链长等）假设p是指向线性表中i个元素（ai）的指针，则p-next是指向i+1个数据元素在单链表中，取得第i个元素必须从头指针开始寻找，因此单链表是非随机的存储结构线性表指逻辑结构，从抽象数据层面来说顺序表和链表指物理存储结构逻辑结构：离散、线性、层次、网状应用见书算法二、栈和队列（一） 栈的基本概念栈（stack）是限定仅在表尾进行插入或删除操作的线性表表尾为栈顶，表头为栈底，遵循后进先出原理（last in first on，LIFO），不含元素则为空栈操作：在栈顶插入（入栈）和删除（出栈），栈初始化、判空、取栈顶元素（算法P45）（二） 栈的顺序存储和链式存储顺序栈，即栈的顺序存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置初始栈时不应限定栈的最大容量，基本做法是先为栈分配一个基本容量，然后在应用过程中，不够用再逐段扩大（算法P46）（三） 递归栈与递归的实现：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数阶乘函数、2阶Fibonacci数列、Ackerman函数、3阶Hanoi问题（多阶呢？）（P54）函数调用函数执行过程笔记（P56）（四） 队列队列先进先出（first in first out，FIFO），队尾一端插入，队首一端删除元素（日常排队）队列与栈均有八种基本操作（P59），队列一般用链表实现，栈用顺序表实现双端队列（限定操作的队列）（P60）（五） 栈和队列的应用链队列、循环队列（P60），离散事件模拟（银行接待工作（P65）（六） 特殊矩阵的压缩存储如何存储矩阵的元，使矩阵的运算有效进行。高级语言常用二维数组存储阵元面对如高阶矩阵，多值相同矩阵和多零元素矩阵进行压缩存储节省空间压缩存储：为多个值相同的元只分配一个空间，对零元不分配值相同元素或零元素具有分布规律则称为特殊矩阵，反之为稀疏矩阵具体应用与算法（P95）三、树与二叉树（一） 树的基本概念树是非线性数据结构，以分支关系定义的层次结构树是n（n=0）个结点的有限集详见（P118），基本术语（P120）（二） 二叉树1. 二叉树的定义及其主要特征： 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。性质：1.2.3.满二叉树：完全二叉树： 4. 5.2. 二叉树的顺序存储结构和链式存储结构顺序存储，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点依次存储在如上定义的一位数组下标为i-1的分量中。123456789链式存储，每个结点中至少包含三个域,左指针，数据，右指针，称作“二叉链表”增加一个双亲指针域，则称作“三叉链表” 详见P126-1273. 二叉树的遍历遍历二叉树，每个结点均被访问一次，且仅有一次。在限定先左后右的访问序列后，有三种遍历方式：先序（DLR），中序（LDR）,后续（LRD）P129 算法6.1（波兰式）层次遍历，无论那种遍历方式，对含n个结点的二叉树，时间复杂度都为O（n），空间复杂度也为O（n）。4. 线索二叉树的基本概念和构造摘要：对于n个结点的二叉树，在二叉链存储结构中有n+1（2n-（n-1）个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索概念：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。构造方法：（三） 树与森林1. 树的存储结构 链表结构：1.双亲表示法 2.孩子表示法 3.孩子兄弟表示法 详见P1352. 森林与二叉树转换 左孩子右兄弟3. 树与森林的遍历 先序、中序遍历，详见P139 当以二叉链表做树的存储结构时，树的先序 = 二叉树先序、树的后序 = 二叉树中序（四） 树与二叉树的应用1. 二叉排序树 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的节点。 查找：步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。2. 平衡二叉树(AVL) 定义：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度 之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1=bf=1图一，图二都是BST，但只有图一是AVL tree3. 哈夫曼（Huffman）树和哈夫曼编码哈夫曼树是一类带权路径长度最短的树，又称最优树。路径和路径长度概念：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一结点的路径长度之和。推广到一般情况，考虑带权结点：结点的带权路径长度为从该结点到树根之间的路径长度与结点上的权值的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作WPL= 带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树哈夫曼算法构造哈夫曼树（P145）哈夫曼编码 前缀编码：设计长短不等的编码，任一字符的编码都不是另一个字符的编码的前缀 利用二叉树来设计前缀编码 约定左分支表示字符“0”右分支表示字符“1”则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。一般情况，当带有权值时，本质上就是设计一棵哈夫曼树，得到二进制前缀编码=哈夫曼编码-算法详见P147四、 图（一） 图的基本概念 图是一种数据结构，加上一组基本操作，构成的一种抽象数据类型 详见（P156） 途中数据元素通常称为顶点，V是顶点的有穷非空集合；VR是两个顶点的关系集合，若属于VR，则表示从v到w的弧，称v为弧尾（初始点），w尾弧头（终结点）此时图是有向图，若属于VR必有属于VR，则以无序对，表示v和w的一条边，此时称图为无向图完全图有向完全图边或弧很少（e终点迪杰斯特拉算法：3.拓扑排序 由某个集合上的偏序得到该集合的全序 偏序：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系；设R是集合上的偏序，如果对每个x，y属于X必有xRy或yRx，则称R是集合X上的全序关系。 详见（P180）4.关键路径（最长路径）（P183）五、 查找（一） 查找的基本概念在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。（二） 顺序查找法1. 顺序查找： 核心：从数据的第一个元素开始，依次比较，直到找到目标数据或查找失败。 1.从表中的第一个元素开始，依次与关键字比较。 2.若某个元素匹配关键字，则 查找成功。 3.若查找到最后一个元素还未匹配关键字，则 查找失败。2. 时间复杂度：顺序查找平均关键字匹配次数为表长的一半，其时间复杂度为O(n)。3.顺序查找的评估：顺序查找的优点是对表无要求，插入数据可在O(1)内完成。缺点是时间复杂度较大，数据规模较大时，效率较低。（三） 折半查找法算法要求：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。查找过程：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。（四） 散列（Hash）表哈希表定义：是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。基本概念：若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址，即k1k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。（五） 字符串模式匹配子串的定位操作是要在主串S中找出一个与子串T相同的子串，通常把主串S称为目标，把子串T称为模式，把从目标S中查找模式为T的子串的过程称为“模式匹配”。1. Brute-Force算法的设计思想Brute-Force是普通的模式匹配算法。将主串S的第1个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较，直到主串的一个连续子串字符序列与模式相等 ，返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功；否则，匹配失败，返回值 0。2. Brute-Force算法的特点： 每次遇到匹配不成功的情况，指针i都要移到本次匹配的开始位置的下一位，称这样的指针移动为回溯。指针的回溯越多，简单模式匹配的执行次数越多Brute-Force匹配算法的最坏时间复杂度为 O(n*m)，一般情况下BF算法的时间复杂度为O(n+m)3.KMP算法的改进 每当一趟匹配过程中出现字符比较不等时，不需回溯指针i，而是利用已经得到的 “部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续比较KMP算法的时间复杂度可以达到O(m+n) 4.KMP算法的设计思想假设以指针 i 和 j 分别指示主串和模式中正待比较的字符，令 i 的初值为0，j 的初值为0若在匹配过程中，Si=Pj，则i和j分别增1，否则i不变，而j退到nextj的位置再比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，依次类推若令nextj=k，则nextj表明当模式中第j个字符与主串中相应字符失配时，在模式中需重新和主串中该字符进行比较的字符的位置模式串的next函数定义为（六） 查找算法的分析及应用六、 排序（一） 排序的基本概念将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。（二） 插入排序直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。（三） 气泡排序冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序（四） 简单选择排序简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。代码实现很简单，一起来看下。（五） 希尔排序希尔排序是基于插入排序的，首先回顾一下插入排序，假设插入是从左向右执行的，待插入元素的左边是有序的，且假如待插入元素比左边的都小，就需要挪动左边的所有元素，如下图所示：相比简单插入排序，大间隔地做插入排序有两个好处：一、大间隔直接导致需要挪动的数据稀少，且数据挪动的效率高，图5中一次挪动可以跨越40个位置；二、经过前一步大间隔的插入排序后，整个数组从整体上粗略地看已经有了明显的顺序，后一步小间隔的插入排序时，一部分操作是不需要挪动数据的，再次减少了挪动数据的次数。间隔的序列：间隔的常用序列，通过递归表示：h=3*h+1。（1,4,13,40,121 .）希尔排序的效率：“没有理论上分析希尔排序的效率的结论，各种基于实验的评估，估计它的时间级从O(N(3/2)到O(N(7/6)”-1。（六） 快速排序快速排序算法的策略是这样的：首先把数组用某个值分为两个子数组，且称这个值为分组值，一个子数组中的元素均小于分组值，另一子数组则均大于等于分组值，这里的子组内并不排序；然后，再分别对两个子组进行再分组，重复递归这个过程，直到最后每两个元素作为一组进行再分组，整个数组就排好序了。分组过程具体如下：同时从左往右和从右往左扫描数组，记扫描标记位为LP和RP。在LP一边，若发现元素小于分组值则跳过（即向右移动一位检查下一个元素），否则等待RP的扫描；RP若发现元素大于等于分组值跳过，直到找到小于分组值的元素，然后LP和RP位置的元素交换，重复这个过程，直到LP和RP相遇。如图7,8所示，以11号元素为分组值，LP停在0号位置，RP跳过10号，停在图7中的9号位置（粉色柱），然后0号和9号交换，后续重复这个过程。分组值的选择，可以想见，理想的分组值应该是待分组元素的中值，这样分组后子组在数量少几乎是一半对一半，不过找中值无疑增加了算法的工作量。图7中采用了更简单的方式，直接选数组最右边的元素为分组值，分组结束后，再把这个值交换到LP和RP相遇的位置，假如初始数组是从大到小排序的，这种情况下，选择最右边的元素作为分组值，其区分度就很差了。更好用的方法是所谓的取首尾中三项数据的中值或者平均值。通过对算法过程的描述可知，其时间复杂度应该为：O(N*logN)，比简单排序和希尔排序都要快。（七） 堆排序堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：大顶堆：arri = arr2i+1 & arri = arr2i+2 小顶堆：arri = arr2i+1 & arri = arr2i+2 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了（八） 基数排序基数排序(Radix Sort)基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。在上图中，首先将所有待比较树脂统一为统一位数长度，接着从最低位开始，依次进行排序。1. 按照个位数进行排序。2. 按照十位数进行排序。3. 按照百位数进行排序。排序后，数列就变成了一个有序序列。（九） 各种内部排序算法的比较 比较排序和非比较排序 常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。 比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。 排序的稳定性和复杂度 不稳定： 选择排序（selection sort） O(n2) 快速排序（quicksort） O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序堆排序 （heapsort） O(nlogn)希尔排序 （shell sort） O(nlogn)基数排序（radix sort） O(nk); 需要 O(n) 额外存储空间 （K为特征个数）稳定：插入排序（insertion sort） O(n2) 冒泡排序（bubble sort） O(n2) 归并排序 （merge sort） O(n log n); 需要 O(n) 额外存储空间 二叉树排序（Binary tree sort） O(nlogn); 需要 O(n) 额外存储空间 计数排序 (counting sort) O(n+k); 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1 桶排序 （bucket sort） O(n); 需要 O(k) 额外存储空间（十） 排序算法的应用