# Simple life, Complicated mind

## Saturday, November 12, 2011

### 該如何學好 "寫程式" #3. 進階應用 - 資料結構 + 問題分析

1. 你該用什麼樣的方式來儲存這樣的地圖資訊?
這裡會用到的知識，是資料結構裡的 GRAPH，典型的方法就是分成點跟線來記錄..
2. 你該用什麼樣的演算法，找出你要的最佳路線?
最基本的是要找出所有可走的路線 (走迷宮)，再找出其中最便宜的一條路。
3. 你的程式的結構該如何設計?
這部份跟課本比較無關，講的是你對程式語言及可用的函式庫/工具的掌握，還有架構等等。

```   1:  public class Node
```
```   2:  {
```
```   3:      public string Name = null;
```
```   4:      public int TollFee = 0;
```
```   5:      public List Links = new List();
```
```   6:      public Node(string name, int tollFee)
```
```   7:      {
```
```   8:          this.Name = name;
```
```   9:          this.TollFee = tollFee;
```
```  10:      }
```
```  11:  }
```

```   1:  public class Link
```
```   2:  {
```
```   3:      public double Distance = 0D;
```
```   4:      public Node FromNode = null;
```
```   5:      public Node ToNode = null;
```
```   6:      public RoadNameEnum Road;
```
```   7:      public Link(Node from, Node to, double distance, RoadNameEnum road)
```
```   8:      {
```
```   9:          this.FromNode = from;
```
```  10:          this.ToNode = to;
```
```  11:          this.Distance = distance;
```
```  12:          this.Road = road;
```
```  13:      }
```
```  14:      public enum RoadNameEnum
```
```  15:      {
```
```  16:          Highway1,
```
```  17:          Highway2,
```
```  18:          Highway3
```
```  19:      }
```
```  20:  }
```

MAP
```   1:  public class Map
```
```   2:  {
```
```   3:      private Dictionary<string, Node> _nodes = new Dictionary<string, Node>();
```
```   4:      public Map()
```
```   5:      {
```
```   6:          //
```
```   7:          //  construct / load map data
```
```   8:          //
```
```   9:          this.AddNode("基金", 0);
```
```  10:          this.AddNode("七堵收費站", 40);
```
```  11:          this.AddNode("汐止系統", 0);
```
```  12:          this.AddNode("樹林收費站", 40);
```
```  13:          // 略
```
```  14:          this.AddLink("基金", "七堵收費站", 4.9-0, Link.RoadNameEnum.Highway3);
```
```  15:          this.AddLink("七堵收費站", "汐止系統", 10.9-4.9, Link.RoadNameEnum.Highway3);
```
```  16:          // 略
```
```  17:      }
```
```  18:      private void AddNode(string name, int tollFee)
```
```  19:      {
```
```  20:          Node n = new Node(name, tollFee);
```
```  21:          this._nodes.Add(name, n);
```
```  22:      }
```
```  23:      private void AddLink(string n1, string n2, double distance, Link.RoadNameEnum road)
```
```  24:      {
```
```  25:          Node node1 = this._nodes[n1];
```
```  26:          Node node2 = this._nodes[n2];
```
```  27:          Link link = new Link(this._nodes[n1], this._nodes[n2], distance, road);
```
```  28:          node1.Links.Add(link);
```
```  29:          node2.Links.Add(link);
```
```  30:      }
```
```  31:      public Link FindLink(string name1, string name2)
```
```  32:      {
```
```  33:          foreach (Link way in this._nodes[name1].Links)
```
```  34:          {
```
```  35:              if (way.GetOtherNodeName(name1) == name2) return way;
```
```  36:          }
```
```  37:          return null;
```
```  38:      }
```
```  39:  }
```

```   1:  private double _cost = 0;
```
```   2:  private string[] _best_path = null;
```
```   3:  private Stack<string> _path = null;
```
```   4:  private void Search(string startName, string endName, double current_cost)
```
```   5:  {
```
```   6:      this._path.Push(startName);
```
```   7:      if (startName == endName)
```
```   8:      {
```
```   9:          if (this._cost == 0 || current_cost < this._cost)
```
```  10:          {
```
```  11:              this._cost = current_cost;
```
```  12:              this._best_path = this._path.ToArray();
```
```  13:          }
```
```  14:          this._path.Pop();
```
```  15:          return;
```
```  16:      }
```
```  17:      foreach (Link way in this._nodes[startName].Links)
```
```  18:      {
```
```  19:          string next = way.GetOtherNodeName(startName);
```
```  20:          if (this._path.Contains(next) == false)
```
```  21:          {
```
```  22:              this.Search(
```
```  23:                  next,
```
```  24:                  endName,
```
```  25:                  current_cost + this._nodes[next].TollFee + way.Distance * 3);
```
```  26:          }
```
```  27:      }
```
```  28:      this._path.Pop();
```
```  29:  }
```
```  30:  public string[] FindBestPath(string startName, string endName, out double cost)
```
```  31:  {
```
```  32:      try
```
```  33:      {
```
```  34:          this._cost = 0;
```
```  35:          this._path = new Stack<string>();
```
```  36:          this.Search(startName, endName, 0);
```
```  37:          cost = this._cost;
```
```  38:          return this._best_path;
```
```  39:      }
```
```  40:      finally
```
```  41:      {
```
```  42:          this._cost = 0;
```
```  43:          this._path = null;
```
```  44:      }
```
```  45:  }
```

if (this._path.Contains(next) == false)

This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

The HashSet<(Of <(T>)>) class provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.
The capacity of a HashSet<(Of <(T>)>) object is the number of elements that the object can hold. A HashSet<(Of <(T>)>) object's capacity automatically increases as elements are added to the object.

If Count is less than the capacity of the internal array, this method is an O(1) operation. If theHashSet<(Of <(T>)>) object must be resized, this method becomes an O(n) operation, where n is Count.

HashSet.Contains( T ):
This method is an O(1) operation.

HashSet.IntersectWith(Hash):
If the collection represented by the other parameter is a HashSet<(Of <(T>)>) collection with the same equality comparer as the current HashSet<(Of <(T>)>) object, this method is an O(n) operation. Otherwise, this method is an O(n + m) operation, where n is Count and m is the number of elements in other.

---------------------------

• 我不會這些，程式還不一樣寫的好好的?
• 都什麼年代了，現在講求的是程式架構!
• 物件導向不是都講求封裝? 幹嘛還要去挖這些?
• 現在資料都放資料庫了，還學這幹嘛?
• ...

Reference: