数据结构复习资料

1、数据结构(C+版)第一章绪论(1) 数据结构+算法=程序(2) 数据的逻辑结构：线性表，树，图 等数摇结构。其核心是如何纽织待处理数据以 及数据之间关系。(3) 数据的存储结构：如何将线性表，树，图等数据结构存储到计算机的存储器中，其核 心是如何有效的存储数据以及数据之间的逻辑关系。(4) 常用数据处理技术：包括查找技术，排序技术，索引技术等(5) 数据元素是数据的基本单位，构成数据元素的不可分割的就小单位称为数据项。(6) 数据结构分为以下四类：集合(属于同一集合)，线性结构(一对一)，树结构(一对 多)，图结构(多对多)(7) 数据的存储结构又称为物理结构。(8) 抽象数据类型ADT:包括

2、数据元素间的逻辑关系和操作声明(9) 算法必须满足五个重要特性：输入，输出，有穷性，确定性，可行性(10) 算法的描述方法：自然语言，流程图，程序设计语言，伪代码(11) 算法的时间复杂度：算法中基本语句的执行次数在渐进意艾下的阶，通常用0记号 表彷O(12) 算法的空间复杂度：算法的执行过程中，需要的辅助空间数量。S (n)=0(f (n) n为问題规模第二章线性表(1) 线性表简称表，是n(n> = 0)个具有相同数据元素的有限序列，线性表中数据元素 的个数称为线性表的长度。(2) 元素a1无前驱，元素a n无后继，其他元素有且仅有一个前驱和一个后继。(3) 线性表的存储结构称为顺序

3、表。(4) 顺序表按位查找算法GetTemp I ate <cla s s DataT ype>Data T y p e Se q Li st <DataT y p e> :Get (i n t i)I f ( i < 1 && i>length) t how “查找位置非法“； Else retur n dat a iT;(5) 顺序表按值查找算法LocateT e mp I ate<c I a s s Da t aTyp e >I n t SeqLi s tDataType> : :Loc a te (Dat a Typ

4、e x)For (i=0; i < le n gth ; i+)I f (d a tai=x) ret urn i+1;R eturn 0;(6) 顺序表的存储结构单链表1 单链表的遍历算法Pri ntLi s tTem p la t e<cI a ss Da t aT y p e>Vo i d L inkList<Da taType>: : Pr int L i st ()p= f i r s t->ne x t;whi I e (p! =NULL)Co u t«p>d ata;P=p> n e x t ;2 单傩表的按值佥找算法Lo

5、cateTemp I at e< c la s s D a taT ype>I nt LinkL i st<Da t aTy p e >: :L o cate (Da t aT y p e x)P=fr ist ->next ；count=1;Whi I e (p!二NULL)I f (p >data =x) ret u r n count;P= p ->nex t：Coun t+;r etu r n 0:3 单链表插入算法Inser tTemp I ate V c lass Da t a Type>Void Lin k L is t VData

6、T ype>: I n s ert (i nt i: D a ta T ype x) P = f i r st;c o un t =0;Whi I e (p!=NULL && count<i-1)P=p > next;Count+ i ;I f (p 二二 NULL) t hr ow “位置''；Else S=n e w Node;s->data = x;s ->ne x t=p>ne x t; p ->next= s ;4 尾赭法建立单链表Li n kListT e mp I at e < c I ass Da

7、t aT y p e >Lin k Lis t <D a ta T ype>:L i n k Lis t (Da taTyp e a , i n t n)Fi r st =new Node;R=f i r s t ;F o r (i =0; i <n; i +)s=new Node : s >data= a i;r-> n ex t =s;r=s：r-> n ext 二NULL;第三章栈和队列(1) 栈是限定仅在表尾进行插入和刪除操作的线性表，允许插入和删除的一端称为栈顶, 另一端称为栈底。后进先出事栈的特性。(2) 栈的顺序存储结构顺序栈1 顺序栈入

8、栈算法PushT emp I at e<c I ass Dat aTy p e >Void Se q Stac k <DataType>: Pu s h (Da t a Typex)If (to p =St a ckSi z e - 1 ) thow "上溢"；data + to p=x；2 顺序栈出栈算法PopT em p I at e <clas s Da t a T yp e >If (top=-1) thow “上溢“；x = d a tatop:retun x;(3) 栈的链接存储结构一链栈栈的链接存储结构称为縫栈。1 链栈入栈

9、算法PushTemp late <c I a ss Da t a Type>Vo i d LinkSt a c k <D a t aType>: P ush (DataT y pe x)S=new No d e ;s->da t a=x：S->next二top; t op=s;(4) 队列的定狡:P人列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。 允许插入的一端称为队尾，允许删除的一端称为队头。(5) 臥列的顺序存储结构：循环队列头尾相接的顺序存储结构称为循环队列。重要问題！队空和队满的判定：队空条件fro n t二rear队满条件(rea r

10、 + 1 )%Q u enu e S i z e =from1 循环队列的入队算法EnQueueT emp I a t e<c lass D a ta T ype>Vo i d C i r Queu e <DataType>: E nQue u e (DataT y pe x)I f ( ( r e a r + 1) %QueueSize=front) t hrow” 上溢"；Rear= (rea r+1) %Queu e S i z e ;D a tar e a r =x;2 循环队列出队算法DeQ ueueTemp I a t e<cI ass D

11、ata T ype>Da t aType Ci rQu e u e <Data T y p e>: DeQu e ue ()I f (r e ar=front) t h ro w"下溢”;F ront= (f r ont+ 1 )%Que u e Size;Return data f r o n t;(6) 队列的链接存储结构称为链队列。第四章 字符串和多维数组(1) 字符串，简称串，是零个或者多个字符组成的有限序列。给定两个字符串S = " s1,s2, sn”和T二“2,tn",在主串S中寻找子串T的过程称为模式匹配.T称为模式。1 朴素的模

12、式匹配算法BFI n t BF (char S , c h ar T )l=0;j=0;Whi I e (Si ! =' 0)&&(Tj" (r )lf(s i =T j)i+;j+Else (i = i-j+1;j=O;JI f (Tj = 0f ) re t u r n (i j+1);E I se retur n 0 ;第5章树和二叉树(1) 在树中常将数扌居元素称为结点。树有且仅有一个称为根的结点。(2) 菜结点所拥有的子树的个数称为该结点的度。(3) 树的遍历操作：1前序遍历：访问根结点，按照从左到右的顺序祈序遍历根结点的毎 一棵子树。2后序遍历：按

13、照从左到右的顺序后序遍历根结点的每一棵子树，访问根 结点。3层序遍历：从树的第一层开始，自上而下逐层遍历，在同一层，按从左到右的 顺序对结点逐个访问。(4) 树的存储结构：双亲表示法，孩子表示法，双亲孩子表示法，孩子兄弟表示法。(5) 二叉树:是n个结点的有限集合，该集合或者为空集(称为空二叉树)，或者有一个根结点 和两棵互不相交的，分别称为根结点的左子树和右子树的二义树组成。斜树(每层只有 一个结点)满二叉树(叶子只能出现在最下一层，只有度为0和度为2的结点)完全二叉 树(叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左侧连续的 位置，如果有度为1的结点，只可能有一个，且该结

14、点只有左孩子。)(6) 二叉树的基本性质：1二叉树的第i层上最多有2的(i-1)次方个结点。(i > = 1)2在一棵深度为k的二叉树中，最多有2的k次方T个结点，最少有k个结点。3在一棵二叉树中，如果叶子结点的个数为nO,度为2的结点个数为门2,则nO=n2+14具有n个结点的完全二叉树的深度为I og2 n +1.(7) 二叉树的遍历操作：前序遍历，中序適历(中序遍历根结点的左子树，访问根结点，中序 遍历根结点的右子树)后序遍历，层序遍历由二叉树的后序序列和中序序列课唯一缺定一棵二叉树，但是如果只知道二叉树的前序序 列和后序序列，則不能唯一确定一颗二叉树。(8) 二叉树的存储结构及实

15、现二叉树一般用二叉链表存储：另二叉树的每个结点对应一个链表结点，链表除了存放与二叉 树结点有关的数据信息外，还要设置指示左右孩子的指针。1二叉树的前序遍历递归算法PreOrderTem p I ate<class Da t aType>Vo i d B i T ree<DataType>: P r eOrder (B iNode< DataType>* b t)I f (bt=NULL) return;Else C o ut<< b t > d at a ;PreO r der (bt->lchiId);P reO r de r (b

16、t->rchi Id);2二叉树中序遍历递归算法I nOrde rTemp I ate c las sData T ype>Void B i T re e <D a taT ype>: I n e Orde r (BiNode<Da t aTyp e >*bt)If ( b t=NULL) r etu r n;Else InOrder (bt>lchi Id);Cout<<bt->d ata;InOrder ( b t->r child);3 二叉树的后序遍历算法PostOrd e rTempi at e<cla s sD

17、at a T yp e >Void BiTr e e <D a t aType>: PostOr d e r (B i T ree<DataTy p e >* b t )If (b t =NULL) return ;Else!Pos t 0rder(b t->lchiId);PostOrder (bt->r c h i I d );C o ut«b t ->Data;(9) 层序遍历非递归队列：设豈一个队列存放已访问结点，遍历从二叉树的根结点开始，首 先将根指针入队，然后从队头取出一个元素并执行下述操作：访问该指针所指结点，若该指针 所

18、指结点的左。右孩子结点非空，则將其左孩子指针和右孩子指针入队。电复执行直到队列 为空。(10) 二叉树遍历的非递归算法：1前序遍历非递归算法 PreOrderTern p I a t e<clas s Data T ype>Vo i d B iTre e <DataTyp e >:P r e Ord e r (B i T r ee<Da t aType> * b t)T op=- 1 ;While ( bt!二NULL| | t op!=-1)Whil e (bt!二NULL)Cou t «b t ->data;S4-+top=bt;Bt=b

19、t->I chi Id;I f (top! =- 1) Bt二stop;B t = b t ->rch i Id;(11) 树，森林与二叉树的转换：树转换为二叉树：1 加线树中所有相邻兄弟结点之间加一条连线；2 去线对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩 子结点之间的连线。3 层次调螯以根结点为轴心，将树顺时针转动一定得角度，使之层次分明树的前序遍历=二叉树的询序遍历树的后序遍历=二叉树的中序遍历(12) 森林的遍历：前序(根)遍历和后序(根)遍历前序遍历森林即为前序遍历森林里的每一棵树； 后序遍历森林即为后序遍历森林里的每一棵树。(13) 哈夫曼树：

20、也称最优二叉树，给定一组具有确定权值的叶子结点，可以构造出不同的二 叉树，将其中带权路径长度最小得二叉树称为哈夫曼树。(1 4)前缀编码：如果一组编码中任一编码都不是其他任何一个编码的前缀，我们称这纽编 码为前綴编码。前缀编码保证了编码被解码时不会有多种可能。第六章 图(1) 简单图：若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。(2) 顶点的度，入度，出度：在无向图中，顶点V的度是指依附于该顶点的边的个数，记 为TD (V)o入度是指以该顶点为弧头的弧的个数记为ID(V)°出度是指以该顶点为弧尾 的弧的个数，记为OD (V)o(3) 图的遍历操作：深度优先遍

21、历，广度优先遍历。深度优先遍历：访问顶点V;从V的未被访问的邻接点中选取一个顶点W,从W出发进行深度 优先遍历；重复上述两步，直到图中所有和V有路径想通的顶点都被访问到。广度优先遍历：访问顶点V;依次访问V的各个未被访问的邻接点V 1 ,V2,Vk；分别从 V1,V2,Vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于 “后被访问顶点的邻接点”被访问。直到图中所有和V有路径想通的顶点都被访问到。(4) 邻接矩阵：图的邻接矩阵存储也称数组表示法，其方法是用一个一唯数组存储图中顶点 的信息，用一个二维数组存储图中边的信息(即各顶点之间的邻接关系)，存储顶点之间的邻 接关系的二维

22、数组称为邻接矩阵。(5) 算法在邻接矩阵存储结构下的实现：1深度优先遍历算法 D F STraverseT e mplate <class D ataType>Voi d MG r a p h<Data T y pe>: : DFSTraverse (i nt v )Cout« ver t e xv; v i s i t ed v=1;Fo r (j = 0; j <ver t e x N u m; j +)If (arcv j =1 && visite d j = O)DFSTra v e r se(j);2广度优先遍历算法BFSTra

23、ver seT e mp late <c lassDataType>Void MG ra p h<DataTy p e> : BFSTra v e rse(int v)Fr o n t =rear = 1:Co u t«ver t ex v ; vi s i tedv =1; Q+rear= v ;While (front! =r e a r )V=Q+f r ont:For (j=0; j< v e r texNurn; j+)If (arc v j = = 1 && visitedj=0) Cout<<v e r t e

24、x j ;vi s it e dj =1 ;Q+rea r = j ;最小生成树"殳G = (V, E)是一个无向联通网，生成树上冬边的权值之和称为该生成树的 代价，在G的所有生成树中代价最小的生成树称为灵小生成树。第七章查找技术(1)静态查找，动态查找：不涉入插入和删除操作的查找称为静态查找。涉及插入和删除操作 的查找称为动态查找。(2) 查找时构：面向査找操作的数据结构称为查找结构。线性表:适用于静态査找，主要采用顺序查找技术，折半查找技术。树表：适用于动态查找，主要釆用二叉排序树的查找技术。散列表：赫态查找和动态查找均适用，主要采用散列技术。(3) 顺序表的顺序查找算法 Seq

25、SearchlS eqSearc h 1 ( i n t r , in t n, i nt k)R0 =k：l=n;Whi I e (ri !=k)i ；r etut n i ;(4) 折半查找：要求线性表中的记录必须按关键码有序，并且必须釆用顺序存储。一般只能 应用于赫态查找。1折半查找非递归算法 B i n Search 1B i n Searc h 1 (i nt r , int n, int k)low=1 ;high = n;w h i I e ( I o w<=h i gh)mid=(low +high)/2;if (k<r mid) I ow= m id- 1 ;el

26、se if (k>r mid) low=mid+ 1 ; e I se return mi d ;2折半查找递归算法Bi n Sear ch2I nt Bin Sea r c h2(in t r , i n t low , int high , int k)rif (Iow>hi g h ) r et u r n 0;mid= (low+h i gh) return 0 ;i f (k< r mid) ret u rn BinS e a rc h 2 ( r , Iow, m i d- 1 , k ); else i f(k>r m i d) return Bin Search2 (r, mi d +1,h i gh,k) ; e I se return mid;(5) 二叉排序树：又称二叉查找树它或者是一棵空的二叉树，或者是具有以下性质的二叉 树：若它的左子树不空，则左子