首页 > 代码库 > 单链表
单链表
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 =http://www.mamicode.com/=>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 =http://www.mamicode.com/=>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; } |
运行结果: |
单链表