按照大纲的知识点整理----数据结构.docx

《按照大纲的知识点整理----数据结构.docx》由会员分享，可在线阅读，更多相关《按照大纲的知识点整理----数据结构.docx（18页珍藏版）》请在优知文库上搜索。

1、一、线性表（一）线性表的定义和根本操作（二）线性表的实现1 .顺序存储结构2 .链式存储结构3 .线性表的应用二、栈、队列和数组（一）栈和队列的根本概念循环队列:为了克服假溢出时移动元素的缺点.循环队列的入队操作：先输入,后加尾指针.循环队列的出队操作：先取数据,后加头指针.队列中元素个数（如同补码原理）rear-front,rear-front0（rear-front+maxsize）%maxsize,rear-front0判断队列的空与满：另设置一个标志位以区别队列是空还是满少用一个元素的空间，约定以“队列头指针在队列尾指针的下一位置上”作为队列呈满状态的标志Qfgt=Qg空.小Q.fro

2、nt=（Q.rear+1）%maxsize,?两因此循环队列中少用一个位置.实际大小为maxsize1（线性存储的情况）（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储对称矩阵:%a=ajide特殊矩阵三角矩阵:0bf00c一a0O-对角矩阵:0b000C如果是上三角矩阵,那么的位置k=i*（i+l）2+j如果是下三角矩阵,那么力的位置k=j*（j+l）2+j,下三角与上三角互相对称的原理.行优先存储：将数组元素按行向量排列开始地址为:loc(0,00)列优先存储：三、树与二叉树/*树有且只有一个根结点，二叉树有0个或1个根结点(一)树的概念

3、(二)二叉树1.二叉树的定义及其主要特征空二叉树(2)只有根节点的二叉树二叉树的五种类型(3)没有左子树的二叉树(4)没有右子树的二叉树(5)同时有左右子树的二叉树2 .二叉树的顺序存储结构和链式存储结构3 .二叉树的遍历(1)二叉树的递归遍历A.前序B.中序C.后续(2)二叉树的非递归遍历A.前序B.中序C.后序i. 双栈ii. 栈中存标志位的方法iii. 除了栈只用一个指针变量的方法uoidpostorder(bitreebt)bitree*p=null,lastUiSit=null;/*IaStUiSit指向最后访问节点，用于判别右子树是否已经访问WStackst;InitStack(S

4、t);push(st,bt);Mhile(tStackempty(st)lchild?=null)push(st,p-lchild);p=p-lchild;/*此时P指向最左节点*/while(p-rchild=nullp-rchild=lastuisit)&p?=null)lastuisit=pop(st);printf(,%d,lastuisit-data);p-getStack(st);if(p-rchildfnull)push(st,p);*while*postorder*/(3)二叉树的层次遍历4 .线索二叉树的根本概念和构造5 .二叉排序树空树定义(2)1）若左子树不空，则左子树上

5、结点的值均小于根节点的值2）若它的右子树不空，则右子树上结点的值均大于根结点的值3）它的左右子树分别为二叉排序树6.平衡二叉树空树（2）它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1（三）树、森林1.树的存储结构(1)双亲表示法以一组连续空间存储树的结构，同时在每个结点中附设一个指示器指示其双亲结点在链表中位置。孩子表示法顺序与链式相结合的方式datafirstciIdBCDI23（3）孩子兄弟表示法（也即，二叉链表表示法）.占.名吉才句;贵工-LcliAldclgIAn仪trypeder-ctCySTcdcfRIoI-TlClata;SJ-UCfUSZQdeM长

6、lrstChIle1,矢me:XtSibIiKk皂二USlSrOCIGsfcOSTioo;2.森林与二叉树的转换由森林车争换成二文树的转-按规则为：若F=力，WdB=否则由KOO(T1)又才应彳导至UNUe(rct):由(*11，七2tlll)采上应彳导组JLBT二由(T2,T3,.Tn)走十应彳导至URBTO由二又柑专学演为乐和KMT左拳按ML贝U为：若B=e_刎F=cr1吉贝”，r7No.1由LBT.又十应彳寻3JLr.,tLm)i1.7RHTr又十应彳寻壬UT2,T3,.,T.Jo17止匕、才对开D.而和卜合勺餐手中才柒彳乍上勺f-与二攵韦寸合勺多科格彳乍才白乂寸庐应5主意自W是、于7枳

7、寸又寸应臼勺歹一机匕-兵左、右子彳对白勺柢C会已吱变为二左是拔子，后是亢羊将一棵树转换为一叉树的思路,主要根据树的孩子兄弟存储方式而求的,方法是：（Ij树中所方相邻兄弟之间加一条连线J（2）对树中的每个结点，只保K/其与第一介孩子结点之间的连线.删去其与其它孩子结点之间的连线J（3以树的根结心为铀心，杓监探树顺时针除转一方的fl?度，使Z结构层次分明U切以证明，树做武样的转换所构成的叉树是唯一的。2 .森林转换为二义树森林是若十棵树的集合.招可以转换为二叉树，森林同样也可以转换为一叉树。因此，森林也可以力便地用孩子兄弟登去去示,森林转换为二叉树的方法如下：（1）将森林中的每棵树转换成相应的_叉

8、树.（2）第一棵二叉利不动，从第二棵二叉树开始，依次把后一棵叉树的根结点作为前一棵叉树根结点的石孩子当所有二叉树连在一起后，所得到的二叉树就是由森林转换;得到的一叉树.3 .树和森林的遍历比才艮（次存）遍历：若树不空，则先访问才艮结点，然后代次先?艮遍_历各择于枳to后才艮（次序）通历:若木对不空，则先住次后才艮边历备择子树,然后访问才艮结忐一4屋历：若树不空，则奉上而下自主至右访问树中多个结，点、C森林可以分解成三部分:1o森4z卡中第棵树的方艮结点；2。森林中第一根树的子树森林；3。赤林中其它树构成的森X木C树先根遍历后根遍历森林二叉树先手遍历先号遍历中序遍历中声遍历(四)树的应用1 .等

9、价类问题2 .哈夫曼(Huffman)树和哈夫曼编码(1)每次合并权值最小的和次小的.(2)排列时权值左小右大四、图(一)图的概念图中的数据元素为顶点(VerteX),V是顶点的有穷非空集合;VR是两个顶点之间的关系的集合.假设u,w属于VR,那么u,w表示从U到w的一条弧(ArC),且称为弧尾或初始点,w为弧头或终端点,此时的图称为有向图.无向图:以(U,w)表示,w之间的一条边.用G=(V,E)表示图.用n表示图中顶点数目,用e表示边或弧的数目.对于无向图,叫边.对有向图,叫弧对于无向图：0e(一1)1z八-nn-)无向完全图：有2条边对于有向图Oen(n-1)有向完全图:有ST）边的有向

10、图.稀疏图:有很少条边或弧的图.反之称为稠密图.边上的权:表示从一个顶点到另一个顶点的距离或消耗.网：带权的图如果两个顶点之间直接有边相连那么这两个顶点互为临接点.度:和顶点相关联的顶点的数目.入度：以某顶点为头的弧的数目称为该顶点的入度.出度：以某顶点为尾的弧的数目称为该顶点的出度.度=入度+出度路径：从某顶点到另一个顶点的顶点序列.路径的长度:路径上边或弧的数目.回路或环:第个顶点和最后一个顶点相同的路径.简单路径:序列中顶点不重复出现在无向图中：如果从顶点V到顶点W之间有路径,称V和W是连通的.如果图中任意两点都是连通（即任意两点之间都有路径相通）的,那么称G是连通图.连通分量：无向图中

11、的极大连通子图极大连通子图:在原来图的根底上（即包括原来图的所有顶点和边（弧）拥有最多的边数和最多的顶点数的图.一个连通图的生成树是一个极小连通子图.它含有图中全部顶点,但只有足以构成一颗树的n-1条边.如果在一个生成树上添加一条边必定构成i个环.非连通图：有n个顶点和小于n-1条边有n个顶点和大于n-1条边的图肯定有环.但是有n-1条边的图不一定是生成树.在有向图中：如果对任意两个顶点之间都存在一条有向路径,那么称G是强连通图.极大连通子图称为强连通分量.如果一个有向图恰有一个顶点的入度为0,其余定点的入度均为1,那么是一颗有向树.一个有向图的生成森林由假设千颗有向树组成.含有全部顶点,但只

12、有足以构成假设千颗不相交的有向树的弧.（二）图的存储及根本操作1 .邻接矩阵法2 .邻接表法对图中每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点V的边（对有向图是以定点V为尾的弧）.每个节点由三个域构成.Adjvex与顶点V邻接的点在图中的位置Nextarc下一条边或弧的节点Info权值等每个链表上附设一个表头结点.DataFirstarc指向链域这些表头节点通常以顺序结构的形式存储.为了便于确定有向图中定点的入度.建立有向图的逆链接表.在建立邻接表或逆邻接表时,假设输入的定点信息即为顶点的编号,那么建立临界表的时间复杂度为O（n+e）,否那么需要通过查找才能得到顶点在图中的位置,

13、那么时间复杂度为O(n*e).优点：找任意顶点第一个邻接点和下一个邻接点容易缺点：判定两个顶点是否有边或狐不比邻接矩阵方便(三)图的遍历为了防止同一-顶点被访问屡次,设个辅助数组ViSited0.n-l,初始值为0.以下两种搜索对无向图和有向图都适合.1.深度优先搜索类似于树的先根遍历算法描述：初始状态是图中所有顶点都未被访问从图中某个顶点V出发,访问此定点,然后依次从V的未被访问的邻接点出发深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到；如此时图中尚有顶点未被访问,那么另选图中一个未曾被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问到为止.BleanvisitedMax;voidDFSTraverse(GraphG,Status(*Visit)(intv)VisitFunc=Visit;for(v=o;vGvexnum;+v)visitedv=FALSE;for(v=o;v=0;W=NeXtAdjVeX(GV,w)其中FirstAdjVex函数作用是获得第V个节点的第一个边if(!visitedw)DFS(G,w);Status(*VisitFunc)(intv);函数变量是一个静态分