链表类List

这个类是为了给GeneralTree提供Queue队列操作才创建的。

因为GeneralTree使用层次遍历的时候，必须要使用这样一个队列。当然如果你没有这样一个队列，但是你在每个节点那里设置了计数器，那么你还是可以完成一个层
次遍历操作。

这里为了保持GeneralTreeNode的最简单性，所以没有添加计数器属性。

下面是List类的具体代码：

/* * create by chico chen * date: 2009/02/02 / #ifndef LIST_H #define
LIST_H template class ListNode { public: T data; ListNode next;
ListNode() { next = NULL; } ListNode(T & data) { this->data = data; next =
NULL; } ListNode(T & data, ListNode* next) { this->data = data; this->next
= next; } ~ListNode() { next = NULL; } }; template class List {
private: int length; ListNode* head; public: List() { head = NULL; length =
0; } List(ListNode* head) { this->head = head; length = 1; } ~List() {
ListNode* tempHead = head; while(NULL != head) { tempHead = head->next;
delete head; head = tempHead; } length = 0; } bool IsEmpty() { return 0 ==
length; } // the coral function to insert the node // pre : none // post: no
matter what kind of situation, the function can work. void Insert(ListNode*
node, int index) { if(0 == index) { // insert in the front if(NULL == head) {
head = node; } else { node->next = head; head = node; } } else { if(NULL ==
head) { head = node; } else { if(index >= length || index < 0) { index =
length; } ListNode* temp = head; while(NULL != temp->next && index–) {
temp = temp->next; } temp->next = node; } } length ++; } ListNode*
GetHead() { return this->head; } // pre: list is not empty // post: return the
last element. ListNode* GetTail() { if(NULL == head) { return NULL; }
ListNode* tempHead = head; while(NULL != tempHead->next) { tempHead =
tempHead->next; } return tempHead; } // pre: node is not NULL // post: return
the node’s next node ListNode* GetNext(ListNode* node) { if(NULL !=
node) { return node->next; } } // pre: begin at zero, and the index is less
than the length of the list // post: if index is -1, then return the last //
post: if index is not -1 and less than zer, or bigger than the length, throw
exception. ListNode* GetAt(int index) { ListNode* temp = NULL; if(-1 ==
index) { // get the last temp = GetTail(); } else if(0 <= index && index <
length) { ListNode* tempHead = head; while(tempHead && index–) { tempHead
= tempHead->next; } temp = tempHead; } else { throw “out of list”; } return
temp; } void DeleteHead() { ListNode* tempHead = head; head = head->next;
delete tempHead; this->length–; } // pre: head is not NULL // post: delete
the last one and length subtract 1 void DeleteTail() { if(NULL == head)
return; ListNode* tempTail = head; while(NULL != tempTail->next) { tempTail
= tempTail->next; } delete tempTail; length–; } // pre: head may be not NULL
// post: if index is equal to -1, then delete tail element // post: if index
is equal to 0, then delete the head // post: if it is bigger than the length,
or less than 0, throw exception // post: delete one node at index and length
subtract 1 void DeleteAt(int index) { if(-1 == index) { DeleteTail(); } else
if(0 == index) { DeleteHead(); } else if(0 < index && index < length) {
ListNode* temp = GetAt(index-1); ListNode* dNode = temp->next;
temp->next = dNode->next; delete dNode; length --; } else { throw “out of
List”; } } }; #endif