資料結構與算法筆記（五） 連結清單的應用

1.箱子排序：

假設：

用連結清單儲存一個班級學生的清單，節點的資料域包括：姓名，社會保險号碼，作業和考試的分數，所有作業和權重的總分。假設分數介于(0-100)之間，按照總分對學生進行排序，一種較快的排序方法是箱子排序(bin sort)：把相同分數的節點放到一個箱子裡，然後把箱子連接配接起來就得到有序的連結清單

箱子排序要做的是:(1)逐個删除輸傳入連結表的節點，把删除的節點配置設定到相應的箱子中9,每個箱子相當于一個連結清單  (2)把每個箱子中的連結清單收集起來并連接配接，使其成為一個有序的連結清單

定義學生記錄：

struct studentRecord
{
	int score;
    string name;
    
    // 構造方法
	studentRecord(const string& name, int score)
	{
		this->name = name;
		this->score = score;
	} 
	
    int operator !=(const studentRecord& x) const
    {
		return score==x.score;
	}
	
	operator int() const
	{
		return score;
	}
	
};
           

凸包：

多邊形：至少有三條直線便的平面封閉圖形，多邊形包含邊線上的點，也包含變現内的點。多邊形的任意兩個點的連線都不包含多邊形以内的點，則稱為凸多邊形.

一個平面點集S的凸包：包含點集S的最小凸多邊形

多邊形的定點稱為S的極點。

尋找平面點集S的凸包的算法：

1.處理退化情況

S的點數少于3;

S的所有點在同一條直線上， 傳回包含S的所有點的最短直線的定點

2. 極角排序：

假定在S的凸包内取一點X, 從X向下畫垂線。垂線和X到點s_i之間的連線有一個夾角，稱為極角。

按照極角的遞增次序排列S的點，如果極角相同，則按照與X的距離遞增來排列S的點。

3.尋找并删除非極點的點

如果u,v,w是按照逆時針排列的三個連續的極點，從u->v,w->v之間的連線的夾角應該大于180，當按照極角排列的三個點的極角小于等于180時，則第二個點不是極點，可以将其删除。因為當按照逆時針方向在一個凸多邊形上行走時，所有的轉彎都是向左轉。

采用雙向循環連結清單存儲資料

假設p時連結清單中的點（y坐标最小或者x坐标最大, 因為這個點肯定在凸包上）：

for(x=p, rx=x->right; p!=rx)
{
     rrx = rx->right;
     if(invalid(x,rx,rrx))    // 三個點不滿足條件， 删除rx
     {
          rx = x;
          x = rx;
     }
     else
     {
          x = rx;
          rx = rrx;
     }
}

           

---------------------------------------------------分割線-----------------------------------------------