線性表之單連結清單的c++實作

單連結清單是線性表的一種鍊式存儲結構,它同順序表(由于順序表實作比較簡單,本文不做講述了)不同,是用一組任意位址的存儲單元,存放線性表中的元素。為了表示結點之間的關系,每個結點不僅要存儲它表示的元素，還要存儲它下一個結點的資訊。

下面我們用C++的模版來實作以下單連結清單:

結點定義

template <class T>
struct Node
{
	Node* pNextNode;
	T m_value;
};

單連結清單定義:

template <class T>
class CLinkList
{
private:
	Node<T>* m_pHead;
	int m_nLength; // 單連結清單長度
// 一進制多項式求和
	friend void Add(CLinkList<elem> & A, CLinkList<elem>& B);</span>
public:
	friend void Circle(int n, int m);

// 約瑟夫環
	CLinkList();</span>
	// 初始化含有n個元素,值為value的單連結清單n>=1
	CLinkList(int n, T value);
	~CLinkList();
	// 求單連結清單長度
	int GetLength();
	// 删除單連結清單的第i個結點,傳回删除結點的值
	T Delete(int i);
	// 在單連結清單中第i個位置插入值為x的元素
	void Insert(int i, T x);
	// 傳回值為value的序号
	int GetValue(T value);
	// 傳回第i個元素的值
	T GetLocate(int i);
	// 單連結清單周遊
	void PrintList();
	// 單連結清單逆序
	void Reverse();
将當連結清單轉換成環,此方法使用之後,隻能使用Delete(i)方法;此方法是為了解決約瑟夫環問題
	void Ring();
};

template <class T>
CLinkList<T>::CLinkList()
{
m_pHead = NULL;
}

1)關于單連結清單的建立

單連結清單的建立有兩種方法:頭插法:新插入的元素始終為插入的第一個元素建立過程:初始化頭指針為NULL,每建立一個元素,使其指向頭指針,将頭指針指向這個新建立的元素.

尾插法:先建立單連結清單頭指針元素,建立一個尾指針,指向目前元素.每建立一個元素,将尾指針元素的下一個結點指向建立元素,尾指針指向目前元素.

template <class T>
CLinkList<T>::CLinkList(int n, T value)
{
	if (n < 1)
	{
		m_pHead = NULL;
		return;
	}
	// 頭插法建立單連結清單
	/*for (int i = 0; i<n; i++)
	{
		Node* pNode = new Node<T>;
		pNode->m_value = value;
		pNode->pNextNode = pHead;
		pHead = pNode;
	}*/
	// 尾插法建立單連結清單
	m_pHead = new Node<T>;
	m_pHead->m_value = value++;
	m_pHead->pNextNode = NULL;
	Node<T>* pTail = m_pHead;
	for (int i = 1; i<n; i++)
	{
		Node<T>* pWork = new Node<T>;
		pWork->m_value = value++;
		pWork->pNextNode = NULL;
		pTail->pNextNode = pWork;
		pTail = pWork;
	}
}

2)求單連結清單長度

從頭結點周遊到尾結點,擷取長度.
<pre name="code" class="cpp">template <class T>
int CLinkList<T>::GetLength()
{
	if (m_pHead == NULL)
	{
		return 0;
	}
	int i = 0;
	Node<T>* r = m_pHead;
	while (r != NULL)
	{
		i++;
		r = r->pNextNode;
	}
	return i;
}

3)删除指定位置的連結清單結點,傳回删除結點的值

要特别注意删除位置是頭結點的情況,需要将頭指針重新指向

另外為了删除結點,還要儲存目前删除結點的前驅結點資訊.
<pre name="code" class="cpp">template <class T>
T CLinkList<T>::Delete(int i)
{
	if (i <= 0 || m_pHead == NULL)
	{
		CError error("删除位置異常");
		throw error;
	}
	// 頭指針删除
	if (i == 1)
	{
		Node<T>* r = m_pHead;
		m_pHead = m_pHead->pNextNode;
		int nValue = r->m_value;
		delete r;
		return nValue;
	}
	Node<T>* r = m_pHead;
	Node<T>* prev = m_pHead;
	while (--i && r != NULL)
	{
		prev = r;
		r = r->pNextNode;
	}
	if (r == NULL)
	{
		CError error("連結清單未初始化");
		throw error;
	}
	// r是要删除的結點,prev是前置結點
	int value = r->m_value;
	prev->pNextNode = r->pNextNode;
	delete r;
	return value;
}

4)在位置i插入值為x的結點

<pre name="code" class="cpp">template <class T>
void CLinkList<T>::Insert(int i, T x)
{
	if (i <= 0)
	{
		CError error("插入位置異常!");
		throw  error;
	}
	if (m_pHead == NULL)
	{
		m_pHead = new Node<T>;
		m_pHead->m_value = x;
		m_pHead->pNextNode = NULL;
		return;
	}
	// 尋找插入結點
	Node<T>* r = m_pHead;
	Node<T>* prev = m_pHead;
	while (--i && r!=NULL)
	{
		prev = r;
		r=r->pNextNode;
	}
	if (r == NULL) // 此種情況認為插在隊尾
	{
		r = new Node<T>;
		r->m_value = x;
		r->pNextNode = NULL;
		prev->pNextNode = r;
		return;
	}
	// 如果是在頭結點插入,将頭指針指向這個結點,這個結點下一個為原來的頭指針
	if (r == m_pHead)
	{
		Node<T>* pNode = new Node<T>;
		pNode->m_value = x;
		pNode->pNextNode = r;
		m_pHead = pNode;
		return;
	}

	Node<T>* pNode = new Node<T>;
	pNode->m_value = x;
	pNode->pNextNode = r;
	prev->pNextNode = pNode;
	return;
}

5)擷取指定位置的元素值

template <class T>
T CLinkList<T>::GetLocate(int i)
{
	Node<T>* pNode = m_pHead;
	while (--i && pNode != NULL)
	{
		pNode = pNode->pNextNode;
	}
	if (pNode == NULL)
	{
		CError error("查找位置非法");
		throw error;
	}
	int nValue = pNode->m_value;
	return nValue;
}

6)擷取值為value元素的位置

template <class T>
int CLinkList<T>::GetValue(T value)
{
	int j = 1;
	Node<T>* pNode = m_pHead;
	while ( pNode != NULL )
	{
		if (pNode->m_value == value)
		{
			return j;
		}
		j++;
		pNode = pNode->pNextNode;
	}
	// 沒有找到
	return -1;
}

7)單連結清單周遊輸出

template <class T>
void CLinkList<T>::PrintList()
{
	Node<T>* pNode = m_pHead;
	while (pNode != NULL)
	{
		printf("%d\r\n", pNode->m_value);
		pNode = pNode->pNextNode;
	}
}

8)單連結清單析構釋放記憶體template <class T>

CLinkList<T>::~CLinkList()

{

Node<T>* pNode = m_pHead;

while (pNode != NULL)

{

Node<T>* r = pNode;

pNode = pNode->pNextNode;

delete r;

}

m_pHead = NULL;

}9)單連結清單逆序

template <class T>
void CLinkList<T>::Reverse()
{
	Node<T>* pPrev = NULL;
	Node<T>* pCur = m_pHead;
	while(pCur!=NULL && pCur->pNextNode != NULL)
	{
		Node<T>* next = pCur->pNextNode;
		pCur->pNextNode = pPrev;
		pPrev = pCur;
		pCur = next;
	}
	pCur->pNextNode = pPrev;
	m_pHead = pCur;
}

10)使單連結清單形成環,為了解決一些環形連結清單的問題。但是将連結清單轉換為環後,關于單連結清單尾指針後繼結點為NULL的判斷将不成立,

是以一些插入,删除等方法将不能是用，必須注意!!!

<pre name="code" class="cpp">template <class T>
void CLinkList<T>::Ring()
{
	if (m_pHead == NULL)
	{
		return;
	}
	// 找到尾結點
	Node<T>* r = m_pHead;
	while (r->pNextNode != NULL)
	{
		r = r->pNextNode;
	}
	// 找到了尾結點,使其指向頭結點
	r->pNextNode = m_pHead;
}

11)友元函數實作一進制多項式求和

一個單連結清單的實際應用,一進制多項式求和.(這個有點問題,以後有機會再修改,大緻思路是這樣的)
<pre name="code" class="cpp">void Add(CLinkList<elem> & A, CLinkList<elem>& B)
{
	Node<elem>* pa = A.m_pHead;
	Node<elem>* pb = B.m_pHead;
	Node<elem>* pPrevA = NULL;
	Node<elem>* pPrevB = NULL;
	while (pa != NULL && pb != NULL)
	{
		// 如果A系數大于B, 将B元素插入到A目前元素的前邊
		if (pa->m_value.exp > pb->m_value.exp)
		{
			Node<elem>* r = new Node<elem>;
			r->m_value.coef = pb->m_value.coef;
			r->m_value.exp = pb->m_value.exp;
			if (pa == A.m_pHead) // 頭結點之前插入,要改變頭指針
			{
				r->pNextNode = pa;
				A.m_pHead = r;
				pPrevA = r;
				pPrevB = pb;
				pb = pb->pNextNode;
			}else // 如果不是頭指針
			{
				r->pNextNode = pa;
				pPrevA->pNextNode = r;
				pPrevA = r;
				pPrevB = pb;
				pb = pb->pNextNode;
			}
			// 将b元素删除
			if (pb == B.m_pHead )
			{
				Node<elem>* s = pb;
				pb = pb->pNextNode;
				B.m_pHead = pb;
				pPrevB = NULL;
				delete s;
			}else
			{
				Node<elem>* s = pb;
				pb = pb->pNextNode;
				pPrevB->pNextNode = pb;
				delete s;
			}

		}else if (pa->m_value.exp < pb->m_value.exp) // 如果A系數小于B,比較A下一個元素
		{
			pPrevA = pa;
			pa = pa->pNextNode;
		}else // 如果相等,求和
		{
			pa->m_value.coef += pb->m_value.coef;
			if (pa->m_value.coef == 0) // 如果系數為0,删除pa目前元素
			{
				if (pa == A.m_pHead)  
				{
					A.m_pHead = pa->pNextNode;
					Node<elem>* s = pa;
					pa = pa->pNextNode;
					pPrevB = pb;
					pb = pb->pNextNode;
					delete s;
				}else
				{
					pPrevA->pNextNode = pa->pNextNode;
					pPrevA = pa;
					Node<elem>* s = pa;
					pa = pa->pNextNode;
					pPrevB = pb;
					pb = pb->pNextNode;
					delete s;
				}
			}else 
			{
				pPrevA = pa;
				pPrevB = pb;
				pa = pa->pNextNode;
				pb = pb->pNextNode;
			}
		}
	}
	if (pb != NULL)
	{
		pPrevA->pNextNode = pb;
	}
}

12)約瑟夫環問題

void Circle(int n, int m)
{
	CLinkList<int> MyLinkList;
	for (int i = 1; i<=n; i++)
	{
		MyLinkList.Insert(i, i);
	}
	printf("報數:");
	MyLinkList.PrintList();
	// 環
	MyLinkList.Ring();
	printf("報%d出圈,出圈次序:", m);
	int k = m;
	Node<int>* pWork = MyLinkList.m_pHead;
	Node<int>* pPrev = pWork;
	for (int i = 0; i<n; i++)
	{
		while (--k)
		{
			pPrev = pWork;
			pWork = pWork->pNextNode;
		}
		k = m;
		printf("出圈%d, ", pWork->m_value);
		Node<int>* s = pWork;
		pPrev->pNextNode = pWork->pNextNode;
		pWork = pWork->pNextNode;
		delete s;
	}
	MyLinkList.m_pHead = NULL;
}

注:紅色功能是複雜的功能,不是單連結清單的必有實作.

單連結清單是鍊式存儲結構,為了查找第i個元素,必須先找到i-1個元素.不同于順序表的随機存取結構.

下面是百度轉載的一份關于順序表和單連結清單的比較:

在C++ STL中vector和list的實作,類似于順序表和單連結清單,兩種結構什麼情況使用也可以參照下面的比較.

順序表與連結清單的比較

一、順序表的特點是邏輯上相鄰的資料元素，實體存儲位置也相鄰，并且，順序表的存儲空間需要預先配置設定。

它的優點是：

　　（1）方法簡單，各種進階語言中都有數組，容易實作。

　　（2）不用為表示節點間的邏輯關系而增加額外的存儲開銷。

　　（3）順序表具有按元素序号随機通路的特點。

缺點：

　　（1）在順序表中做插入、删除操作時，平均移動表中的一半元素，是以對n較大的順序表效率低。

　　（2）需要預先配置設定足夠大的存儲空間，估計過大，可能會導緻順序表後部大量閑置；預先配置設定過小，又會造成溢出。

二、在連結清單中邏輯上相鄰的資料元素，實體存儲位置不一定相鄰，它使用指針實作元素之間的邏輯關系。并且，連結清單的存儲空間是動态配置設定的。

連結清單的最大特點是：

　　插入、删除運算友善。

缺點：

　　（1）要占用額外的存儲空間存儲元素之間的關系，存儲密度降低。存儲密度是指一個節點中資料元素所占的存儲單元和整個節點所占的存儲單元之比。

　　（2）連結清單不是一種随機存儲結構，不能随機存取元素。

三、順序表與連結清單的優缺點切好相反，那麼在實踐應用中怎樣選取存儲結構呢？通常有以下幾點考慮：

　　（1）順序表的存儲空間是靜态配置設定的，在程式執行之前必須明确規定它的存儲規模，也就是說事先對“MaxSize”要有合适的設定，設定過大會造成存儲空間的浪費，過小造成溢出。是以，當對線性表的長度或存儲規模難以估計時，不宜采用順序表。然而，連結清單的動态配置設定則可以克服這個缺點。連結清單不需要預留存儲空間，也不需要知道表長如何變化，隻要記憶體空間尚有空閑，就可以再程式運作時随時地動态配置設定空間，不需要時還可以動态回收。是以，當線性表的長度變化較大或者難以估計其存儲規模時，宜采用動态連結清單作為存儲結構。

　　但在連結清單中，除資料域外海需要在每個節點上附加指針。如果節點的資料占據的空間小，則連結清單的結構性開銷就占去了整個存儲空間的大部分。當順序表被填滿時，則沒有結構開銷。在這種情況下，順序表的空間效率更高。由于設定指針域額外地開銷了一定的存儲空間，從存儲密度的角度來講，連結清單的存儲密度小于1.是以，當線性表的長度變化不大而且事先容易确定其大小時，為節省存儲空間，則采用順序表作為存儲結構比較适宜。

　　（2）基于運算的考慮（時間）

　　順序存儲是一種随機存取的結構，而連結清單則是一種順序存取結構，是以它們對各種操作有完全不同的算法和時間複雜度。例如，要查找線性表中的第i個元素，對于順序表可以直接計算出a(i)的的位址，不用去查找，其時間複雜度為0(1).而連結清單必須從連結清單頭開始，依次向後查找，平均需要0(n)的時間。是以，如果經常做的運算是按序号通路資料元素，顯然順表優于連結清單。

　　反之，在順序表中做插入，删除時平均移動表中一半的元素，當資料元素的資訊量較大而且表比較長時，這一點是不應忽視的；在連結清單中作插入、删除，雖然要找插入位置，但操作是比較操作，從這個角度考慮顯然後者優于前者。

　　（3）基于環境的考慮（語言）

　　順序表容易實作，任何進階語言中都有數組類型；連結清單的操作是基于指針的。相對來講前者簡單些，也使用者考慮的一個因素。

　　總之，兩種存儲結構各有長短，選擇哪一種由實際問題中的主要因素決定。通常“較穩定”的線性表，即主要操作是查找操作的線性表，适于選擇順序存儲；而頻繁做插入删除運算的（即動态性比較強）的線性表适宜選擇鍊式存儲。

線性表之單連結清單的c++實作

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器