C++進階學習——單向鏈表的實現

C++進階學習——單向鏈表的實現

示例代碼如下：

#include 
using namespace std;

class Node //節點類
{
public:
	//普通構造函數：無參數，帶1個參數，帶2個參數
	Node(){}
	Node(int n){ num = n; next = NULL; }
	Node(int n, Node *p){ num = n; next = p; }
	
	void setNum(int n = 0) { num = n; }
	int getNum() const { return num; }
	
	void setNext(Node *p = NULL){ next = p; } //設置指針域
	Node *getNext() const { return next; }//獲取指針域
	
private:
	int num;    //數據域
	Node *next; //指針域
};

class Linklist //鏈表類
{
public:
	//構造函數和析構函數
	Linklist(){ head = NULL; }
	Linklist(int n){ head = new Node(n); }
	~Linklist() { clear(); }
	
	void addAtEnd(int n);//往鏈表尾添加節點
	void addAtHead(int n);//往鏈表頭添加節點
	void addByNum(int n);//升序插入節點
	
	void visitAllNode() const;//遍歷所有的節點
	Node *searchByNum(int n) const; //查找值為num的節點
	
	void deleteByNum(int n);//刪除值為n的節點
	void clear();//刪除鏈表所有節點
	
private:
	Node *head;
};

//往鏈表尾添加節點
void Linklist::addAtEnd(int n)  
{
	if(NULL == head)
	{ 
		head = new Node(n);
	}
	else
	{
		Node *temp=head;
		while( temp->getNext() != NULL)
		{ 
			temp = temp->getNext(); //用temp來指向下一個節點
		}
		//執行到這時，說明temp是最後一個節點，temp的下一個節點為NULL
		
		temp->setNext( new Node(n) );//插入節點
	}
 
}

//往鏈表頭添加節點
void Linklist::addAtHead(int n) 
{
	if(NULL == head)
	{ 
		head = new Node(n);
	}
	else
	{
		Node *temp = new Node(n);//待插入的節點
		temp->setNext(head);//temp的下一個節點執行頭
		head = temp; //新節點當做頭結點
	}
 
}

//升序插入節點
void Linklist::addByNum(int n)
{
	if(NULL == head)//頭結點為NULL
	{
		head = new Node(n);
	}
	else
	{
		Node *pf, *pb; //pf前一個結點， pb為後一個節點
		pf = pb = head;
		while(NULL != pb)
		{
			if(pb->getNum() >= n)//>=升序，<降序
			{
				break;
			}
			pf = pb; //pf保存當前節點
			pb = pb->getNext(); //pb指向下一個節點
		}
		
		if(NULL == pb)//尾結點
		{
			pf->setNext( new Node(n) );//插入節點
		}
		else
		{
			Node *temp = new Node(n);//待插入的節點
			
			if(pb == head) //頭節點
			{
				temp->setNext(head);//temp的下一個節點執行頭
				head = temp; //新節點當做頭結點
			}
			else //中間
			{
				pf->setNext(temp);
				temp->setNext(pb);
			}
			
		}
			
	}
}

//遍歷所有的節點
void Linklist::visitAllNode() const
{
	if(NULL == head)
	{
		cout<<空鏈表!<getNum()<< --> ;
			temp=temp->getNext();
		}
		cout << NULL << endl;
	}
}

//查找值為num的節點
Node * Linklist::searchByNum(int n) const
{
	Node *temp = head;
	while(temp != NULL)
	{
		if(temp->getNum() == n)
		{
			return temp;
		}
		
		temp = temp->getNext();
	}
	
	return NULL;
}

//刪除節點
void Linklist::deleteByNum(int n) 
{
	Node *pf, *pb;
	pf = pb = head;
	
	while(NULL != pb)
	{
		if(pb->getNum() == n)
		{
			break;
		}
		pf = pb;
		pb = pb->getNext();
	}
	
	if(NULL == pb)
	{
		cout << n << :此值不存在 << endl;
	}
	else
	{
		//頭結點
		if(pb == head)
		{
			pf = head->getNext();
			delete head;
			head = pf;
		}
		else
		{
			pf->setNext( pb->getNext() );
			delete pb;
		}
	}	
}

//刪除鏈表所有節點
void Linklist::clear()
{
	Node *temp = NULL;
	temp = head; //用一個臨時節點保存頭結點

    //遍歷鏈表，每次先保存頭結點的next結點，然後刪除頭結點
    while (NULL != temp)
    {
        temp = head->getNext();//先保存頭結點的next結點
        delete head;//刪除頭結點
		head = temp;//之前頭結點的next節點重新作為head
    }
	
	cout << 鏈表已經清空
;
}

int main()
{
	Linklist myList(1); //創建鏈表對象
	
	myList.visitAllNode(); //遍歷所有的節點
	
	cout << endl;
	
	myList.addAtEnd(2); //尾部插入
	myList.addAtHead(0);//頭部插入
	myList.visitAllNode(); //遍歷所有的節點
	
	cout << endl;
	
	for(int i = 3; i < 10; i++)
	{
		myList.addByNum(i); //升序插入節點
	}
	myList.visitAllNode(); //遍歷所有的節點
	
	cout << endl;
	
	Node *temp = myList.searchByNum(5); //查找值為5的節點
	if(NULL != temp)
	{
		cout << 此節點的值為： << temp->getNum() << endl;
	}
	else
	{
		cout << 值為5的節點不存在 << endl;
	}
	
	temp = myList.searchByNum(100); //查找值為100的節點
	if(NULL != temp)
	{
		cout << 此節點的值為： << temp->getNum() << endl;
	}
	else
	{
		cout << 值為100的節點不存在 << endl;
	}
	
	cout << endl;
	
	myList.deleteByNum(5);//刪除值為5的節點
	cout << 刪除值為5的節點：;
	myList.visitAllNode(); //遍歷所有的節點
	
	cout << endl;
	myList.deleteByNum(100);//刪除值為100的節點
	
	cout << endl;
	
	return 0;
}