/***************************************************************************
* file name : LinkList.h
* created : 2011/11/03
* description :
* author : Gavin Dai XLX
* update :
****************************************************************************/
#ifndef __LINKLIST_H
#define __LINKLIST_H
#include <iostream>
using namespace std;
template <class T>
struct LinkNode
{
T data;
LinkNode<T>* link;
LinkNode(LinkNode<T> *ptr = NULL) { link = ptr; }
LinkNode(const T& item, LinkNode<T> *ptr = NULL) { data = item; link = ptr; }
};
template <class T>
class LinkList
{
public:
LinkList() { first = new LinkNode<T>; }//带头结点
LinkList(const T& x) { first = new LinkNode<T>(x); }//带头结点,x可是是一些如表长之类的信息
LinkList(const LinkList<T>& list);
~LinkList() { makeEmpty(); }
void makeEmpty();
int length()const;
LinkNode<T>* getHead()const { return first; }
LinkNode<T>* search(T x);
LinkNode<T>* locate(int i);
bool getData(int i, T& x)const;
void setData(int i, T& x);
bool insert(int i, T& x);
bool remove(int i, T& x);
bool isEmpty()const { return first->link == NULL ? true : false ; }
bool isFull()const { return false; }
//void input();
void output();
void inputFront(T endTag);
void inputRear(T endTag);
LinkList<T>& operator=(LinkList<T>& list);
private:
LinkNode<T> *first;
};
#endif
/***************************************************************************
* file name : LinkList.cpp
* created : 2011/11/03
* description :
* author : Gavin Dai XLX
* update :
****************************************************************************/
#include "LinkList.h"
template <class T>
void LinkList<T>::makeEmpty()
{
LinkNode<T>* pdel;
while(first->link != NULL)
{
pdel = first->link;
first->link = pdel->link;
delete pdel;
}
}
template <class T>
int LinkList<T>::length() const
{
LinkNode<T>* p = first->link;
int count = 0;
while(p != NULL)
{
p = p->link;
count++;
}
return count;
}
template <class T>
LinkNode<T>* LinkList<T>::search(T x)
{
LinkNode<T>* current = first->link;
while(current != NULL)
{
if (current->data == x)
{
break;
}else
{
current = current->link;
}
}
return current;
}
template <class T>
LinkNode<T>* LinkList<T>::locate(int i)
{
if (i < 0)
{
return NULL;
}
LinkNode<T>* current = first->link;
int k = 0;
while( current != NULL && k < i)
{
current = current->link;
k++;
}
return current;
}
template <class T>
bool LinkList<T>::getData(int i, T &x) const
{
if (i < 0)
{
return false;
}
LinkNode<T>* current = locate(i);
if (current == NULL)
{
return false;
}else
{
x = current->data;
return true;
}
}
template <class T>
void LinkList<T>::setData(int i, T &x)
{
if ( x < 0)
{
return;
}
LinkNode<T>* current = locate(i);
if (current == NULL)
{
return;
}else
{
current->data = x;
}
}
template <class T>
bool LinkList<T>::insert(int i, T &x)
{
LinkNode<T>* current = locate(i);
if (current == NULL)
{
return false;
}
LinkNode<T>* newNode = new LinkNode<T>(x);
if (newNode == NULL)
{
cerr<<"存储分配错误"<<endl;
exit(1);
}
newNode->link = current;
current->link = newNode;
return true;
}
template <class T>
bool LinkList<T>::remove(int i, T &x)
{
LinkNode<T>* current = locate(i-1);
if (current == NULL || current->link == NULL)
{
return false;
}
LinkNode<T>* del = current->link;
current->link = del->link;
x = del->data;
delete del;
return true;
}
template <class T>
void LinkList<T>::output()
{
LinkNode<T>* current = first->link;
while(current != NULL)
{
cout<<current->data<<endl;
current = current->link;
}
}
template <class T>
LinkList<T>& LinkList<T>::operator=(LinkList<T> &list)
{
T value;
LinkNode<T>* srcptr = list.getHead();
LinkNode<T>* destprt = first = new LinkNode<T>;
while(srcptr->link != NULL)
{
value = srcptr->link->data;
destprt->link = new LinkNode<T>(value);
destprt = destprt->link;
srcptr = srcptr->link;
}
destprt->link = NULL;
return *this;
}
template <class T>
LinkList<T>::LinkList(const LinkList<T> &list)
{
T value;
LinkNode<T>* srcptr = list.getHead();
LinkNode<T>* desptr = first = new LinkNode<T>;
while (srcptr->link != NULL)
{
value = srcptr->link->data;
desptr->link = new LinkNode<T>(value);
desptr = desptr->link;
srcptr = srcptr->link;
}
desptr->link = NULL;
}
template <class T>
void LinkList<T>::inputFront(T endTag)
{
first = new LinkNode<T>;
LinkNode<T> *newNode;
T value;
cin>>value;
while(value != endTag)
{
newNode = new LinkNode<T>(value);
if (newNode == NULL)
{
cerr<<"存储分配错误"<<endl;
exit(1);
}
newNode->link = first->link;
first->link = newNode;
cin>>value;
}
}
template <class T>
void LinkList<T>::inputRear(T endTag)
{
LinkNode<T> *newNode, *last;
T value;
cin>>value;
first = new LinkNode<T>;
last = first;
while(value != endTag)
{
newNode = new LinkNode<T>(value);
last->link = newNode;
last = newNode;
cin>>value;
}
last->link = NULL;
}
/***************************************************************************
* file name : main.cpp
* created : 2011/11/03
* description :
* author : Gavin Dai XLX
* update :
****************************************************************************/
#include "LinkList.cpp"
int main()
{
LinkList<int>* list = new LinkList<int>;
list->inputRear(0);
list->output();
cout<<"the length of list"<<list->length();
int val = 100;
list->setData(2,val);
list->output();
system("pause");
}