鏈型數據，型數據

鏈型數據，型數據

最近這幾天好忙, 基本沒什麼時間去學習. 不過好在, 最近項目中碰到了一個小功能, 索性就記錄下來.

一、鏈型結構

鏈型結構的數據, 學過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;
}

循環的時候, 只要左側, 或者右側, 能找到數據, 那麼就要繼續下一輪查找, 只有當遍歷一遍源之後, 找不到任何匹配的數據, 才可以跳出循環, 繼續下一組數據的判斷.