2023年数据结构知识点整理

数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序辨认和解决的符号（数值、字符等)的集合。数据元素（数据成员）是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等数据对象具有相同性质的数据元素（数据成员)的集合数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure＝{D,R}其中，Ｄ是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。数据类型是指一种类型,以及定义在这个值集合上的一组操作的总称。ﻫ判断一个算法的优劣重要标准:对的性、可使用性、可读性、效率、健壮性、简朴性。算法效率的衡量方法:后期测试,事前估计算法分析是算法的渐进分析简称数据结构涉及“逻辑结构”和“物理结构”两个方面（层次):逻辑结构是对数据成员之间的逻辑关系的描述,它可以用一个数据成员的集合和定义在此集合上的若干关系来表达物理结构是逻辑结构在计算机中的表达和实现，故又称“存储结构”线性表的定义：n(³0)个表项的有限序列L=（a1,ａ2,…,ａn）ａi是表项,n是表长度。第一个表项是表头,最后一个是表尾。线性表的特点:表中元素的数据类型相同;线性表中,结点和结点间的关系是一对一的,有序表和无序表线性表的存储方式。一,顺序存储方式，二,链表存储方式。顺序表的存储表达有2种方式：静态方式和动态方式。顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺序访问，也可以随机访问。单链表是一种最简朴的链表表达,也叫线性链表，用她来表达线性表时，用指针表达结点间的逻辑关系。特点:是长度可以很方便地进行扩充。连续存储方式(顺序表)特点:存储运用率高，存取速度快缺陷:插入、删除等操作时需要移动大量数据：链式存储方式(链表)特点：适应表的动态增长和删除。缺陷:需要额外的指针存储空间单链表的类定义:多个类表达一个概念(单链表）。分为:链表结点(LiｓtＮoｄｅ)类，链表(Lisｔ)类。循环链表的概念:是另一种形式的表达线性表的链表，它的结点结构与单链表相同,与单链表不同的是链表中表尾结点的LINK域中不是NULL，而是存放了一个指向链表开始结点的指针，这样，只要知道表中任何一个结点的地址，就能遍历表中其他任何一结点。双向链表的概念:在双向链表的没饿结点中应有两个链接指针作为它的数据成员：1LIＮK指示它的前驱结点,RＬINＫ指示它的后继结点，因此，双向链表的每个结点至少有３个域:1LINK（前驱指针)DＡDA(数据）RLINＫ（后继指针)。栈：定义为只允许在表的末端进行插入和删除的线性表。特点是：后进先出。递归的定义:若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况经常用到递归方法一。定义是递归的二。数据结构是递归的三问题的解法是递归的。队列：队列是只允许在一端删除,在另一端插入的顺序表允许删除的一端叫做队头，允许插入的一端叫做队尾。特性：先进先出。优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维数组的推广。多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简朴。字符串是n(³0)个字符的有限序列,记作S：“c1c2c3…cn”其中，S是串名字c1ｃ2ｃ3…cｎ”是串值ci是串中字符n是串的长度，广义表是n（≥0)个表元素组成的有限序列,记作LS(ａ１，a２,a3,…,aｎ),LS是表名,aｉ是表元素,可以是表(称为子表）,可以是数据元素（称为原子)。n为表的长度。ｎ=0的广义表为空表。n>0时,表的第一个表元素称为广义表的表头（head），除此之外,其它表元素组成的表称为广义表的表尾(taiｌ有根树：一棵有根树Ｔ,简称为树,它是n(ｎ≥0)个结点的有限集合。当n＝0时,T称为空树;否则,Ｔ是非空树,记作Ｔ=｛空集n=0{r,Ｔ1,T2….Tn｝,ｎ＞0ｒ是一个特定的称为根(ｒｏｏｔ）的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m³0)个互不相交的有限集合Ｔ1,Ｔ２,…,Tｍ，每个集合又是一棵树,并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继二叉树的定义:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。完全二叉树:─若设二叉树的深度为k，则共有k层。除第k层外，其它各层(１～k-1)的结点数都达成最大个数,第k层从右向左连续缺若干结点，这就是完全二叉树二叉树的遍历就是按某种顺序访问树中的结点,规定每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R。则也许的遍历顺序有：前序ＶＬR镜像ＶＲL;中序LVR镜像ＲVＬ；后序ＬＲＶ镜像ＲLV前序遍历二叉树算法的框架是：若二叉树为空，则空操作;否则访问根结点(V);前序遍历左子树（L);前序遍历右子树(Ｒ）。遍历结果-＋ａ＊b-ｃd/ef树的后根顺序遍历:当树非空时依次后根遍历根的各棵子树访问根结点:树后根遍历EＦBCGDA；相应二叉树中序遍历EＦBＣGDA；树的后根遍历结果与其相应二叉树。表达的中序遍历结果相同：树的后根遍历可以借助相应二叉树的中序遍历算法实现最小堆和最大堆：假如有一个关键码集合K＝{K０，K１，Ｋ2，K3,….，Kn－1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并满足Ki≤K２i＋1且Kｉ≤K2i+2(或者Kｉ≥Ｋ２i+1且KiK2i+２)ｉ＝0，1,…．[（n-２)/2］，则称这个集合为最小堆或最大堆。堆是最高效的一种数据结构，每次出队列的是优先权最高的元素。用堆实现其存储表达,可以高效运作。堆的建立：有2种方式建立最小的堆,一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分派得到,另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。途径:从树中一个结点到达另一个结点之间的分支构成该两结点之间的途径。途径长度：是指途径上的分支条数，树的途径长度是从树的根结点到每一个结点的途径长度之和。由树的定义,从根结点到达书中每一结点有且仅有一条途径。Ｈuffｍan树:带权途径长度最小的二叉树应是权值大的外结点离根结点最近的扩充二叉树。带途径长度最小的扩充二叉树不一定是完全二叉树。集合是成员（元素)的一个群集。集合中的成员可以是原子(单元素），也可以是集合。字典是一些元素的集合,每个元素有一个称作关键码(keｙ）的域，不同元素的关键码互不相同。散列方法：抱负的搜索方法是可以不通过比较，一次直接从字典中得到要搜索的元素。假如在元素存储位置与其关键码之间建立一个拟定的相应函数关系Hasｈ(),使得每个关键码与结构中一个唯一的存储位置相相应:Ａｄdress=Hａｓh（key)。在插入时依此函数计算存储位置并按此位置存放。在搜索时对元素的关键码进行同样的计算,把求得的函数值当做元素存储位置,在结构中按此位置搜索。这就是散列方法。在散列方法中所用转换函数叫做散列函数。按此方法构造出来的表叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较,搜索速度比较快，可以直接到达或逼近具有此关键码的表项的实际存放地址。散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有也许通过散列函数的计算，把不同的关键码映射到同一个散列地址上,这就产生了冲突搜索就是在数据集合中寻找满足某种条件的数据对象。搜索的结果通常有两种也许:搜索成功,即找到满足条件的数据对象。这时,作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息。搜索不成功,或搜索失败。作为结果,应报告一些信息,如失败标志、位置等搜索结构通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象(或记录)组成。在每个对象中有若干属性,其中有一个属性，其值可唯一地标记这个对象。称为关键码。使用基于关键码的搜索，搜索结果应是唯一的。但在实际应用时,搜索条件是多方面的,可以使用基于属性的搜索方法，但搜索结果也许不唯一。实行搜索时有两种不同的环境。静态环境,搜索结构在插入和删除等操作的前后不发生改变。¾静态搜索表动态环境，为保持较高的搜索效率,搜索结构在执行插入和删除等操作的前后将自动进行调整,结构也许发生变化。¾动态搜索表顺序搜索重要用于在线性表中搜索。设若表中有ＣuｒrｅntSize个元素，则顺序搜索从表的先端开始,顺序用各元素的关键码与给定值x进行比较若找到与其值相等的元素,则搜索成功,给出该元素在表中的位置。若整个表都已检测完仍未找到关键码与x相等的元素,则搜索失败。给出失败信息二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树：1每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。2左子树（假如非空）上所有结点的关键码都小于根结点的关键码。3右子树（假如非空)上所有结点的关键码都大于根结点的关键码。４左子树和右子树也是二叉搜索树。二叉搜索树为二叉排序树假如对一棵二叉搜索树进行中序遍历,可以按从小到大的顺序,将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为ｘ的元素,搜索过程从根结点开始。假如根指针为NＵLL，则搜索不成功；否则用给定值x与根结点的关键码进行比较：若给定值等于根结点关键码,则搜索成功,返回搜索成功信息并报告搜索到结点地址。若给定值小于根结点的关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子二叉搜索树的插入算法:为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前,先使用搜索算法在树中检查要插入元素有还是没有。假如搜索成功，说明树中已有这个元素,不再插入;假如搜索不成功,说明树中本来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。图定义：图是由顶点集合（ｖerｔex)及顶点间的关系集合组成的一种数据结构：Ｇraph=（V,E)其中V={x|ｘÎ某个数据对象}是顶点的有穷非空集合；E＝｛(x,y)|ｘ，ｙÎV}或E={＜x,y>｜x，ｙÎV&&Path（x，y）},是顶点之间关系的有穷集合,也叫做边(ｅdge)集合。Path(x,y)表达从x到y的一条单向通路,它是有方向的。有向图与无向图：在有向图中,顶点对＜x,y>是有序的。在无向图中，顶点对（ｘ,y)是无序的。完全图:若有n个顶点的无向图有n(n-１)/2条边，则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图在图的邻接矩阵表达中，有一个记录各个顶点信息的顶点表,尚有一个表达各个顶点之间关系的邻接矩阵。邻接表是邻接矩阵的改善形式。为此需要把邻接矩阵的各行分别组织为一个单链表。在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边（边结点）,结点中有另一顶点的下标dest和指针link。对于带权图，边结点中还要保存该边的权值cｏst。顶点表的第i个顶点中保存该顶点的数据，以及它相应边链表的头指针adｊ最短途径问题：假如从图中某一顶点（称为源点)另一顶点(称为终点)的途径也许不止一条,如何找到一条途径使得沿此途径上各边上的权值总和达成最小。排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表（ｄatalist):它是待排序数据元素的有限集合。排序码(ｋey):通常数据元素有多个属性域，即多个数据成员组成,其中有一个属性域可用来区分元素，作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码,要视具体的应用需要而定。插入排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上,直到元素所有插入为止。链表1、单链表中的插入与删除第一种情况:在第一个结点前插入ｎewnodｅ→lｉｎk=ｆirst；first=neｗｎoｄe;第二种情况：在链表中间插入newnｏde→link=p→link; p→linｋ=newnｏde;第三种情况：在链表末尾插入nｅwnoｄe→link＝p→link; ﻩp→liｎk=lasｔ＝neｗnｏdｅ；２、链表插入算法实现３、链表结点删除算法intLisｔ：：Iｎsｅrｔ(coｎstintx,ｃonｓｔinti){／／在链表第i个结点处插入新元素xListNoｄe*p=fiｒst;iｎtｋ=0；wｈile(p!=NULL&&k<i－１）{p＝p→ｌink;k++;}//找第i-1个结点if（ｐ==ＮＵLL&＆fｉｒsｔ!=NＵLL){ﻩcｏuｔ<<“无效的插入位置!\n”;retｕrn０;}ﻩＬｉｓｔNｏde＊ｎewｎｏｄe=newListNｏｄe(ｘ,NULL);/／创建新结点,其数据为x,指针为0if（fiｒｓt＝=ＮＵLL|｜i==0)｛/／插在表前ｎｅwnｏde→link＝ｆｉrst;ﻩﻩﻩif（fｉｒst==NULＬ)lａsｔ＝neｗnode;ﻩfirsｔ=ｎewnｏde;｝else{／/插在表中或末尾neｗnｏde→lｉnk=p→lｉnk； if（p→link=＝NUＬL）last=neｗｎｏde;p→lｉnk=ｎeｗｎode;}return1; ﻩﻩﻩ ﻩ}intList::Removｅ(ｉnti)｛／/在链表中删除第i个结点Nodｅ*p=fiｒst,＊q;intｋ=0;while(ｐ!=ＮＵＬL&&k<ｉ-1)｛ｐ=p→link；ｋ+＋;｝//找第i-1个结点iｆ（p＝=NULＬ||p→link=＝NＵLL){cout<<“无效的删除位置!＼n”；reｔuｒn0;}if(i==０)｛／／删除表中第1个结点q＝fiｒsｔ;//ｑ保存被删结点地址p=firsｔ=first→link;／/修改fiｒst｝ ﻩeｌｓe{ﻩﻩ//删除表中或表尾元素ｑ=p→link；p→liｎk=q→link;／/重新链接｝ﻩ ﻩif（q=＝last)lａst＝ｐ; ／/也许修改ｌａsｔｋ＝q→dａtａ;deleteq;/／删除qｒｅｔurnk; ﻩﻩ}在带表头结点的单链表,第一个结点前插入新结点newnoｄｅ→lｉnｋ＝p→ｌiｎk;ﻩif(ｐ→link=＝NULL)last=ｎewnｏdｅ；p→ｌiｎk=newｎode;从带表头结点的单链表中删除第一个结点q=p→ｌink；p→link=q→liｎk;delｅteq;if(p→lｉnｋ==NＵLＬ)lasｔ=ｐ;排序直接插入排序的算法折半插入排序的算法#inclｕde"ｄａtaＬｉst.ｈ"teｍpｌate<cｌassT>vｏidInsertＳort（daｔａＬist＜Ｔ>&Ｌ,intleft，intrｉght）{/／依次将元素Ｌ.Vectoｒ［i]按其排序码插入到有序表/／L.Ｖｅｃtor[ｌeft]，…,L.Vector[i-1]中,使得//L.Vecｔor[lｅft]到L．Vｅctoｒ[ｉ］有序。Elｅmｅｎt<T>temp;inti,j;ｆｏr（i=lｅｆt＋1;ｉ＜=ｒighｔ；ｉ+＋)if(Ｌ[ｉ]＜L[i-1]){ｔemp＝L[ｉ］;ｊ=i-1;do｛L[j+1]=L［j]；j--；}whiｌｅ（j＞＝leｆt&&ｔemp<L[ｊ]);Ｌ[j+1]=temp;｝｝; #ｉncluｄe"dataList.ｈ"template＜claｓsT＞voidBinaryInseｒtSoｒｔ(ｄatａList＜Ｔ>&L,coｎsｔintlｅft,ｃonstiｎｔright)｛//运用折半搜索,在Ｌ.Vectoｒ[leｆt］到L.Veｃtor[i-1]中//查找L.Veｃtｏr[ｉ]应插入的位置,再进行插入。Ｅleｍeｎｔ＜Ｔ>ｔｅmp;inti,lｏw，high,ｍiddlｅ,k；foｒ(i=lefｔ＋1;i<=right；ｉ++){temp=Ｌ[i]；low=left;high＝ｉ－1;ｗhilｅ(ｌoｗ＜＝high){ //折半搜索插入位置mｉddle=(ｌow＋ｈｉgｈ)/2；ﻩ/／取中点iｆ(temp<L[ｍiddlｅ］)ﻩ//插入值小于中点值high=midｄle-1;ﻩ／/向左缩社区间eｌseｌｏｗ=midｄle+1;ﻩ//否则,向右缩社区间}foｒ(ｋ=i-1;k>=ｌow;k--)Ｌ[k+1]=L[k］；ﻩ/／成块移动,空出插入位置 L［low］=ｔｅｍp; //插入}}；堆排序的算法直接选择排序的算法tｅｍpｌaｔe＜ｃlａsｓT>vｏiｄHeaｐSorｔ(datａLisｔ<T>&L){//对表L.Ｖｅｃtoｒ［0]到L.Vector[n-1]进行排序,使得表／/中各个元素按其排序码非递减有序inｔｉ,n=L.ｌength()；foｒ（ｉ=(n-２)/２;i>=０;i-－) /／将表转换为堆ｓiftDown(L,i，n-1）; for（ｉ=ｎ-１;i>=0;i-－){ ﻩ／/对表排序L.Swaｐ(0，ｉ);siｆｔDown(L,0,i-１);}｝;#iｎclude"datａLiｓｔ.h"tempｌaｔe<cｌaｓsT>ｖoidSelectSort(dａtaＬisｔ＜Ｔ>＆L，ｃｏｎstintleｆt，coｎstｉnｔｒigｈt)｛fｏr(ｉnｔi=left;ｉ<rigｈt;i＋+){intk=i;/在L[ｉ]到L[n-1]找最小排序码元素ｆoｒ(intj=ｉ+1；ｊ<=ｒiｇhｔ;ｊ++）ｉf（L[ｊ］<Ｌ[k]）k=j;if（ｋ!=i）Ｓwap(L［ｉ］,L[k］)； //互换}};希尔排序的算法起泡排序的算法#ｉｎcｌuｄe"dａtａLｉsｔ.h＂teｍplaｔe＜ｃｌassT＞voidShellsorｔ（dataLiｓt<T＞&Ｌ,cｏnsｔiｎtleft，constｉntrｉght）｛inti,j,ｇap=rｉｇhｔ-lｅft＋１;ﻩﻩ//增量的初始值 Elemenｔ<T>tｅｍp;dｏ{gaｐ=gａp/3+1；ﻩ ／/求下一增量值foｒ(ｉ＝lｅｆｔ+gap；i<=righｔ;i+＋)if（L[ｉ]＜L［ｉ－gaｐ]){ﻩﻩ／/逆序teｍp=Ｌ［i］;j＝i-gap;dｏ{L[j+gap]=L[j];ｊ=j－gaｐ；｝while（j>＝ｌefｔ&&temp＜L［j］);Ｌ［j+gap]=tｅmｐ； ／/将ｖeｃtor[i］回送}}whiｌe(gap>1);};ｔｅmｐｌatｅ＜classT>voiｄBｕbbleSort(daｔaLiｓt＜T＞＆L,coｎｓtiｎtleft,ｃonsｔiｎｔｒｉｇht){intpａss＝left+1,exｃhaｎgｅ=1;whｉｌｅ（pasｓ<=right&&exchangｅ){ｅｘcｈanｇe=0;ﻩ //标志为0假定未互换ｆor（intj=ｒiｇht；j>＝pａss;j--)iｆ(L[j-1]>L[j］)｛ﻩ/／逆序Swap(Ｌ[j-１］,L[j]）; //互换 exchange＝１;//标志置为1，有互换}pａss＋＋；}｝;两路归并算法最大堆的向下调整算