5.单链表.docx

ListNode.h#ifndef _ListNode_H_#define _ListNode_H_templateclass SingleList;template class ListNodeprivate:friend typename SingleList ;ListNode() :m_pnext(NULL)ListNode(const Type item, ListNode *next = NULL) :m_data(item), m_pnext(next)ListNode()m_pnext = NULL;public:Type GetData();friend ostream& operator (ostream&, ListNode&);private:Type m_data;ListNode *m_pnext;template Type ListNode:GetData()return this-m_data;template ostream& operator(ostream& os, ListNode& out)os out.m_data;return os;#endifSingleList.h#ifndef _SingleList_H_#define _SingleList_H_#include ListNode.htemplateclass SingleListpublic:SingleList() :head(new ListNode()SingleList()MakeEmpty();delete head;public:/make the list emptyvoid MakeEmpty(); /get the lengthint Length(); /find thd nth data which is equal to valueListNode *Find(Type value, int n);/find the nth dataListNode *Find(int n);/insert the data in the nth positionbool Insert(Type item, int n = 0);/remove the nth dataType Remove(int n = 0);/remove all the data which is equal to itembool RemoveAll(Type item);/get the nth dataType Get(int n);/print the listvoid Print();private:ListNode *head;/清空链表template void SingleList:MakeEmpty()ListNode *pdel;while (head-m_pnext != NULL)pdel = head-m_pnext;head-m_pnext = pdel-m_pnext;delete pdel;/求链表的长度template int SingleList:Length()ListNode *pmove = head-m_pnext;int count = 0;while (pmove != NULL)pmove = pmove-m_pnext;count+;return count;/查找第n个元素template ListNode* SingleList:Find(int n)if (n 0)cout The n is out of boundary endl;return NULL;ListNode *pmove = head-m_pnext;for (int i = 0; i m_pnext;if (pmove = NULL)cout The n is out of boundary endl;return NULL;return pmove;template ListNode* SingleList:Find(Type value, int n)if (n 1)cout The n is illegal endl;return NULL;ListNode *pmove = head;int count = 0;while (count != n&pmove)pmove = pmove-m_pnext;if (pmove-m_data = value)count+;if (pmove = NULL)cout cant find the element endl;return NULL;return pmove;template bool SingleList:Insert(Type item, int n)if (n 0)cout The n is illegal endl;return 0;ListNode *pmove = head;ListNode *pnode = new ListNode(item);if (pnode = NULL)cout Application error! endl;return 0;for (int i = 0; i m_pnext;if (pmove = NULL)cout the n is illegal m_pnext = pmove-m_pnext;pmove-m_pnext = pnode;return 1;/删除所有template bool SingleList:RemoveAll(Type item)ListNode *pmove = head;ListNode *pdel = head-m_pnext;while (pdel != NULL)if (pdel-m_data = item)pmove-m_pnext = pdel-m_pnext;delete pdel;pdel = pmove-m_pnext;continue;pmove = pmove-m_pnext;pdel = pdel-m_pnext;return 1;template Type SingleList:Remove(int n)if (n 0)cout cant find the element endl;exit(1);ListNode *pmove = head, *pdel;for (int i = 0; i m_pnext; i+)pmove = pmove-m_pnext;if (pmove-m_pnext = NULL)cout cant find the element m_pnext;pmove-m_pnext = pdel-m_pnext;Type temp = pdel-m_data;delete pdel;return temp;/获得第那个元素template Type SingleList:Get(int n)if (n 0)cout The n is out of boundary endl;exit(1);ListNode *pmove = head-m_pnext;for (int i = 0; i m_pnext;if (NULL = pmove)cout The n is out of boundary m_data;template void SingleList:Print()ListNode *pmove = head-m_pnext;cout head;while (pmove)cout m_data;pmove = pmove-m_pnext;cout over endl endl endl;#endifTest.cpp#include using namespace std;#include SingleList.hint main()SingleList list;for (int i = 0; i 20; i+)list.Insert(i * 3, i);for (int i = 0; i 5; i+)list.Insert(3, i * 3);cout the Length of the list is list.Length() endl;list.Print();list.Remove(5);cout the Length of the list is list.Length() endl;list.Print();list.RemoveAll(3);cout the Length of the list is list.Length() endl;list.Print();cout The third element is list.Get(3) endl;cout *list.Find(18, 1) endl;list.Find(100);list.MakeEmpty();cout the Length of the list is list.Length() endl;list.Print();cin.get();return 0;运行结果: