Lecture 8

Posted on | Post modified | In |

Lecture 8

tags: Data Structure NYCU

Reference & Background

Note

Rewind

  • Array: 之前提到Array的結構，其缺點是大小是固定的，但有時候需要儲存的東西可能是動態改變的，且沒有用到的空間就會變成一種浪費
  • Solution: 此時就可能可以考慮用Link-List的結構處理這樣的資料

  • 主要結構: 每一個Element都會有兩個儲存單位，一個是儲存資料本體，另一個是儲存pointer，指向下一個Element的位置

  • Insert GAT: Create新的node，儲存GAT，並改變前後的指標，原本FAT的指標要assign給GAT的pointer，然後GAT的位址也要assign給FAT

  • Delete GAT: 把HAT的位址assign給FAT

    • 缺點：如果要delete某一個Element就需要”先找到該Element的位置在哪裡”，如果Link-List 很長，則要做到這件事情的Overhead就會很高
    • Solution: Double-Link-List，可以從前後同時找要刪除的Element，這樣的話就會比較快

Implement

Composite Classes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class ThreeLetterList; // forward delcanon 
class ThreeLetterNode {
    friend class ThreeLetterList; 
    private 
    char data[3]; // 每一個Elment就是只有儲存三個字元
    ThreeLetterNode *link;
};

class ThreeLetterList{ 
    public: 
        // List Manipulat10n operabons 
    private:
        ThreeLetterNode *first;
};

Another Implementation - Nested Classes

1
2
3
4
5
6
7
8
9
10
11
class ThreeLetterList{
    public:
    // List ManipuIation operatlons 
    private:
        class ThreeLetterNode{ // nested class 
        public:
            char data[3]; 
            ThreeLetterNode *link;
        };
        ThreeLetterNode *first;
};
  • How to create 2 link-list element 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
      void List::Create2()
  {
      /* create a linked list with two nodes */ 
      first = new ListNode(10); 
      first->link = new ListNode(20); 
  }
  ListNode::ListNode(int element=0)
  {
      data = element; 
      link = 0;
  }

  • How to insert 50 in a existed link-list 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
      void List::Insert50 (ListNode *x)
  {
      /* insert a new node with data=50 into the list* */ 
      ListNode *t = new ListNode(50); 
      if (!first) 
      {
          first = t; 
          return;
      }
      //insert after x 
      t->link = x->link; 
      x->link = t;
  }