5.单链表.docx

ListNode.h
#ifndef __ListNode_H__
#define __ListNode_H__

template
class SingleList;

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

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;
}

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

template
class SingleList{
public:
SingleList() :head(new ListNode()){}
~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 *Find(Type value, int n);
//find the nth data
ListNode *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 *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 < n&&pmove; i++){
pmove = pmove->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 << "can't 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 < 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
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 << "can't find the element" << endl;
exit(1);
}
ListNode *pmove = head, *pdel;
for (int i = 0; i < npmove->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;
}

//获得第那个元素
templateype>
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 < n; i++){
pmove = pmove->m_pnext;
if (NULL == pmove){
cout << "The n is out of boundary" << endl;
exit(1)
}
}
return pmove->m_data;
}

template
void SingleList::Print(){
ListNode *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
using namespace std;

#include "SingleList.h"

int 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;
}
运行结果: