今天介绍一个有趣的算法——位移算法，此算法来源于《编程珠玑-第二版》，是为了解决在最小空间内完成链表中的位移问题。书中用左右手做了个例子，通俗的讲解位移算法。因为书中没有代码，所以我自己实现了一个，和大家一起学习。此代码是如此简单，第一次运行就直接通过。真不是知道Brain Kernighan和P.J.Plauger两位大神在1981年是咋想出来的。
c#源代码如下：
/// <summary>
/// 原语位移算法
/// 原语通常由若干条指令组成，用来实现某个特定的操作。通过一段不可分割的或不可中断的程序实现其功能。
/// 算法来源参考《编程珠玑 第二版》 P24 原语的力量一节
/// </summary>
public class PrimitiveDisplacement
{
private PrimitiveDisplacement() { }
/// <summary>
/// 偏移计算
/// </summary>
/// <param name="list">泛型数组</param>
/// <param name="offset">偏移量（偏移量不得大于泛型数组长度）</param>
/// <returns>泛型数组</returns>
public static string Displace(string str, int offset)
{
int length = str.Length;
offset = offset % length;
string s1 = str.Substring(0, offset);
s1 = Turn(s1);
string s2 = str.Substring(offset, length - offset);
s2 = Turn(s2);
return Turn(s1 + s2);
}
/// <summary>
/// 位置互换算法
/// </summary>
/// <param name="str">字符串</param>
/// <returns>互换位置后的字符串</returns>
private static string Turn(string str)
{
int length = str.Length;
switch (length)
{
case 0:
case 1:
return str;
case 2:
return str[1].ToString() + str[0].ToString();
default:
string s1 = str.Substring(0, length / 2);
s1 = Turn(s1);
string s2 = str.Substring(length / 2, length - length / 2);
s2 = Turn(s2);
return s2 + s1;
}
}
}
单元测试如下：
[TestMethod()]
public void DisplaceTest()
{
string actual = PrimitiveDisplacement.Displace("abcdefgh", 3);
Assert.AreEqual("defghabc", actual);
}
[TestMethod()]
public void TurnTest()
{
string actual = PrimitiveDisplacement_Accessor.Turn("abcdefgh");
Assert.AreEqual("hgfedcba", actual);
}
本文出自 “张隽永” 博客
