資料結構 (Data Structure)

資料結構:電腦儲存資料的方式,例如陣列。

Stack 堆疊

  • 疊盤子,後進先出。

Queue 佇列

  • 排隊,先進先出。

Deque 雙端佇列

  • 念作 “deck”。
  • stack+queue=deque.

Linked List 連接串列

  • 對每個資料紀錄前後資料的位置。
  • 可以 O(1) 加入、刪除特定資料。
  • 不能 O(1) 存取指定 index 的資料。

Vector

Pair

  • #include <utility>
  • Pair:只有兩個參數的 struct。
pair<int,int> p;
p = make_pair(5, 3);
cout << p.first << ' ' << p.second << endl;

Heap 堆積

  • 一個能維護極值(最大值)的資料結構。
  • 功能:存取、刪除 heap 最頂端(極值)的資料。
  • 複雜度:O(log N)
  • STL提供的 heap 叫做 priority_queue。
  • Binary Heap Tree
#include <queue>
priority_queue<int> heap;

Set 集合

  • Set = 集合 = 元素不重複
  • 有排序的。
  • 可以插入(insert)、刪除(erase)、尋找(find)資料。
  • set.count(87) 回傳該元素是否存在。
  • 可以利用 prev() , next() 得到前後的 iterator。
  • 尋找值大於等於自己的第一個 iterator:set.lower_bound(87);
  • 尋找值大於自己的第一個 iterator:set.upper_bound(87);
  • Disjoint Set 併查集:詢問兩元素是否在同一集合、合併兩個元素所在的集合。
for(set<int>::iterator i=s.begin(); i!=s.end(); i++){
  cout << *i << endl;
}

Map 映射

  • 一個 key 對到一個 value,key 不可重複,value 可以重複。
  • 插入、修改、刪除、尋找
  • map 是有序的(按照 key 排序)。
map<int,int> m;
m.insert(pair<int,int>(1,11));
m.insert(pair<int,int>(2,22));
m.insert(pair<int,int>(3,33));
for(map<int,int>::iterator i=m.begin(); i!=m.end(); i++){
  cout << i->first << ' ' << i->second << endl;
}
分享文章!
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。