2021年度数据结构知识点_第1页
2021年度数据结构知识点_第2页
2021年度数据结构知识点_第3页
2021年度数据结构知识点_第4页
2021年度数据结构知识点_第5页
已阅读5页,还剩3页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据是信息载体,是描述客观事物数、字符、以及所有能输入到计算机中,被计算机程序辨认和解决符号(数值、字

符等)集合。

数据元素(数据成员)是数据基本单位。在不同条件下,数据元素又可称为元素、结点、顶点、记录等

数据对象具备相似性质数据元素(数据成员)集合

数据构造由某一数据对象及该对象中所有数据成员之间关系构成。记为Data_Structure={D,R}其中,D是某一数据对

象,R是该对象中所有数据成员之间关系有限集合。

数据类型是指一种类型,以及定义在这个值集合上一组操作总称。

判断一种算法优劣重要原则:对的性、可使用性、可读性、效率、健壮性、简朴性。

算法效率衡量办法:后期测试,事前预计

算法分析是算法渐进分析简称

数据构造涉及“逻辑构造”和“物理构造''两个方面(层次):

逻辑构造是对数据成员之间逻辑关系描述,它可以用一种数据成员集合和定义在此集合上若干关系来表达物理构造是

逻辑构造在计算机中表达和实现,故又称“存储构造”

线性表定义:n(>0)个表项有限序列L=(«1,al,an)出是表项,〃是表长度。第一种表项是表头,最后一

种是表尾。

线性表特点:表中元素数据类型相似;线性表中,结点和结点间关系是一对一,有序表和无序表线性表存储方式。一,

顺序存储方式,二,链表存储方式。

顺序表存储表达有2种方式:静态方式和动态方式。

顺序表定义是:把线性表中所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始一块持续存储空间

中。

顺序表特点:用地址持续一块存储空间顺序存储各表项,各表项逻辑顺序与物理顺序一致,对各个表项可以顺序访问,

也可以随机访问。

单链表是一种最简朴链表表达,也叫线性链表,用她来表达线性表时,用指针表达结点间逻辑关系。特点:是长度可

以很以便地进行扩充。

持续存储方式(顺序表)特点:存储运用率高,存取速度快缺陷:插入、删除等操作时需要移动大量数据:

链式存储方式(链表)特点:适应表动态增长和删除。缺陷:需要额外指针存储空间

单链表类定义:各种类表达一种概念(单链表)。分为:链表结点(LisWa/e)类,链表(乙4)类。

循环链表概念:是另一种形式表达线性表链表,它结点构造与单链表相似,与单链表不同是链表中表尾结点LINK域

中不是NULL,而是存储了一种指向链表开始结点指针,这样,只要懂得表中任何一种结点地址,就能遍历表中其她

任何一结点。

双向链表概念:在双向链表没饿结点中应有两个链接指针作为它数据成员:1LINK批示它前驱结点,RLINK批示它后

继结点,因而,双向链表每个结点至少有3个域:1L1NK(前驱指针)DADA(数据)RLINK(后继指针)。

栈:定义为只容许在表末端进行插入和删除线性表。特点是:后进先出。

递归定义:若一种对象某些地包括它自己,或用它自己给自己定义,则称这个对象是递归;若一种过程直接地或间

接地调用自己,则称这个过程是递归过程。如下三种状况常惯用到递归办法一。定义是递归二。数据构造是递归三

问题解法是递归。

队列:队列是只容许在一端删除,在另一端插入顺序表容许删除一端叫做队头,容许插入一端叫做队尾。特性:先进

先出。

优先级队列:是不同于先进先出队列另一种队列。每次从队列中取出是具备最高优先权元素。多维数组是一维数组推

广。

多维数组是一维数组推广。多维数组特点是每一种数据元素可以有各种直接前驱和各种直接后继。数组元素下标普通

具备固定下界和上界,因而它比其她复杂非线性构造简朴。

字符串是n(>0)个字符有限序列,记作S:“clc2c3…cn”其中,S是串名字clc2c3…cn”是串值ci是串中字符〃是

串长度,n=0称为空串。

广义表是〃(》0)个表元素构成有限序列,记作LS(al,al,a3....an),LS是表名,ai是表元素,可以是表(称

为子表),可以是数据元素(称为原子)。"为表长度。"=0广义表为空表。〃>0时,表第一种表元素称为广义表表

头(head),除此之外,其他表元素构成表称为广义表表尾(tail

有根树:一棵有根树T,简称为树,它是〃(〃20)个结点有限集合。当〃=0时,T称为空树;否则,T是非空树,

记作T={空集n=0

{r,Tl,T2....Tn},n>0

r是一种特定称为根(root)结点,它只有直接后继,但没有直接前驱;根以外其她结点划分为胆⑺20)个互不相交有

限集合T1,72,…,Tm,每个集合又是一棵树,并且称之为根子树。每棵子树根结点有且仅有一种直接前驱,但可以

有0个或各种直接后继

二叉树定义:一棵二叉树是结点一种有限集合,该集合或者为空,或者是由一种根结点加上两棵分别称为左子树和右子

树、互不相交二叉树构成。

完全二叉树:一若设二叉树深度为则共有k层。除第A层外,其他各层(1〜&-1)结点数都达到最大个数,第4

层从右向左持续缺若干结点,这就是完全二叉树

二叉树遍历就是按某种顺序访问树中结点,规定每个结点访问一次且仅访问一次。设访问根结点记作V遍历根左子树

记作L遍历根右子树记作R。则也许遍历顺序有:前序VLR镜像VRL;中序LVR镜像RVL;后序LRV镜像RLV

前序遍历二叉树算法框架是:若二叉树为空,则空操作;否则访问根结点(V);前序遍历左子树(L);前序遍历右子树

(R)<,遍历成果-+a*b-cd/ef

树后根顺序遍历:当树非空时依次后根遍历根各棵子树访问根结点:树后根遍历EFBCGDA;相应二叉树中序遍历

EFBCGDA;树后根遍历成果与其相应二叉树。

表达中序遍历成果相似:树后根遍历可以借助相应二叉树中序遍历算法实现

最小堆和最大堆:如果有一种核心码集合K={KO,K1,K2,K3,.Kn-1},把它所有元素按完全二叉树顺序存储方式

存储在一种一维数组中。并满足Ki<K2i+l且KiWK2i+2(或者Ki2K2i+l且KiK2i+2)i=O,l.....[(n-2)/2],则称这个

集合为最小堆或最大堆。

堆是最高效一种数据构造,每次出队列是优先权最高元素。用堆实现其存储表达,可以高效运作。

堆建立:有2种方式建立最小堆,一种方式是通过第一种构造函数建立一种空堆,其大小通过动态存储分派得到,另

一中建立最小堆方式是通过第二个构造函数复制一种记录数组并对其加以调节形成一种堆。

途径:从树中一种结点到达另一种结点之间分支构成该两结点之间途径。

途径长度:是指途径上分支条数,树途径长度是从树根结点到每一种结点途径长度之和。由树定义,从根结点到达书

中每一结点有且仅有一条途径。

Huffman树:带权途径长度最小二叉树应是权值大外结点离根结点近来扩充二叉树。带途径长度最小扩充二叉树不一

定是完全二叉树。

集合是成员(元素)一种群集。集合中成员可以是原子(单元素),也可以是集合。

字典是某些元素集合,每个元素有一种称作核心码(key)域,不同元素核心码互不相似。

散列办法:抱负搜索办法是可以不通过比较,一次直接从字典中得到要搜索元素。如果在元素存储位置与其核心码之

间建立-一种拟定相应函数关系Hash(),使得每个核心码与构造中一种唯一存储位置相相应:Address=Hash(key)。

在插入时依此函数计算存储位置并按此位置存储。在搜索时对元素核心码进行同样计算,把求得函数值当做元素存储

位置,在构造中按此位置搜索。这就是散列办法。在散列办法中所用转换函数叫做散列函数。按此办法构造出来表叫

做散列表。使用散列办法进行搜索不必进行多次核心码比较,搜索速度比较快,可以直接到达或逼近具备此核心码表

项实际存储地址。

散列函数是一种压缩映象函数。核心码集合比散列表地址集合大得多。因而有也许通过散列函数计算,把不同核心码

映射到同一种散列地址上,这就产生了冲突

搜索就是在数据集合中寻找满足某种条件数据对象。搜索成果普通有两种也许:搜索成功,即找到满足条件数据对象。

这时,作为成果,可报告该对象在构造中位置,还可给出该对象中详细信息。搜索不成功,或搜索失败。作为成

果,应报告某些信息,如失败标志、位置等

搜索构造普通称用于搜索数据集合为搜索构造,它是由同一数据类型对象(或记录)构成。在每个对象中有若干属性,其

中有一种属性,其值可唯一地标记这个对象。称为核心码。使用基于核心码搜索,搜索成果应是唯一。但在实际应用

时,搜索条件是多方面,可以使用基于属性搜索办法,但搜索成果也许不唯一。实行搜索时有两种不同环境。静态环

境,搜索构造在插入和删除等操作先后不发生变化。—静态搜索表动态环境,为保持较高搜索效率,搜索构造在执

行插入和删除等操作先后将自动进行调节,构造也许发生变化。—动态搜索表

顺序搜索重要用于在线性表中搜索。设若表中有Currentsize个元素,则顺序搜索从表先端开始,顺序用各元素核心码

与给定值x进行比较若找到与其值相等元素,则搜索成功,给出该元素在表中位置。若整个表都已检测完仍未找到核

心码与x相等元素,则搜索失败。给出失败信息

二叉搜索树或者是一棵空树,或者是具备下列性质二叉树:1每个结点均有一种作为搜索根据核心码(key),所有结点

核心码互不相似。2左子树(如果非空)上所有结点核心码都不大于根结点核心码。3右子树(如果非空)上所有结点

核心码都不不大于根结点核心码。4左子树和右子树也是二叉搜索树。

二叉搜索树为二叉排序树如果对-一棵二叉搜索树进行中序遍历,可以按从小到大顺序,将各结点核心码排列起来,因

此也称二叉搜索树为二叉排序树

在二叉搜索树上进行搜索,是一种从根结点开始,沿某一种分支逐级向下进行比较判等过程。它可以是一种递归过程。

假设想要在二叉搜索树中搜索核心码为x元素,搜索过程从根结点开始。如果根指针为NULL,则搜索不成功;否则

用给定值x与根结点核心码进行比较:若给定值等于根结点核心码,则搜索成功,返回搜索成功信息并报告搜索到结

点地址。若给定值不大于根结点核心码,则继续递归搜索根结点左子树;否则。递归搜索根结点右子

二叉搜索树插入算法:为了向二叉搜索树中插入一种新元素,必要先检查这个元素与否在树中已经存在。在插入之前,

先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功,阐明树中已有这个元素,不再插入;如果搜索不

成功,阐明树中本来没有核心码等于给定值结点,把新元素加到搜索操作停止地方。

图定义:图是由顶点集合(vertex)及顶点间关系集合构成一种数据构造:Graph=(V,E)其中V={x\xe某个数

据对象}是顶点有穷非空集合;E-{(x,y)|x,yeV}或E={<x,y>|x,yeV&&Path(x,y)},是顶点之间关

系有穷集合,也叫做边(edge)集合。Path(x,y)表达仄x到y一条单向通路,它是有方向。

有向图与无向图:在有向图中,顶点对<x,y>是有序。在无向图中,顶点对(x,y)是无序。

完全图:若有〃个顶点无向图有n(n-l)/2条边,则此图为完全无向图。有n个顶点有向图有〃(小1)条边,则此图为

完全有向图

在图邻接矩阵表达中,有一种记录各个顶点信息顶点表,尚有一种表达各个顶点之间关系邻接矩阵。

邻接表是邻接矩阵改进形式。为此需要把邻接矩阵各行分别组织为一种单链表。在邻接表中,同一种顶点发出边链接

在同一种边链表中,每一种链结点代表一条边(边结点),结点中有另一顶点下标dest和指针link。对于带权图,边

结点中还要保存该边权值cost。顶点表第i个顶点中保存该顶点数据,以及它相应边链表头指针adj

最短途径问题:如果从图中某一顶点(称为源点)另一顶点(称为终点)途径也许不止一条,如何找到一条途径使得

沿此途径上各边上权值总和达到最小。

排序:将一组杂乱无章数据按一定规律顺次排列起来。

数据表(dafa/isf):它是待排序数据元素有限集合。

排序码(左分):普通数据元素有各种属性域,即各种数据成员构成,其中有一种属性域可用来区别元素,作为排序根据。

该域即为排序码。每个数据表用哪个属性域作为排序码,要视详细应用需要而定。

插入排序基本办法是:每步将一种待排序元素,按其排序码大小,插入到前面己经排好序一组元素恰当位置上,直到

元素所有插入为止。

链表

1、单链表中插入与删除

第一种状况:在第一种结点前插入第二种状况:在链表中间插入第三种状况:在链表末尾插入

newnode-^link=first;newnode-^link=pfink;newnode-^link=p—link;

first=newnode;pflink=newnode;pfink-last-newnode;

2、链表插入算法实现3、链表结点删除算法

intList::Insert(constintx,constintz){intList::Remove(inti){〃在链表中删除第i个结点

〃在链表第i个结点处插入新元素xNode*p=first,*q;intk=0;

ListNode*p=first;int%=0;while(pNULL&&k<i-1)

while(p!=NULL&&%<,」){p=pink;攵++;)〃找第M个结点

{p-pflink;k++;}〃找第M个结点if(p==NULLIIpfink==NULL){

if(p==NULL&&first!=NULL){cout«“无效删除位置!\n”;

cout«“无效插入位置!\n”;return0;

return0;)

}if(i==0){〃删除表中第1个结点

ListNode^newmode-newListNode(xfNULL);q-first%Hq保存被删结点地址

〃创立新结点,其数据为x,指针为0p=first=firstflink;〃修改

if(first==NULL||Z==0){〃插在表前}

newnode-'link=first;else{〃删除表中或表尾元素

if(first==NULL)last=newnode;q-pflink;

first=newnode;pink=qfink;〃重新链接

)}

else{〃插在表中或末尾if(4==last)last=p;〃也许修改last

newnode-^link=p—/ink;k=q-^data;

if(pflink==NULL)last=newnode;deleteq\〃删除q

p-link=newnode;returnk;

)}

return1;

)

在带表头结点单链表,第一种结点前插入新结点从带表头结点单链表中删除第一种结点

newnode-^link=p—link;q=pflink;p—link=qflink;

if(p-link==NULL)last=newnode;deleteq\

pflink=newnode;if(p—link==NULL)last-p;

排序

直接插入排序算法折半插入排序算法

#include"dataList.h"#include"dataList.h"

template<classT>template<classT>

voidInsertSort(dataList<T>&L,intleft,intright){voidBinarylnsertSort(dataList<T>&L,

〃依次将元素L.Vector[i]按其排序码插入到有序表constintleft,constintright){

〃L・Vcctor[left],・・・,L.Vector[i・l]中,使得〃运用折半搜索,在L.Vecto叩eft]到L.Vector[i・l]中

//L.Vector[left]至1」L・Vector[i]有序。〃查找L.Vector[i]应插入位置,再进行插入。

Element<T>temp;inti,j;Element<T>temp;

for(i=left+1;i<=right;i++)int},low,high,middle,k;

if(L[i]<L[i-l]){for(i=left+1;i<=right;i++){

temp=L[i];j=i-1;temp=L[i];low=left;high=i-1;

do{while(low<=high){〃折半搜索插入位置

LU+l]=L[j];j-;middle=(low+high)/2;〃取中点

}while(j>=left&&temp<L[j]);if(temp<L[middle])〃插入值不大于中点值

L|j+lJ=temp;high=middle-1;〃向左缩社区间

}elselow=middle-*-1;〃否则,向右缩社区间

);)

for(k=i-1;k>=low;k—)L[k+1]=L[k];

〃成块移动,空出插入位置

L[low]=temp;〃插入

)

1;

堆排序算法直接选取排序算法

template<classT>#include"dataList.h1'

voidHeapSort(dataList<T>&L){template<classT>

〃对表L.Vector[0倒L.Vector[n・l]进行排序,使得表voidSelectSort(dataList<T>&L,

〃中各个元素按其排序码非递减有序constintleft,constintright){

inti,n=L.length();for(inti=left;i<right;i++){

for(i=(n-2)/2;i>=0;i-)〃将表转换为堆intk=i;/在L[i]到L[n・l]找最小排序码元素

siftDown(L,i,n-1);for(intj=i+1;j<=right:j++)

for(i=n-1;i>=0;i—){〃对表排序if(LU]<L[k])k=j;

L.Swap(0,i);siftDown(L,0,i-1);if(k!=i)Swap(L[i],L[k]);〃互换

})

};);

希尔排序算法起泡排序算法

#include"dataList.h"template<classT>

template<classT>voidBubbleSort(dataList<T>&L,constintleft,

voidShellsort(dataList<T>&L,constintright){

constintleft,constintright){intpass=left+1,exchange=1;

inti,j,gap=right-left+1;〃增量初始值while(pass<=right&&exchange){

Element<T>temp;exchange=0;〃标志为0假定未互换

do{for(intj=right;j>=pass;j--)

gap=gap/3+1;〃求下一增量值if(L[j-l]>L[j]){〃逆序

for(i=left+gap;i<=right;i++)Swap(L[j-l],L[jJ)5〃互换

if(L[i]<L[i-gap]){〃逆序exchange=1;〃标志置为1,有互换

temp=L[i];j=i-gap;)

do{pass++;

L|j+gap]=L[jJ;j=j-gap;)

}while(j>=left&&temp<L[j]););

L|j+gap]=temp;〃将vector[i]回送

)

}while(gap>I);

);

两路归并算法最大堆向下调节算法

#include"dataList.h0template<classT>

temp

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论