5.单链表.docx

ListNode.h
#ifndef __ListNode_H__
#define __ListNode_H__

template<typename Type>
class SingleList;

template<typename Type>
class ListNode{
private:
friend typename SingleList < Type >;

ListNode() :m_pnext(NULL){}

ListNode(const Type item, ListNode<Type> *next = NULL)
:m_data(item), m_pnext(next){}
~ListNode(){
m_pnext = NULL;
}

public:
Type GetData();
friend ostream& operator<< <Type>(ostream&, ListNode<Type>&);

private:
Type m_data;
ListNode *m_pnext;
};

template<typename Type>
Type ListNode<Type>::GetData(){
return this->m_data;
}

template<typename Type>
ostream& operator<<(ostream& os, ListNode<Type>& out){
os << out.m_data;
return os;
}

#endif
SingleList.h
#ifndef __SingleList_H__
#define __SingleList_H__
#include "ListNode.h"

template<typename Type>
class SingleList{
public:
SingleList() :head(new ListNode<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<typename Type>
void SingleList<Type>::MakeEmpty(){
ListNode<Type> *pdel;
while (head->m_pnext != NULL){
pdel = head->m_pnext;
head->m_pnext = pdel->m_pnext;
delete pdel;
}
}

//求链表的长度
template<typename Type>
int SingleList<Type>::Length(){
ListNode<Type> *pmove = head->m_pnext;
int count = 0;
while (pmove != NULL){
pmove = pmove->m_pnext;
count++;
}
return count;
}

//查找第n个元素
template<typename Type>
ListNode<Type>* SingleList<Type>::Find(int n){
if (n < 0){
cout << "The n is out of boundary" << endl;
return NULL;
}
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;
return NULL;
}
return pmove;
}

template<typename Type>
ListNode<Type>* SingleList<Type>::Find(Type value, int n){
if (n < 1){
cout << "The n is illegal" << endl;
return NULL;
}
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;
return NULL;
}
return pmove;
}

template<typename Type>
bool SingleList<Type>::Insert(Type item, int n){
if (n < 0){
cout << "The n is illegal" << endl;
return 0;
}
ListNode<Type> *pmove = head;
ListNode<Type> *pnode = new ListNode<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<typename Type>
bool SingleList<Type>::RemoveAll(Type item){
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<typename Type>
Type SingleList<Type>::Remove(int n){
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<typename Type>
Type SingleList<Type>::Get(int n){
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<typename Type>
void SingleList<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>
using namespace 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;
}
运行结果: