IntNode(int el, IntNode* ptr = 0){ info = el; next = ptr; } };
classIntSLList{
private: IntNode *head, *tail;
public:
IntSLList(){ head = tail = 0; } ~IntSLList();
intisEmpty(){ return head==0; }
voidaddToHead(int); voidaddToTail(int); intdeleteFromHead(); // delete the head and return its info; intdeleteFromTail(); // delete the tail and return its info; voiddeleteNodeFromEl(int); voiddeleteNodeFromPos(int); voidaddToLList(int el, int pos); boolisInList(int)const; voidprintLinkedLists();
int el = head->info; IntNode *tmp = head; if(head == tail) // if only one node in the list head = tail = 0; else head = head->next; delete tmp; return el; }
intIntSLList::deleteFromTail(){ int el = tail->info; if(head == tail){ delete head; head = tail = 0; } else{ // if more than one node in the list IntNode * tmp; // find the predecessor of tail for(tmp=head; tmp->next!=tail;tmp=tmp->next); delete tail; tail = tmp; tail->next = 0; } return el; }
voidIntSLList::deleteNodeFromEl(int el){ if(head != 0){ // if non-empty list if(head == tail && el == head->info){ // if only one delete head; // node in the list head = tail = 0; } elseif(el == head->info){ // if more than one node in the list IntNode* tmp = head; // 原文是head->next, 应该是错了 head = head->next; delete tmp; // and old head is deleted } else{// if mpre than onde node in the lsit IntNode *pred, *tmp; for(pred = head, tmp = head->next; tmp!=0 && !(tmp->info == el); pred = pred->next, tmp = tmp->next); // and a non-head node is deleted
constint defaultSize = 10; // Array based list implementation template <typename E> 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 public: Alist(int size=defaultSize){// Constructor maxSize = size; listSize = curr = 0; listArray = new E[maxSize]; }
~Alist(){delete [] listArray;} // Destructor
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--) listArray[i] = listArray[i-1]; // shift 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++) listArray[i] = listArray[i+1]; // shift them down listSize--; 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]; }
// Print the list voidprintList()const{ for(int i=0; i < listSize; i++){ std::cout << listArray[i] << " "; } std::cout << "\n"; } };
// Singly linked list node template <typename E> classLink{ public: E element; // Value for the node Link* next; // Pointer to next node in list
// Constructor Link(const E& elemval, Link* nextval = NULL){ element = elemval; next = nextval; } Link(Link* nextval=NULL){next=nextval;} };
// 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; // Pointer to current element int cnt; // Size of list
voidinit(){ // Initialization helper method curr = tail = head = new Link<E>; cnt = 0; }
voidremoveall(){ // Return link node 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 if(tail == curr->next) tail = curr; // Reset tail curr->next = curr->next->next; // Remove from list delete ltemp; // Reclaim space 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; 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) return; curr = curr->next; }
intlength()const{ return cnt; }
// Return the position of the current element intcurrPos()const{ Link<E>*temp = head; int i; for(i=0; temp!=curr; 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;} }