intlist.c~

hashtree算发

#include <stdio.h>
#include <stdlib.h>
#include "IntList.h"

// Constructor
IntList::IntList()
:head(NULL), len(0)
{  
}

// Copy constructor
IntList::IntList(const IntList& il)
{
  printf("Warning: IntList::IntList(const IntList& il) is not yet implemented\n");
}

// Destructor
IntList::~IntList()
{
  listnode* curNode = head;
  listnode* nextNode;
  
  while (curNode!=NULL) {
    nextNode = curNode->next;
    delete curNode;
    curNode = nextNode;
  }
}

// Prepend an item to the list
void IntList::prepend(int n)
{
  listnode* newNode;

  newNode = new listnode;
  if (newNode==NULL) { 
    printf("Memory allocation error!\n");
    exit(3);
  }
  newNode->item = n;
  newNode->next = head;
  head = newNode;
  
  len++;
}

// Append an item to the list
void IntList::append(int n)
{
  listnode* curNode = head;
  listnode* newNode;

  // Create new node
  newNode = new listnode;
  if (newNode==NULL) { 
    printf("Memory allocation error!\n");
    exit(3);
  }
  newNode->item = n;
  newNode->next = NULL;
  
  // Insert to node to the end
  if (curNode==NULL) {
    head = newNode;
  }
  else {
    // Seek to the end of list
    while (curNode->next!=NULL) 
      curNode = curNode->next;
    curNode->next = newNode;
  }    
  
  len++;  // update counter
}

// Insert an item into a SORTED list
// Remark: the original list must be sorted
void IntList::insertSorted(int n)
{
  listnode* curNode = head;
  listnode* newNode;

  // Empty list
  if (curNode==NULL) {
    prepend(n);
    return; 
  }

  // Search for the position to insert
    
  // Check first node
  if (n<curNode->item) {
    prepend(n);
    return;
  }
        
  // Check the rest
  while (curNode->next!=NULL) {
    if (n<curNode->next->item) {
      newNode = new listnode;
      if (newNode==NULL) { 
        printf("Memory allocation error!\n");
        exit(3);
      }
      newNode->item = n;
      newNode->next = curNode->next;
      curNode->next = newNode;
      len++;

      return;
    }
    
    curNode = curNode->next;
  }
    
  // Not found so append to the end
  append(n);
}

// Delete the (n-1)th element from the list
void IntList::remove(int n)
{
  int i;
  listnode* curNode = head;
  listnode* tmpNode;
  
  if (n>=len) {
    printf("IntList::remove(): Warning: removal of non-existence element from list\n");
  }

  len--;
  
  if (n==0) {
    tmpNode = head;
    head = head->next;  // Update links
    
    delete tmpNode;     // Delete node
  }
  
  for (i=0; i<n-1; i++) {
    curNode = curNode->next;
  }
  
  tmpNode = curNode->next;
  curNode->next = curNode->next->next;  // Update links
  delete tmpNode;                       // Delete node
}

// Locate an item
listnode* IntList::locate(int n)
{
  listnode* curNode = head;

  while (curNode!=NULL) {
    if (curNode->item==n) {
      return curNode;
    }
    curNode = curNode->next;
  }
  
  return NULL;
}

// Copy a linked-list
void IntList::copy(const IntList& il)
{
  listnode* curNode1;
  listnode* curNode2;

  clear();
  len = il.len;

  // Empty list
  if (il.head==NULL) {
    head = NULL; 
    return;
  }  

  // Initialize the head  
  head = new listnode;

  curNode1 = il.head;
  curNode2 = head;
  
  // Copy nodes
  while (curNode1!=NULL) {
    curNode2->item = curNode1->item;
    curNode1 = curNode1->next;
    
    // Create new node
    if (curNode1!=NULL) {
      curNode2->next = new listnode;
      curNode2 = curNode2->next;
    } else {
      curNode2->next = NULL;
    }
  }
}

// Clear the list
void IntList::clear()
{
  // Delete all nodes. Release the memory.
  listnode* curNode = head;
  listnode* nextNode;
  
  while (curNode!=NULL) {
    nextNode = curNode->next;
    delete curNode;
    curNode = nextNode;
  }  

  // Reset the private variables
  head = NULL;
  len = 0;
}

// compare the first k-1 item of 2 list to see if they are the same
bool IntList::compare_k_1(const IntList& il)
{
  int i;
  listnode* curNode1;
  listnode* curNode2;

  // Check the length of the two subspaces
  if (len!=il.len) {
    printf("IntList::compare_k_1(): Cannot compare two subspaces of different length\n");
  }
  
  // Initialize the variables
  curNode1 = head;
  curNode2 = il.head;
  
  // Compare the value of first k-1 nodes  
  for (i=0; i<len-1; i++) {
    if (curNode1->item != curNode2->item)
      return false;
      
    // Advance to next node
    curNode1 = curNode1->next;
    curNode2 = curNode2->next;
  }
  
  return true;
}

// Check if a value exist in the list
bool IntList::exist(int n)
{
  listnode* curNode = head;

  while (curNode!=NULL) {
    if (curNode->item==n) return true;
    curNode = curNode->next;
  }
  
  return false;
}

// Show the list
void IntList::show() const
{
  listnode* curNode = head;

  printf("show::!\n");
  cout << "show" << endl;  
  while (curNode!=NULL) {
    printf("%d ", curNode->item);
    curNode = curNode->next;
  }
}

// Retrieve the (i+1)-th element of the linked-list
int IntList::operator[](int i) const
{
  listnode* curNode = head;

  if (i<0) {
    printf("Warning: Access to negative element\n");
  }
  
  if (i>=len) {
    printf("Warning: Index out of range\n");
  }
  
  while (i>0) {
    curNode = curNode->next;
    i--;
  }
  
  return curNode->item;
}

// Compare two lists
bool IntList::operator== (const IntList& il) const
{
  int i;
  listnode* curNode1;
  listnode* curNode2;

  // Check the length of the two subspaces
  if (len!=il.len) 
    return false;  // Two lists of different lengths mustn't be equal
  
  // Initialize the variables
  curNode1 = head;
  curNode2 = il.head;
  
  // Compare the value of all nodes  
  for (i=0; i<len; i++) {
    if (curNode1->item != curNode2->item)
      return false;
      
    // Advance to next node
    curNode1 = curNode1->next;
    curNode2 = curNode2->next;
  }
  
  return true;
}