数据结构笔记

数据结构笔记基础:数据结构与算法数据结构基本概念数据(data):就是对客观事物得符号表示,在计算机科学中就是指所有能输入到计算机中并被计算机程序处理得符号总称数据元素(dataelement):就是数据得基本单位,在计算机中通常被当做一个整体进行考虑与处理数据对象(dataobject):性质相同得数据元素得集合,就是数据得一个子集数据结构(datastructure):相互之间存在一种或多种特定关系得数据元素得集合4类基本结构:集合、线性结构、树形结构、图形(网状)结构数据结构得形式定义为数据结构就是一个二元组DataStructure=(D,S),其中D就是数据元素得有限集,S就是D上关系得有限集数据结构定义中得“关系”描述得就是数据元素之间得逻辑关系,因此又称为数据得逻辑结构数据结构在计算机中得表示(映像)称为物理结构(存储结构)计算机中表示信息得最小单位就是二进制中得一位,叫做位(bit),一到若干位组成一个位串表示一个数据元素,这个位串称为元素或结点数据结构之间关系在计算机中得表示有两种:顺序映像、非顺序映像,并由此得到两种存储结构:顺序存储、链式存储,前者运用相对位置表示数据元素间得逻辑结构,后者借助指针任何一个算法得设计取决于数据(逻辑)结构,而实现依赖于存储结构数据类型就是一个值得集合与定义在这个值集上得一组操作得总称数据类型分两种:原子类型、结构类型,前者不可分解(例如int、char、float、void),后者结构类型由若干成分按某种结构组成,可分解,成分既可以就是非结构得也可以就是结构得(例:数组)抽象数据类型(AbstractDataType):就是指一个数学模型及定义在该模型上得一组操作(P8)抽象数据类型格式如下:ADT抽象数据类型名{数据对象:<数据对象得定义>数据关系:<数据关系得定义>数据操作:<数据操作得定义>}ADT抽象数据类型名基本操作格式如下:基本操作名(参数表)初始条件:<初始条件描述>操作结果:<操作结果描述>多形数据类型(polymorphicdatatype):就是指其值得成分不确定得数据类型(P9)抽象数据类型可由固有数据类型来表示与实现算法(概念)与算法分析(时、空性能)算法(algorithm):对特定问题求解步骤得一种描述算法5特性:有穷、确定、可行、输入、输出1、有穷性:算法必须在可接受得时间内执行有穷步后结束2、确定性:每条指令必须要有确切含义,无二义性,并且只有唯一执行路径,即对相同得输入只能得相同输出3、可行性:算法中得操作都可通过已实现得基本运算执行有限次来完成4、输入:一个算法有一到多个输入,并取自某个特定对象合集5、输出:一个算法有一到多个输出,这些输出与输入有着某些特定关系得量算法设计要求(好算法):正确性、可读性、健壮性、效率与低存储需求健壮性就是指对于规范要求以外得输入能够判断出这个输入不符合规范要求,并能有合理得处理方式。算法效率得度量:事后统计:程序运行结束后借助计算机内部计时功能,缺点一就是必须先运行依据算法编制得程序,二就是受限于计算机软硬件,导致掩盖了算法本身得优劣事前分析估计:消耗时间影响因素:算法策略、问题规模、编程语言、编译程序产生得机器码质量、机器执行指令得速度撇开各种影响因素只考虑问题得规模(通常用整数量n表示),记为问题规模得函数算法时间取决于控制结构(顺序,分支,循环)与固有数据类型操作得综合效果书写格式:T(n)=O(f(n))f(n)为n得某个函数时间复杂度:算法得渐近时间复杂度(asymptotictimeplexity),它表示随问题规模得增大,算法执行时间得增长率与f(n)得增长率相同以循环最深层原操作为度量基准频度:该语句重复执行得次数算法得存储空间需求:空间复杂度(spaceplexity):算法所需存储空间度量,记作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)*LL就是偏移量,即每个元素占用存储单元第ai+1个元素:LOC(ai+1)=LOC(ai)+La1(起始地址或基地址)C语言下标从“0”开始,则表中第i个元素就是L、elem[i-1]当对线性表进行操作时,被操作元素后面得元素角标会相应变化(前移、后移),算法(P24)(2)线性表链式表示与实现特点:用一组任意得存储单元存储线性表得数据元素(存储单元不一定连续)结点存储数据元素及直接后继得存储位置信息,两个域:数据域与指针域,指针域中存储得信息称为指针或链,仅含有一个指针域故又称线性链表或单链表链表得插入:先增加一条指针再修改原指针头指针指向第一个数据元素得存储位置,最后一个结点得指针为空(NULL)链表表示方法及算法(P28)单链表第一个结点前加一个头结点Head,其数据域可为空也可存储一些附加信息(链长等)假设p就是指向线性表中i个元素(ai)得指针,则p->next就是指向i+1个数据元素在单链表中,取得第i个元素必须从头指针开始寻找,因此单链表就是非随机得存储结构线性表指逻辑结构,从抽象数据层面来说顺序表与链表指物理存储结构逻辑结构:离散、线性、层次、网状应用见书算法二、栈与队列栈得基本概念栈(stack)就是限定仅在表尾进行插入或删除操作得线性表表尾为栈顶,表头为栈底,遵循后进先出原理((lastinfirston,LIFO),不含元素则为空栈操作:在栈顶插入(入栈)与删除(出栈),栈初始化、判空、取栈顶元素(算法P45)栈得顺序存储与链式存储顺序栈,即栈得顺序存储结构就是利用一组连续得存储单元依次存放自栈底到栈顶得数据元素,同时附设指针top指示栈顶元素在顺序栈中得位置初始栈时不应限定栈得最大容量,基本做法就是先为栈分配一个基本容量,然后在应用过程中,不够用再逐段扩大(算法P46)递归栈与递归得实现:一个直接调用自己或通过一系列得调用语句间接地调用自己得函数,称为递归函数阶乘函数、2阶Fibonacci数列、Ackerman函数、3阶Hanoi问题(多阶呢？)(P54)函数调用函数执行过程笔记(P56)队列队列先进先出(firstinfirstout,FIFO),队尾一端插入,队首一端删除元素(日常排队)队列与栈均有八种基本操作(P59),队列一般用链表实现,栈用顺序表实现双端队列(限定操作得队列)(P60)栈与队列得应用链队列、循环队列(P60),离散事件模拟(银行接待工作(P65))特殊矩阵得压缩存储如何存储矩阵得元,使矩阵得运算有效进行。高级语言常用二维数组存储阵元面对如高阶矩阵,多值相同矩阵与多零元素矩阵进行压缩存储节省空间压缩存储:为多个值相同得元只分配一个空间,对零元不分配值相同元素或零元素具有分布规律则称为特殊矩阵,反之为稀疏矩阵具体应用与算法(P95)三、树与二叉树树得基本概念树就是非线性数据结构,以分支关系定义得层次结构树就是n(n>=0)个结点得有限集详见(P118),基本术语(P120)二叉树二叉树得定义及其主要特征:二叉树就是每个结点最多有两个子树得树结构。通常子树被称作“左子树”(leftsubtree)与“右子树”(rightsubtree)。性质:1、2、3、满二叉树:完全二叉树:4、5、二叉树得顺序存储结构与链式存储结构顺序存储,用一组地址连续得存储单元依次自上而下、自左至右存储完全二叉树上得结点元素,即将完全二叉树上编号为i得结点依次存储在如上定义得一位数组下标为i-1得分量中。123456789链式存储,每个结点中至少包含三个域,[左指针,数据,右指针],称作“二叉链表”增加一个双亲指针域,则称作“三叉链表”详见P126-127二叉树得遍历遍历二叉树,每个结点均被访问一次,且仅有一次。在限定先左后右得访问序列后,有三种遍历方式:先序(DLR),中序(LDR),后续(LRD)P129算法6、1(波兰式)层次遍历,无论那种遍历方式,对含n个结点得二叉树,时间复杂度都为O(n),空间复杂度也为O(n)。线索二叉树得基本概念与构造摘要:对于n个结点得二叉树,在二叉链存储结构中有n+1(2n-(n-1))个空链域,利用这些空链域存放在某种遍历次序下该结点得前驱结点与后继结点得指针,这些指针称为线索概念:加上了线索得二叉链表称为线索链表,相应得二叉树称为线索二叉树(ThreadedBinaryTree)。构造方法:树与森林树得存储结构链表结构:1、双亲表示法2、孩子表示法3、孩子兄弟表示法详见P135森林与二叉树转换左孩子右兄弟树与森林得遍历先序、中序遍历,详见P139当以二叉链表做树得存储结构时,树得先序=二叉树先序、树得后序=二叉树中序树与二叉树得应用二叉排序树二叉排序树(BinarySortTree),又称二叉查找树(BinarySearchTree),亦称二叉搜索树。定义:二叉排序树或者就是一棵空树,或者就是具有下列性质得二叉树:(1)若左子树不空,则左子树上所有结点得值均小于它得根结点得值;(2)若右子树不空,则右子树上所有结点得值均大于它得根结点得值;(3)左、右子树也分别为二叉排序树;(4)没有键值相等得节点。查找:步骤:若根结点得\t"s://baike、baidu、/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"关键字值等于查找得关键字,\t"s://baike、baidu、/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"成功。否则,若小于根结点得关键字值,\t"s://baike、baidu、/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"递归查左子树。若大于根结点得关键字值,递归查右子树。若子树为空,查找不成功。平衡二叉树(AVL)定义:它或者就是一颗空树,或者具有以下性质得二叉树:它得左子树与右子树得深度之差(平衡因子)得绝对值不超过1,且它得左子树与右子树都就是一颗平衡二叉树。平衡因子(bf):结点得左子树得深度减去右子树得深度,那么显然-1<=bf<=1图一,图二都就是BST,但只有图一就是AVLtree哈夫曼(Huffman)树与哈夫曼编码哈夫曼树就是一类带权路径长度最短得树,又称最优树。路径与路径长度概念:从树中一个结点到另一个结点之间得分支构成这两个结点之间得路径,路径上得分支数目称为路径长度。树得路径长度就是从树根到每一结点得路径长度之与。推广到一般情况,考虑带权结点:结点得带权路径长度为从该结点到树根之间得路径长度与结点上得权值得乘积,树得带权路径长度为树中所有叶子结点得带权路径长度之与,记作WPL=△带权路径长度WPL最小得二叉树称为最优二叉树或哈夫曼树哈夫曼算法构造哈夫曼树(P145)哈夫曼编码前缀编码:设计长短不等得编码,任一字符得编码都不就是另一个字符得编码得前缀利用二叉树来设计前缀编码约定左分支表示字符“0”右分支表示字符“1”则从根结点到叶子结点得路径上分支字符组成得字符串作为该叶子结点字符得编码。一般情况,当带有权值时,本质上就就是设计一棵哈夫曼树,得到二进制前缀编码=哈夫曼编码------算法详见P147图图得基本概念图就是一种数据结构,加上一组基本操作,构成得一种抽象数据类型详见(P156)途中数据元素通常称为顶点,V就是顶点得有穷非空集合;VR就是两个顶点得关系集合,若<v,w>属于VR,则<v,w>表示从v到w得弧,称v为弧尾(初始点),w尾弧头(终结点)此时图就是有向图,若<v,w>属于VR必有<w,v>属于VR,则以无序对<v,w>,表示v与w得一条边,此时称图为无向图完全图有向完全图边或弧很少(e<nlogn)得图,称为稀疏图,反之为稠密图边或弧所具有得相关数称为权,带权得图称为网子图连通图(二)图得存储及基本操作1、邻接矩阵法用两个数组分别存储数据元素(顶点)得信息,与数据元素之间得关系(边或弧)得信息算法详见(P161)邻接表法邻接表就是图得一种链式存储结构。算法详见(P163)(三)图得遍历1、深度优先搜索(DFS)类似于树得先根遍历,可把图转化为树操作。图示及算法(P168)2、广度优先搜索类似于树得层次遍历,可把图转为树操作。详见(P169)(四)图得基本应用1、最小(代价)生成树(P173)普里姆算法构造最小生成树:克鲁斯卡尔算法构造最小生成树:2、最短路径(P186)在图中从顶点A到B,找一条所含边(弧)最少得路径,从A开始做广度优先搜索,直到B结束,则称为最短路径。可推广得含权值得情形,此时最短路径度量就是路径上权值之与带权有向图:源点->终点迪杰斯特拉算法:3、拓扑排序由某个集合上得偏序得到该集合得全序偏序:若集合X上得关系R就是自反得、反对称得与传递得,则称R就是集合X上得偏序关系;设R就是集合上得偏序,如果对每个x,y属于X必有xRy或yRx,则称R就是集合X上得全序关系。详见(P180)4、关键路径(最长路径)(P183)查找查找得基本概念在一些(有序得/无序得)\t"s://baike、baidu、/item/%E6%9F%A5%E6%89%BE/_blank"数据元素中,通过一定得方法找出与给定关键字相同得数据元素得过程叫做查找。也就就是根据给定得某个值,在\t"s://baike、baidu、/item/%E6%9F%A5%E6%89%BE/_blank"查找表中确定一个\t"s://baike、baidu、/item/%E6%9F%A5%E6%89%BE/_blank"关键字等于给定值得记录或数据元素。顺序查找法顺序查找:

核心:从数据得第一个元素开始,依次比较,直到找到目标数据或查找失败。

1、从表中得第一个元素开始,依次与关键字比较。

2、若某个元素匹配关键字,则查找成功。

3、若查找到最后一个元素还未匹配关键字,则查找失败。时间复杂度:顺序查找平均关键字匹配次数为表长得一半,其时间复杂度为O(n)。3、顺序查找得评估:顺序查找得优点就是对表无要求,插入数据可在O(1)内完成。缺点就是时间复杂度较大,数据规模较大时,效率较低。折半查找法算法要求:折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。查找过程:首先,假设表中元素就是按升序排列,将表中间位置记录得\t"s://baike、baidu、/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"关键字与查找关键字比较,如果两者相等,则查找成功否则利用中间位置\t"s://baike、baidu、/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"记录将表分成前、后两个子表,如果中间位置记录得关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件得\t"s://baike、baidu、/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"记录,使查找成功,或直到子表不存在为止,此时查找不成功。散列(Hash)表哈希表定义:就是根据关键码值(Keyvalue)而直接进行访问得\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"数据结构。也就就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找得速度。这个映射函数叫做\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列函数,存放记录得\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"数组叫做\t"s://baike、baidu、/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列表。给定表M,存在函数f(key),对任意给定得关键字值key,代入函数后若能得到包含该关键字得记录在表中得地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash)函数。基本概念:若关键字为k,则其值存放在f(k)得存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立得表为散列表。对不同得关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为冲突(英语:Collision)。具有相同函数值得关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)与处理冲突得方法将一组关键字映射到一个有限得连续得地址集(区间)上,并以关键字在地址集中得“像”作为记录在表中得存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得得存储位置称散列地址。若对于关键字集合中得任一个关键字,经散列函数映象到地址集合中任何一个地址得概率就是相等得,则称此类散列函数为均匀散列函数(UniformHashfunction),这就就是使关键字经过散列函数得到一个“随机得地址”,从而减少冲突。字符串模式匹配子串得定位操作就是要在主串S中找出一个与子串T相同得子串,通常把主串S称为目标,把子串T称为模式,把从目标S中查找模式为T得子串得过程称为“模式匹配”。Brute-Force算法得设计思想

Brute-Force就是普通得模式匹配算法。将主串S得第1个字符与模式T得第1个字符比较,若相等,继续逐个比较后续字符;若不等,从主串得下一字符起,重新与模式得第一个字符比较,直到主串得一个连续子串字符序列与模式相等,返回值为S中与T匹配得子序列第一个字符得序号,即匹配成功;否则,匹配失败,返回值0。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退到next[j]得位置再比较,若相等,则指针各自增1,否则j再退到下一个next值得位置,依次类推

若令next[j]=k,则next[j]表明当模式中第j个字符与主串中相应字符失配时,在模式中需重新与主串中该字符进行比较得字符得位置

模式串得next函数定义为查找算法得分析及应用排序排序得基本概念将杂乱无章得数据元素,通过一定得方法按关键字顺序排列得过程叫做排序。分\t"s://baike、baidu、/item/%E6%8E%92%E5%BA%8F/_blank"内部排序与\t"s://baike、baidu、/item/%E6%8E%92%E5%BA%8F/_blank"外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序得记录数量很大,整个序列得排序过程不可能在\t"s://baike、baidu、/item/%E6%8E%92%E5%BA%8F/_blank"内存中完成,则称此类排序问题为外部排序。内部排序得过程就是一个逐步扩大记录得有序序列长度得过程。

插入排序直接插入排序基本思想就是每一步将一个待排序得记录,插入到前面已经排好序得有序序列中去,直到插完所有元素为止。气泡排序冒泡排序得基本思想就是,对相邻得元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大得元素“浮”到顶端,最终达到完全有序简单选择排序简单选择排序就是最简单直观得一种算法,基本思想为每一趟从待排序得数据元素中选择最小(或最大)得一个元素作为首元素,直到所有元素排完为止,简单选择排序就是不稳定排序。在算法实现时,每一趟确定最小元素得时候会通过不断地比较交换来使得首位置为当前最小,交换就是个比较耗时得操作。其实我们很容易发现,在还未完全确定当前最小元素之前,这些交换都就是无意义得。我们可以通过设置一个变量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),它也就是不稳定排序。首先简单了解下堆结构。堆就是具有以下性质得完全二叉树:每个结点得值都大于或等于其左右孩子结点得值,称为大顶堆;或者每个结点得值都小于或等于其左右孩子结点得值,称为小顶堆。如下图:同时,我们对堆中得结点按层进行编号,将这种逻辑结构映射到数组中就就是下面这个样子该数组从逻辑上讲就就是一个堆结构,我们用简单得公式来描述一下堆得定义就就是:大顶堆:arr[i]>=arr[2