大话数据结构十三：二叉树的链式存储结构（二叉链表）

2017年02月05日 37 阅读

大话数据结构十三：二叉树的链式存储结构（二叉链表）2014-12-301. 关于树① 树的度 — 也即是宽度，简单地说，就是结点的分支数。② 树的深度 — 组成该树各结点的最大层次。③ 森林 — 指若干棵互不相交的树的集合。④ 有序树 — 指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。2. 二叉树的特点i、每个结点最多有两颗子树ii、左子树和右子树是有顺序的，次...

大话数据结构十四：二叉树的顺序存储结构（数组实现）

2017年02月05日 33 阅读

大话数据结构十四：二叉树的顺序存储结构（数组实现）2014-12-301. 顺序存储结构：二叉树的顺序存储结构就是用一维数组存储二叉树中的结点。2. 完全二叉树：完全二叉树由于其结构上的特点，通常采用顺序存储方式存储。一棵有n个结点的完全二叉树的所有结点从1到n编号，就得到结点的一个线性系列。如下图：完全二叉树除最下面一层外，各层都被结点充满了，每一层结点的个数恰好是上一层结点个数的2倍，因此通过一个结点的编号就可以推知它的双亲结点及左，右孩子结点的编号：...

大话数据结构十五：线索二叉树

2017年02月05日 35 阅读

大话数据结构十五：线索二叉树2014-12-301. 什么是线索二叉树？n个结点的二叉链表中含有（2n-（n-1）=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。2. 为什么要加线索？① 很多空指针域没有存储任何事物，对内存资源是一种浪费。② 二叉链表中，我们只能知道每个结点指向其左右孩子结点...

大话数据结构十六：哈夫曼树（最优二叉树）

2017年02月05日 37 阅读

大话数据结构十六：哈夫曼树（最优二叉树）2014-12-301. 引子当前素质教育的背景下，小学的学科成绩都改为了优秀、良好、及格、不及格这样的模糊词语，而不再通报具体的分数。用代码可以表示如下：if（ a < 60 ）System.out.print（"不及格"）;else if（ a < 70 ）System.out.print（"及格"）;else if（ a < 90 ）System.out...

大话数据结构十七：图的一些概念

2017年02月05日 35 阅读

大话数据结构十七：图的一些概念2014-12-30图的基本术语：1） 图（Graph）：图G由两个集合V和E组成，记为G=（V,E），这里V是顶点的有穷非空集合，E是边（或弧）的集合，而边（或弧）是V中顶点的偶对。顶点（Vertex）：图中的结点又称为顶点。边（Edge）：相关顶点的偶对称为边。2） 有向图（Digraph）：若图G中的每条边都是有方向的，则称G为有向图。弧（Arc）：又称为有向边。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常...

大话数据结构十八：图的存储结构之邻接矩阵

2017年02月05日 36 阅读

大话数据结构十八：图的存储结构之邻接矩阵2014-12-301. 邻接矩阵（无向图）的特点：图的邻接矩阵存储方式是用两个数组来表示图：1.）一个一维数组存储存储图中顶点信息。2.）一个二维数组（称为邻接矩阵）存储图中边或弧的信息。上图中我们设置两个数组：顶点数组：vertex[4] = {V0，V1，V2，V3}边数组：arc[4][4] 为对称矩阵（0表示顶点间不存在边，1表示顶点间存在边）2. 邻接矩阵（有向图）的特点：无向图的边构成了一个对称矩阵，貌...

大话数据结构十九：图的存储结构之邻接表

2017年02月05日 35 阅读

大话数据结构十九：图的存储结构之邻接表2014-12-301. 邻接表（无向图）的特点：有时候邻接矩阵并不是一个很好的选择：如上图： 边数相对顶点较少，这种结构无疑是存在对存储空间的极大浪费。邻接表： 数组和链表结合一起来存储。1.）顶点用一个一位数组存储。2.）每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择单链表来存储。2. 邻接表（有向图）的特点：把顶点当弧尾建立的邻接表，这样很容易就可以得到每个顶点的出度。有时为了便于确...

大话数据结构二十：图的存储结构之十字链表

2017年02月05日 35 阅读

大话数据结构二十：图的存储结构之十字链表2014-12-301. 引言：对于有向图来说，邻接表是有缺陷的：邻接表：关心了出度问题，想了解入度就必须要遍历整个图才知道。逆邻接表：解决了入度，却不了解出度的情况。能否把邻接表和逆邻接表结合起来呢？答案就是：使用十字链表。2.十字链表存储结构：顶点表结点结构：firstin：表示入边表头指针，指向该顶点的入边表中第一个结点。firstout：表示出边表头指针，指向该顶点的出边表中的第一个结点。边表结点结构：tai...

大话数据结构二十一：图的存储结构之邻接多重表

2017年02月05日 34 阅读

大话数据结构二十一：图的存储结构之邻接多重表2014-12-301.引言：若要删除左边的（V0，V2）这条边，需要对图下表的阴影两个结点进行删除操作。2.邻接多重表的存储结构：iVex和jVex：是与某条边依附的两个顶点在顶点表中的下标。iLink：指向依附顶点iVex的下一条边。jLink：指向依附顶点jVex的下一条边。3.邻接多重表示意图绘制：作者：csdn博客 zdp072...

大话数据结构二十二：图的存储结构之边集数组

2017年02月05日 36 阅读

大话数据结构二十二：图的存储结构之边集数组2014-12-301. 边集数组简介：边集数组由两个一维数组构成：1.） 一个存储顶点信息。2.） 一个存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）、和权（weight）组成。2. 边集数组适用场景：边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。作者：csdn博客 z...

详解Sha-1算法

2017年02月05日 35 阅读

详解Sha-1算法2015-02-11在信息系统中，安全目标的实现除了保密技术外，另一个重要方面就是认证技术，认证技术主要用于防止对手对系统进行主动攻击，如伪装，窜扰等，这对于开放环境中的信息安全就显得尤为重要，认证的目的有两方面，一是验证信息的发送者是合法的，二是验证信息的完整性。一、Hash函数和消息完整性Hash函数也称为杂凑函数或散列函数，其输入为一可变长度x返回一固定长度串，该串被称为输入x的Hash值，还有形象的说法就是数字指纹，因为Hash函...

记录每个客户的通话情况并计算出每个客户的月账单情况

2017年02月05日 46 阅读

记录每个客户的通话情况并计算出每个客户的月账单情况2015-02-11题目概述系统会记录每个客户的通话情况, 会告诉你每个时间段（00:00~01:00, 01:00~02:00, ...）的通话费用. 要求计算出每个客户的月账单情况.输入每个输入包含测试用例, 每个测试用例包含两部分: 每个时间段的通话费用（分（cent）/分钟）和每个客户的通话情况.通话费用由24个非负整数组成, 代表了24小时内每个小时的通话费用.接下来N（<= 1000）行是...

已知客户的到达时间T和服务该客户所需时间 计算所有客户的平均等待时间

2017年02月05日 39 阅读

已知客户的到达时间T和服务该客户所需时间 计算所有客户的平均等待时间2015-02-11题目概述假设有N个客户在K个窗口等待服务。 每个窗口可以容纳一个人, 因此其他客户需要进行等待. 当某个客户服务完成后, 下一个客户可以进入该窗口并被服务. 我们假设没有窗口会被占用1小时以上.现在我们给出每个客户的到达时间T和服务该客户所需要的时间P, 请计算所有客户的平均等待时间.输入每个输入文件包含一个测试用例. 每个测试用例, 第一行包含两个整数N（ <=...

数的计数：找出具有下列性质数的个数

2017年02月05日 36 阅读

数的计数：找出具有下列性质数的个数2015-02-11题目概述我们要求找出具有下列性质数的个数（包含输入的自然数n）:先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理1. 不作任何处理;2. 在它的左边加上一个自然数，但该自然数不能超过原数的一半;3. 加上数后，继续按此规则进行处理，直到不能再立生自然数为止.输入一个自然数n.输出一个整数, 总的个数.解题思路我不得不说, 这题意叙述得实在是...非常棒！ 举个栗子说: 若n ...

0-1背包问题思想的算法题目

2017年02月05日 36 阅读

0-1背包问题思想的算法题目2015-02-11题目概述经过抽签选择, 小智将军第一个进入考场.菜虫: （身上散射出华贵（？）的光芒）欢迎你, 第一位挑战者！！小智: ……（走到菜虫身后, 关灯）女王陛下, 虽然我们国家现在很富裕, 但也请您不要浪费电来用这么大功率的灯泡.菜虫（汗）: 啊啊~~爱卿所言甚是~~那么, 你的题目是……我们的情报组织探听到敌人的重要将领——小飞侠星...

编程之美：24点游戏

2017年02月05日 35 阅读

编程之美：24点游戏2015-02-11一、问题描述给玩家4张牌，每张牌牌面值在1~13之间，允许其中有数值相同的牌。采用加、减、乘、除四则运算，允许中间运算存在小数，并且可以使用括号，但每张牌只能使用一次，尝试构造一种表达式，使其运算结果为24.如输入：3 3 7 7输出：（（（3）/（7））+（3））*（7）二、程序实现原理遍历所有可能的组合，直到找到一个符合条件的组合或者遍历所有情况没有找到满足的组合，具体详见代码注释三、程序基本实现#include...

编程之美：1的数目

2017年02月05日 35 阅读

编程之美：1的数目2015-02-11一、问题描述给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下之中所有“1”的个数。例如：N=12,（1,2,3,4,5,6,7,8,9,10,11,12）共有5个1二、解题思想假设N=abcde为一个整数，a,b,c,d,e分别对应十进制数，如果要计算（1到N）百位出现1的个数,他将受三个因素的影响：百位以上的数，百位数和百位一下的数，具体依赖如下：分别设整数N百位以上，百位和百位一...

编程之美：找到符合条件的整数

2017年02月05日 35 阅读

编程之美：找到符合条件的整数2015-02-11一、问题描述任意给定一个正整数N,求一个最小正整数M（M>1），使得N*M的十进制形式只含1和0。比如 N=99,M=1 122 334 455 667 789 ,N*M=111 111 111 111 111 111;M就是当N=99时，符合条件的数二、解题思路考虑将问题转化为：找只含有0和1的能被N整除的最小正整数。可以看出这是和原问题等价的。那么需要将0和1组成的所有数从小到大遍历吗？ 这样的话，...

平面上有n个点 如何寻找距离最远的两个点

2017年02月05日 36 阅读

平面上有n个点 如何寻找距离最远的两个点2015-02-11一、问题描述平面上有n个点，如何寻找距离最远的两个点？二、解题思路第一步，寻找凸包（因为最远距离的两个点一定在凸包上）第二步，用旋转卡（qia）壳 寻找距离最大的点凸包和旋转卡壳算法参见http://blog.csdn.net/kaytowin/article/details/5140111三、代码实现#include<iostream>#include<vector>#i...

实现文件增量同步的算法

2017年02月05日 35 阅读

实现文件增量同步的算法2015-02-11问题：如何增量同步文件，例如一个文本文件有10M，分别存放在A，B两个地方，现在两个文件是完全一样的，但是我马上要在A上对这个文件进行修改，B如何实现自动和A上的文件保持一致，并且网络的传输量最少。应用场景：这样的使用场景太多，这里随便列举几个1.A机器为线上运营的机器，现在需要一台备份的机器B，当A发生宕机的时候，或者硬盘损坏等各种认为非人为原因导致数据不可用时，可以很快从B恢复2.SVN这样的应用场景，不需要每...