链型数据

最近这几天好忙, 基本没什么时间去学习. 不过好在, 最近项目中碰到了一个小功能, 索性就记录下来.

一、链型结构

链型结构的数据, 学过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. 先看效果:

最终的效果, 就是这种的了

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;
}

这里使用了一个递归, 来生成一条链条.

其实, 从拿到第一个数据的时候, 我并不知道他是开始的数据, 还是中间的数据, 所以, 我采取了, 向两边扩展延伸的方式, 去递归查找他的其他数据.

许多时候, 递归都是可以用循环转换的. 这里也是

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;
}

循环的时候, 只要左侧, 或者右侧, 能找到数据, 那么就要继续下一轮查找, 只有当遍历一遍源之后, 找不到任何匹配的数据, 才可以跳出循环, 继续下一组数据的判断.

链型数据

推荐阅读