天天看點
傳回

線性表（三） 連結清單

目錄

    • 連結清單
      • 單連結清單
      • 雙連結清單
      • 循環連結清單
      • 總結

連結清單

連結清單是由一系列稱為表的結點的對象組成的。它可以動态配置設定存儲空間，解決了數組的靜态配置設定存儲空間的一些弊端。在一些應用中，常采用動态配置設定靜态化的思想為連結清單配置設定存儲空間，這種技術稱為“存儲池”。常見的連結清單類型有：單連結清單、雙連結清單、循環連結清單，本文将對三者做詳細介紹。

單連結清單

實作一個連結清單首先需要定義連結清單的“零件”——Link類

template <typename E> class Link 
{
public:
	E element;
	Link *next;
	Link(const E& elemval, Link* nextval = NULL)
	{	element = elemval;	next = nextval;	}
	Link(Link* nextval = NULL)
	{	next = nextval;	}
}

此為單連結清單的Link類：包含一個存儲元素值的element域和一個存儲表中下一結點指針的next域。它的構造函數有兩種形式，一個函數有初始化元素的值，另一個則沒有。

注：看上去Link類的資料成員聲明為公有違反了封裝原則，實際上Link類作為連結清單(或棧、隊列)實作的一個私有類來實作，是以對程式其他部分是不可見的。

下面給出單連結清單類LList的實作

template <typename E> class LList : public List<E>
{
private:
	Link<E>* head;
	Link<E>* tail;
	Link<E>* curr;
	int cnt;

	void init()
	{
		curr = tail = head = new Link<E>;
		cnt = 0;
	}

	void removeall()
	{
		while (head != NULL)
		{
			curr = head;
			head = head->next;
			delete curr; //一切操作都是對目前位置的操作
		}
	}

public:
	LList(int size = defaultSize) { init(); }
	~LList() { removeall(); }
	void print() const;
	void clear() { removeall(); init(); }

	// 關鍵函數實作
	void insert(const E& it)
	{
		curr->next = new Link<E>(it, curr->next);
		if (tail == curr) tail = curr->next; // New tail
		cnt++;
	}

	void append(const E& it)
	{
		tail = tail->next = new Link<E>(it, NULL);
		cnt++;
	}

	E remove()
	{
		Assert(curr->next != NULL, "No element")
		E it = curr->next->element;
		Link<E>* ltemp = curr->next;
		if(tail == curr->next) tail = curr;
		curr->next = curr->next->next;
		delete ltemp;
		cnt--;
		return it;
	}
	
	void moveToStart()
	{ curr = head; }

	void moveToEnd()
	{ curr = tail; }

	void prev() //前驅
	{
		if(curr == head) return;
		Link<E>* temp = head;
		while(temp->next != curr) temp = temp->next;
		curr->temp;
	}

	void moveToPos(int pos)
	{
		Assert((pos >= 0) && (pos <= cnt), "Position out of range");
		curr = head;
		for(int i = 0; i < pos; i++) curr = curr->next;
	}

	void next() //後繼
	{
		if(curr != tail) curr = curr->next; 
	}

	// 連結清單目前相關參數
	int length() const { return cnt; }

	int currPost() const 
	{
		Link<E>* temp = head;
		int i;
		for (int i = 0; curr != temp; i++)
			temp = temp->next;
		return i;
	}

	const E& getValue() const //Return current element
	{
		Assert(curr->next != NULL; "No value");
		return curr->next->element;
	}
};

注：

  1. 為了加速對連結清單尾端的通路，特别為了允許append函數的執行時間為一常數值，名為tail的指針儲存了連結清單的最後一鍊。
  2. 為了

    操作的便利性

     以及考慮對特殊情況的

    一緻性處理

    ，本例的設計考慮了如下兩個政策：

    i) 讓curr指針指向

    目前元素

    的前一個元素

    ii) 增加特殊的

    表頭結點
  3. cnt存放線性表的長度，對連結清單的每個修改操作都要更新它們的值。
  4. 類LList包含兩個私有成員函數：init和removeall。LList的構造函數、析構函數和clear函數都用到了這兩個函數。
  5. 請額外注意體會

    insert

     和

    remove

    的實作。

    i) 在連結清單的目前位置插入一個新元素包括三個步驟。首先，要建立一個新的結點；其次，新結點的next域要指向目前結點；最後，重定向curr的next域至新結點。

    ii) 從連結清單删除一個元素必須小心。不要“丢失”被删除結點的記憶體。此記憶體應該傳回給存儲器。是以，首先将要删除的指針指向臨時指針ltemp，然後調用delete函數釋放被删除結點占用的記憶體。

下面給出一個小結論幫助記憶：

修改curr，使用temp指針作為輔助量；修改連結清單元素，使用curr指針作為輔助量。（分别參考prev和clear函數）

雙連結清單

單連結清單隻允許從一個表結點直接通路它的後繼結點，而雙連結清單存儲了兩個指針，使得雙連結清單可以從一個表結點出發，線上性表中随意通路它的前驅結點和後繼結點。雙連結清單使用起來比單連結清單更加便捷，也更容易實作和調試，是以廣受喜愛。它和單連結清單相比唯一的缺點就是使用更多的空間1。

類似于單連結清單，為了去除一些特殊情況以及簡化操作，雙連結清單的實作使用了不包含任何資料資訊的頭結點和尾結點。它們在雙連結清單初始化時被建立，并用head和tail指針分别指向。

雙連結清單Link類：

template <typename E> class Link 
{
public:
	E element;
	Link* prev;
	Link *next;
	
	Link(const E& it, Link* prevp, Link* nextp)
	{	
		element = it;
		prev = prevp;
		next = nextp;
	}
	Link( Link* prevp = NULL, Link* nextp = NULL)
	{	
		element = it;
		prev = prevp;
		next = nextp;
	}
}

雙連結清單關鍵操作：

void insert(const E& it)
{
	curr->next = curr->next->prev = new Link<E>(it, curr, curr->next);
	//先長後短：先修改curr->next->prev,再修改curr->next
	cnt++;
}

template<typename E>
void LList<E>:: append(const E& it)
{
	tail->prev = tail->prev->next = new Link<E>(it, tail->prev, tail);
	cnt++;
}

template<typename E>
E LList<E>:: remove()
{
	if(curr->next==tail) return NULL;
	E it = curr->next->element;
	Link<E>* ltemp = curr->next;
	/*先長後短：先修改curr->next->next->prev,再修改curr->next*/
	curr->next->next->prev = curr;
	curr->next = curr->next->next;
	delete ltemp;
	cnt--;
	return it;
}

template<typename E>
void LList<E>:: prev()
{
	if(curr != head)
		curr = curr->prev;
}

這裡再給出一個小結論： 雙連結清單增删操作中，總要重定向原表中兩個指針，且總是先修改"易丢失"的結點的指針(即沒被curr指向的結點)，在本示例代碼中可以直覺的展現為修改的先長後短原則（如下圖）

線性表（三） 連結清單

注意，此結論同樣适用于單連結清單的增删操作。

思考

考慮一種

基于異或

的節省空間的方法，用來消除雙連結清單額外的空間需求，盡管它會使實作變得複雜，運作速度稍微減慢。（這種方法是一個時空權衡的例子）

分析：

由 (L^R)^R = L, (L^R)^L = R 可知，給出兩個值，并将它們異或，則其中任何一個值都可以由另外一個值與它們異或後的結果再異或而得到。是以，雙連結清單可以通過在一個指針域中存儲兩個指針值的異或結果來實作。這樣一來，一個結點的指針值可以由它的前驅結點指針值與該前驅的next域異或得到。是以，隻要分解連結域就能順着連結清單走下去，像拉開拉鍊一樣。

注：這種方法的原理值得注意，計算機圖形學中廣泛利用了這一原理。(把螢幕上一個區域與一個矩形圖像異或，使該區域的圖像高亮，再次與矩形圖像異或使之複原)

循環連結清單

循環連結清單是指連結清單中最後那個鍊結點的指針域存放指向連結清單最前面那個結點的指針，整個連結清單形成一個環。

隻要給出任何一個結點的位置，則由此出發就可以通路表中其他所有結點。

線性表（三） 連結清單
template<class E>
void LList<E>:: LList(const int sz)
{
	head = tail = curr = new link();
	head->next = head;
	cnt = 0;
}

template<class E>
void LList<E>::clear()
{
	while(head->next != NULL)
	{
		curr = head->next;
		head->next = curr->next;
		delete curr;
	}
	tail = curr = head->next = head;
}

template<class E>
void LList<E>::append(const E& it)
{tail = tail->next = new link(it, head);}

template<class E>
void LList<E>::insert(const E& it)
{
	assert(curr != NULL);
	curr->next = new link(it, curr->next);
	if(tail->next != head) tail = tail->next;
	cnt++;
}

template<class E>
void LList<E>::next()
{curr = curr->next;}

template<class E>
void LList<E>::prev()
{
	link* temp = curr;
	while(temp->next != curr) temp = temp->next;
	curr = temp;
}

總結

通過三種連結清單的學習，我們可以發現，連結清單的組成就是一個個Link對象，連結清單的操作無非為增删查改，代碼編寫過程中的需注意的特殊情況主要有是否為空、是否為首尾，删除時注意記憶體管理防止記憶體洩露。

Data Structure and Algorithm 連結清單
上一篇: 深入淺出DevOps：初識Pipline流水線任務
下一篇: 深入淺出DevOps：Jenkins任務建構結果通知

繼續閱讀