線性表--單鏈表(C++)-創(chuàng)新互聯(lián)

單鏈表演示圖：

創(chuàng)新互聯(lián)公司于2013年成立，先為五家渠等服務(wù)建站，五家渠等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為五家渠企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

線性表--單鏈表(C++)

單鏈表結(jié)構(gòu)體：

struct Node
{
	Node(const DataType& d)//節(jié)點的構(gòu)造函數(shù)
	:_data(d)
	,_next(NULL)
	{}
	DataType _data;        //數(shù)據(jù)  
	struct Node *_next;    //指向下一個節(jié)點的指針
};

帶頭結(jié)點和尾節(jié)點的單鏈表：

線性表--單鏈表(C++)

多一個Tail指針的好處就是很方便可以找到鏈表尾部，方便在尾部插入一個元素什么的。

下面我們用類來實現(xiàn)單鏈表：

class SList
{
	friend ostream& operator<<(ostream& os, const SList& s);  //輸出運算符重載(友元)
public:
	SList()                           //構(gòu)造函數(shù)
		:_head(NULL)
		,_tail(NULL)
	{}
	SList(const SList& s)             //拷貝構(gòu)造
		:_head(NULL)
		, _tail(NULL)
	{
		Node *cur = _head;
		while (cur)
		{
			PushBack(cur->_data );
			cur = cur->_next;
		}
		_tail = cur;
	}
	~SList()                           //析構(gòu)函數(shù)
	{
		if (_head == NULL)
			return;
		Node *cur = _head;
		if (cur != NULL)
		{
			Node *del = cur;
			cur = cur->_next;
			delete del;
		}
		_tail = NULL;
		_head = NULL;
	}

	SList& operator=(SList s)           //賦值運算符重載
	{
		swap(_head, s._head);
		swap(_tail, s._tail);
		return *this;
	}

單鏈表最基本的四個函數(shù)：

void SList::PushBack(const DataType& d)   //尾插
{
	Node *newNode = new Node(d);      //構(gòu)建一個新的節(jié)點
	if (_head == NULL)
	{
		_head = newNode;
		_tail = newNode;
	}
	else
	{
		_tail->_next = newNode;
		_tail = newNode;
	}
}
void SList::PushFront(const DataType& d)   //頭插
{
	Node *newNode = new Node(d);
	if (_head == NULL)
	{
		_head = newNode;
		_tail = newNode;
	}
	else
	{
		newNode->_next = _head;
		_head = newNode;
	}
}
void SList::PopBack()                     //尾刪
{
	if (_head == NULL)
		return;
	else if (_head == _tail)
	{
		delete _tail;
		_tail = NULL;
		_head = NULL;
	}
	else
	{
		Node *cur = _head;
		while (cur->_next != _tail)
		{
			cur = cur->_next;
		}
		delete _tail;
		_tail = cur;
		_tail->_next = NULL;
	}
}
void SList::PopFront()                  //頭刪
{
	if (_head == NULL)
		return;
	else if (_head == _tail)
	{
		delete _tail;
		_tail = NULL;
		_head = NULL;
	}
	else
	{
		Node *del = _head;
		_head = _head->_next;
		delete del;
	}
}

給一個數(shù)據(jù)，若找到該節(jié)點則返回該節(jié)點，沒找到則返回NULL

Node* SList::Find(const DataType& d)
{
	Node *cur = _head;
	while (cur != NULL)
	{
		if (cur->_data == d)
			return cur;
		cur = cur->_next;
	}
	return NULL;
}

給定一個節(jié)點，在該節(jié)點后插入一個新的節(jié)點

void SList::Insert(Node* pos, const DataType& d)
{
	Node *newNode = new Node(d);
	if (pos == _tail)                    //若給定的節(jié)點是尾節(jié)點，此處可以直接調(diào)用尾插
	{
		_tail->_next = newNode;
		_tail = newNode;
	}
	else
	{
		newNode->_next = pos->_next;
		pos->_next = newNode;
	}
}

鏈表的逆序：此處用三個指針來實現(xiàn)

void SList::Reverse()
{
	Node *p1 = NULL;
	Node *p2 = _head;
	Node *newhead = NULL;
	while (p2)
	{
		p1 = p2;
		p2 = p2->_next;
		p1->_next = newhead;
		newhead = p1;
		
	}
	_head = newhead;
}

鏈表的排序：采用冒泡排序

void SList::Sort()
{
	Node *cur = _head;
	Node *end = NULL;
	while (cur != end)
	{
		while (cur->_next  != end)
		{
			if (cur->_data > cur->_next->_data)
			{
				DataType tmp = cur->_data;
				cur->_data = cur->_next->_data;
				cur->_next->_data = tmp;
			}
          cur = cur->_next;
		}
	  end = cur;
      cur = _head;
	}
}

刪除某個節(jié)點（給定一個數(shù)據(jù)，刪除數(shù)據(jù)與之相等的第一個節(jié)點）

void SList::Remove(const DataType& d)
{
	Node *cur = _head;
	while (cur != NULL)
	{
		if (cur->_data == d)
		{
			Node *del = cur->_next;
			DataType tmp = cur->_data;
			cur->_data = cur->_next->_data;
			cur->_next->_data = tmp;
			cur->_next = cur->_next->_next;
			delete del;
			return;
		}
		cur = cur->_next;
	}
}

刪除某些節(jié)點（給定一個數(shù)據(jù)，刪除數(shù)據(jù)與之相等的每一個節(jié)點）

void SList::RemoveAll(const DataType& d)
{
	Node *cur = _head;
	while (cur != NULL)
	{
		if (cur->_data == d)
		{
			Node *del = cur->_next;
			DataType tmp = cur->_data;
			cur->_data = cur->_next->_data;
			cur->_next->_data = tmp;
			cur->_next = cur->_next->_next;
			delete del;
		}
		cur = cur->_next;
	}
	return;
}

刪除非尾節(jié)點

void SList::EarseNotTail(Node *pos)
{
	Node *del = pos;
	Node *cur = _head;
	while (cur->_next!=pos)     //找到該節(jié)點的前一個節(jié)點
	{
		cur = cur->_next;
	}
	cur->_next = pos->_next;     //讓它的_next指向要刪除節(jié)點的_next
	delete del;
}

找到中間節(jié)點

Node*  SList::FindMinNode()                //快慢指針問題
{                                          //兩個指針都指向頭結(jié)點
	Node *cur = _head;                 //快的一次走兩步，慢的一次走一步
	Node *fast = cur;                  //當(dāng)快指針走到尾的時候，慢指針指向中間節(jié)點
	Node *slow = cur;
	while (fast)
	{
		fast = fast->_next->_next;
		slow = slow->_next;
	}
	return slow;
}

刪除倒數(shù)第K個節(jié)點

void  SList::DelKNode(int k)
{
	Node *cur = _head;
	int i = k - 1;
	while (i)                   //先讓cur指向正數(shù)第K個節(jié)點
	{
		cur = cur->_next;
		i = i - 1;;
	}
	Node *p1 = _head;            
	Node *tmp = NULL;
	while (cur->_next )          //讓一個指向頭結(jié)點的指針和cur一起走
	{
		tmp = p1;
		p1 = p1->_next;
		cur = cur->_next;     //當(dāng)cur指向尾節(jié)點時，那個指針指向倒第K個節(jié)點
	}
	Node *del = p1;
	tmp->_next = p1->_next ;
	delete p1;

}

檢測是否帶環(huán)

//檢測是否帶環(huán)
int  SList::CheckCycle(const SList& s)      //快慢指針問題
{
	Node *fast = _head;
	Node *slow = _head;
	while (slow)
	{
		if (slow == fast)
		{
			return 1;
		}
		fast = fast->_next->_next;
		slow = slow->_next;
	}
	return 0;
}

獲取環(huán)的入口點

Node*  SList::GetCycleEoryNode()
{
	Node *cur = _head;
	while (cur)
	{
		if (cur == _tail)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}

判斷是否相交

int  SList::CheckCross(SList& l1, SList& l2)
{
	int count1 = l1.LengthOfList(l1);
	int count2 = l2.LengthOfList(l2);
	if (count1 > count2)
	{
		Node *cur = l1._head;
		while (cur)
		{
			if (l2._tail == cur)
				return 1;
			cur = cur->_next;
		}
	}
	else
	{
		Node *cur = l2._head;
		while (cur)
		{
			if (l1._tail == cur)
				return 1;
			cur = cur->_next;
		}
	}
	return 0;
}

合并兩個鏈表

int  SList::CheckCross(SList& l1, SList& l2)
{
	int count1 = l1.LengthOfList(l1);
	int count2 = l2.LengthOfList(l2);
	if (count1 > count2)
	{
		Node *cur = l1._head;
		while (cur)
		{
			if (l2._tail == cur)
				return 1;
			cur = cur->_next;
		}
	}
	else
	{
		Node *cur = l2._head;
		while (cur)
		{
			if (l1._tail == cur)
				return 1;
			cur = cur->_next;
		}
	}
	return 0;
}

求兩個鏈表的交點

Node*  SList::GetLinkCross(SList& l1, SList& l2)
{ 
	int count1 = l1.LengthOfList(l1);
	int count2 = l2.LengthOfList(l2);
	Node *cur1 = l1._head;
	Node *cur2 = l2._head;
	if (count1 > count2)
	{
		Node *cur1 = l1._head;
		Node *cur2 = l2._head;
		while (cur2)
		{
			if (cur2->_next  == cur1->_next )
				return cur1;
			else
			{
				cur1 = cur1->_next;
				cur2 = cur2->_next;
			}
		}
	}
	else
	{
		Node *cur1 = l1._head;
		Node *cur2 = l2._head;
		while (cur1)
		{
			if (cur2->_next == cur1->_next)
				return cur1;
			else
			{
				cur1 = cur1->_next;
				cur2 = cur2->_next;
			}
		}
	}
	return NULL;
}

求鏈表長度

int SList::LengthOfList(const SList& s)

{

int length = 0;

Node *cur = _head;

while (cur)

{

length++;

cur = cur->_next;

}

return length;

}

以后會有改進(jìn)版奉上，希望大家多多支持線性表--單鏈表(C++)

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證，機(jī)房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

分享文章：線性表--單鏈表(C++)-創(chuàng)新互聯(lián)
分享路徑：http://www.bm7419.com/article42/cdjehc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、建站公司、服務(wù)器托管、網(wǎng)站排名、手機(jī)網(wǎng)站建設(shè)、自適應(yīng)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容