Home   Cover Cover Cover Cover
 

Generische sortierte Liste

A03.cs
using System;

//==========================================================
// SortedList< T >
//==========================================================
class SortedList< T > where T: IComparable {
  
  class Node {
    public T val;
    public Node next;
    public Node(T x) { val = x; }
  }
  
  Node head = null;
  
  // adds x to the list
  public void Add(T x) {
    Node p = head, prev = null;
    while (p != null && p.val.CompareTo(x) < 0) {
      prev = p; p = p.next;
    }
    // p == null || p.val >= x
    Node n = new Node(x);
    n.next = p;
    if (prev == null) head = n; else prev.next = n;
  }
  
  // removes x from the list
  public void Remove(T x) {
    Node p = head, prev = null;
    while (p != null && p.val.CompareTo(x) != 0) {
      prev = p; p = p.next;
    }
    // p == null || p.val == x
    if (p != null) {
      if (prev == null) head = p.next; else prev.next = p.next;
    }
  }
  
  // returns the list length
  public int Count {
    get {
      int len = 0;
      for (Node p = head; p != null; p = p.next) len++;
      return len;
    }
  }
  
  // accesses the i-th element of the list
  public T this[int i] {
    get {
      if (i < 0) throw new Exception("-- index out of bounds");
      Node p = head;
      int j = 0;
      while (p != null && j < i) {
        p = p.next;
        j++;
      }
      // p == null || (j == i && p points to the i-th element)
      if (p == null) throw new Exception("-- index out of bounds");
      return p.val;
    }
  }
}

//----------------------------------------------------------
// test program
//----------------------------------------------------------
class Test {
  
  public static void Main() {
    SortedList<string> list = new SortedList<string>();
    //--- add words
    for (;;) {
      Console.Write("add word (terminate with empty string): ");
      string word = Console.ReadLine();
      if (word.Length == 0) break;
      list.Add(word);
    }
    //--- remove words
    for (;;) {
      //--- print the list
      int len = list.Count;
      for (int i = 0; i < len; i++) Console.WriteLine(list[i]);
      Console.WriteLine();
      //--- ask for the next word to be removed
      Console.Write("remove word (terminate with empty string): ");
      string word = Console.ReadLine();
      if (word.Length == 0) break;
      list.Remove(word);
    }
  }
}