轉載自：http://blog.csdn.net/itcastcpp/article/details/39081953

為了加深對模板的理解，我們今天一起用模板寫一個單鏈表，希望通過這個例子，能夠幫助大家加深對模板的體會，具體如下：

SList.hpp內容：

[cpp]?view plain?copy

#ifndef?_SLIST_H_??

#define?_SLIST_H_??

#include?<iostream>??

using?namespace?std;??

template<typename?T>??

struct?Node??

{??

????T?m_Data;??

????Node<T>?*?m_pNext;??

????Node()??

????{??

????????m_pNext?=?NULL;??

????}??

};??

template<typename?T>??

class?CSList??

{??

public:??

????CSList();??

????~CSList();??

????//尾插法??

????bool?AppendNode(T?Data);??

????//刪除??

????bool?DelNode(T?Key);??

????//修改??

????bool?ModNode(T?Key,?T?New);??

????//查找??

????bool?FindNode(T?Key);??

????//逆序??

????bool?Reverse();???

????//打印??

????void?Print();??

????//銷毀??

????void?Clear();??

private:??

????Node<T>?*?m_pFirst;??

};??

template<typename?T>??

CSList<T>::CSList()??

{??

????m_pFirst?=?NULL;??

}??

template<typename?T>??

CSList<T>::~CSList()??

{??

????Node<T>?*?pCurNode?=?NULL;??

????pCurNode?=?m_pFirst;??

????while?(pCurNode)??

????{??

????????m_pFirst?=?m_pFirst->m_pNext;??

????????delete?pCurNode;??

????????pCurNode?=?m_pFirst;??

????}??

}??

//尾插法??

template<typename?T>??

bool?CSList<T>::AppendNode(T?Data)??

{??

????Node<T>?*?pNewNode?=?new?Node<T>;??

????Node<T>?*?pCurNode?=?NULL;??

????if?(!pNewNode)??

????????return?false;??

????pNewNode->m_Data?=?Data;??

????pNewNode->m_pNext?=?NULL;??

????if?(!m_pFirst)??

????{??

????????m_pFirst?=?pNewNode;??

????????return?true;??

????}??

????pCurNode?=?m_pFirst;??

????while?(pCurNode->m_pNext)??

????{??

????????pCurNode?=?pCurNode->m_pNext;??

????}??

????pCurNode->m_pNext?=?pNewNode;??

????return?true;??

}??

//刪除??

template<typename?T>??

bool?CSList<T>::DelNode(T?Key)??

{??

????Node<T>?*?pPrevNode?=?NULL;??

????Node<T>?*?pCurNode?=?NULL;??

????if?(!m_pFirst)??

????????return?false;??

????if?(m_pFirst->m_Data?==?Key)??

????{??

????????pCurNode?=?m_pFirst;??

????????m_pFirst?=?m_pFirst->m_pNext;??

????????delete?pCurNode;??

????????pCurNode?=?NULL;??

????????return?true;??

????}??

????pPrevNode?=?m_pFirst;??

????pCurNode?=?m_pFirst->m_pNext;??

????while?(pCurNode->m_Data)??

????{??

????????if?(pCurNode->m_Data?==?Key)??

????????{??

????????????pPrevNode->m_pNext?=?pCurNode->m_pNext;??

????????????delete?pCurNode;??

????????????return?true;??

????????}??

????????pPrevNode?=?pCurNode;??

????????pCurNode?=?pCurNode->m_pNext;??

????}??

????return?false;??

}??

//修改??

template<typename?T>??

bool?CSList<T>::ModNode(T?Key,?T?New)??

{??

????Node<T>?*?pCurNode?=?NULL;??

????if?(!m_pFirst)??

????????return?false;??

????pCurNode?=?m_pFirst;??

????while?(pCurNode)??

????{??

????????if?(pCurNode->m_Data?==?Key)??

????????{??

????????????pCurNode->m_Data?=?New;??

????????????return?true;??

????????}??

????????pCurNode?=?pCurNode->m_pNext;??

????}??

????return?false;??

}??

//查找??

template<typename?T>??

bool?CSList<T>::FindNode(T?Key)??

{??

????Node<T>?*?pCurNode?=?NULL;??

????if?(!m_pFirst)??

????????return?false;??

????pCurNode?=?m_pFirst;??

????while?(pCurNode)??

????{??

????????if?(pCurNode->m_Data?==?Key)??

????????????return?true;??

????????pCurNode?=?pCurNode->m_pNext;??

????}??

????return?false;??

}??

//逆序??

template<typename?T>??

bool?CSList<T>::Reverse()??

{??

????Node<T>?*?pPrevNode?=?NULL;??

????Node<T>?*?pCurNode?=?m_pFirst;??

????Node<T>?*?pNext?=?NULL;??

????while?(pCurNode)??

????{??

????????pNext?=?pCurNode->m_pNext;??

????????pCurNode->m_pNext?=?pPrevNode;??

????????pPrevNode?=?pCurNode;??

????????pCurNode?=?pNext;?????????

????}??

????m_pFirst?=?pPrevNode;??

????return?true;??

}??

??

template<typename?T>??

void?CSList<T>::Print()??

{??

????Node<T>?*?pCurNode?=?m_pFirst;??

????while?(pCurNode)??

????{??

????????cout?<<?pCurNode->m_Data?<<?"\t";??

????????pCurNode?=?pCurNode->m_pNext;??

????}??

????cout?<<?endl;??

}??

template<typename?T>??

void?CSList<T>::Clear()??

{??

????Node<T>?*?pCurNode?=?NULL;??

????pCurNode?=?m_pFirst;??

????while?(pCurNode)??

????{??

????????m_pFirst?=?m_pFirst->m_pNext;??

????????delete?pCurNode;??

????????pCurNode?=?m_pFirst;??

????}??

}??

#endif??

main.cpp的內容：

[cpp]?view plain?copy

#define?CRTDBG_MAP_ALLOC????

#include?<stdlib.h>????

#include?<crtdbg.h>????

#include?"SList.hpp"??

??

void?main()??

{??

????CSList<int>?IntList;??

????IntList.AppendNode(1);??

????IntList.AppendNode(7);??

????IntList.AppendNode(4);??

????IntList.AppendNode(2);??

????IntList.AppendNode(8);??

????IntList.AppendNode(5);??

????IntList.AppendNode(9);??

????IntList.AppendNode(6);??

????IntList.AppendNode(3);??

????IntList.Print();??

????IntList.Reverse();??

????IntList.Print();??

????IntList.DelNode(3);??

????IntList.DelNode(1);??

????IntList.DelNode(2);??

????IntList.Print();??

????if?(IntList.FindNode(6)?==?true)??

????{??

????????cout?<<?"find"?<<?endl;??

????}??

????else??

????{??

????????cout?<<?"not?find"?<<?endl;??

????}??

????if?(IntList.FindNode(7)?==?true)??

????{??

????????cout?<<?"find"?<<?endl;??

????}??

????else??

????{??

????????cout?<<?"not?find"?<<?endl;??

????}??

????if?(IntList.FindNode(5)?==?true)??

????{??

????????cout?<<?"find"?<<?endl;??

????}??

????else??

????{??

????????cout?<<?"not?find"?<<?endl;??

????}??

????if?(IntList.FindNode(100)?==?true)??

????{??

????????cout?<<?"find"?<<?endl;??

????}??

????else??

????{??

????????cout?<<?"not?find"?<<?endl;??

????}??

????IntList.ModNode(6,?66);??

????IntList.ModNode(7,?77);??

????IntList.ModNode(5,?55);??

????IntList.Print();??

????IntList.Clear();??

????_CrtDumpMemoryLeaks();??

????system("pause");??

}??

運行效果如圖1所示：

圖1 運行效果圖

??? 從今天開始，我們以實踐的方式，幫助大家加深對模板的理解。

總結

以上是生活随笔為你收集整理的用模板写单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。