ifndef __LINKEDLIST_HPP__
#define __LINKEDLIST_HPP__
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
extern C {
int exit(int);
};
//單鏈表結(jié)點(diǎn)類定義
template <class T> //結(jié)點(diǎn)數(shù)據(jù)域data的類型以參數(shù) (模板)形式提供
class Node {
public: //公有成員
T data; //數(shù)據(jù)域，允許外部直接訪問(wèn)
private: //私有成員
Node<T> *next; //指針域(鏈域)，指向后繼結(jié)點(diǎn)的指針
public: //公有成員
//構(gòu)造函數(shù)(初始化data和next)
Node(const T& item, Node<T> *pNext=NULL) :
data(item), next(pNext){}
//在當(dāng)前結(jié)點(diǎn)之后插入指針p所指結(jié)點(diǎn)
void InsertAfter(Node<T> *p) {
if (!p) return; //若p為空，則返回
p->next = next; //將待插入結(jié)點(diǎn)p的next指向當(dāng)前結(jié)點(diǎn)的next域
next = p; //將當(dāng)前結(jié)點(diǎn)的next更新為待插入結(jié)點(diǎn)p
}
//刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)并返回被刪除結(jié)點(diǎn)的地址
Node<T> *DeleteAfter() {
if (!next) return NULL; //若無(wú)后繼(next為NULL)，則返回
Node<T> *pNext = next; //next不為空，則記錄其地址(留待函數(shù)返回后做處理)
next = next->next; //用后繼結(jié)點(diǎn)(next)的后繼來(lái)更改當(dāng)前結(jié)點(diǎn)的next域
return pNext; //返回已記錄下的待刪除結(jié)點(diǎn)地址
}
//返回指向當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針
Node<T> *NextNode() const { return next; }
T GetData() const { return data; }
void SetData(const T &item) { data = item; }
};
//單鏈表類定義
template <class T>
class LinkedList {
private:
Node<T> *front, *rear; //表頭,表尾
Node<T> *currptr; //指向當(dāng)前結(jié)點(diǎn)的指針
int size; //表長(zhǎng)(結(jié)點(diǎn)的個(gè)數(shù))
private:
//生成新結(jié)點(diǎn)
Node<T> *GetNode(const T& item, Node<T> *pNext = NULL) {
Node<T> *newNode;
//新分配一結(jié)點(diǎn)存儲(chǔ)空間并初始化數(shù)據(jù)成員
newNode = new Node<T>(item, pNext);
if (!newNode) {
cerr << 存儲(chǔ)空間分配失?。〕绦?qū)⒔K止。 << endl;
exit(1);
}
return newNode;
}
//釋放結(jié)點(diǎn)p
void *freeNode(Node<T> *p) { if (p) delete p; }
private:
//當(dāng)鏈表為空時(shí)插入結(jié)點(diǎn)時(shí)的處理
int InsertNewNodeWhenListIsEmpty(const T &item) {
if (size > 0) return 0; //不為空表，返回False(0)
currptr = GetNode(item);
front = currptr;
rear = currptr;
size ++;
return 1; //在空表中插入了結(jié)點(diǎn)，返回True(1)
}
public:
//構(gòu)造函數(shù)
LinkedList() {
front = NULL;
rear = NULL;
currptr = NULL;
size = 0;
}
//拷
