ListNode.h |
#ifndef __ListNode_H__ #define __ListNode_H__
template<typenameType> classSingleList;
template<typenameType> classListNode{ private: friendtypenameSingleList < Type >;
ListNode() :m_pnext(NULL){}
ListNode(constTypeitem, ListNode<Type> *next = NULL) :m_data(item), m_pnext(next){} ~ListNode(){ m_pnext = NULL; }
public: Type GetData(); friendostream& operator<< <Type>(ostream&, ListNode<Type>&);
private: Type m_data; ListNode *m_pnext; };
template<typenameType> TypeListNode<Type>::GetData(){ returnthis->m_data; }
template<typenameType> ostream& operator<<(ostream& os, ListNode<Type>& out){ os << out.m_data; returnos; }
#endif |
SingleList.h |
#ifndef __SingleList_H__ #define__SingleList_H__ #include"ListNode.h"
template<typenameType> classSingleList{ public: SingleList() :head(newListNode<Type>()){} ~SingleList(){ MakeEmpty(); delete head; }
public: //make the list empty void MakeEmpty(); //get the length int Length(); //find thd nth data which is equal to value ListNode<Type> *Find(Type value, int n); //find the nth data ListNode<Type> *Find(int n); //insert the data in the nth position bool Insert(Type item, int n = 0); //remove the nth data Type Remove(int n = 0); //remove all the data which is equal to item bool RemoveAll(Type item); //get the nth data Type Get(int n); //print the list void Print();
private: ListNode<Type> *head; };
//清空链表 template<typenameType> voidSingleList<Type>::MakeEmpty(){ ListNode<Type> *pdel; while (head->m_pnext != NULL){ pdel = head->m_pnext; head->m_pnext = pdel->m_pnext; delete pdel; } }
//求链表的长度 template<typenameType> intSingleList<Type>::Length(){ ListNode<Type> *pmove = head->m_pnext; int count = 0; while (pmove != NULL){ pmove = pmove->m_pnext; count++; } return count; }
//查找第n个元素 template<typenameType> ListNode<Type>* SingleList<Type>::Find(intn){ if (n < 0){ cout << "The n is out of boundary" << endl; returnNULL; } ListNode<Type> *pmove = head->m_pnext; for (int i = 0; i < n&&pmove; i++){ pmove = pmove->m_pnext; } if (pmove == NULL){ cout << "The n is out of boundary" << endl; returnNULL; } return pmove; }
template<typenameType> ListNode<Type>* SingleList<Type>::Find(Typevalue, intn){ if (n < 1){ cout << "The n is illegal" << endl; returnNULL; } ListNode<Type> *pmove = head; int count = 0; while (count != n&&pmove){ pmove = pmove->m_pnext; if (pmove->m_data == value){ count++; } } if (pmove == NULL){ cout << "can't find the element" << endl; returnNULL; } return pmove; }
template<typenameType> boolSingleList<Type>::Insert(Typeitem, intn){ if (n < 0){ cout << "The n is illegal" << endl; return 0; } ListNode<Type> *pmove = head; ListNode<Type> *pnode = newListNode<Type>(item); if (pnode == NULL){ cout << "Application error!" << endl; return 0; } for (int i = 0; i < n&&pmove; i++){ pmove = pmove->m_pnext; } if (pmove == NULL){ cout << "the n is illegal" << endl; return 0; } pnode->m_pnext = pmove->m_pnext; pmove->m_pnext = pnode; return 1; }
//删除所有 template<typenameType> boolSingleList<Type>::RemoveAll(Typeitem){ ListNode<Type> *pmove = head; ListNode<Type> *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<typenameType> TypeSingleList<Type>::Remove(intn){ if (n < 0){ cout << "can't find the element" << endl; exit(1); } ListNode<Type> *pmove = head, *pdel; for (int i = 0; i < n&&pmove->m_pnext; i++){ pmove = pmove->m_pnext; } if (pmove->m_pnext == NULL){ cout << "can't find the element" << endl; exit(1); } pdel = pmove->m_pnext; pmove->m_pnext = pdel->m_pnext; Type temp = pdel->m_data; delete pdel; return temp; }
//获得第那个元素 template<typenameType> TypeSingleList<Type>::Get(intn){ if (n < 0){ cout << "The n is out of boundary" << endl; exit(1); } ListNode<Type> *pmove = head->m_pnext; for (int i = 0; i < n; i++){ pmove = pmove->m_pnext; if (NULL == pmove){ cout << "The n is out of boundary" << endl; exit(1); } } return pmove->m_data; }
template<typenameType> voidSingleList<Type>::Print(){ ListNode<Type> *pmove = head->m_pnext; cout << "head"; while (pmove){ cout << "--->" << pmove->m_data; pmove = pmove->m_pnext; } cout << "--->over" << endl << endl << endl; } #endif |
Test.cpp |
#include<iostream> usingnamespace std;
#include"SingleList.h"
int main() { SingleList<int> 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; } |
运行结果:
|
