// This is the file to include in your code if you want access to the // complete AList template class
// First, get the declaration for the base list class #include"list.h"
// This is the declaration for AList. It is split into two parts // because it is too big to fit on one book page template <typename E> // Array-based list implementation classAList : public List<E> { private: int maxSize; // Maximum size of list int listSize; // Number of list items now int curr; // Position of current element E* listArray; // Array holding list elements
voidclear(){ // Reinitialize the list delete [] listArray; // Remove the array listSize = curr = 0; // Reset the size listArray = new E[maxSize]; // Recreate array }
// Insert "it" at current position voidinsert(const E& it){ Assert(listSize < maxSize, "List capacity exceeded"); for(int i=listSize; i>curr; i--) // Shift elements up listArray[i] = listArray[i-1]; // to make room listArray[curr] = it; listSize++; // Increment list size }
// Remove and return the current element. E remove(){ Assert((curr>=0) && (curr < listSize), "No element"); E it = listArray[curr]; // Copy the element for(int i=curr; i<listSize-1; i++) // Shift them down listArray[i] = listArray[i+1]; listSize--; // Decrement size return it; } voidmoveToStart(){ curr = 0; } // Reset position voidmoveToEnd(){ curr = listSize; } // Set at end voidprev(){ if (curr != 0) curr--; } // Back up voidnext(){ if (curr < listSize) curr++; } // Next
// Return list size intlength()const{ return listSize; }
// Return current position intcurrPos()const{ return curr; }
// Set current list position to "pos" voidmoveToPos(int pos){ Assert ((pos>=0)&&(pos<=listSize), "Pos out of range"); curr = pos; }
const E& getValue()const{ // Return current element Assert((curr>=0)&&(curr<listSize),"No current element"); return listArray[curr]; } };
// Singly linked list node template <typename E> classLink { public: E element; // Value for this node Link *next; // Pointer to next node in list // Constructors Link(const E& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } };
// Insert "it" at current position voidinsert(const E& it){ curr->next = newLink<E>(it, curr->next); if (tail == curr) tail = curr->next; // New tail cnt++; }
// This is the file to include in your code if you want access to the // complete LList template class
// First, get the declaration for the base list class #include"list.h" #define defaultSize 100 // This is the declaration for LList. It is split into two parts // because it is too big to fit on one book page // Linked list implementation template <typename E> classLList: public List<E> { private: Link<E>* head; // Pointer to list header Link<E>* tail; // Pointer to last element Link<E>* curr; // Access to current element int cnt; // Size of list
voidinit(){ // Intialization helper method curr = tail = head = new Link<E>; cnt = 0; }
voidremoveall(){ // Return link nodes to free store while(head != NULL) { curr = head; head = head->next; delete curr; } }
// Insert "it" at current position voidinsert(const E& it){ curr->next = newLink<E>(it, curr->next); if (tail == curr) tail = curr->next; // New tail cnt++; }
voidappend(const E& it){ // Append "it" to list tail = tail->next = newLink<E>(it, NULL); cnt++; }
// Remove and return current element E remove(){ //Assert(curr->next != NULL, "No element"); E it = curr->next->element; // Remember value Link<E>* ltemp = curr->next; // Remember link node（这一步非常重要，不能“丢失”结点的内存，而是应该先创建临时指针ltemp，它的next域指向被删除的结点） if (tail == curr->next) tail = curr; // Reset tail curr->next = curr->next->next; // Remove from list delete ltemp; // Reclaim space（然后再使用delete函数释放被删除节点占用的内存） cnt--; // Decrement the count return it; }
voidmoveToStart()// Place curr at list start { curr = head; }
voidmoveToEnd()// Place curr at list end { curr = tail; }
// Move curr one step left; no change if already at front voidprev(){ if (curr == head) return; // No previous element Link<E>* temp = head; // March down list until we find the previous element while (temp->next!=curr) temp=temp->next; curr = temp; }
// Move curr one step right; no change if already at end voidnext() { if (curr != tail) curr = curr->next; }
intlength()const{ return cnt; } // Return length
// Return the position of the current element intcurrPos()const{ Link<E>* temp = head; int i; for (i=0; curr != temp; i++) temp = temp->next; return i; }
// Move down list to "pos" position voidmoveToPos(int pos){ //Assert ((pos>=0)&&(pos<=cnt), "Position out of range"); curr = head; for(int i=0; i<pos; i++) curr = curr->next; }
const E& getValue()const{ // Return current element //Assert(curr->next != NULL, "No value"); return curr->next->element; } };
// Singly linked list node with freelist support template <typename E> classLink { private: static Link<E>* freelist; // Reference to freelist head public: E element; // Value for this node Link* next; // Point to next node in list
// Constructors Link(const E& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; }
void* operatornew(size_t){ // Overloaded new operator if (freelist == NULL) return ::new Link; // Create space Link<E>* temp = freelist; // Can take from freelist freelist = freelist->next; return temp; // Return the link }
// Overloaded delete operator voidoperatordelete(void* ptr){ ((Link<E>*)ptr)->next = freelist; // Put on freelist freelist = (Link<E>*)ptr; } };
// The freelist head pointer is actually created here template <typename E> Link<E>* Link<E>::freelist = NULL;
// Doubly linked list link node with freelist support template <typename E> classLink { private: static Link<E>* freelist; // Reference to freelist head
public: E element; // Value for this node Link* next; // Pointer to next node in list Link* prev; // Pointer to previous node
void* operatornew(size_t){ // Overloaded new operator if (freelist == NULL) return ::new Link; // Create space Link<E>* temp = freelist; // Can take from freelist freelist = freelist->next; return temp; // Return the link }
// Overloaded delete operator voidoperatordelete(void* ptr){ ((Link<E>*)ptr)->next = freelist; // Put on freelist freelist = (Link<E>*)ptr; }
// Insert "it" at current position voidinsert(const E& it){ curr->next = curr->next->prev = newLink<E>(it, curr, curr->next); cnt++; }
// Append "it" to the end of the list. voidappend(const E& it){ tail->prev = tail->prev->next = newLink<E>(it, tail->prev, tail); cnt++; }
// Remove and return current element E remove(){ if (curr->next == tail) // Nothing to remove returnNULL; E it = curr->next->element; // Remember value Link<E>* ltemp = curr->next; // Remember link node curr->next->next->prev = curr; curr->next = curr->next->next; // Remove from list delete ltemp; // Reclaim space cnt--; // Decrement cnt return it; }
// Move fence one step left; no change if left is empty voidprev(){ if (curr != head) // Can't back up from list head curr = curr->prev; } };
// The freelist head pointer is actually created here template <typename E> Link<E>* Link<E>::freelist = NULL;
