C语言链型数据

最近这几天好忙, 基本没什么时间去学习. 可是幸而,
近日项目中相见了贰个小功效, 索性就记下下来.

壹 、链型结构

链型结构的多寡, 学过C 语言的童鞋肯定不会不熟悉, C 高级里面,
有贰个链表的概念, 然后就是对链表各个插入, 删除, 拼接. 

在C#中, 并没有这种链表的概念, 但是却得以利用别的艺术,
来完毕出那种效果. 

只是上述, 都跟本次的大旨没有简单关系. 接下去进入正题了.

假如有一堆杂乱的冬季的多寡, 例如那种的:

2->3, 4->1, 1->2, 5->6, 3->4, 6->8, 7->11, 8->10, 9->35, 10->7, 11->9

她们中间, 并没有先后的一一, 未来要做的, 正是把上边那条有向数据,
拼接成若干链型, 或许叫链条吧, 通俗一点.

那里有少数要留意, 左边的数码无法重复, 左边的数额也不能够重复.
若是出现重复, 就开了叉, 不是自身想要的多寡了. 那些提前就要做实判断.

 

二、实现

  1. 先看效率:

C语言 1

最后的效应, 就是那种的了

 2. 代码:

/// <summary>
/// 待交换数据
/// </summary>
public class Changed
{
    public int Source { get; set; }

    public int Target { get; set; }
}

/// <summary>
/// 链条
/// </summary>
public class Line
{
    public List<int> OneLine { get; set; }

    public override string ToString()
    {
        return string.Join("->", OneLine);
    }
}

public static void Test()
{
    List<Line> lines = new List<Line>();
    List<Changed> changes = new List<Changed>()
    {
        new Changed(){ Source=2, Target=3},
        new Changed(){ Source=4, Target=1},
        new Changed(){ Source=1, Target=2},
        new Changed(){ Source=5, Target=6},
        new Changed(){ Source=3, Target=4},
        new Changed(){ Source=6, Target=8},
        new Changed(){ Source=7, Target=11},
        new Changed(){ Source=8, Target=10},
        new Changed(){ Source=9, Target=35},
        new Changed(){ Source=10, Target=7},
        new Changed(){ Source=11, Target=9},
    };
    List<Changed> temp = changes.GetRange(0, changes.Count);
    foreach (var item in changes)
    {
        Line currentLine = lines.Find(n => n.OneLine.Contains(item.Source));
        if (currentLine != null)
        {
            continue;
        }
        //每次找的时候, 会把整条链查找到, 并且生成出来
        currentLine = new Line() { OneLine = new List<int> { item.Source, item.Target } };
        temp.Remove(item);
        currentLine = GetALine(currentLine, temp);

        lines.Add(currentLine);
    }

    lines.ForEach(n => Console.WriteLine(n.ToString()));
    Console.ReadKey();
}

public static Line GetALine(Line line, List<Changed> changes)
{
    var flagLeft = false;
    var flagRight = false;
    if (changes.Count == 0)
    {
        return line;
    }

    Changed left = null;
    Changed right = null;
    foreach (var item in changes)
    {
        if (item.Target == line.OneLine[0])
        {
            flagLeft = true;
            left = item;
        }
        if (item.Source == line.OneLine.Last())
        {
            if (item.Target == line.OneLine[0])
            {
                flagLeft = false;
            }
            flagRight = true;
            right = item;
        }
    }

    if (flagLeft || flagRight)
    {
        if (flagLeft)
        {
            line.OneLine.Insert(0, left.Source);
            changes.Remove(left);
        }
        if (flagRight)
        {
            line.OneLine.Add(right.Target);
            changes.Remove(right);
        }
        return GetALine(line, changes);
    }
    return line;
}

 那里运用了1个递归, 来生成一条链条.

 

实则, 从得到第一个数据的时候, 笔者并不知道他是从头的数额, 依然中间的多少,
所以, 作者使用了, 向两边扩张延伸的艺术, 去递归查找他的其他数据.

很多时候, 递归都以足以用循环转换的. 那里也是

public static Line GetALineByWhile(Line line, List<Changed> changes)
{
    while (true)
    {
        var flagLeft = false;
        var flagRight = false;
        Changed left = null;
        Changed right = null;
        if (changes.Count == 0)
        {
            break;
        }
        foreach (var item in changes)
        {
            if (item.Target == line.OneLine[0])
            {
                flagLeft = true;
                left = item;
            }
            if (item.Source == line.OneLine.Last())
            {
                if (item.Target == line.OneLine[0])
                {
                    flagLeft = false;
                }
                flagRight = true;
                right = item;
            }
        }
        if (flagLeft || flagRight)
        {
            if (flagLeft)
            {
                line.OneLine.Insert(0, left.Source);
                changes.Remove(left);
            }
            if (flagRight)
            {
                line.OneLine.Add(right.Target);
                changes.Remove(right);
            }
            continue;
        }
        break;
    }
    return line;
}

巡回的时候, 只要左边, 可能右边, 能找到数据, 那么快要继续下一轮查找,
唯有当遍历二遍源之后, 找不到其余匹配的数码, 才能够跳出循环,
继续下一组数据的判断.