6.cpp

《数据结构与程序设计》书本所有源代码！！！！

/* Program extracts from Chapter 6 of
   "Data Structures and Program Design in C++"
   by Robert L. Kruse and Alexander J. Ryba
   Copyright (C) 1999 by Prentice-Hall, Inc.  All rights reserved.
   Extracts from this file may be used in the construction of other programs,
   but this code will not compile or execute as given here. */


// Section 6.2:

template <class List_entry>
class List{
   //  Add in member information for the class.
};


template <class List_entry>
class List {
public:
//  methods of the List ADT
   List();
   int size() const;
   bool full() const;
   bool empty() const;
   void clear();
   void traverse(void (*visit)(List_entry &));
   Error_code retrieve(int position, List_entry &x) const;
   Error_code replace(int position, const List_entry &x);
   Error_code remove(int position, List_entry &x);
   Error_code insert(int position, const List_entry &x);

protected:
//  data members for a contiguous list implementation
   int count;
   List_entry entry[max_list];
};


template <class List_entry>
int List<List_entry>::size() const
/*
Post: The function returns the number of entries in the List.
*/
{
   return count;
}


template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/*
Post: If the List is not full and 0 <= position <= n,
      where n is the number of entries in the List, the function succeeds:
      Any entry formerly at position and all later entries have their
      position numbers increased by 1 and x is inserted at position of the List.
      Else: The function fails with a diagnostic error code.
*/
{
   if (full())
      return overflow;

   if (position < 0 || position > count)
      return range_error;

   for (int i = count - 1; i >= position; i--)
      entry[i + 1] = entry[i];

   entry[position] = x;
   count++;
   return success;
}


template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/*
Post: The action specified by function (*visit) has been performed on every
      entry of the List, beginning at position 0 and doing each in turn.
*/
{
   for (int i = 0; i < count; i++)
      (*visit)(entry[i]);
}


template <class Node_entry>
struct Node {
//  data members
   Node_entry entry;
   Node<Node_entry> *next;
//  constructors
   Node();
   Node(Node_entry, Node<Node_entry> *link = NULL);
};


template <class List_entry>
class List {
public:
//  Specifications for the methods of the list ADT go here.
//  The following methods replace compiler-generated defaults.
   ~List();
   List(const List<List_entry> &copy);
   void operator =(const List<List_entry> &copy);
protected:
//  Data members for the linked list implementation now follow.
   int count;
   Node<List_entry> *head;

//  The following auxiliary function is used to locate list positions
   Node<List_entry> *set_position(int position) const;
};


template <class List_entry>
Node<List_entry> *List<List_entry>::set_position(int position) const
/*
Pre:  position is a valid position in the List; 0 <= position < count.
Post: Returns a pointer to the Node in position.
*/
{
   Node<List_entry> *q = head;
   for (int i = 0; i < position; i++) q = q->next;
   return q;
}


new_node->next = following;
previous->next = new_node;


template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/*
Post: If the List is not full and 0 <= position <= n,
      where n is the number of entries in the List, the function succeeds:
      Any entry formerly at position and all later entries have their position
      numbers increased by 1, and x is inserted at position of the List.
      Else: The function fails with a diagnostic error code.
*/
{
   if (position < 0 || position > count)
      return range_error;
   Node<List_entry> *new_node, *previous, *following;
   if (position > 0) {
      previous = set_position(position - 1);
      following = previous->next;
   }
   else following = head;
   new_node = new Node<List_entry>(x, following);
   if (new_node == NULL)
      return overflow;
   if (position == 0)
      head = new_node;
   else
      previous->next = new_node;
   count++;
   return success;
}


template <class List_entry>
class List {
public:
//  Add specifications for the methods of the list ADT.
//  Add methods to replace the compiler-generated defaults.

protected:
//  Data members for the linked-list implementation with
//  current position follow:
   int count;
   mutable int current_position;
   Node<List_entry> *head;
   mutable Node<List_entry> *current;

//  Auxiliary function to locate list positions follows:
   void set_position(int position) const;
};


template <class List_entry>
void List<List_entry>::set_position(int position) const
/*
Pre:  position is a valid position in the List: 0 <= position < count.
Post: The current Node pointer references the Node at position.
*/
{
   if (position < current_position) {  //  must start over at head of list
      current_position = 0;
      current = head;
   }
   for ( ; current_position != position; current_position++)
      current = current->next;
}


template <class Node_entry>
struct Node {
//  data members
   Node_entry entry;
   Node<Node_entry> *next;
   Node<Node_entry> *back;
//  constructors
   Node();
   Node(Node_entry, Node<Node_entry> *link_back = NULL,
                    Node<Node_entry> *link_next = NULL);
};


template <class List_entry>
class List {
public:
//  Add specifications for methods of the list ADT.
//  Add methods to replace compiler generated defaults.
protected:
//  Data members for the doubly-linked list implementation follow:
   int count;
   mutable int current_position;
   mutable Node<List_entry> *current;

//  The auxiliary function to locate list positions follows:
   void set_position(int position) const;
};


template <class List_entry>
void List<List_entry>::set_position(int position) const
/*
Pre:  position is a valid position in the List: 0 <= position < count.
Post: The current Node pointer references the Node at position.
*/
{
   if (current_position <= position)
      for ( ; current_position != position; current_position++)
         current = current->next;
   else
      for ( ; current_position != position; current_position--)
         current = current->back;
}


template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/*
Post: If the List is not full and 0 <= position <= n,
      where n is the number of entries in the List, the function succeeds:
      Any entry formerly at position and all later entries have their
      position numbers increased by 1 and x is inserted at position of the List.
      Else: the function fails with a diagnostic error code.
*/
{
   Node<List_entry> *new_node, *following, *preceding;
   if (position < 0 || position > count) return range_error;
   if (position == 0) {
      if (count == 0) following = NULL;
      else {
         set_position(0);
         following = current;
      }
      preceding = NULL;
   }
   else {
      set_position(position - 1);
      preceding = current;
      following = preceding->next;
   }
   new_node = new Node<List_entry>(x, preceding, following);

   if (new_node == NULL) return overflow;
   if (preceding != NULL) preceding->next = new_node;
   if (following != NULL) following->back = new_node;
   current = new_node;
   current_position = position;
   count++;
   return success;
}




// Section 6.3:

class String {
public:                           //  methods of the string ADT
   String();
   ~String();
   String (const String &copy);   //  copy constructor
   String (const char * copy);    //  conversion from C-string
   String (List<char> &copy);     //  conversion from List

   void operator =(const String &copy);
   const char *c_str() const;     //  conversion to C-style string

protected:
   char *entries;
   int length;
};

bool operator ==(const String &first, const String &second);
bool operator   >(const String &first, const String &second);
bool operator   <(const String &first, const String &second);
bool operator >=(const String &first, const String &second);
bool operator <=(const String &first, const String &second);
bool operator !=(const String &first, const String &second);


String::String (const char *in_string)
/*
Pre:  The pointer in_string references a C-string.
Post: The String is initialized by the C-string in_string.
*/
{
   length = strlen(in_string);
   entries = new char[length + 1];
   strcpy(entries, in_string);
}


String::String (List<char> &in_list)
/*
Post: The String is initialized by the character List in_list.
*/
{
   length = in_list.size();
   entries = new char[length + 1];
   for (int i = 0; i < length; i++) in_list.retrieve(i,entries[i]);
   entries[length] = '\0';
}


const char*String::c_str() const
/*
Post: A pointer to a legal C-string object matching the String is returned.
*/
{
   return (const char *) entries;
}


   String s = "abc";
   const char *new_string = s.c_str();
   s = "def";
   cout << new_string;


   String s = "Some very long string";
   cout << s.c_str();  //  creates garbage from a temporary C-string object


bool operator ==(const String &first, const String &second)
/*
Post: Return true if the String first agrees with String second.
      Else: Return false.
*/
{
   return strcmp(first.c_str(), second.c_str()) == 0;
}


String s = "some_string";
cout << s.c_str() << endl;
cout << strlen(s.c_str()) << endl;


void strcat(String &add_to, const String &add_on)
/*
Post: The function concatenates String add_on onto the end of String add_to.
*/
{
   const char *cfirst = add_to.c_str();
   const char *csecond = add_on.c_str();
   char *copy = new char[strlen(cfirst) + strlen(csecond) + 1];
   strcpy(copy, cfirst);
   strcat(copy, csecond);
   add_to = copy;
   delete []copy;
}


String read_in(istream &input)
/*
Post: Return a String read (as characters terminated
      by a newline or an end-of-file character) from an istream parameter.
*/
{
   List<char> temp;
   int size = 0;
   char c;
   while ((c = input.peek()) != EOF && (c = input.get()) != '\n')
      temp.insert(size++, c);
   String answer(temp);
   return answer;
}


void write(String &s)
/*
Post: The String parameter s is written to cout.
*/
{
   cout << s.c_str() << endl;
}



// Section 6.4:

int main(int argc, char *argv[]) // count, values of command-line arguments
/*
Pre:  Names of input and output files are given as command-line arguments.
Post: Reads an input file that contains lines (character strings),
      performs simple editing operations on the lines, and
      writes the edited version to the output file.
Uses: methods of class Editor
*/
{
   if (argc != 3) {
      cout << "Usage:\n\t edit  inputfile  outputfile" << endl;
      exit (1);
   }
   ifstream file_in(argv[1]);   //  Declare and open the input stream.
   if (file_in == 0) {
      cout << "Can't open input file " << argv[1] << endl;
      exit (1);
   }
   ofstream file_out(argv[2]);   //  Declare and open the output stream.
   if (file_out == 0) {
      cout << "Can't open output file " << argv[2] << endl;
      exit (1);
   }
   Editor buffer(&file_in, &file_out);
   while (buffer.get_command())
      buffer.run_command();
}


class Editor:public List<String> {
public:
   Editor(ifstream *file_in, ofstream *file_out);
   bool get_command();
   void run_command();
private:
   ifstream *infile;
   ofstream *outfile;
   char user_command;

//  auxiliary functions
   Error_code next_line();
   Error_code previous_line();
   Error_code goto_line();
   Error_code insert_line();
   Error_code substitute_line();
   Error_code change_line();
   void read_file();
   void write_file();
   void find_string();
};


Editor::Editor(ifstream *file_in, ofstream *file_out)
/*