src.all

来自「经典c++程序的实现」· ALL 代码 · 共 874 行 · 第 1/2 页

// alist.cpp

#include <stdio.h>
#include <iostream.h>
#include <assert.h>
#include "..\include\book.h"

typedef int ELEM;

#include "..\include\alist.h" // Load the member functions for list

list::list(const int sz)           // Constructor: initialize
  { msize = sz;  numinlist = curr = 0; listarray = new ELEM[sz]; }

list::~list()                      // Destructor: return array space
  { delete [] listarray; }

void list::clear()                 // Remove all ELEMs from list
  { numinlist = curr = 0; }        // Simply reinitialize values


// Insert ELEM at current position
void list::insert(const ELEM& item) {
  // Array must not be full and curr must be a legal position
  assert((numinlist < msize) && (curr >=0) && (curr <= numinlist));
  for(int i=numinlist; i>curr; i--) // Shift ELEMs up to make room
    listarray[i] = listarray[i-1];
  listarray[curr] = item;
  numinlist++;                     // Increment current list size
}

void list::append(const ELEM& item) { // Insert ELEM at tail of list
  assert(numinlist < msize);          // List must not be full
  listarray[numinlist++] = item;      // Increment list size
}

ELEM list::remove() {              // Remove and return current ELEM
  assert(!isEmpty() && isInList());   // Must be an ELEM to remove
  ELEM temp = listarray[curr];        // Store removed ELEM
  for(int i=curr; i<numinlist-1; i++) // Shift elements down
    listarray[i] = listarray[i+1];
  numinlist--;                        // Decrement current list size
  return temp;
}

void list::setFirst()              // Set curr to first position
  { curr = 0; }

void list::prev()                  // Move curr to previous position
  { curr--; }

void list::next()                  // Move curr to next position
  { curr++; }

int list::length() const           // Return current length of list
  { return numinlist; }

void list::setPos(const int pos)   // Set curr to specified position
  {curr = pos; }

void list::setValue(const ELEM& val) { // Set current ELEM's value
  assert(isInList());              // Curr must be at valid position
  listarray[curr] = val;
}

ELEM list::currValue() const {     // Return current ELEM's value
  assert(isInList());              // Must be at a valid position
  return listarray[curr];
}

bool list::isEmpty() const         // Return TRUE if list is empty
  { return numinlist == 0; }

bool list::isInList() const        // TRUE if curr is within list
  { return (curr >= 0) && (curr < numinlist); }

bool list::find(const ELEM& val) { // Find value (starting at curr)
  while (isInList())               // Stop if reach end
    if (currValue() == val) return TRUE;  // Found it
    else next();
  return FALSE;                    // Not found
}

// almain.cpp

#include <iostream.h>

#include "..\include\book.h"

typedef int ELEM;
#include "..\include\alist.h"

// This is poor style to include this code.  The only reason I do it
// is because otherwise lprint.c would need to include the proper
// list header, which would require a separate lprint.c version for
// array-based and linked lists.
#include "..\include\lprint.c"

main()
{
  list L1;
  list L2(15);
  list L3;

  L2.append(10);
  print(L2);
  L2.append(20);
  L2.append(15);
  print(L2);
  L1.setFirst();
  L1.insert(39);
  L1.next();
  L1.insert(12);
  L1.append(5);
  L1.append(4);
  L1.append(3);
  L1.append(2);
  L1.append(1);
  print(L1);
  L2.setFirst();
  L2.find(20);
  if (L2.isInList())
    cout << "L2 curr: " << L2.currValue() << "\n";
  else
    cout << "Odd - what happened to 20?\n";
  cout << "L1: "; print(L1);
  cout << "Size: " << L1.length() << "\n";
  cout << "L2: "; print(L2);
  cout << "L3: "; print(L3);
  L1.setFirst();
  L1.find(20);
  if (L1.isInList())
    cout << "Odd - shouldn't find 20 in L1!\n";
  else
    cout<< "20 not in L1.\n";
  L1.setFirst();
  L1.find(5);
  if (L1.isInList())
    cout << L1.currValue() << "\n";
  L2.setFirst();
  L2.find(20);
  if(L2.isInList())
    cout << L2.currValue() << "\n";
  else
    cout << "Didn't find it the first time\n";
  L2.next();
  L2.find(20);
  if (L2.isInList())
    cout << "Found it again!\n";
  else
    cout << "Only once in list.\n";
  L1.setFirst();
  cout << L1.currValue() << "\n";
  L1.setValue(42);
  print(L1);
  L2.setFirst();
  cout << "Removing: " << L2.remove() << "\n";
  cout << "Removing: " << L2.remove() << "\n";
  print(L2);
  cout << "Size: " << L2.length() << "\n";
  L2.clear(); print(L2);
  cout << "Size: " << L2.length() << "\n";
  L2.append(5); print(L2);
  cout << "Start a new round.\n";
  L2.clear();
  print(L2);
  L2.setFirst();
  L2.insert(1);
  print(L2);
  L2.insert(2);
  print(L2);
  L2.setPos(2);
  L2.insert(3);
  print(L2);
  cout << "That is all.\n";
  cout << "-----------------------\n";
  return(0);
}


// llist.cpp

#include <stdio.h>
#include <iostream.h>
#include <assert.h>

#include "..\include\book.h"

typedef int ELEM;

#include "..\include\link.h"

#include "..\include\llist.h"

// Load the member functions for list
list::list(const int sz)       // Constructor -- Ignore sz
  { tail = head = curr = new link; }  // Create header node

list::~list() {                // Destructor
  while(head != NULL) {        // Return link nodes to free store
    curr = head;
    head = head->next;
    delete curr;
  }
}

void list::clear() {           // Remove all ELEMs from list
  while (head->next != NULL) { // Return link nodes to free store
    curr = head->next;         //   (keep header node)
    head->next = curr->next;
    delete curr;
  }
  curr = tail = head;          // Reinitialize
}

// Insert ELEM at current position
void list::insert(const ELEM& item) {
  assert(curr != NULL);       // Must be pointing to list ELEM
  curr->next = new link(item, curr->next);
  if (tail == curr)           // Appended new ELEM
    tail = curr->next;
}

void list::append(const ELEM& item) // Insert ELEM at tail of list
  { tail = tail->next = new link(item, NULL); }

ELEM list::remove() {              // Remove and return current ELEM
  assert(isInList());              // Must be valid position in list
  ELEM temp = curr->next->element; // Remember value
  link* ltemp = curr->next;        // Remember link node
  curr->next = ltemp->next;        // Remove from list
  if (tail == ltemp) tail = curr;  // Removed last ELEM: set tail
  delete ltemp;                    // Send link to free store
  return temp;                     // Return value removed
}

void list::setFirst()              // Set curr to first position
  { curr = head; }

void list::next()                  // Move curr to next position
  { if (curr != NULL)  curr = curr->next; }

void list::prev() {                // Move curr to previous position
  link* temp = head;
  if ((curr == NULL) || (curr == head)) // No previous ELEM
    { curr = NULL;  return; }           //   so just return
  while ((temp!=NULL) && (temp->next!=curr)) temp=temp->next;
  curr = temp;
}

int list::length() const {          // Return current length of list
  int cnt = 0;
  for (link* temp = head->next; temp != NULL; temp = temp->next)
     cnt++;                         // Count the number of ELEMs
  return cnt;
}

void list::setPos(const int pos) { // Set curr to specified position
  curr = head;
  for(int i=0; (curr!=NULL) && (i<pos); i++)
    curr = curr->next;
}

void list::setValue(const ELEM& val) // Set current ELEM's value
  { assert(isInList());  curr->next->element = val; }

ELEM list::currValue() const         // Return value of current ELEM
  { assert(isInList());  return curr->next->element; }

bool list::isEmpty() const          // Return TRUE if list is empty
  { return head->next == NULL; }

bool list::isInList() const         // TRUE if curr is within list
  { return (curr != NULL) && (curr->next != NULL); }

bool list::find(const ELEM& val) {  // Find value (starting at curr)
  while (isInList())
    if (curr->next->element == val) return TRUE;
    else curr = curr->next;
  return FALSE;                     // Not found
}

// llmain.cpp

#include <iostream.h>

#include "..\include\book.h"

typedef int ELEM;

#include "..\include\link.h"

#include "..\include\llist.h"

// This is poor style to include this code.  The only reason I do it
// is because otherwise lprint.c would need to include the proper
// list header, which would require a separate lprint.c version for
// array-based and linked lists.
#include "..\include\lprint.c"

main()
{
  list L1;
  list L2(15);
  list L3;

  L2.append(10);
  print(L2);
  L2.append(20);
  L2.append(15);
  print(L2);
  L1.setFirst();
  L1.insert(39);
  L1.next();
  L1.insert(12);
  L1.append(5);
  L1.append(4);
  L1.append(3);
  L1.append(2);
  L1.append(1);
  print(L1);
  L2.setFirst();
  L2.find(20);
  if (L2.isInList())
    cout << "L2 curr: " << L2.currValue() << "\n";
  else
    cout << "Odd - what happened to 20?\n";
  cout << "L1: "; print(L1);
  cout << "Size: " << L1.length() << "\n";
  cout << "L2: "; print(L2);
  cout << "L3: "; print(L3);
  L1.setFirst();
  L1.find(20);
  if (L1.isInList())
    cout << "Odd - shouldn't find 20 in L1!\n";
  else
    cout << "20 not in L1.\n";
  L1.setFirst();
  L1.find(5);
  if (L1.isInList())
    cout << L1.currValue() << "\n";
  L2.setFirst();
  L2.find(20);
  if(L2.isInList())
    cout << L2.currValue() << "\n";
  else
    cout << "Didn't find it the first time\n";
  L2.next();
  L2.find(20);
  if (L2.isInList())
    cout << "Found it again!\n";
  else
    cout << "Only once in list.\n";
  L1.setFirst();
  cout << L1.currValue() << "\n";
  L1.setValue(42);
  print(L1);
  L2.setFirst();
  cout << "Removing: " << L2.remove() << "\n";
  cout << "Removing: " << L2.remove() << "\n";
  print(L2);
  cout << "Size: " << L2.length() << "\n";
  L2.clear(); print(L2);
  cout << "Size: " << L2.length() << "\n";
  L2.append(5); print(L2);
  cout << "Start a new round.\n";
  L2.clear();
  print(L2);
  L2.setFirst();
  L2.insert(1);
  print(L2);
  L2.insert(2);
  print(L2);
  L2.setPos(2);
  L2.insert(3);
  print(L2);
  cout << "That is all.\n";
  cout << "-----------------------\n";
  return(0);
}



// llist.cpp

#include <stdio.h>
#include <iostream.h>
#include <assert.h>

#include "..\include\book.h"

typedef int ELEM;

#include "..\include\link.h"

#include "..\include\llist.h"

// Load the member functions for list
list::list(const int sz)       // Constructor -- Ignore sz
  { tail = head = curr = new link; }  // Create header node

list::~list() {                // Destructor
  while(head != NULL) {        // Return link nodes to free store
    curr = head;
    head = head->next;
    delete curr;
  }
}

void list::clear() {           // Remove all ELEMs from list
  while (head->next != NULL) { // Return link nodes to free store
    curr = head->next;         //   (keep header node)
    head->next = curr->next;
    delete curr;
  }
  curr = tail = head;          // Reinitialize
}

// Insert ELEM at current position
void list::insert(const ELEM& item) {
  assert(curr != NULL);       // Must be pointing to list ELEM
  curr->next = new link(item, curr->next);
  if (tail == curr)           // Appended new ELEM
    tail = curr->next;
}

void list::append(const ELEM& item) // Insert ELEM at tail of list
  { tail = tail->next = new link(item, NULL); }

ELEM list::remove() {              // Remove and return current ELEM
  assert(isInList());              // Must be valid position in list
  ELEM temp = curr->next->element; // Remember value
  link* ltemp = curr->next;        // Remember link node
  curr->next = ltemp->next;        // Remove from list
  if (tail == ltemp) tail = curr;  // Removed last ELEM: set tail
  delete ltemp;                    // Send link to free store