事业单位招聘考试论坛

 找回密码
 立即注册
12
返回列表 发新帖

2018年国家电网考试备考计算机之数据结构与算法

[复制链接]

0

主题

1万

帖子

2万

积分

论坛元老

Rank: 8Rank: 8

积分
26936
发表于 2017-11-2 23:05:54 | 显示全部楼层

        
                 
       

201409273308.png

201409273308.png

       

201409276608.png

201409276608.png

       

201409279208.png

201409279208.png

       

2014092712808.png

2014092712808.png

        从代码中可以得到,n个顶点和e条边的无向网图的创建,时间复杂度为O(n + n2 + e),其中对邻接矩阵Grc的初始化耗费了O(n2)的时间。
       
回复 支持 反对

使用道具 举报

0

主题

1万

帖子

2万

积分

论坛元老

Rank: 8Rank: 8

积分
27110
发表于 2017-11-3 00:34:20 | 显示全部楼层

        
                 
        1.2 邻接表
        邻接矩阵是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表。
        邻接表的处理方法是这样的:
        (1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
        (2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。
        例如,下图就是一个无向图的邻接表的结构。
       

        对于邻接表结构,图的建立代码如下。
       

       

       
回复 支持 反对

使用道具 举报

0

主题

1万

帖子

2万

积分

论坛元老

Rank: 8Rank: 8

积分
26784
发表于 2017-11-3 01:28:02 | 显示全部楼层

        
                 
       

       

       

        对于无向图,一条边对应都是两个顶点,所以,在循环中,一次就针对i和j分布进行插入。
        本算法的时间复杂度,对于n个顶点e条边来说,很容易得出是O(n+e)。
        1.3 十字链表
        对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才知道,反之,逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法:十字链表,就是把邻接表和逆邻接表结合起来的。
        重新定义顶点表结点结构,如下所示。
       
回复 支持 反对

使用道具 举报

0

主题

1万

帖子

2万

积分

论坛元老

Rank: 8Rank: 8

积分
27110
发表于 2017-11-3 01:47:37 | 显示全部楼层

        
                 
       

        重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说,它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点,如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2,如上图圆圈2。对于顶点v1,它有一个入边顶点v2,所以它的firstin指向顶点v2的边表结点中headvex为1的结点,如上图圆圈3。
        十字链表的好处就是因为把邻接表和逆邻接表整合在一起,这样既容易找到以v为尾的弧,也容易找到以v为头的弧,因而比较容易求得顶点的出度和入度。
        而且除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图应用中,十字链表是非常好的数据结构模型。
        这里就介绍以上三种存储结构,除了第三种存储结构外,其他的两种存储结构比较简单。
        二、图的遍历
        图的遍历和树的遍历类似,希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫图的遍历。
        对于图的遍历来说,如何避免因回路陷入死循环,就需要科学地设计遍历方案,通过有两种遍历次序方案:深度优先遍历和广度优先遍历。
        2.1 深度优先遍历
        深度优先遍历,也有称为深度优先搜索,简称DFS。其实,就像是一棵树的前序遍历。
        它从图中某个结点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中的所有顶点都被访问到为止。
        我们用邻接矩阵的方式,则代码如下所示。
       

       
回复 支持 反对

使用道具 举报

0

主题

1万

帖子

2万

积分

论坛元老

Rank: 8Rank: 8

积分
26993
发表于 2017-11-3 02:22:04 | 显示全部楼层

        
                 
        如果使用的是邻接表存储结构,其DFSTraverse函数的代码几乎是相同的,只是在递归函数中因为将数组换成了链表而有不同,代码如下。
       

        对比两个不同的存储结构的深度优先遍历算法,对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找某个顶点的邻接点需要访问矩阵中的所有元素,因为需要O(n2)的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。
        2.2 广度优先遍历
        广度优先遍历,又称为广度优先搜索,简称BFS。图的广度优先遍历就类似于树的层序遍历了。
        邻接矩阵做存储结构时,广度优先搜索的代码如下。
       

        对于邻接表的广度优先遍历,代码与邻接矩阵差异不大, 代码如下。
       

        对比图的深度优先遍历与广度优先遍历算法,会发现,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的,只是不同的情况选择不同的算法。
       
回复 支持 反对

使用道具 举报

0

主题

1万

帖子

2万

积分

论坛元老

Rank: 8Rank: 8

积分
27060
发表于 2017-11-3 03:03:59 | 显示全部楼层

        
                 
        7.堆 (Heap)
        在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。
        例程
        为将元素X插入堆中,找到空闲位置,建立一个空穴,若满足堆序性(英文:heap order),则插入完成;否则将父节点元素装入空穴,删除该父节点元素,完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。
        void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full.\n" ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}
        以上是插入到一个二叉堆的过程。
        DeleteMin,删除最小元,即二叉树的根或父节点。删除该节点元素后,队列最后一个元素必须移动到堆得某个位置,使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。
        ElementType DeleteMin( PriorityQueue H ){ int i, Child; ElementType MinElement, LastElement; if( IsEmpty( H ) ) { printf( "Queue is empty.\n" ); return H->Elements[0]; } MinElement = H->Elements[1]; LastElement = H->Elements[H->Size--]; for( i = 1; i*2 Size; i = Child ) { /* Find smaller child. */ Child = i*2; if( Child != H->Size && H->Elements[Child+1] Elements[Child] ) Child++; /* Percolate one level. */ if( LastElement > H->Elements[Child] ) H->Elements[i] = H->Elements[Child]; else break; } H->Elements[i] = LastElement; return MinElement;}
        7.算法设计的分析技术
        算法是对问题求解过程的准确描述,由有限条指令组成,这些指令能在有限时间内执行完毕并产生确定性的输出。
        进行算法的时间复杂度分析,就是求其T(n),并用O、Ω或是Θ以尽可能简单的形式进行表示。
        理想情况下,希望能够使用Θ表示算法的时间复杂性。退而求其次,可以使用O或是Ω。
        使用O时,希望估计的上界的阶越小越好。
        使用Ω时,希望估计的下界的阶越大越好。
        树的高度为ëlognû,所以将一个元素插入大小为n的堆所需要的时间是O(logn).
        delete(H,i) 所需要的时间是O(logn).
        make-heap(A): 从数组A创建堆
        方法1:从一个空堆开始,逐步插入A中的每个元素,直到A中所有元素都被转移到堆中。
        时间复杂度为O(nlogn).
        方法2:
        MAKEHEAP(创建堆)
        输入:数组A[1…n]
        输出:将A[1…n]转换成堆
        1. fori← ën/2û downto 1
        2. Sift-down(A,i){使以A[i]为根节点的子树调整成为堆,故调用down过程}
        3. endfor
        时间复杂度为O(n).
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|新都网 ( 京ICP备09058993号 )

GMT+8, 2024-5-8 11:13 , Processed in 0.104461 second(s), 8 queries , WinCache On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表