图与基本的图算法

图的基本概念及表示

图的基本概念

逻辑结构二元组B=(K,R),任意一对结点间都允许一个关系存在

  • 分类:无向图、有向图、带权图、稠密图、完全图、连通图等
  • 最一般的数据结构

表示:G=(V, E),有向完全图 $n * (n - 1)$ 条边,无向完全图 $n * (n - 1) / 2$ 条边

带权的连通图称为网络

图G有$n$个顶点,$e$条边,顶点$v_{i}$的度数为$TD(v_{i})$,则有$$e = \frac{1}{2} \sum_{i = 0}^{n - 1}TD(v_{i})$$

环:回路,无向图平行边不构成环,有向图两条边可构成环

阅读剩余部分 -

英语数字转换器

1:英语数字转换器
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在这个问题中,将用英语给你一个或多个整数。你的任务是将这些数字转换成整型表示。数字范围从-999,999,999到999,999,999.下面是你的程序必须考虑的详尽的英语单词表:

negative, zero, one, two, three, four,five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen,fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty,sixty, seventy, eighty, ninety, hundred, thousand, million





阅读剩余部分 -

P2P局域网快速分发大文件

情景

教学环境中局域网分发大文件(如镜像),单文件体积在10G+,如果从某一服务端分发单文件传输虽然可以达到100M/s以上,但是对于网络稳定性要求较高,而且如果并发速度并不理想。同时由于网络环境较为复杂,存在着非同一交换机下的数据传输需求,所以这种C/S模式并不能满足大文件快速分发的要求。

所以希望通过P2P相关技术来使得服务器本身不再是制约因素,传输过程依赖于网络中所有参与者的计算能力以及网络带宽。

本文主要内容参考了P2P技术在大文件共享中的应用研究.pdf

P2P相关技术

分类

  • 集中式P2P网络:有节点保存索引信息
  • 分布式P2P网络:利用flooding,节点较为松散
  • 混合式P2P网络

基于实际情况,我们使用Bit-Torrent来实现混合式P2P网络

阅读剩余部分 -

字符串匹配的相关算法

设文本串T与模式串P,分别长nm,字符串匹配即为找到所有的有效偏移,使PT中以该偏移出现

后缀重叠定理

假设x, y和z,x, y是z的后缀,如果|x|<|y|,那x是y的后缀;若相等,则x = y.

暴力匹配(brute force)算法

通过循环的方法,对共计n - m + 1个可能的s值进行检测,成功则返回位置,时间复杂度为$O((n - m + 1) m)$

NaiveStringMatcher(T, P)
n = T.length
m = P.length
for s = 0 to (n - m)
    if P[1..m] == T[s + 1..s + m]
        return true
int BruteForce(char* T, char* p)
{
    int tLen = strlen(t);
    int pLen = strlen(p);
  
    int i = 0;
    int j = 0;
    while (i < tLen && j < pLen)
    {
        if (t[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {   
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == pLen)
        return i - j;
    else
        return -1;
}

阅读剩余部分 -

Web技术概论

Arbitrary Definition of TCP/IP

Basic Web Protocol Suite

  1. Scheme:
    identify particular sources of information that server hosts
  2. The way browser present information
    the content itself contains the formatting information(raw information)
    HTML(Hypertext Markup Language) enables information creators to describe the format of the information to be rendered at browser side
  3. How to interpret the text stream ?
    server is responsible to look at the file name extension and map it to something called MIME(Multipurpose Internet Mail Extensions)
  4. How should a browser ask a server to deliver some information ?
    HTTP request browser tell the server more in addition to the file name
    HTTP response server tell the browser something like content type and when the file was last modified
  5. CGI(common gateway interface)
    allow a browser (user at browser side) to invoke some procedure at the server side, passing data to the procedure and getting processed result back, not just asking for pre-stored information







阅读剩余部分 -

最新文章

最近回复

分类

归档

其它

微博

基佬们

Fork me on GitHub