private void getNextval(StringList T, int[] nextval) {

    int i, j;   //代表第几个字符
    i = 1;
    j = 0;
    nextval[1] = 0;
    for (i=2; i < nextval.Length; i++)
    {
        while (j > 0 && T[i] != T[j + 1])
        {
            j = nextval[j];
        }
        if (T[i] == T[j + 1])
        {
            j++;
        }
        nextval[i] = j;
    }

}

这里计算的就是匹配串的前index（包括index）的字符串的最长前后缀相同的字符个数

例如：ababaaaba，那么

"a"，next[1] = 0

"ab"，next[2] = 0

"aba"，next[3] = 1

"abab"，next[4] = 2

"ababa"，next[5] = 3

"ababaa"，next[6] = 1

"ababaaa"，next[7] = 1

"ababaaab"，next[8] = 2

"ababaaaba"，next[9] = 3

这个数组的作用就是，比如说：你在主串ababatabssss中匹配ababaaaba，你会发现前面5个字符都是一样的，就是第5+1个不一样

普通的匹配模式，主串会从第二个开始ababaaabssss，而匹配串从头开始ababaaaba

但是因为有next数组的存在，next[5]的存在，匹配串回到next[5]=3，然后主串位置不变，比较第3+1位

ababatabssss

abababaaaba

这样就可以减少很多的匹配次数了

//普通匹配查找串的位置
public int SimpleIndex(StringList T, int pos = 1) {
    if (T.isEmpty() || this.isEmpty()) {
        return 0;
    }

    int mainLength = this.Length();
    int matchLength = T.Length();
    int i;
    if (pos > 0 && pos <= mainLength) {
        i = pos;

        while (i <= mainLength - matchLength + 1) {
            StringList sub = this.SubString(i, matchLength);
            if (sub.Compare(T) != 0)
            {
                i++;
            }
            else {
                return i;
            }
        }
    }
    return 0;
}

一步步截取匹配长度的子串和匹配串对比。并不效率！

//获取子字符数组
private char[] subChar(char[] chars, int index, int length) {

    if (chars == null) {
        Console.WriteLine("截取的字符数组为空！");
        return null;
    }

    int cLength = chars.Length;
    if (length <1 || index < 1||index > cLength || index + length - 1 > cLength) {
        Console.WriteLine("索引和长度错误！");
        return null;
    }

    char[] newChar = new char[length];
    for (int i = 0; i < length; i++) {
        newChar[i] = chars[index - 1 + i];
    }

    return newChar;
}


//截取指定位置长度的串，成为一个新的串
public StringList SubString(int index, int length) {
    char[] sub = this.subChar(this._data, index, length);
    if (sub == null) {
        return null;
    }

    StringList newString = new StringList(sub);
    return newString;
}

//插入字符数组
public bool Insert(int index , char[] chars)
{
    if (this.isEmpty()||chars == null) {
        Console.WriteLine("插入的字符不能为空！");
        return false;
    }

    int length = _data.Length;
    if (index > length || index < 1) {
        Console.WriteLine("索引位置错误！");
        return false;
    }

    int cLength = chars.Length;

    char[] term = _data;
    _data = new char[length + cLength];
    int i = 0;
    for (; i < index - 1; i++) {
        _data[i] = term[i];
    }

    for (int j = 0; j < cLength; j++) {
        _data[i] = chars[j];
        i++;
    }

    for (int k = index - 1; k < length; k++) {
        _data[i] = term[k];
        i++;
    }

    return true;
}

①先判断本串和字符数组是否为空

②判断索引的合法性

③临时保存本串的数据

④重构本串的数据域大小为原串长度+插入字符数组长度

⑤原串index前的字符，插入的字符，原串index和其后的字符，分为三段分别按顺序赋值给新的数据域

队列的链式存储结构很简单，需要两个变量指标来指向队头和队尾，这里的队尾是真实的队尾元素，用来添加元素。所以当队列只有一个元素时，队头和队尾指向的都是同一个元素。