串的链式存储结构

发表评论
24,893 views

A+

最近比较忙，一堆论文要写，还要做各种毕业设计和课程设计，继续努力！！串的链式存储结构，其实与线性结构中的链式结构一样，它存储的元素是char元素，所以实现再实现这样的结构就没什么意义了，一个结点存放一个char，是乎也很浪费结点。我实现一下一个结点存放不同个元素，就是每个结点用一个字符数组来存储元素，不废话了，实现吧

class StringLink
{
    class Node {
        public char[] data;
        public Node next; 
    }

    private int _nodeLength = 10;
    private int _length = 0;
    private Node _headNode = null;
    private Node _lastNode = null;

    //初始化为空串
    public StringLink() : this(null, 0) { }

    //初始化串
    public StringLink(char[] chars):this(chars,0) {
    }

class StringLink

{

class Node {

public char[] data;

public Node next;

}

private int _nodeLength = 10;

private int _length = 0;

private Node _headNode = null;

private Node _lastNode = null;

//初始化为空串

public StringLink() : this(null, 0) { }

//初始化串

public StringLink(char[] chars):this(chars,0) {

}

定义一个抽象数据结点，这里的数据域为char数组，它的大小由_nodeLength定义，其他的变量就不用讲了，下面看看构造函数（构造串）。

//自定义单节点长度串
public StringLink(char[] chars,int nodeLength) {

    if (nodeLength > 1) {
        this._nodeLength = nodeLength;
    }

    //新建头结点
    this._headNode = new Node();
    this._headNode.data = null;
    this._headNode.next = null;

    this.ValueTo(chars);
            
}

//自定义单节点长度串

public StringLink(char[] chars,int nodeLength) {

if (nodeLength > 1) {

this._nodeLength = nodeLength;

}

//新建头结点

this._headNode = new Node();

this._headNode.data = null;

this._headNode.next = null;

this.ValueTo(chars);

}

新建一个头结点，自定义结点的字符长度，为串初始化为，下面看ValueTo方法

//赋值为链串
public void ValueTo(StringLink s) {
    char[] chars = s.ToChars();
    this.ValueTo(chars);
}

//赋值为字符数组
public void ValueTo(char[] chars) {
    this.Clear();

    if (chars == null)
    {
        return;
    }

    int length = chars.Length;
    int j = 0;
    for (int i = 0; i < length; i++)
    {
        if (i % this._nodeLength == 0)
        {

            //新建一个结点继续保存数据
            Node addNode = new Node();
            addNode.data = new char[this._nodeLength];
            addNode.next = null;
            if (this._lastNode == null)
            {
                this._lastNode = addNode;
                this._headNode.next = addNode;
            }
            else {
                this._lastNode.next = addNode;
                this._lastNode = addNode;
            }
            j = 0;
        }

        this._lastNode.data[j] = chars[i];
        j++;
    }

    this._length = length;
}

//赋值为链串

public void ValueTo(StringLink s) {

char[] chars = s.ToChars();

this.ValueTo(chars);

}

//赋值为字符数组

public void ValueTo(char[] chars) {

this.Clear();

if (chars == null)

{

return;

}

int length = chars.Length;

int j = 0;

for (int i = 0; i < length; i++)

{

if (i % this._nodeLength == 0)

{

//新建一个结点继续保存数据

Node addNode = new Node();

addNode.data = new char[this._nodeLength];

addNode.next = null;

if (this._lastNode == null)

{

this._lastNode = addNode;

this._headNode.next = addNode;

}

else {

this._lastNode.next = addNode;

this._lastNode = addNode;

}

j = 0;

}

this._lastNode.data[j] = chars[i];

j++;

}

this._length = length;

}

赋值串为字符数组

①清空串

//清空串
public void Clear() {
    this._headNode.next = null;
    //第一个结点地址没有被引用，被回收
    //它所指向的下一结点也失去引用，也被回收......
    this._lastNode = null;
}

//清空串

public void Clear() {

this._headNode.next = null;

//第一个结点地址没有被引用，被回收

//它所指向的下一结点也失去引用，也被回收......

this._lastNode = null;

}

②遍历整个字符数组，填充到结点数组中，i%this._nodeLength==0表示当前结点的字符数组被填充满了，所以要新建结点，在赋值，链接上个结点，用最后_lastNode指向新加结点，再向它填充数据

③赋值长度

第一个ValueTo方法有个ToChars方法

//转换为字符数组
public char[] ToChars() {
    if (this._length == 0) {
        return null;
    }

    char[] chars = new char[this._length];
    Node valueNode = this._headNode.next;
    int j = 0;
    for (int i = 0; i < this._length; i++) {
        chars[i] = valueNode.data[j];
        j++;
        if (j == this._nodeLength) {
            //当前结点赋值完毕，到下一个结点
            valueNode = valueNode.next;
            j = 0;
        }
    }

    return chars;
}

//转换为字符数组

public char[] ToChars() {

if (this._length == 0) {

return null;

}

char[] chars = new char[this._length];

Node valueNode = this._headNode.next;

int j = 0;

for (int i = 0; i < this._length; i++) {

chars[i] = valueNode.data[j];

j++;

if (j == this._nodeLength) {

//当前结点赋值完毕，到下一个结点

valueNode = valueNode.next;

j = 0;

}

return chars;

}

同样的遍历所有的结点，取出每个结点的字符数组的元素，用j指标表示当前结点数据元素的位置，取完后就到下一个结点，并让指标j从头来过，返回总的字符数组

//获取指定位置的字符
public bool GetElementByIndex(int index, ref char c) {
    if (index < 1 || index > this._length) {
        Console.WriteLine("索引非法！");
        return false;
    }

    int nodeIndex = 0;
    int dataIndex = (index - 1) % this._nodeLength;
    if (dataIndex + 1 == this._nodeLength)
    {
        //刚刚结点尾数据
        nodeIndex = index / this._nodeLength;
    }
    else {
        nodeIndex = (int)(index / this._nodeLength) + 1;
    }

    Node whichNode = this._headNode;
    for (int i = 0; i < nodeIndex; i++) {
        whichNode = whichNode.next;
    }

    c = whichNode.data[dataIndex];
    return true;
}

//获取指定位置的字符

public bool GetElementByIndex(int index, ref char c) {

if (index < 1 || index > this._length) {

Console.WriteLine("索引非法！");

return false;

}

int nodeIndex = 0;

int dataIndex = (index - 1) % this._nodeLength;

if (dataIndex + 1 == this._nodeLength)

{

//刚刚结点尾数据

nodeIndex = index / this._nodeLength;

}

else {

nodeIndex = (int)(index / this._nodeLength) + 1;

}

Node whichNode = this._headNode;

for (int i = 0; i < nodeIndex; i++) {

whichNode = whichNode.next;

}

c = whichNode.data[dataIndex];

return true;

}

获取指定位置的字符

①判断索引的合法性

②得出某个结点的具体位置（数组的下标）

这里(5-1)%2 = 0

③再通过数据下标来判断结点位置是否需要+1。由上图5/2 = 2.5 = 2，由数据下标0可知不是结点最后一个元素，所以结点位置需要+1 ，2+1 = 3。表示在第三个结点，其实这里想表达的是向上取整，获得正确的结点位置。

④遍历结点找到刚刚第（刚刚得到位置）的结点

⑤再取出得到结点的对应数据下标元素

public char this[int index] {
    get {
        char c = '\0';
        this.GetElementByIndex(index, ref c);
        return c;
    }
}

public char this[int index] {

get {

char c = '\0';

this.GetElementByIndex(index, ref c);

return c;

}

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

    if (index < 1 || index > this.GetLength()) {
        Console.WriteLine("索引错误！");
        return false;
    }

    //1.找出index的位置，是哪一个结点
    int nodeIndex = index / this._nodeLength;
    //2.找出是那个节点的第几位
    int dataIndex = (index-1) % this._nodeLength;
    if (dataIndex != this._nodeLength - 1) {
        nodeIndex++;
    }
            
    //遍历找到第nodeIndex-1结点
    Node preNode = this._headNode;
    for (int i = 1; i < nodeIndex; i++) {
        preNode = preNode.next;
    }

    //保存第nodeIndex个结点
    Node targetNode = preNode.next;

    //新建结点
    Node addNode = new Node();
    addNode.data = new char[this._nodeLength];
    //填充目标结点targetIndex目标位置dataIndex前的数据
    for (int i = 0; i < dataIndex; i++) {
        addNode.data[i] = targetNode.data[i];
    }

    //初始化插入指标为dataIndex
    int cur = dataIndex;
    //插入chars数组的数据
    for (int i = 0; i < chars.Length; i++) {
        addNode.data[cur] = chars[i];
        cur++;
        if (cur >= this._nodeLength) {
            preNode.next = addNode;
            preNode = addNode;
            cur = 0;
            if (i != chars.Length - 1) {
                addNode = new Node();
                addNode.data = new char[this._nodeLength];
            }
        }
    }

            

    //将前面新加的结点和被插入部分的结点链接起来
    if (cur != 0) {
        //表示addNode没填充满，也没有进行链接
        preNode.next = addNode;
        preNode = addNode;
    }
    preNode.next = targetNode;

    //不需要向前移动的情况
    if (cur == 0 && dataIndex == 0)
    {
        return true;
    }

    //只需要移动少数的情况
    if (this._nodeLength - cur == dataIndex) {
        while (cur < this._nodeLength) {
            preNode.data[cur] = targetNode.data[dataIndex];
            cur++;
            dataIndex++;
        }

        //删除target结点
        preNode.next = targetNode.next;
        if (targetNode.next == null) {
            this._lastNode = preNode;
        }
        return true;
    }

    //向前移动数据
    int goIndex = index;
    int iIndex = cur;
    int jIndex = dataIndex;
    Node iNode = addNode;
    Node jNode = targetNode;
    if (iIndex == 0) {
        iNode = addNode.next;
    }
            
    while (goIndex <= this.GetLength()) {//表示要向前移动的数据
        iNode.data[iIndex] = jNode.data[jIndex];

        iIndex++;
        jIndex++;

        if (iIndex >= this._nodeLength) {
            iIndex = 0;
            iNode = iNode.next;
        }
        if (jIndex >= this._nodeLength) {
            jIndex = 0;
            jNode = jNode.next;
        }

        goIndex++;
    }

    if (this._nodeLength - cur + dataIndex > this._nodeLength) {
        //表示最后一个结点为空了,抛弃最后那个结点
        this._lastNode = iNode;
        iNode.next = null;
    }
    this._lastNode = iNode;
    iNode.next = null;

    this._length += chars.Length;

    return true;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

//插入字符数组

public bool Insert(int index, char[] chars) {

if (chars == null || this.IsEmpty()) {

Console.WriteLine("插入的字符数组或自身为空！");

return false;

}

if (index < 1 || index > this.GetLength()) {

Console.WriteLine("索引错误！");

return false;

}

//1.找出index的位置，是哪一个结点

int nodeIndex = index / this._nodeLength;

//2.找出是那个节点的第几位

int dataIndex = (index-1) % this._nodeLength;

if (dataIndex != this._nodeLength - 1) {

nodeIndex++;

}

//遍历找到第nodeIndex-1结点

Node preNode = this._headNode;

for (int i = 1; i < nodeIndex; i++) {

preNode = preNode.next;

}

//保存第nodeIndex个结点

Node targetNode = preNode.next;

//新建结点

Node addNode = new Node();

addNode.data = new char[this._nodeLength];

//填充目标结点targetIndex目标位置dataIndex前的数据

for (int i = 0; i < dataIndex; i++) {

addNode.data[i] = targetNode.data[i];

}

//初始化插入指标为dataIndex

int cur = dataIndex;

//插入chars数组的数据

for (int i = 0; i < chars.Length; i++) {

addNode.data[cur] = chars[i];

cur++;

if (cur >= this._nodeLength) {

preNode.next = addNode;

preNode = addNode;

cur = 0;

if (i != chars.Length - 1) {

addNode = new Node();

addNode.data = new char[this._nodeLength];

}

//将前面新加的结点和被插入部分的结点链接起来

if (cur != 0) {

//表示addNode没填充满，也没有进行链接

preNode.next = addNode;

preNode = addNode;

}

preNode.next = targetNode;

//不需要向前移动的情况

if (cur == 0 && dataIndex == 0)

{

return true;

}

//只需要移动少数的情况

if (this._nodeLength - cur == dataIndex) {

while (cur < this._nodeLength) {

preNode.data[cur] = targetNode.data[dataIndex];

cur++;

dataIndex++;

}

//删除target结点

preNode.next = targetNode.next;

if (targetNode.next == null) {

this._lastNode = preNode;

}

return true;

}

//向前移动数据

int goIndex = index;

int iIndex = cur;

int jIndex = dataIndex;

Node iNode = addNode;

Node jNode = targetNode;

if (iIndex == 0) {

iNode = addNode.next;

}

while (goIndex <= this.GetLength()) {//表示要向前移动的数据

iNode.data[iIndex] = jNode.data[jIndex];

iIndex++;

jIndex++;

if (iIndex >= this._nodeLength) {

iIndex = 0;

iNode = iNode.next;

}

if (jIndex >= this._nodeLength) {

jIndex = 0;

jNode = jNode.next;

}

goIndex++;

}

if (this._nodeLength - cur + dataIndex > this._nodeLength) {

//表示最后一个结点为空了,抛弃最后那个结点

this._lastNode = iNode;

iNode.next = null;

}

this._lastNode = iNode;

iNode.next = null;

this._length += chars.Length;

return true;

}

这里实现的是插入字符数组

①首先判断索引和字符数组等的合法性

②找出index位置对应的第几个结点（目标结点），和对应这个结点的数组元素位置（下标）

③找到目标结点的前一个结点，用于链接，并用一个临时引用保存目标结点。（等下会割断前一结点和目标结点的关系）

④新建一个结点，先保存目标结点，被插位置前面的数据元素

⑤初始化指标为被插结点数据数组的下标，遍历要插入的字符数组，填充到对应的指标中，当指标到达结点数据域的最后时，链接这个结点到上一个结点上，并制定上一个结点为当前结点，新建一个结点，继续赋值。（注意如果字符数组的最后一个元素都已经赋值了，就不需要新建了）

⑥cur!=0时，需要链接一下前一个结点和当前新加结点，这里是弥补前面cur没有达到最后而没有进行链接，再链接新加结点和目标结点，使整条链表链接起来了

⑦chars数组元素已经插入，下面就要看被插的数据是否需要前移

⑦①当cur==0并且dataIndex==0表示不用迁移，也就是说被插元素的位置刚好的结点的第一位，在它前面插入数据，只需要新建结点保存数据就好，同时cur==0表示插入的数据刚好填充满新加的结点，这时，只需要将他们链接起来。

⑦②只需要移动少许的情况就是，目标结点被插入位置后的数据刚好可以填满，新加结点剩下的数据区域，这时只需要填充好数据，再直接链接，新加结点和目标结点的下一个结点，也就是说target结点就没用了。（这里需要注意的是目标结点是尾结点的情况）

⑦③最麻烦的就是要移动了，goIndex是需要移动元素位置的指标，用于判断移动完没，jNode，jIndex对应为前移数据的结点和位置，iNode，iIndex对应为前移数据的目标结点和位置，当前移的位置大于结点数据的长度时，就表示移动后，最后一个结点的数据都移动到前面去了，所以删除掉这结点。

⑧最后长度+插入字符数组的长度

//插入字符串到指定位置
public bool Insert(int index, StringLink s) {
    if (s.IsEmpty())
    {
        Console.WriteLine("插入的字符串不能为空！");
        return false;
    }

    char[] chars = s.ToChars();
    return this.Insert(index, chars);
}

//插入字符串到指定位置

public bool Insert(int index, StringLink s) {

if (s.IsEmpty())

{

Console.WriteLine("插入的字符串不能为空！");

return false;

}

char[] chars = s.ToChars();

return this.Insert(index, chars);

}

//删除指定位置长度的字符
public bool Delete(int index, int length) {
    if (this.IsEmpty()) {
        Console.WriteLine("字符串不能为空！");
        return false;
    }

    if (index < 1 || index > this.GetLength()) {
        Console.WriteLine("索引错误！");
        return false;
    }

    if (length + index - 1 > this.GetLength()) {
        Console.WriteLine("删除的长度有误！");
        return false;
    }

    int iNodeIndex = index / this._nodeLength;
    int iDataIndex = (index - 1) % this._nodeLength;
    if (iDataIndex != this._nodeLength - 1) {
        iNodeIndex++;
    }

            
    Node preNode = this._headNode;
    for (int i = 1; i < iNodeIndex; i++) {
        preNode = preNode.next;
    }
    Node itargetNode = preNode.next;
            
    if (index + length -1 == this.GetLength()) {
        if (index == 1)
        {
            //表示删除所有元素
            this._lastNode = null;
            this._headNode = null;
        }
        else {
            //删除index后面全部
            if (iDataIndex == 0)
            {
                //要删除itargetNode及后面的全部
                preNode.next = null;
                this._lastNode = preNode;
            }
            else {
                //只删除itargetNode的部分及后面全部
                itargetNode.next = null;
                this._lastNode = itargetNode;
            }
                    
        }

        this._length -= length;
        return true;
    }

    int jIndex = index + length;
    int jNodeIndex = jIndex / this._nodeLength;
    int jDataIndex = (jIndex - 1) % this._nodeLength;
    if (jDataIndex != this._nodeLength - 1)
    {
        jNodeIndex++;
    }

    Node jtargetNode = itargetNode;
    for (int i = iNodeIndex; i < jNodeIndex; i++)
    {
        jtargetNode = jtargetNode.next;
    }

    int goIndex = index + length;
    while (goIndex <= this.GetLength()) {
        itargetNode.data[iDataIndex] = jtargetNode.data[jDataIndex];
        iDataIndex++;
        jDataIndex++;
        goIndex++;
        if (iDataIndex >= this._nodeLength) {
            itargetNode = itargetNode.next;
            iDataIndex = 0;
        }

        if (jDataIndex >= this._nodeLength) {
            jtargetNode = jtargetNode.next;
            jDataIndex = 0;
        }

    }

    this._lastNode = itargetNode;
    this._lastNode.next = null;
    this._length -= length;

    return true;
}

//删除指定位置长度的字符

public bool Delete(int index, int length) {

if (this.IsEmpty()) {

Console.WriteLine("字符串不能为空！");

return false;

}

if (index < 1 || index > this.GetLength()) {

Console.WriteLine("索引错误！");

return false;

}

if (length + index - 1 > this.GetLength()) {

Console.WriteLine("删除的长度有误！");

return false;

}

int iNodeIndex = index / this._nodeLength;

int iDataIndex = (index - 1) % this._nodeLength;

if (iDataIndex != this._nodeLength - 1) {

iNodeIndex++;

}

Node preNode = this._headNode;

for (int i = 1; i < iNodeIndex; i++) {

preNode = preNode.next;

}

Node itargetNode = preNode.next;

if (index + length -1 == this.GetLength()) {

if (index == 1)

{

//表示删除所有元素

this._lastNode = null;

this._headNode = null;

}

else {

//删除index后面全部

if (iDataIndex == 0)

{

//要删除itargetNode及后面的全部

preNode.next = null;

this._lastNode = preNode;

}

else {

//只删除itargetNode的部分及后面全部

itargetNode.next = null;

this._lastNode = itargetNode;

}

this._length -= length;

return true;

}

int jIndex = index + length;

int jNodeIndex = jIndex / this._nodeLength;

int jDataIndex = (jIndex - 1) % this._nodeLength;

if (jDataIndex != this._nodeLength - 1)

{

jNodeIndex++;

}

Node jtargetNode = itargetNode;

for (int i = iNodeIndex; i < jNodeIndex; i++)

{

jtargetNode = jtargetNode.next;

}

int goIndex = index + length;

while (goIndex <= this.GetLength()) {

itargetNode.data[iDataIndex] = jtargetNode.data[jDataIndex];

iDataIndex++;

jDataIndex++;

goIndex++;

if (iDataIndex >= this._nodeLength) {

itargetNode = itargetNode.next;

iDataIndex = 0;

}

if (jDataIndex >= this._nodeLength) {

jtargetNode = jtargetNode.next;

jDataIndex = 0;

}

this._lastNode = itargetNode;

this._lastNode.next = null;

this._length -= length;

return true;

}

这里是删除指定位置长度的子串

①先检查各种的合法性

②找到要删除位置的目标结点和位置（下标），并保存目标结点的上一个结点和目标结点

③如果是直接删除目标位置后面所有的子串的话

③①目标位置是1，则清空整条串

③②目标位置不是1，则删除目标结点目标位置后面的子串，注意如果目标位置为0时，说明目标结点整个都要被删除，这时串的尾结点就是我们先前保存的目标结点的前一个结点了

③③长度减小对应的值，返回删除成功

④对于只删除目标位置后面串的部分的，这时就需要移动了，通过index+length得到需要保留的子串的第一个位置，通过这个索引得到对应的结点和下标，遍历保留子串的每个字符，向前移动到对应被删除的位置，注意这时尾结点就是最后被赋值的结点

⑤长度减少length

//在尾部链接字符数组
public bool Concat(char[] chars) {
    if (this._headNode.next == null || chars == null) {
        Console.WriteLine("链接的串或字符数组不能为空！");
        return false;
    }
            

    //计算最后结点的偏移
    int offset = this._length % this._nodeLength;
    int j = offset;
    for (int i = 0; i < chars.Length; i++) {
        if ((i + offset) % this._nodeLength == 0) {
            //新建结点
            Node addNode = new Node();
            addNode.data = new char[this._nodeLength];
            addNode.next = null;
            this._lastNode.next = addNode;
            this._lastNode = addNode;
            j = 0;
        }

        this._lastNode.data[j] = chars[i];
        j++;
                
    }

    this._length += chars.Length;

    return true;
}

//在尾部链接字符数组

public bool Concat(char[] chars) {

if (this._headNode.next == null || chars == null) {

Console.WriteLine("链接的串或字符数组不能为空！");

return false;

}

//计算最后结点的偏移

int offset = this._length % this._nodeLength;

int j = offset;

for (int i = 0; i < chars.Length; i++) {

if ((i + offset) % this._nodeLength == 0) {

//新建结点

Node addNode = new Node();

addNode.data = new char[this._nodeLength];

addNode.next = null;

this._lastNode.next = addNode;

this._lastNode = addNode;

j = 0;

}

this._lastNode.data[j] = chars[i];

j++;

}

this._length += chars.Length;

return true;

}

在尾部链接加上字符串数组

①检查串和字符数组是否为空

②计算出偏移，就是最后结点可以填充字符的下标，然后其他跟赋值时差不多，只不过现在是从当前结点的offset位置开始

//在尾部链接串
public bool Concat(StringLink s) {
    if (s.IsEmpty()) {
        Console.WriteLine("链接的串不能为空！");
        return false;
    }

    char[] chars = s.ToChars();
    return this.Concat(chars);
}

//在尾部链接串

public bool Concat(StringLink s) {

if (s.IsEmpty()) {

Console.WriteLine("链接的串不能为空！");

return false;

}

char[] chars = s.ToChars();

return this.Concat(chars);

}

//KMP匹配串的位置
public int Index(StringLink s,int where = 1) {
    if (s.IsEmpty() || this.IsEmpty() || where < 1 || where > this.GetLength()) {
        Console.WriteLine("串不能为空或索引非法！");
        return 0;
    }

    int[] nextval = this._GetNextVal(s);
    int matchLength = s.GetLength();
    int length = this.GetLength();
    int i = where;
    int j = 1; 
    while (i <= length && j<=matchLength) {
        if (j == 0 || this[i] == s[j])
        {
            j++;
            i++;
        }
        else {
            j = nextval[j];
        }

    }

    if (j > matchLength) {
        return i - matchLength;
    }

    return 0;
}

private int[] _GetNextVal(StringLink s) {
    int length = s.GetLength();
    int[] nextval = new int[length + 1];
    int i = 1;
    int j = 0;
    nextval[1] = 0;

    for (; i < length;) {

        if (j == 0 || s[i] == s[j])
        {
            i++;
            j++;
            if (s[i] == s[j])
            {
                nextval[i] = nextval[j];
            }
            else
            {
                nextval[i] = j;
            }
        }
        else {
            j = nextval[j];
        }
    }

    return nextval;
}

//KMP匹配串的位置

public int Index(StringLink s,int where = 1) {

if (s.IsEmpty() || this.IsEmpty() || where < 1 || where > this.GetLength()) {

Console.WriteLine("串不能为空或索引非法！");

return 0;

}

int[] nextval = this._GetNextVal(s);

int matchLength = s.GetLength();

int length = this.GetLength();

int i = where;

int j = 1;

while (i <= length && j<=matchLength) {

if (j == 0 || this[i] == s[j])

{

j++;

i++;

}

else {

j = nextval[j];

}

if (j > matchLength) {

return i - matchLength;

}

return 0;

}

private int[] _GetNextVal(StringLink s) {

int length = s.GetLength();

int[] nextval = new int[length + 1];

int i = 1;

int j = 0;

nextval[1] = 0;

for (; i < length;) {

if (j == 0 || s[i] == s[j])

{

i++;

j++;

if (s[i] == s[j])

{

nextval[i] = nextval[j];

}

else

{

nextval[i] = j;

}

else {

j = nextval[j];

}

return nextval;

}

KMP匹配字符串的算法，详情看前一篇博客

//替换字符串
public int Replace(StringLink match, StringLink replace, int index = 1) {
    if (match.IsEmpty() || this.IsEmpty()) {
        Console.WriteLine("当前串或匹配串不能为空！");
        return 0;
    }

    if (index < 1 || index > this.GetLength()) {
        Console.WriteLine("索引错误！");
        return 0;
    }

    int matchIndex = this.Index(match, index);
    if (matchIndex != 0) {
        this.Delete(matchIndex, match.GetLength());
        if (matchIndex - 1 == this.GetLength())
        {
            this.Concat(replace);
        }
        else {
            this.Insert(matchIndex, replace);
        }
                

        return 1;
    }

    return 0;
}

//替换字符串

public int Replace(StringLink match, StringLink replace, int index = 1) {

if (match.IsEmpty() || this.IsEmpty()) {

Console.WriteLine("当前串或匹配串不能为空！");

return 0;

}

if (index < 1 || index > this.GetLength()) {

Console.WriteLine("索引错误！");

return 0;

}

int matchIndex = this.Index(match, index);

if (matchIndex != 0) {

this.Delete(matchIndex, match.GetLength());

if (matchIndex - 1 == this.GetLength())

{

this.Concat(replace);

}

else {

this.Insert(matchIndex, replace);

}

return 1;

}

return 0;

}

这里是替换字符串，这里直接调用了三个写好的方法，我偷懒了（这样是不好的），也没什么好说的，用Index方法匹配到位置，再用Delete方法删除匹配的内容，再调用Insert方法插入替换的字符串

测试

static void TestStringLink() {
    int nodeLength = 3;
    StringLink s = new StringLink(new char[] { 'a', 'f', 'g', 'g', 's', 'k' }, nodeLength);
    PrintStringLink(s,"串s为：");
    StringLink s2 = new StringLink(new char[] { '5', '2', '0','a' }, nodeLength);
    PrintStringLink(s2, "串s2为：");
    s.Concat(s2);
    StringLink s3 = new StringLink(new char[] { 'l', 'o', 'v', 'e' }, 20);
    PrintStringLink(s,"串链接s2后：");
    Console.WriteLine();

    Console.WriteLine("在串s中查找串s2：的位置为："+s.Index(s2));
    s.Insert(5, new char[] { '1', '2', '8' });
    PrintStringLink(s,"在串s位置5插入128后：");
    s.Replace(s2, new StringLink(new char[] { 'l', 'u', 'o','9' }, nodeLength));
    PrintStringLink(s,"替换串s中的s2为luo9后：");
    Console.WriteLine();
            
    Console.WriteLine("在算中查找gg的位置为："+s.Index(new StringLink(new char[] { 'g', 'g' }, nodeLength)));
    s.Insert(9, s2);
    PrintStringLink(s,"在串s位置9前插入s2(520a)后：");
    s.Replace(new StringLink(new char[] { 'g', 'g' }, nodeLength), s2);
    PrintStringLink(s,"在串s中替换gg为s2(520a)后：");
    Console.WriteLine();

    PrintStringLink(s3, "串s3为：");
    s.Concat(s3);
    PrintStringLink(s,"串s链接串s3后：");
    s.Delete(2, 3);
    PrintStringLink(s,"删除串s位置为2长度为3的子串后：");
    s.Concat(s3);
    PrintStringLink(s,"串s链接串s3后：");
    s.Delete(1, 3);
    PrintStringLink(s, "删除串s位置为1长度为3的子串后：");
    s.Delete(6, 1);
    PrintStringLink(s, "删除串s位置为6长度为1的子串后：");
}

static void PrintStringLink(StringLink s,string text = "输出:") {

    Console.Write(text);
    for (int i = 0; i < s.GetLength(); i++) {
        Console.Write(s[i + 1]);
    }
    Console.WriteLine();
}

static void TestStringLink() {

int nodeLength = 3;

StringLink s = new StringLink(new char[] { 'a', 'f', 'g', 'g', 's', 'k' }, nodeLength);

PrintStringLink(s,"串s为：");

StringLink s2 = new StringLink(new char[] { '5', '2', '0','a' }, nodeLength);

PrintStringLink(s2, "串s2为：");

s.Concat(s2);

StringLink s3 = new StringLink(new char[] { 'l', 'o', 'v', 'e' }, 20);

PrintStringLink(s,"串链接s2后：");

Console.WriteLine();

Console.WriteLine("在串s中查找串s2：的位置为："+s.Index(s2));

s.Insert(5, new char[] { '1', '2', '8' });

PrintStringLink(s,"在串s位置5插入128后：");

s.Replace(s2, new StringLink(new char[] { 'l', 'u', 'o','9' }, nodeLength));

PrintStringLink(s,"替换串s中的s2为luo9后：");

Console.WriteLine();

Console.WriteLine("在算中查找gg的位置为："+s.Index(new StringLink(new char[] { 'g', 'g' }, nodeLength)));

s.Insert(9, s2);

PrintStringLink(s,"在串s位置9前插入s2(520a)后：");

s.Replace(new StringLink(new char[] { 'g', 'g' }, nodeLength), s2);

PrintStringLink(s,"在串s中替换gg为s2(520a)后：");

Console.WriteLine();

PrintStringLink(s3, "串s3为：");

s.Concat(s3);

PrintStringLink(s,"串s链接串s3后：");

s.Delete(2, 3);

PrintStringLink(s,"删除串s位置为2长度为3的子串后：");

s.Concat(s3);

PrintStringLink(s,"串s链接串s3后：");

s.Delete(1, 3);

PrintStringLink(s, "删除串s位置为1长度为3的子串后：");

s.Delete(6, 1);

PrintStringLink(s, "删除串s位置为6长度为1的子串后：");

}

static void PrintStringLink(StringLink s,string text = "输出:") {

Console.Write(text);

for (int i = 0; i < s.GetLength(); i++) {

Console.Write(s[i + 1]);

}

Console.WriteLine();

}

结果

写的时候我就在考虑了，这样子特么就像把链式结构写成顺序结构，后来我也想了下，能把想法，成功写出来，也特么是一种锻炼，想太多的时间，还不写出来，以后在测试性能也是可以的！

发表评论取消回复

登录 注册 找回密码

登录注册找回密码