链表对象的 substring() 方法

Question

我在为 class 我正在构建的 LString 编写 substring() 方法时遇到了一些问题。 class 创建了一个名为 LString 的链表对象，用于构建字符串。它模仿 Java 中的 String 和 StringBuilder 对象。

substring(int start, int end) 从给定的 this LString，从 start 提供的索引到 end 创建一个新的 LString。它 returns 输入 LString.

这是错误消息，没有任何编辑以包含 end：

Running substring tests (63 tests)
Starting tests: ......E........................................................
Time: 0.031

There was 1 failure:
1) test43cSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.AssertionError: Substring of One Character LString is not equals LString expected: LString<a> but was: LString<a>
        at org.junit.Assert.fail(Assert.java:88)
        at org.junit.Assert.failNotEquals(Assert.java:743)
        at org.junit.Assert.assertEquals(Assert.java:118)
        at LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(LStringTest.java:401)
        ... 10 more

Test Failed! (1 of 63 tests failed.)

Test failures: abandoning other phases.

这会产生更简单的错误消息，只有 1 次失败。

这是与该错误消息对应的代码：

import java.io.*;
import java.util.*;

public class LString    {

     node   front;
     int size;

     //Creating a node class
     private    class   node {
          char data;
          node next;

          public    node (){
          }

          public    node    (char   newData){
                this.data = newData;
          }

          public    node    (char   newData,    node newNext){
                this.data = newData;
                this.next = newNext;
          }


     }
     //Constructors
     public LString(){
          this.size =   0;
          this.front =  null;
     }
     public LString(String original)    {
          this.size = original.length();
          if (original.length() > 0){

              this.front =  new node(original.charAt(0));
              node curr = this.front;

              for   (int i =1; i <  original.length(); i++) {
                    curr.next = new node(original.charAt(i));
                    curr = curr.next;
              }
          }



     }

    //  Length method,  returns the length of LString
     public int length()    {
        return this.size;
    }

    //  compareTo method,   compares    this LString to anotherLString, returns 0   if  equal,
    //  -1  if  lexicogrpahically   less,   and 1   if  lexicographically   greater
    public int compareTo(LString anotherLString)    {
        int len1    = length();
        int len2    = anotherLString.length();
        int lim = Math.min(len1, len2);

        node cn1    = front;
        node cn2    = anotherLString.front;

        int k   = 0;
        while   (k  < lim) {
            char c1 = cn1.data;
            char c2 = cn2.data;
            if  (c1 != c2) {
                return c1-c2;
            }
            k++;
            cn1 =   cn1.next;
            cn2 =   cn2.next;
        }
        return len1 - len2;

    }

    //  a boolean equals method that returns true   if  LString and other   are the same, false if not
    public boolean  equals(Object other)    {
        if  (this   ==  other) {
            return true;
        }
        if  (other instanceof   LString)    {
            LString otherLString    = (LString)other;
            int n   = length();
            if  (n  ==  otherLString.length()) {
                node n1 = front;
                node n2 = otherLString.front;
                while   (n1 != null) {
                    if  (n1.data    !=  n2.data)    {
                        return false;
                    }
                    n1  = n1.next;
                    n2  = n2.next;
                }
                return true;
            }
        }

        return false;
    }


    //  charAt returns  the character of LString at the argument index
    public char charAt(int index)   {

        if  ((index < 0) || (index >= this.length()))   {
            throw   new IndexOutOfBoundsException();
        }
        node curNode =  front;
        for (int    i = 0; i    < this.length(); i++, curNode   = curNode.next) {
            if  (i  ==  index) {
                return curNode.data;
            }
        }
        throw   new IllegalStateException();
    }

    //
    public void setCharAt(int index,    char ch)    {
      if (index < 0 || index >= this.length()) {
         throw new IndexOutOfBoundsException();
      }
      else {
         node currNode = front;
         for (int i = 0; i <this.length(); i++, currNode = currNode.next) {
            if (i == index) {
            currNode.data = ch;
            }
         }
      }
   }

    public LString  substring(int start,    int end)    {
      if (start < 0 || end > this.length() || start > end) {
         throw new IndexOutOfBoundsException();
      }
      LString substring = new LString();
      if (start == end) {
         return substring;
      }
      node node = this.front;
      for (int i = 0; i < start; i++) {
         node = node.next;
      }
      node copy = new node(node.data);
      substring.front = copy;
      for (int i = start+1; i < end; i++) {
         node = node.next;
         copy = copy.next = new node(node.data);
      }
      return substring;      
    }
    public LString  replace(int start, int end, LString lStr)   {
        return null;
    }

    public String toString(){
        StringBuilder result    = new   StringBuilder();

        node curr = front;
        while   (curr   !=  null){

            result.append(curr.data);
            curr = curr.next;
        }
        return result.toString();
    }
}

几点说明：我确实写了一个toString()方法，这段代码里还有一个replace()方法，以后再写。

这里是使 end 包含在内的错误和代码：

错误：

Running substring tests (63 tests)
Starting tests: E....EEE....E.EEEEEE.....E.EEEEEEE....E.EEEEEEE....E.EEEEEEE...
Time: 0.028

There were 35 failures:
1) test41aSubStringEmpty(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test41aSubStringEmpty(LStringTest.java:368)
        ... 10 more
2) test43bSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43bSubStringOneChar(LStringTest.java:395)
        ... 10 more
3) test43cSubStringOneChar(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43cSubStringOneChar(LStringTest.java:401)
        ... 10 more
4) test43dSubStringOneCharIsNew(LStringTest$LStringSubStringTestSpecial)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTestSpecial.test43dSubStringOneCharIsNew(LStringTest.java:407)
        ... 10 more
5) test51bEmptySubstringAtEnd[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
6) test51dSubstringAtStart[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
7) test51eSubstringAtEnd[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
8) test51fSubstringInMiddle[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<[]> but was:<[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
9) test51gSubstringAll[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
10) test51hSubstringAtStartIsNew[0](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
11) test51jSubstringAtEndIsNew[0](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
12) test51bEmptySubstringAtEnd[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
13) test51dSubstringAtStart[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
14) test51eSubstringAtEnd[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
15) test51fSubstringInMiddle[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<b[]> but was:<b[c]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
16) test51gSubstringAll[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
17) test51hSubstringAtStartIsNew[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<a[]> but was:<a[b]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
18) test51jSubstringAtEndIsNew[1](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
19) test51kSubstringInMiddleIsNew[1](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<b[]> but was:<b[c]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more
20) test51bEmptySubstringAtEnd[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
21) test51dSubstringAtStart[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<A long []> but was:<A long [s]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
22) test51eSubstringAtEnd[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
23) test51fSubstringInMiddle[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<ng str[]> but was:<ng str[i]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
24) test51gSubstringAll[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
25) test51hSubstringAtStartIsNew[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<A long []> but was:<A long [s]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
26) test51jSubstringAtEndIsNew[2](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
27) test51kSubstringInMiddleIsNew[2](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<ng str[]> but was:<ng str[i]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more
28) test51bEmptySubstringAtEnd[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51bEmptySubstringAtEnd(LStringTest.java:468)
        ... 10 more
29) test51dSubstringAtStart[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not correct expected:<This is an even[]> but was:<This is an even[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51dSubstringAtStart(LStringTest.java:478)
        ... 10 more
30) test51eSubstringAtEnd[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51eSubstringAtEnd(LStringTest.java:483)
        ... 10 more
31) test51fSubstringInMiddle[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not correct expected:<an even longer[]> but was:<an even longer[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51fSubstringInMiddle(LStringTest.java:488)
        ... 10 more
32) test51gSubstringAll[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51gSubstringAll(LStringTest.java:493)
        ... 10 more
33) test51hSubstringAtStartIsNew[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(0, mid) is not new LString expected:<This is an even[]> but was:<This is an even[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51hSubstringAtStartIsNew(LStringTest.java:500)
        ... 10 more
34) test51jSubstringAtEndIsNew[3](LStringTest$LStringSubStringTest)
java.lang.IndexOutOfBoundsException
        at LString.substring(LString.java:142)
        at LStringTest$LStringSubStringTest.test51jSubstringAtEndIsNew(LStringTest.java:505)
        ... 10 more
35) test51kSubstringInMiddleIsNew[3](LStringTest$LStringSubStringTest)
org.junit.ComparisonFailure: substring(left, right) is not new LString expected:<an even longer[]> but was:<an even longer[ ]>
        at org.junit.Assert.assertEquals(Assert.java:115)
        at LStringTest$LStringSubStringTest.test51kSubstringInMiddleIsNew(LStringTest.java:515)
        ... 10 more

Test Failed! (35 of 63 tests failed.)

Test failures: abandoning other phases.

这里是代码的相关区别，只有substring()不同：

public LString  substring(int start,    int end)    {
  if (start < 0 || end >= this.length() || start > end) {
     throw new IndexOutOfBoundsException();
  }
  LString substring = new LString();
  /*if (start == end) {
     return substring;
  }*/
  node node = this.front;
  for (int i = 0; i < start; i++) {
     node = node.next;
  }
  node copy = new node(node.data);
  substring.front = copy;
  for (int i = start; i < end; i++) {
     node = node.next;
     copy = copy.next = new node(node.data);
  }
  return substring;      
}

LStringTest 中有关错误的部分：

   @Test public void test43aSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not Empty",
               nullLString, testLString.substring(0, 0));
      }

      @Test public void test43bSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not Empty",
               nullLString, testLString.substring(1, 1));
      }

      @Test public void test43cSubStringOneChar() {
         LString testLString = new LString("a");
         assertEquals("Substring of One Character LString is not equals LString",
               testLString, testLString.substring(0, 1));
      }

Answer 1

我没有查看所有代码，只是把 substring() 方法的逻辑放在一起。由于您可以通过在给定位置设置一些字符来改变 LString ，因此我假设您确实想要子字符串的链表副本：您不希望采取子字符串的行为, 修改父字符串并修改子字符串。

您可以实现一个 "clever" 实现，在必要时才真正复制节点。例如，您可以让子字符串观察父字符串，以进行任何会影响子字符串节点的修改。当有一个时，就会发生复制。请参阅 Observer/Observable 模式来实现它。在您的情况下，如果您只保留一个 class、LString，它将实现 Observer 和 Observable。

无论如何，这是简单的复制实现

public LString  substring(int start,    int end)    {
    if (start < 0 || end > this.length() || start > end) {
        throw new IndexOutOfBoundsException();
    }
    if (start == end) {
        return new LString(); // return an "empty" LString
    }

    // Find starting node
    Node currentNode = front;
    for (int i = 0; i < start; i++) {
        currentNode = currentNode.next;
    }

    // create new LString and copy each node from start to end
    LString ls = new LString();
    ls.front = new node(currentNode.data)
    node newCur = ls.front;
    for (int i = start+1; i<end; i++) {
        currentNode = currentNode.next;
        node newNext = new node(currentNode.data);
        newCur.next = newNext;
        newCur = newNext;
    }
    ls.size = end-start;
    return ls;
}

Answer 2

其他答案中的代码无法编译，即使编译了，也无法正常运行。

假设您正在使用标准（对于 Java）从零开始的索引，并且 end 索引是独占的，此代码编译并测试。

public LString substring(int start, int end) {
    if (start < 0 || end > length() || start > end) {
        throw new IndexOutOfBoundsException();
    }
    LString result = new LString();
    if (start == end) {
        return result;
    }
    node node = this.front;
    for (int i = 0; i < start; i++) {
        node = node.next;
    }
    node copy = new node(node.data);
    result.front = copy;
    for (int i = start + 1; i < end; i++) {
        node = node.next;
        copy = copy.next = new node(node.data);
    }
    result.size = end - start;
    return result;
}

如果您希望 end 具有包容性，虽然这会违反 Java 惯例，但您需要更改三件事：

方法开头的保护子句必须说 end >= length() 而不是 end > length()、
第二个保护条款 if (start == end) { return substring; } 需要完全删除，并且
最后一个 for 循环将初始化 int i = start 而不是 int i = start + 1。

顺便说一句，如果您在 class.

中有一个 toString() 方法，那么查看您的 LString 实例发生了什么会容易得多

@Override
public String toString() {
    if (this.front == null) return "";
    StringBuilder sb = new StringBuilder(length());
    node node = this.front;
    do sb.append(node.data);
    while ((node = node.next) != null);
    return sb.toString();
}

链表对象的 substring() 方法

substring() method for linked list object

java

substring

linked-list