串的链式存储结构Ⅱ

发表评论
3,022 views

A+

上一篇的链式存储结构中,结点中的数据域都是要求能装满就装满的，这样虽然减少了对空间的浪费，但是在发生插入或删除的时候，有可能造成大量的移动，这就像顺序存储结构那样了。这次我们改一下，每个结点都可以不存满，余下的空间存'\0'，新增一个结点长度，来表示结点真实存储的数据大小。

class StringLink2
{
    class Node {
        public char[] data;
        public Node next;
        public int length = 0;
    }

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

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

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

    public StringLink2(char[] chars, int nodeLenth) {
        if (nodeLenth > 0) {
            this._nodeLength = nodeLenth;
        }

        this._headNode = new Node();
        this._headNode.next = null;
        this._headNode.data = null;
        this.ValueTo(chars);
    }

class StringLink2

{

class Node {

public char[] data;

public Node next;

public int length = 0;

}

private Node _headNode = null;

private Node _lastNode = null;

private int _nodeLength = 10;

private int _length = 0;

public StringLink2():this(null,0) {

}

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

}

public StringLink2(char[] chars, int nodeLenth) {

if (nodeLenth > 0) {

this._nodeLength = nodeLenth;

}

this._headNode = new Node();

this._headNode.next = null;

this._headNode.data = null;

this.ValueTo(chars);

}

可以看出只有结点那里不一样了，新增加了一个结点真实长度域，ValueTo方法也没有怎么变

//赋值为字符数组
public void ValueTo(char[] chars) {
    this.Clear();
    if (chars == null) {
        return;
    }
            
    for (int i = 0; i < chars.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._headNode.next = addNode;
                this._lastNode = addNode;
            }
            else {
                this._lastNode.next = addNode;
                this._lastNode = addNode;
            }
                    
        }

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

    //空的地方填充为\0
    for (int i = this._lastNode.length; i < this._nodeLength; i++) {
        this._lastNode.data[this._lastNode.length] = '\0';
    }

    this._length = chars.Length;
}

//赋值为字符数组

public void ValueTo(char[] chars) {

this.Clear();

if (chars == null) {

return;

}

for (int i = 0; i < chars.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._headNode.next = addNode;

this._lastNode = addNode;

}

else {

this._lastNode.next = addNode;

this._lastNode = addNode;

}

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

this._lastNode.length++;

}

//空的地方填充为\0

for (int i = this._lastNode.length; i < this._nodeLength; i++) {

this._lastNode.data[this._lastNode.length] = '\0';

}

this._length = chars.Length;

}

没什么好说的，只有数组的指标直接使用了结点真实长度，方便快捷了，最后一个结点的空闲位置用'\0'填充

//赋值为串
public void ValueTo(StringLink2 s) {
    this.ValueTo(s.ToChars());
}

//赋值为串

public void ValueTo(StringLink2 s) {

this.ValueTo(s.ToChars());

}

上面出现了个ToChar方法

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

    Node goNode = this._headNode;
    char[] chars = new char[this._length];
    int i = 0;
    while (goNode.next != null) {
        goNode = goNode.next;
        for (int j = 0; j < goNode.length; j++) {
            chars[i] = goNode.data[j];
            i++;
        }
    }

    return chars;
}

//转换为字符数组

public char[] ToChars() {

if (this.IsEmpty()) {

return null;

}

Node goNode = this._headNode;

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

int i = 0;

while (goNode.next != null) {

goNode = goNode.next;

for (int j = 0; j < goNode.length; j++) {

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

i++;

}

return chars;

}

①判断串是否为空

②新建对应串长度的字符数组

③遍历每一个结点，将每个结点应的不同或相同长度的字符，按顺序赋值的对应位置的字符数组

④最后就返回字符数组的引用

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

    int i = 0;
    Node goNode = this._headNode;
    while (i < index) {
        goNode = goNode.next;
        i += goNode.length;
    }

    c = goNode.data[goNode.length - i + index - 1];
    return true;
}

//获取指定位置的字符

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

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

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

return false;

}

int i = 0;

Node goNode = this._headNode;

while (i < index) {

goNode = goNode.next;

i += goNode.length;

}

c = goNode.data[goNode.length - i + index - 1];

return true;

}

①检查索引的合法性

②找到对应的结点

③取出对应结点对应位置的数据

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

    for (int i = 0; i < chars.Length; i++) {
        if (this._lastNode.length >= this._nodeLength) {
            Node addNode = new Node();
            addNode.data = new char[this._nodeLength];
            addNode.next = null;
            this._lastNode.next = addNode;
            this._lastNode = addNode;
        }

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

    for (int i = this._lastNode.length; i < this._nodeLength; i++) {
        this._lastNode.data[i] = '\0';
    }

    this._length += chars.Length;
    return true;
}

//链接字符数组在串后面

public bool Concat(char[] chars) {

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

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

return false;

}

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

if (this._lastNode.length >= this._nodeLength) {

Node addNode = new Node();

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

addNode.next = null;

this._lastNode.next = addNode;

this._lastNode = addNode;

}

this._lastNode.data[this._lastNode.length++] = chars[i];

}

for (int i = this._lastNode.length; i < this._nodeLength; i++) {

this._lastNode.data[i] = '\0';

}

this._length += chars.Length;

return true;

}

链接字符数组在串的后面，这里跟上次的也差不多，跟ValueTo方法也很相同。这里直接向最后一个结点赋值数据，若最后结点已满，则更改最后一个结点为新的结点，继续赋值填充数据，最后修改长度就好。

public bool Concat(StringLink2 s) {
    char[] chars = s.ToChars();
    return this.Concat(chars);
}

public bool Concat(StringLink2 s) {

char[] chars = s.ToChars();

return this.Concat(chars);

}

//在指定位置插入字符数组
public bool Insert(int index, char[] chars) {

    if (this.IsEmpty() || chars == null) {
        Console.WriteLine("被插入的串或插入的字符数组不能为空！");
        return false;
    }

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

    int i = 0;
    Node preNode = this._headNode;
    Node targetNode = this._headNode;
    while (i < index) {
        preNode = targetNode;
        targetNode = targetNode.next;
        i += targetNode.length;
    }

    //获取目标位置中目标结点中数据的下标
    int sub = targetNode.length - (i - index) - 1;

    Node addNode = null;
    if (sub == 0)
    {
        //填充前一个结点的空闲位置
        addNode = preNode;
    }
    else {
        addNode = new Node();
        addNode.data = new char[this._nodeLength];
        addNode.next = null;
    }
            
    //填充目标结点中目标下标前的数据
    for (int j = 0; j < sub; j++) {
        addNode.data[addNode.length++] = targetNode.data[j];
    }
            
    for (int j = 0; j < chars.Length; j++) {
        if (addNode.length >= this._nodeLength)
        {
            preNode.next = addNode;
            preNode = addNode;
            addNode = new Node();
            addNode.data = new char[this._nodeLength];
            addNode.next = null;
        }
        addNode.data[addNode.length++] = chars[j];
    }

    //链接最后新加的结点
    preNode.next = addNode;
    preNode = addNode;
            

    if(sub != 0){
        for (int j = sub; j < targetNode.length; j++) {
            if (addNode.length >= this._nodeLength) {
                addNode = new Node();
                addNode.data = new char[this._nodeLength];
                addNode.next = null;
            }

            addNode.data[addNode.length++] = targetNode.data[j];
        }

        //链接
        preNode.next = addNode;
        preNode = addNode;

        //抛弃targetNode结点
        targetNode = targetNode.next;
    }

    preNode.next = targetNode;
    if (targetNode == null) {
        this._lastNode = preNode;
    }

    this._length += chars.Length;
    return true;
}

//在指定位置插入字符数组

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

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

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

return false;

}

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

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

return false;

}

int i = 0;

Node preNode = this._headNode;

Node targetNode = this._headNode;

while (i < index) {

preNode = targetNode;

targetNode = targetNode.next;

i += targetNode.length;

}

//获取目标位置中目标结点中数据的下标

int sub = targetNode.length - (i - index) - 1;

Node addNode = null;

if (sub == 0)

{

//填充前一个结点的空闲位置

addNode = preNode;

}

else {

addNode = new Node();

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

addNode.next = null;

}

//填充目标结点中目标下标前的数据

for (int j = 0; j < sub; j++) {

addNode.data[addNode.length++] = targetNode.data[j];

}

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

if (addNode.length >= this._nodeLength)

{

preNode.next = addNode;

preNode = addNode;

addNode = new Node();

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

addNode.next = null;

}

addNode.data[addNode.length++] = chars[j];

}

//链接最后新加的结点

preNode.next = addNode;

preNode = addNode;

if(sub != 0){

for (int j = sub; j < targetNode.length; j++) {

if (addNode.length >= this._nodeLength) {

addNode = new Node();

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

addNode.next = null;

}

addNode.data[addNode.length++] = targetNode.data[j];

}

//链接

preNode.next = addNode;

preNode = addNode;

//抛弃targetNode结点

targetNode = targetNode.next;

}

preNode.next = targetNode;

if (targetNode == null) {

this._lastNode = preNode;

}

this._length += chars.Length;

return true;

}

①检查字符串，字符数组和索引的合法性

②找到插入位置的结点和它的前一个结点，并找出插入位置结点的插入位置下标

③同上次，将插入结点分为插入位置前和后。当sub == 0 时，表示直接在其前结点或增加结点填充，sub ！= 0 时，表示插入结点有数据需要先保存

④先填充原插入结点的数据，再填充插入的字符数组，再填充插入结点插入位置和其后的数据

⑤注意结点的链接，注意抛弃插入结点后的情况

这里的步骤就不详细说了，可以参照上一篇，这里少了移动，只是将空闲的位置保留着

public bool Insert(int index,StringLink2 s) {
    char[] chars = s.ToChars();
    return this.Insert(index,chars);
}

public bool Insert(int index,StringLink2 s) {

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._length) {
        Console.WriteLine("索引错误！");
        return false;
    }


    Node preNode = this._headNode;
    Node targetNode = this._headNode;
    int i = 0;
    while (i < index) {
        preNode = targetNode;
        targetNode = targetNode.next;
        i += targetNode.length;
    }
    //获取位置下标
    int sub = targetNode.length - (i - index) - 1;


    //找出被删除后分开出来的第二部分子串
    int j = i - targetNode.length;
    int saveIndex = index + length;

    if (saveIndex > this.GetLength()) {
        //删除后面全部
        if (index == 1)
        {
            this.Clear();
        }
        else {
            if (sub == 0)
            {
                this._lastNode = preNode;
                preNode.next = null;
            }
            else {
                targetNode.length = sub;
                for (int k = sub; k < targetNode.length; k++) {
                    targetNode.data[k] = '\0';
                }
                this._lastNode = targetNode;
                targetNode.next = null;
            }
        }

        this._length -= length;
        return true;
    }

    Node saveNode = preNode;
    while(j < saveIndex)
    {
        saveNode = saveNode.next;
        j += saveNode.length;
    }
    int saveSub = saveNode.length - (j - saveIndex) - 1;
            

    if (saveSub >= sub)
    {
        for (int k = saveSub; k < saveNode.length; k++)
        {
            targetNode.data[sub++] = saveNode.data[k];
        }
        targetNode.length = sub;

        if (targetNode != saveNode) {
            targetNode.next = saveNode.next;
        }
    }
    else {
        targetNode.length = sub;
        for (int k = sub; k < this._nodeLength; k++) {
            targetNode.data[k] = '\0';
        }

        if (saveSub != 0) {
            for (int k = 0; k < saveNode.length - saveSub; k++)
            {
                saveNode.data[k] = saveNode.data[saveSub++];
            }

            saveNode.length = saveSub;
        }
                
        targetNode.next = saveNode;
    }

    this._length -= length;
    return true;
}

//删除指定长度的子串

public bool Delete(int index, int length) {

if (this.IsEmpty()) {

Console.WriteLine("删除的串不能为空！");

return false;

}

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

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

return false;

}

Node preNode = this._headNode;

Node targetNode = this._headNode;

int i = 0;

while (i < index) {

preNode = targetNode;

targetNode = targetNode.next;

i += targetNode.length;

}

//获取位置下标

int sub = targetNode.length - (i - index) - 1;

//找出被删除后分开出来的第二部分子串

int j = i - targetNode.length;

int saveIndex = index + length;

if (saveIndex > this.GetLength()) {

//删除后面全部

if (index == 1)

{

this.Clear();

}

else {

if (sub == 0)

{

this._lastNode = preNode;

preNode.next = null;

}

else {

targetNode.length = sub;

for (int k = sub; k < targetNode.length; k++) {

targetNode.data[k] = '\0';

}

this._lastNode = targetNode;

targetNode.next = null;

}

this._length -= length;

return true;

}

Node saveNode = preNode;

while(j < saveIndex)

{

saveNode = saveNode.next;

j += saveNode.length;

}

int saveSub = saveNode.length - (j - saveIndex) - 1;

if (saveSub >= sub)

{

for (int k = saveSub; k < saveNode.length; k++)

{

targetNode.data[sub++] = saveNode.data[k];

}

targetNode.length = sub;

if (targetNode != saveNode) {

targetNode.next = saveNode.next;

}

else {

targetNode.length = sub;

for (int k = sub; k < this._nodeLength; k++) {

targetNode.data[k] = '\0';

}

if (saveSub != 0) {

for (int k = 0; k < saveNode.length - saveSub; k++)

{

saveNode.data[k] = saveNode.data[saveSub++];

}

saveNode.length = saveSub;

}

targetNode.next = saveNode;

}

this._length -= length;

return true;

}

①判断索引和串的合法性

②找到删除位置的结点，和下标，考虑特殊情况，删除下标后面的所有子串

③若不是特殊情况，找到需要保留的结点和下标位置，考虑保留结点的结点数据长度小于或等于删除结点的删除数据。（保留下标>=删除下标），将保留结点的数据填充到删除结点中，节省空间，然后抛弃保留结点，链接删除结点和保留节点的下一个结点

④如果删除结点的删除空间不足填充保留结点的数据，那么修改删除结点的长度为相应长度（sub），填充空闲位置为'\0'，然后将保留结点的数据前移到最前面，修改长度

⑤对应长度减少

KMP匹配算法，这个也不说了哈

//KMP匹配
public int Index(StringLink2 match,int index = 1)
{
    if (match.IsEmpty() || this.IsEmpty()) {
        Console.WriteLine("串不能为空！");
        return 0;
    }

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

    int[] nextval = this._getNextVal(match);
    int i = index;
    int j = 1;
    while(i<=this.GetLength()) {
        if (j == 0 || this[i] == match[j])
        {
            i++;
            j++;
        }
        else {
            j = nextval[j];
        }

        if (j > match.GetLength())
        {
            return i - match.GetLength();
        }
    }

            

    return 0;
}

private int[] _getNextVal(StringLink2 s) {
    int[] nextVal = new int[s.GetLength()+1];
    nextVal[1] = 0;
    int i = 1;
    int j = 0;
    for (; i < s.GetLength();) {
        if (j == 0 || s[i] == s[j])
        {
            j++;
            i++;
            if (s[i] == s[j])
            {
                nextVal[i] = nextVal[j];
            }
            else
            {
                nextVal[i] = j;
            }
        }
        else
        {
            j = nextVal[j];
        }
    }

    return nextVal;
}

//KMP匹配

public int Index(StringLink2 match,int index = 1)

{

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

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

return 0;

}

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

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

return 0;

}

int[] nextval = this._getNextVal(match);

int i = index;

int j = 1;

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

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

{

i++;

j++;

}

else {

j = nextval[j];

}

if (j > match.GetLength())

{

return i - match.GetLength();

}

return 0;

}

private int[] _getNextVal(StringLink2 s) {

int[] nextVal = new int[s.GetLength()+1];

nextVal[1] = 0;

int i = 1;

int j = 0;

for (; i < s.GetLength();) {

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

{

j++;

i++;

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

{

nextVal[i] = nextVal[j];

}

else

{

nextVal[i] = j;

}

else

{

j = nextVal[j];

}

return nextVal;

}

//替换
public bool Replace(StringLink2 match, StringLink2 replace, int index = 1) {
    if (match.IsEmpty() || replace.IsEmpty() || this.IsEmpty()) {
        Console.WriteLine("串不能为空！");
        return false;
    }

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

    int i = this.Index(match, index);
    if (i != 0) {
        this.Delete(i, match.GetLength());
        if (i > this.GetLength()) {
            return this.Concat(replace);
        } else {
            return this.Insert(i, replace);
        }
    }

    return false;
}

//替换

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

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

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

return false;

}

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

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

return false;

}

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

if (i != 0) {

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

if (i > this.GetLength()) {

return this.Concat(replace);

} else {

return this.Insert(i, replace);

}

return false;

}

替换子串为其他串，这个也不说了哈

测试

static void TestStringLink2() {
    StringLink2 s = new StringLink2(new char[] { 'h', 'e', 'l', 'g', 'o' },3);
    PrintStringLink2(s,"串s为：");
    StringLink2 s2 = new StringLink2(new char[] { 'g', 'o' });
    s.Insert(2, new char[] { 'w', 'o' });
    PrintStringLink2(s,"串s在2位置插入wo后：");
    PrintStringLink2(s2, "串s2为：");
    Console.WriteLine("在串s中查找s2的位置为："+s.Index(s2));
    s.Insert(3, new char[] { 'f', 't' });
    PrintStringLink2(s,"串s在3号位插入ft后：");
    s.Delete(3, 3);
    PrintStringLink2(s,"串s删除3号位后3个字符后：");
    Console.WriteLine();

    s.Replace(s2, new StringLink2(new char[] { 'c', 'h', 'i' }));
    PrintStringLink2(s,"替换go为chi后：");
    s.Concat(new char[] { 'l', 'o', 'v', 'e' });
    PrintStringLink2(s,"链接love后：");
    s.Replace(new StringLink2(new char[] { 'v' }), s2);
    PrintStringLink2(s,"替换v为go后：");
    s.Insert(3, s2);
    PrintStringLink2(s,"3号位插入go后：");
    Console.WriteLine();

    Console.WriteLine("go的位置是："+ s.Index(s2));
    s.Delete(5, 1);
    PrintStringLink2(s,"删除5号位字符后：");
    s.Delete(1, s.GetLength());
    PrintStringLink2(s,"删除全部后：");
    s.ValueTo(new char[] { 'a', 'b', 'c' });
    PrintStringLink2(s,"赋值为abc后：");
    s.Concat(s2);
    PrintStringLink2(s,"链接go后：");
    Console.WriteLine("go的位置为："+s.Index(s2));
}

static void PrintStringLink2(StringLink2 s, string text = "输出：") {
    Console.Write(text);
    for (int i = 1; i <= s.GetLength(); i++) {
        char c = '\0';
        s.GetElementBuIndex(i, ref c);
        Console.Write(c);
    }
    Console.WriteLine();
}

static void TestStringLink2() {

StringLink2 s = new StringLink2(new char[] { 'h', 'e', 'l', 'g', 'o' },3);

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

StringLink2 s2 = new StringLink2(new char[] { 'g', 'o' });

s.Insert(2, new char[] { 'w', 'o' });

PrintStringLink2(s,"串s在2位置插入wo后：");

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

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

s.Insert(3, new char[] { 'f', 't' });

PrintStringLink2(s,"串s在3号位插入ft后：");

s.Delete(3, 3);

PrintStringLink2(s,"串s删除3号位后3个字符后：");

Console.WriteLine();

s.Replace(s2, new StringLink2(new char[] { 'c', 'h', 'i' }));

PrintStringLink2(s,"替换go为chi后：");

s.Concat(new char[] { 'l', 'o', 'v', 'e' });

PrintStringLink2(s,"链接love后：");

s.Replace(new StringLink2(new char[] { 'v' }), s2);

PrintStringLink2(s,"替换v为go后：");

s.Insert(3, s2);

PrintStringLink2(s,"3号位插入go后：");

Console.WriteLine();

Console.WriteLine("go的位置是："+ s.Index(s2));

s.Delete(5, 1);

PrintStringLink2(s,"删除5号位字符后：");

s.Delete(1, s.GetLength());

PrintStringLink2(s,"删除全部后：");

s.ValueTo(new char[] { 'a', 'b', 'c' });

PrintStringLink2(s,"赋值为abc后：");

s.Concat(s2);

PrintStringLink2(s,"链接go后：");

Console.WriteLine("go的位置为："+s.Index(s2));

}

static void PrintStringLink2(StringLink2 s, string text = "输出：") {

Console.Write(text);

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

char c = '\0';

s.GetElementBuIndex(i, ref c);

Console.Write(c);

}

Console.WriteLine();

}

结果

发表评论取消回复

登录 注册 找回密码

登录注册找回密码