C＃链接列表（将元素添加到定义的位置）

Question

我们的老师要求我们实施类LinkedList。我能够实现他所要求的一切。但他给了我一个我无法解决的奖金问题。

他让我们实现这个fonction：

public void add(float x, int pos) 
{ 
    // Add x at the position pos, pos = 0 refer to the first element. 
} 

他还要求他的代码验证以下单元测试：

public class UnitTest1 
{ 
    private MyList l; 

    public UnitTest1() 
    { 
     l = new MyList(); 
     for (int i = 0; i < 10; ++i) 
     { 
      l.add(i * i); 
     } 
     for (int i = 0; i < 10; ++i) 
     { 
      l.add(i * i); 
     } 
    } 

    [TestMethod] 
    public void TestAdd() 
    { 
     Assert.AreEqual(l.count(), 20); 
    } 
    [TestMethod] 
    public void TestGet() 
    { 
     for (int i = 0; i < 10; ++i) 
     { 
      Assert.AreEqual(l.get(i), (9 - i) * (9 - i)); 
     } 
     for (int i = 10; i < 20; ++i) 
     { 
      Assert.AreEqual(l.get(i), (19 - i) * (19 - i)); 
     } 
    } 
    [TestMethod] 
    public void TestFind() 
    { 
     int k; 
     for (int i = 0; i < 100; ++i) 
     { 
      for (k = 0; k < 10; ++k) 
      { 
       if (k * k == i) 
       { 
        Assert.AreEqual(l.find(i), true); 
        break; 
       } 
      } 
      if (k == 10) 
      { 
       Assert.AreEqual(l.find(i), false); 
      } 
     } 
    } 

    [TestMethod] 
    public void TestStats() 
    { 
     Assert.AreEqual(l.max(), 81); 
     float s = 0; 
     for (int i = 0; i < 10; ++i) 
     { 
      s += i * i + i * i; 
     } 
     Assert.AreEqual(l.sum(), s); 
     Assert.AreEqual(l.average(), s/20); 
    } 

    [TestMethod] 
    public void TestCountValue() 
    { 
     MyList l1 = new MyList(); 
     for (int i = 0; i < 10; ++i) 
     { 
      l1.add(i); 
      l1.add(i * i); 
     } 
     Assert.AreEqual(l1.count(-1), 0); 
     Assert.AreEqual(l1.count(0), 2); 
     Assert.AreEqual(l1.count(1), 2); 
     Assert.AreEqual(l1.count(2), 1); 
     Assert.AreEqual(l1.count(3), 1); 
     Assert.AreEqual(l1.count(4), 2); 
     Assert.AreEqual(l1.count(5), 1); 
     Assert.AreEqual(l1.count(6), 1); 
     Assert.AreEqual(l1.count(7), 1); 
     Assert.AreEqual(l1.count(8), 1); 
     Assert.AreEqual(l1.count(9), 2); 
     Assert.AreEqual(l1.count(10), 0); 
     Assert.AreEqual(l1.count(16), 1); 
    } 

    [TestMethod] 
    public void TestRemoveFirst() 
    { 
     MyList l1 = new MyList(); 
     for (int i = 0; i < 10; ++i) 
     { 
      l1.add(i); 
      l1.add(i * i); 
     } 
     Assert.AreEqual(l1.count(81), 1); 
     l1.removeFirst(); 
     Assert.AreEqual(l1.count(), 19); 
     Assert.AreEqual(l1.count(81), 0); 
     Assert.AreEqual(l1.count(-1), 0); 
     Assert.AreEqual(l1.count(0), 2); 
     Assert.AreEqual(l1.count(1), 2); 
     Assert.AreEqual(l1.count(2), 1); 
     Assert.AreEqual(l1.count(3), 1); 
     Assert.AreEqual(l1.count(4), 2); 
     Assert.AreEqual(l1.count(5), 1); 
     Assert.AreEqual(l1.count(6), 1); 
     Assert.AreEqual(l1.count(7), 1); 
     Assert.AreEqual(l1.count(8), 1); 
     Assert.AreEqual(l1.count(9), 2); 
     Assert.AreEqual(l1.count(10), 0); 
     Assert.AreEqual(l1.count(16), 1); 
    } 

    [TestMethod] 
    public void TestInsert() 
    { 
     MyList l1 = new MyList(); 
     for (int i = 9; i >= 0; --i) 
     { 
      l1.add(i); 
     } 
     for (int i = 0; i <= 10; ++i) 
     { 
      l1.add(i, 2 * i); 
     } 
     for (int i = 0; i < 10; ++i) 
     { 
      Assert.AreEqual(l1.get(2 * i), i, "i=" + i); 
      Assert.AreEqual(l1.get(2 * i + 1), i); 
     } 
     Assert.AreEqual(l1.get(20), 10); 
    } 
} 

这就是我能：

public class MyList 
{ 
    class Element 
    { 
     public float value; 
     public Element next; 
    } 

    Element first; 

    public MyList() 
    { 
     first = null; 
    } 

    public void add(float x) 
    { 
     Element e = new Element(); 
     e.value = x; 
     e.next = first; 
     first = e; 
    } 
    public float get(int i) 
    { 
     if (first == null) 
     { 
      throw new Exception("Empty list... no elements inside"); 
     } 

     Element tmp = first; 
     for (int j = 0; j < i; ++j) 
     { 
      tmp = tmp.next; 
      if (tmp == null) 
      { 
       throw new Exception("..."); 
      } 
     } 

     return tmp.value; 
    } 

    public void print() 
    { 
     Element e = first; 
     while (e != null) 
     { 
      Console.WriteLine(e.value); 
      e = e.next; 
     } 
    } 

    public bool find(float x) 
    { 
     Element e = first; 
     while (e != null) 
     { 
      if (e.value == x) 
      { 
       return true; 
      } 
      e = e.next; 
     } 

     return false; 
    } 

    public float max() 
    { 
     float G = 0; 
     for (Element e = first; e != null; e = e.next) 
     { 
      if (e.value > G) 
      { 
       G = e.value; 
      } 
     } 

     return G; 
    } 

    public int count() 
    { 
     Element e = first; 
     int c = 0; 
     while (e != null) 
     { 
      c++; 
      e = e.next; 
     } 

     return c; 
    } 

    public int count(float x) 
    { 
     int c = 0; 
     for (Element e = first; e != null; e = e.next) 
     { 
      if (e.value == x) 
      { 
       c++; 
      } 
     } 

     return c; 
    } 

    public float sum() 
    { 
     float S = 0; 
     for (Element e = first; e != null; e = e.next) 
     { 
      S += e.value; 
     } 

     return S; 
    } 

    public float average() 
    { 
     return sum()/count(); 
    } 

    public void removeFirst() 
    { 
     Element e = first; 
     first = e.next; 
    } 

    public void add(float x, int pos) 
    { 
     //I have absolutely no idea how to implement this fonction. 
    } 
} 

Answer 1

它将与get（）方法中的代码类似。

下打破你的问题分成较小的问题

• 是否POS = 0？
  • 如果是这样，创建一个新的根并将其指向旧的根
  • 若否，循环（POS）倍，并创建一个新元素。然后将新元素的下一个属性设置为当前元素的下一个属性。当前元素下一个属性设置为您的新元素

。

public void add(float x, int pos) 
{ 
    if(pos == 0) 
    { 
     // create a new root and point the new root to the existing root 
    } 
    else 
    { 
     Element tmp = first; 
     for(int i = 0; i < pos; i++) 
     { 
      tmp = tmp.next; 
     } 

     // create new element 
     // set new element next property to tmp.next 
     // set tmp.next to new element 
    } 
}