程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 單鏈表的c++實現,使用模板

單鏈表的c++實現,使用模板

編輯:關於C++

節點的構造

 

#include
using namespace std;

template
class list;

template
class list_node
{
	friend class list<_Ty>;
public:
	list_node():next(NULL)
	{}
	list_node(const _Ty item, list_node<_Ty>* tail=NULL):data(item),next(tail)
	{}
	~list_node()
	{}
private:
	_Ty data;
	list_node *next;
};

//list方法實現

 

 

#include "list_node.h"

template
class list
{
public:
	list():head(new list_node<_Ty>())
	{
	}
	~list()
	{
		delete head;
	}
public:
	void Insert(const _Ty x,int i)//將數據x插入到位置i之後
	{
		list_node<_Ty> *phead = head;
		list_node<_Ty> *p = new list_node<_Ty>(x);
		while(--i && phead)
		{
			phead = phead->next;
		}
		p->data = x;
		p->next = phead->next;
		phead->next = p;	
	}
	void Show()const
	{
		list_node<_Ty> *phead = head->next;
		while(phead != NULL)
		{	
			cout<data<<"->";
			phead = phead->next;
		}
		cout< *p = head->next;
		while(--i)
		{
			p = p->next;
		}
		return p->data;
	}
	_Ty Remove(int i)  //刪除i位置的節點,返回被刪除節點的data。
	{
		list_node<_Ty>* p = head;
		list_node<_Ty> *q;
		while(--i && p)
		{
			p = p->next;
		}
		q = p->next;
		p->next = q->next;
		_Ty tmp = q->data;
		delete q;
		return tmp;
	}
	void RemoveAll(_Ty item)  //刪除所有p->data==item的節點
	{
		list_node<_Ty> *p = head->next;
		int i = 1;
		while(p != NULL)
		{
			if(p->data == item)
			{
				p = p->next;  //記錄p的下一個節點,下次從p->next處開始查詢
				Remove(i);
			}			
			else
			{
				i++;
				p = p->next;
			}
		}
	}
	void Clear()
	{
		list_node<_Ty>* p = head->next;
		while(p != NULL)
		{
			p = p->next;
			Remove(1);
		}
	}
	size_t size()const  //不加head節點
	{
		int i = 0;
		list_node<_Ty> *p = head->next;
		while(p != NULL)
		{
			i++;
			p = p->next;
		}
		return i;
	}
private:
	list_node<_Ty> *head;
};

 

//測試實例

 

#include "list.h"

void main()
{
	list st;
	for(int i=1; i<10; ++i)
		st.Insert(i,i);
//	st.Insert(5,5);
//	st.Insert(2,2);
//	st.Show();
//	st.Remove(2);
//	st.Show();
//	st.RemoveAll(2);
	cout<

面試寶典中---查找單鏈表的倒數第K個元素

 

實現思路主要有三個:

1、使用兩個指針fast和slow遍歷,讓fast先遍歷K個節點,此時fast和slow同時遍歷,當fast遍歷到NULL節點時,即為所求 --->(此方法只遍歷一次)

 

_Ty Find2(int K)
{
	list_node<_Ty> *fast = head->next;
	list_node<_Ty> *slow = head->next;
	while(K--)
	{
		fast = fast->next;
	}
	while(fast != NULL)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->data;
}
2、首先遍歷所有節點統計節點個數size,要查找倒數第K個元素,即為查找正數第size-K+1個元素。在重新遍歷到suze-K+1位置處即可。

 

 

_Ty Find(int K) //找出倒數第K個元素
{
	list_node<_Ty> *p = head->next;
	int i = 1;
	while(p->next != NULL)
	{
		i++;  //統計總的元素個數
		p = p->next;
	}  
	int j = i-K+1;  //相當於查找第j個元素
	p = head->next;
	while(--j && p!=NULL)
	{
		p = p->next;
	}
	return p->data;
}
3、使用兩個指針,一個負責遍歷,一個記錄遍歷前節點的指針;首先遍歷K個節點,判斷當前節點是否為空,

 

若為空,則說明遍歷前節點(即首節點為所求);若不為空,記錄指針指向下一個節點,賦給遍歷指針,遍歷指針繼續遍歷K個節點,依次類推...

_Ty Find3(int K)
{
	list_node<_Ty> *p = head->next;
	list_node<_Ty> *q = head->next;
	while(p != NULL)
	{
		while(K--)
		{
			p = p->next;
		}
		if(p == NULL)
			return q;
		else
		{
			q = q->next;
			p = q;
		}		
	}	
}


 



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved