节点类Node	
双向节点类DNode	
链表类LinkedList	
节点函数库	
程序9.1 ：匹配毽值	
程序9.2 ：乱字	
程序9.3：毕业生名单	
程序9.4：表插入排序	
程序9.5：表选择排序	
程序9.6：删除重复值	
程序9.7a：表类——数组实现	
程序9.7a：表类——链表实现	
程序9.9: Josephus问题	
程序9.10: 用双向链表排序	
节点类Node

#ifndef NODE_CLASS
#define NODE_CLASS

template <class T>
class Node
{
    private:
		// next is the address of the following node
        Node<T> *next;
    public:
    	// the data is public
        T data;
    
		// constructor
        Node (const T& item, Node<T>* ptrnext = NULL);
        
        // list modification methods
        void InsertAfter(Node<T> *p);
        Node<T> *DeleteAfter(void);
        
        // obtain the address of the next node
        Node<T> *NextNode(void) const;
};

// constructor. initialize data and pointer members
template <class T>
Node<T>::Node(const T& item, Node<T>* ptrnext) : 
		 data(item), next(ptrnext)
{}
  
// return value of private member next
template <class T>
Node<T> *Node<T>::NextNode(void) const
{
    return next;
} 

// insert a node p after the current one
template <class T>
void Node<T>::InsertAfter(Node<T> *p)
{
	// p points to successor of the current node, 
	// and current node  points to p.
    p->next = next;
    next = p;
}

// delete the node following current and return its address
template <class T>
Node<T> *Node<T>::DeleteAfter(void)
{
	// save address of node to be deleted
    Node<T> *tempPtr = next;

	// if there isn't a successor, return NULL
    if (next == NULL)
        return NULL;
        
	// current node points to successor of tempPtr.
    next = tempPtr->next;
    
	// return the pointer to the unlinked node
    return tempPtr;
}

#endif  // NODE_CLASS
——————————————————————————————————————
双向节点类DNode
#ifndef DOUBLY_LINKED_NODE_CLASS
#define DOUBLY_LINKED_NODE_CLASS

template <class T>
class DNode
{
    private:
    	// circular links to the left and right
        DNode<T> *left;
        DNode<T> *right;
    public: 
    	// data is public 
        T data;
        
		// constructors
        DNode(void); 
        DNode (const T& item);
        
        
        // list modification methods
        void InsertRight(DNode<T> *p);
        void InsertLeft(DNode<T> *p);
        DNode<T> *DeleteNode(void);
        
        
        // obtain address of the next node to the left or right
        DNode<T> *NextNodeRight(void) const;
        DNode<T> *NextNodeLeft(void) const;
};

// constructor that creates an empty list and
// leaves the data uninitialized. use for header
template <class T>
DNode<T>::DNode(void)
{
	// initialize the node so it points to itself
    left = right = this;
}

// constructor that creates an empty list and initializes data
template <class T>
DNode<T>::DNode(const T& item)
{
	// set node to point to itself and initialize data
    left = right = this;
    data = item;
}
        
// insert a node p to the right of current node
template <class T>
void DNode<T>::InsertRight(DNode<T> *p)
{
	// link p to its successor on the right
    p->right = right;
	right->left = p;
	
 	// link p to the current node on its left
    p->left = this;
    right = p;
}

// insert a node p to the left of current node
template <class T>
void DNode<T>::InsertLeft(DNode<T> *p)
{
	// link p to its successor on the left
    p->left = left;
    left->right = p;
    
 	// link p to the current node on its right
    p->right = this;
    left = p;
}

// unlink the current node from the list and return its address
template <class T>
DNode<T> *DNode<T>::DeleteNode(void)
{
	// node to the left must be linked to current node's right
    left->right = right;
    
	// node to the right must be linked to current node's left
    right->left = left;
    
    // return the address of the current node
    return this;
}

// return pointer to the next node on the right
template <class T>
DNode<T> *DNode<T>::NextNodeRight(void) const
{
    return right;
}

// return pointer to the next node on the left
template <class T>
DNode<T> *DNode<T>::NextNodeLeft(void) const
{
    return left;
}

#endif	// DOUBLY_LINKED_NODE_CLASS
——————————————————————————————————————
链表类LinkedList 

#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS

#include <iostream.h>
#include <stdlib.h>

#ifndef NULL
const int NULL = 0;
#endif  // NULL

#include "node.h"

template <class T>
class SeqListIterator;

template <class T>
class LinkedList
{
   private:
      // pointers maintain access to front and rear of list
      Node<T> *front, *rear;
      
      // used for data retrieval, insertion and deletion
      Node<T> *prevPtr, *currPtr;
      
      // number of elements in the list
      int size;
      
      // position in list. used by Reset method
      int position;
      // private methods to allocate and deallocate nodes
      Node<T> *GetNode(const T& item,Node<T> *ptrNext=NULL);
      void FreeNode(Node<T> *p);
      
      // copies list L to current list
      void CopyList(const LinkedList<T>& L);
      
   public:
      // constructors
      LinkedList(void);
      LinkedList(const LinkedList<T>& L);
      
      // destructor
      ~LinkedList(void);
      
      // assignment operator
      LinkedList<T>& operator= (const LinkedList<T>& L);
      
      // methods to check list status
      int ListSize(void) const;               
      int ListEmpty(void) const;
      
      // Traversal methods
      void Reset(int pos = 0);
      void Next(void);
      int EndOfList(void) const;
      int CurrentPosition(void) const;
      
      // Insertion methods
      void InsertFront(const T& item);
      void InsertRear(const T& item);
      void InsertAt(const T& item);
      void InsertAfter(const T& item);
      
      // Deletion methods
      T DeleteFront(void);
      void DeleteAt(void);

      // Data retrieval/modification
      T& Data(void);
      
      // method to clear the list
      void ClearList(void);
      
      // this class (Ch. 12) needs access to front
      friend class SeqListIterator<T>;
};

template <class T>
Node<T> *LinkedList<T>::GetNode(const T& item, 
                      Node<T>* ptrNext)
{
   Node<T> *p;

   p = new Node<T>(item,ptrNext);
   if (p == NULL)
   {
      cout << "Memory allocation failure!\n";
      exit(1);
   }
   return p;
}

template <class T>
void LinkedList<T>::FreeNode(Node<T> *p)
{
   delete p;
}

// copy L to the current list, which is assumed to be empty
template <class T>
void LinkedList<T>::CopyList(const LinkedList<T>& L)
{
   // use p to chain through L
   Node<T> *p = L.front;
   int pos;

   // insert each element in L at the rear of current object
   while (p != NULL)
   {
      InsertRear(p->data);
      p = p->NextNode();
   }
   
   // if list is empty return
   if (position == -1)
      return;

   // reset prevPtr and currPtr in the new list
   prevPtr = NULL;
   currPtr = front;
   for (pos = 0; pos != position; pos++)
   {
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
   }
}

// create empty list by setting pointers to NULL, size to 0
// and list position to -1
template <class T>
LinkedList<T>::LinkedList(void): front(NULL), rear(NULL),
      prevPtr(NULL),currPtr(NULL), size(0), position(-1)
{}

template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)
{
   front = rear = NULL;
   prevPtr = currPtr = NULL;
   size = 0;
   position = -1;
   CopyList(L);
}

template <class T>
void LinkedList<T>::ClearList(void)
{
   Node<T> *currPosition, *nextPosition;

   currPosition = front;
   while(currPosition != NULL)
   {
      // get address of next node and delete current node
      nextPosition = currPosition->NextNode();
      FreeNode(currPosition);
      currPosition = nextPosition;  // Move to next node
   }
   front = rear = NULL;
   prevPtr = currPtr = NULL;
   size = 0;
   position = -1;
}

template <class T>
LinkedList<T>::~LinkedList(void)
{
   ClearList();
}

template <class T>
LinkedList<T>& LinkedList<T>::operator= 
               (const LinkedList<T>& L)
{
   if (this == &L)      // Can't assign list to itself
      return *this;

   ClearList();
   CopyList(L);
   return *this;
}

template <class T>
int LinkedList<T>::ListSize(void) const
{
   return size;
}
                      
template <class T>
int LinkedList<T>::ListEmpty(void) const
{
   return size == 0;
}

// move prevPtr and currPtr forward one node
template <class T>
void LinkedList<T>::Next(void)
{
   // if traversal has reached the end of the list or
   // the list is empty, just return
   if (currPtr != NULL)
   {
      // advance the two pointers one node forward
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
      position++;
   }
}

// True if the client has traversed the list
template <class T>
int LinkedList<T>::EndOfList(void) const
{
   return currPtr == NULL;
}

// return the position of the current node
template <class T>
int LinkedList<T>::CurrentPosition(void) const
{
   return position;
}

// reset the list position to pos
template <class T>
void LinkedList<T>::Reset(int pos)
{
   int startPos;
   
   // if the list is empty, return
   if (front == NULL)
      return;
      
   // if the position is invalid, terminate the program
   if (pos < 0 || pos > size-1)
   {
      cerr << "Reset: Invalid list position: " << pos 
           << endl;
      return;
   }
   
   // move list traversal mechanism to node pos
   if(pos == 0)
   {
      // reset to front of the list
      prevPtr = NULL;
      currPtr = front;
      position = 0;
   }
   else
   // reset currPtr, prevPtr, and position
   {
       currPtr = front->NextNode();
       prevPtr = front;
       startPos = 1;
	   // move right until position == pos 
	   for(position=startPos; position != pos; position++)
	   {
	       // move both traversal pointers forward
	       prevPtr = currPtr;
	       currPtr = currPtr->NextNode();
      }
   }
}

// return a reference to the data value in the current node
template <class T>
T& LinkedList<T>::Data(void)
{
   // error if list is empty or traversal completed
   if (size == 0 || currPtr == NULL)
   {
      cerr << "Data: invalid reference!" << endl;
      exit(1);
   }
   return currPtr->data;
}

// Insert item at front of list
template <class T>
void LinkedList<T>::InsertFront(const T& item)
{
   // call Reset if the list is not empty
   if (front != NULL)
      Reset();
   InsertAt(item);        // inserts at front
}

// Insert item at rear of list
template <class T>
void LinkedList<T>::InsertRear(const T& item)
{
   Node<T> *newNode;
   
   prevPtr = rear;
   newNode = GetNode(item);	// create the new node
   if (rear == NULL)				// if list empty, insert at front
      front = rear = newNode;
   else
   {
      rear->InsertAfter(newNode);
      rear = newNode;
   }
   currPtr = rear;
   position = size;
   size++;
}

// Insert item at the current list position
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{
   Node<T> *newNode;

   // two cases: inserting at the front or inside the list
   if (prevPtr == NULL)
   {
      // inserting at the front of the list. also places
      // node into an empty list
      newNode = GetNode(item,front);
      front = newNode;
   }
   else
   {
      // inserting inside the list. place node after prevPtr
      newNode = GetNode(item);
      prevPtr->InsertAfter(newNode);
   }
   
   // if prevPtr == rear, we are inserting into empty list 
   // or at rear of non-empty list; update rear and position
   if (prevPtr == rear)
   {
      rear = newNode;
      position = size;
   }

   // update currPtr and increment the list size
   currPtr = newNode;
   size++;              // increment list size
}

// Insert item after the current list position
template <class T>
void LinkedList<T>::InsertAfter(const T& item)
{
   Node<T> *p;

   p = GetNode(item);
   if (front == NULL)       // inserting into an empty list
   {
      front = currPtr = rear = p;
      position = 0;
   }
   else
   {
      // inserting after last node of list
      if (currPtr == NULL)
        currPtr = prevPtr;
      currPtr->InsertAfter(p);
      if (currPtr == rear)
      {
        rear = p;
        position = size;
      }
      else
      	position++;
      prevPtr = currPtr;
      currPtr = p;
   }
   size++;              // increment list size
}

// Delete the node at the front of list
template <class T>
T LinkedList<T>::DeleteFront(void)
{
   T item;

   Reset();
   if (front == NULL)
   {
      cerr << "Invalid deletion!" << endl;
      exit(1);
   }
   item = currPtr->data;
   DeleteAt();
   return item;
}

// Delete the node at the current list position     
template <class T>
void LinkedList<T>::DeleteAt(void)
{
   Node<T> *p;

   // error if empty list or at end of list
   if (currPtr == NULL)
   {
      cerr << "Invalid deletion!" << endl;
      exit(1);
   }
   
   // deletion must occur at front node or inside the list
   if (prevPtr == NULL)
   {
      // save address of front and unlink it. if this
      // is the last node, front becomes NULL
      p = front;
      front = front->NextNode();
   }
   else
      // unlink interior node after prevPtr. save address
      p = prevPtr->DeleteAfter();
      
   // if rear is deleted, new rear is prevPtr and position
   // is decremented; otherwise, position is the same
   // if p was last node, rear = NULL and position = -1
   if (p == rear)
   {
      rear = prevPtr;
      position--;
   }
        
   // move currPtr past deleted node. if p is last node 
   // in the list, currPtr becomes NULL
   currPtr = p->NextNode();
   
   // free the node and decrement the list size
   FreeNode(p);
   size--;
}

#endif  // LINKEDLIST_CLASS
节点函数库 
#ifndef NODE_LIBRARY
#define NODE_LIBRARY

#include <iostream.h>
#include <stdlib.h>
// suppress incorrect warning message in InsertFront
#pragma warn -par

#include "node.h"

// allocate a node with data member item and pointer nextPtr
template <class T>
Node<T> *GetNode(const T& item, Node<T> *nextPtr = NULL)
{
    Node<T>  *newNode;

    // allocate memory while passing item and NextPtr to
    // constructor. terminate program if allocation fails
    newNode = new Node<T>(item, nextPtr);
    if (newNode == NULL)
    {
        cerr << "Memory allocation failure!" << endl;
        exit(1);
    }
    
    return newNode;
}

enum AppendNewline {noNewline,addNewline};

// print a linked list
template <class T>
void PrintList(Node<T> *head, AppendNewline addnl = noNewline)
{
    // currPtr chains through the list, starting at head
    Node<T> *currPtr = head;

	// print the current node's data until end of list
    while(currPtr != NULL)
    {
        // output newline if addl == addNewline
        if(addnl == addNewline)
            cout << currPtr->data << endl;
        else
            cout << currPtr->data << "  ";
           
        // move to next node
        currPtr = currPtr->NextNode();
    }
}

// find an item in a linked list head; return TRUE and
// value of previous pointer if found; otherwise return FALSE
template <class T>
int Find(Node<T> *head, T& item, Node<T>* &prevPtr)
{
	// find node with value item and return 1 if found and
	// 0 otherwise.  also give access to the previous pointer
	// begin traversal at first node
	Node<T> *currPtr = head;

	prevPtr = NULL;
	
	// cycle through the list until end of list
	while(currPtr != NULL)
	{
		// compare data field with item and return if
		// successful; otherwise, go to the next node
		if (currPtr->data == item)
		{
			item = currPtr->data;
			return 1;
		}
		prevPtr = currPtr;
		currPtr = currPtr->NextNode();
	}
	
	// failed to locate item
	return 0;
}

// insert item at the front of list
template <class T>
void InsertFront(Node<T>* & head, T item)
{
    // allocate new node so it points to original list head
    // update the list head
    head = GetNode(item,head);
}

// find rear of the list and append item
template <class T>
void InsertRear(Node<T>* & head, const T& item)
{
    Node<T>  *newNode, *currPtr = head;

	// if list is empty, insert item at the front
    if (currPtr == NULL)
        InsertFront(head,item);
    else
    {
		// find the node whose pointer is NULL
    	while(currPtr->NextNode() != NULL)
    		currPtr = currPtr->NextNode();
    		
    	// allocate node and insert at rear (after currPtr)
        newNode = GetNode(item);
        currPtr->InsertAfter(newNode);
    }
}               

// delete the first node of the list
template <class T>
void DeleteFront(Node<T>* & head)
{
	// save the address of node to be deleted
    Node<T> *p = head;

	// make sure list is not empty
    if (head != NULL)
    {
	// move head to second node and delete original
        head = head->NextNode();
        delete p;
    }
}

// delete the first occurrence of key in the list
template <class T>
void Delete (Node<T>* & head, T key)
{
   // currPtr moves through list, trailed by prevPtr
   Node<T>  *currPtr = head, *prevPtr = NULL; 

   // return if the list is empty
   if (currPtr == NULL)
      return;
      
   // cycle list until key is located or come to end
   while (currPtr != NULL && currPtr->data != key)
   {
      // advance currPtr so prevPtr trails it
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
   }

   // if currPtr != NULL, key located at currPtr.
   if (currPtr != NULL)
   {
      // prevPtr == NULL means match at front node
      if(prevPtr == NULL)
         head = head->NextNode();
      else
         // match occurred at 2nd or subsequent node
         // prevPtr->DeleteAfter() unlinks the node
         prevPtr->DeleteAfter();

      // dispose of the node
      delete currPtr;
   }
}

// insert item into the ordered list
template <class T>
void InsertOrder(Node<T>* & head, T item)
{
    // currPtr moves through list, trailed by prevPtr
    Node<T> *currPtr, *prevPtr, *newNode;
    
    // prevPtr == NULL signals match at front
    prevPtr = NULL;
    currPtr = head;
    
    // cycle through the list and find insertion point
    while (currPtr != NULL)
    {
	// found insertion point if item < current data
	if (item < currPtr->data)
		break;
			
	// advance currPtr so prevPtr trails it
        prevPtr = currPtr;
        currPtr = currPtr->NextNode();
    }   

    // make the insertion
    if (prevPtr == NULL)
	// if prevPtr == NULL, insert at front
        InsertFront(head,item);
    else
    {
	// insert new node after previous
        newNode = GetNode(item);
        prevPtr->InsertAfter(newNode);
    }
}

// delete all the nodes in the linked list
template <class T>
void ClearList(Node<T> * &head)
{
    Node<T> *currPtr, *nextPtr;

	// chain through the list deleting nodes
    currPtr = head;
    while(currPtr != NULL)
    {
	// record address of next node, delete current node
        nextPtr = currPtr->NextNode();
        delete currPtr;
        
        // move current node forward
        currPtr = nextPtr;
    }

    // mark list as empty
    head = NULL;
}

#endif  // NODE_LIBRARY

程序9.1 ：匹配毽值

#include <iostream.h>
#pragma hdrstop

#include "node.h"
#include "nodelib.h"
#include "random.h"

void main(void)
{
    // set list head to NULL
    Node<int> *head = NULL, *currPtr;
    
    int i, key, count = 0;
    RandomNumber rnd;

    // insert 10 random integers at front of list
    for (i=0;i < 10;i++)
        InsertFront(head, int(1+rnd.Random(10)));
        
    // print the original list
    cout << "List: ";
    PrintList(head,noNewline);
    cout << endl;
    
    // prompt user for an integer key
    cout << "Enter a key: ";
    cin >> key;
    
    // cycle through the list
    currPtr = head;
    while (currPtr != NULL)
    {
        // if data matches key, increment count
        if (currPtr->data == key)
            count++;
            
        // move to the next node of the list         
        currPtr = currPtr->NextNode();
    }
    
    cout << "The data value " << key << " occurs " << count
         << " times in the list" << endl;
}

/*
<Run of Program 9.1>

List: 3  6  5  7  5  2  4  5  9  10
Enter a key: 5
The data value 5 occurs 3 times in the list
*/
程序9.2 ：乱字
#include <iostream.h>
#pragma hdrstop

#include "random.h"
#include "strclass.h"
#include "nodelib.h"

void main(void)
{

    // node list to hold jumbled characters
    Node<char> *jumbleword = NULL;

    // input string, random number generator, counters
    String  s;
    RandomNumber rnd;
    int i, j;
    
    // input four strings
    for (i = 0; i < 4; i++)
    {
        cin >> s;
        // use Random(2) to determine if char moves to
        // front (value = 0) or rear (value = 1) of list
        for (j = 0; j < s.Length(); j++)
            if (rnd.Random(2))
                InsertRear(jumbleword, s[j]);
            else
                InsertFront(jumbleword, s[j]);

        // print the input string and its jumbled variation
        cout << "String/Jumble: " << s << "   ";
        PrintList(jumbleword);
        cout << endl << endl;
        ClearList(jumbleword);
    }
 }

/*      
<Run of Program 9.2>

pepper
String/Jumble: pepper   r  p  p  e  p  e

hawaii
String/Jumble: hawaii   i  i  h  a  w  a

jumble
String/Jumble: jumble   e  b  m  j  u  l

C++
String/Jumble: C++   +  C  +
*/
程序9.3：毕业生名单 

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <iomanip.h>
#pragma hdrstop

#include "node.h"
#include "nodelib.h"
#include "studinfo.h"

void main(void)
{
    Node<StudentRecord> *graduateList=NULL,
                        *currPtr, *prevPtr,
                        *deletedNodePtr;
    StudentRecord srec;
    ifstream fin;

    fin.open("studrecs",ios::in | ios::nocreate);
    if (!fin)
    {
        cerr << "Cannot open file studrecs." << endl;
        exit(1);
    }
    
    // print gpa with one decimal place
    cout.setf(ios::fixed);
    cout.precision(1);
    cout.setf(ios::showpoint);
    
    while(fin >> srec)
    {
        // insert srec at the head of the list
        InsertFront(graduateList,srec);
    }
        
    prevPtr = NULL;                  // prevPtr trails currPtr
    currPtr = graduateList;          // currPtr at start of list
    while (currPtr != NULL)          // traverse to end of list
    {
        if (currPtr->data.gpa < 2.0) // does student graduate?
        {
            if (prevPtr == NULL)     // student at front of list?
            {
                graduateList = currPtr->NextNode();
                deletedNodePtr = currPtr;
                currPtr = graduateList;
            } 
            else    // delete node inside the list
            {
                currPtr = currPtr->NextNode();
                deletedNodePtr = prevPtr->DeleteAfter();
            }
            delete deletedNodePtr;  // remove deleted node
        }
        else
        {
            // no deletion. move on down list
            prevPtr = currPtr;
            currPtr = currPtr->NextNode();
        }
    }
    fin.close();
    
    fin.open("noattend",ios::in | ios::nocreate);
    if (!fin)
    {
        cerr << "Cannot open file noattend." << endl;
        exit(1);
    }
    
    while(srec.name.ReadString(fin) != -1)
        Delete(graduateList,srec);
    
    cout << "Students attending graduation:" << endl;
    PrintList(graduateList,addNewline);
}

/*
<File "studrecs">
Julie Bailey
1.5
Harold Nelson
2.9
Thomas Frazer
3.5
Bailey Harnes
1.7
Sara Miller
3.9
Nancy Barnes
2.5
Rebecca Neeson
4.0
Shannon Johnson
3.8

<File "noattend">
Thomas Frazer
Sara Miller

<Run of Program 9.3>
Students attending graduation:
Shannon Johnson  3.8
Rebecca Neeson  4.0
Nancy Barnes  2.5
Harold Nelson  2.9

*/
程序9.4：表插入排序 

#include <iostream.h>
#pragma hdrstop

#include "node.h"
#include "nodelib.h"

template <class T>
void LinkSort(T a[], int n)
{
    // set up the linked list ordlist to hold array items
    Node<T> *ordlist = NULL, *currPtr;
    int i;
    
    // insert the elements from the array to the list in order 
    for (i=0;i < n;i++)
        InsertOrder(ordlist, a[i]);
        
    // scan the list and copy the data values back to the array
    currPtr = ordlist;
    i = 0;
    while(currPtr != NULL)
    {
        a[i++] = currPtr->data;
        currPtr = currPtr->NextNode();
    }
    
    // delete all the nodes created for the ordered list
    ClearList(ordlist); 
}

// scan the array and print its elements
void PrintArray(int a[], int n)
{
    for(int i=0;i < n;i++)
        cout << a[i] << "  ";
}

void main(void)
{
    // initialized array with 10 integer values
    int A[10] = {82,65,74,95,60,28,5,3,33,55};
    
    LinkSort(A,10);                     // sort the array
    cout << "Sorted array:     ";
    PrintArray(A,10);                   // print the array      
    cout << endl;
}

/*
<Run of Program 9.4>

Sorted array:     3  5  28  33  55  60  65  74  82  95
*/
程序9.5：表选择排序 

#include <iostream.h>
#pragma hdrstop

#include "link.h"           // include the linked list class
#include "random.h"

// position the list L at its maximum element
template <class T>
void FindMax(LinkedList<T> &L)
{
    if (L.ListEmpty())
    {
        cerr << "FindMax: list empty!" << endl;
        return;
    }

    // reset to start of the list
    L.Reset();
    
    // record first list value as current maximum with position 0
    T max = L.Data();
    int maxLoc = 0;
    
    // move to second data value and scan the list
    for (L.Next(); !L.EndOfList(); L.Next())
        if (L.Data() > max)
        {
            // new maximum. record value and the list position
            max = L.Data();
            maxLoc = L.CurrentPosition();
        }
        
    // reset the list back to the maximum value
    L.Reset(maxLoc);
}

// print list L
template <class T>
void PrintList(LinkedList<T>& L)
{
    // move to front of L. traverse list and print each element
    for(L.Reset(); !L.EndOfList(); L.Next())
        cout << L.Data() << "  ";      
}

void main(void)
{
    // list L is placed in sorted order in list K
    LinkedList<int> L, K;
    RandomNumber rnd;
    int i;
    
    // L is a list of 10 random integers in range 0-99
    for(i=0; i < 10; i++)
        L.InsertRear(rnd.Random(100));

    cout << "Original list: ";
    PrintList(L);
    cout << endl;
    
    // delete data from L until it is empty, inserting into K
    while (!L.ListEmpty())
    {
        // locate max of remaining elements
        FindMax(L);
        
        // insert max at front of list K and delete it from L
        K.InsertFront(L.Data());
        L.DeleteAt();
    }
    
    cout << "Sorted list:   ";
    PrintList(K);
    cout << endl;
}

/*
<Run of Program 9.5>

Original list: 82  72  62  3  85  33  58  50  91  26
Sorted list:   3  26  33  50  58  62  72  82  85  91
*/
程序9.6：删除重复值 

#include <iostream.h>
#pragma hdrstop

#include "link.h"       // include the linked list class
#include "random.h"

// print list L
template <class T>
void PrintList(LinkedList<T>& L)
{
    // move to front of L. traverse list and print each element
    for(L.Reset(); !L.EndOfList(); L.Next())
        cout << L.Data() << "  ";
}

void RemoveDuplicates(LinkedList<int>& L)
{
    // current list position and data value
    int currPos, currValue;
    
    // move to the front of the list
    L.Reset();
    
    // cycle through the list
    while(!L.EndOfList())
    {
        // record the current list data value and its position
        currValue = L.Data();
        currPos = L.CurrentPosition();
        
        // move one node to the right
        L.Next();
        
        // move forward until end of list, deleting
        // all occurrences of currValue
        while(!L.EndOfList())
            // if node deleted, current position is next node
            if (L.Data() == currValue)
                L.DeleteAt();
            else
                L.Next();               // move to the next node
                
        // move to first node with value currValue. go forward
        L.Reset(currPos);
        L.Next();
    }
}
        
void main(void)
{
    LinkedList<int> L;
    int i;
    RandomNumber rnd;
    
    // insert 15 random integers in range 1-7 and print list
    for(i=0; i < 15; i++)
        L.InsertRear(1+rnd.Random(7));
    cout << "Original list: ";
    PrintList(L);
    cout << endl;
        
    // remove all the duplicate data values and print new list
    RemoveDuplicates(L);
    cout << "Final list:    ";
    PrintList(L);
    cout << endl;
}

/*
<Run of Program 9.6>

Original list: 1  7  7  1  5  1  2  7  2  1  6  6  3  6  4
Final list:    1  7  5  2  6  3  4
*/
程序9.7a：表类——数组实现 

#include <iostream.h>
#pragma hdrstop

// use DataType = int to store integer values in the list
typedef int DataType;

// include the array-based SeqList class
#include "aseqlist.h"

void main(void)
{
    // a list with capacity 500 integers
    SeqList L;
    long  i;
    
    // initialize the list with values 0 .. 499
    for (i = 0; i < 500; i++)
        L.Insert(int(i));
        
    // exercise the delete/insert operations 50000 times
    cout << "Program begin!" << endl;
    for (i = 1; i <= 50000L; i++)
    {
        L.DeleteFront();
        L.Insert(0);
   }
    cout << "Program done!" << endl;
}

/*
<Run of Program 9.7a>

Program begin!
Program done!       // 55 seconds

*/
程序9.7a：表类——链表实现 
#include <iostream.h>
#pragma hdrstop

// include the linked list implementation of the SeqList
#include "seqlist1.h"

void main(void)
{
    // define an integer list
    SeqList<int> L;
    long  i;
    
    // initialize the list with values 0 .. 499
    for (i = 0; i < 500; i++)
        L.Insert(int(i));
        
    // exercise the delete/insert operations 50000 times
    cout << "Program begin!" << endl;
    for (i = 1; i <= 50000L; i++)
    {
        L.DeleteFront();
        L.Insert(0);
    }
    cout << "Program done!" << endl;
}

/*
<Run of Program 9.7b>

Program begin!
Program done!   // 4 seconds
*/

程序9.9: Josephus问题
略
#include <iostream.h>
#pragma hdrstop

#include "cnode.h"
#include "random.h"

// create circular linked list with given header node
void CreateList(CNode<int> *header, int n)
{
    // begin inserting after the header
    CNode<int> *currPtr = header, *newNodePtr;
    int i;
    
    // build the n element circular list
    for(i=1;i <= n;i++)
    {
        // allocate node with data value i
        newNodePtr = new CNode<int>(i);
        
        // insert at end of the list and advance currPtr to end
        currPtr->InsertAfter(newNodePtr);
        currPtr = newNodePtr;
    }
}

// given an n item circular list, solve the Josephus problem
// by deleting every m th person until only one remains.
void Josephus(CNode<int> *list, int n, int m)
{
    //prevPtr trails currPtr around the list.
    CNode<int> *prevPtr = list, *currPtr = list->NextNode();
    
    CNode<int> *deletedNodePtr;
    
    // delete all but one person from the list
    for(int i=0;i < n-1;i++)
    {
        // counting current person at currPtr, visit m persons.
        // we must advance m-1 times.
        for(int j=0;j < m-1;j++)
        {
            // advance the pointers
            prevPtr = currPtr;
            currPtr = currPtr->NextNode();
            
            // if currPtr at the header, move pointers again
            if (currPtr == list)
            {
                prevPtr = list;
                currPtr = currPtr->NextNode();
            }
        }

        cout << "Delete person " << currPtr->data << endl;
        
        // record node to delete and advance currPtr
        deletedNodePtr = currPtr;
        currPtr = currPtr->NextNode();
        
        // delete node from the list
        prevPtr->DeleteAfter();
        delete deletedNodePtr;
        
        // if currPtr at the header, move pointers again
        if (currPtr == list)
        {
            prevPtr = list;
            currPtr = currPtr->NextNode();
        }
    }
    
    cout << endl << "Person " << currPtr->data
         << " wins the cruise." << endl;
    
    // delete the one remaining node
    deletedNodePtr = list->DeleteAfter();
    delete deletedNodePtr;
}

void main(void)
{
    // the list of persons
    CNode<int> list;
    
    // n is number of persons, m is rotation selector
    int n, m;
    // use to generate random value 1 <= m <= n
    RandomNumber rnd;
    
    cout << "Enter the number of contestants? ";
    cin >> n;
    
    // create circular list with persons 1, 2, ... n
    CreateList(&list,n);

    m = 1+rnd.Random(n);
    cout << "Generated the random number " << m << endl;
    
    // solve the Josephus problem and print the cruise winner
    Josephus(&list,n,m);
}

/*
<Run of Program 9.9>

Enter the number of contestants? 10
Generated the random number 5
Delete person 5
Delete person 10
Delete person 6
Delete person 2
Delete person 9
Delete person 8
Delete person 1
Delete person 4
Delete person 7

Person 3 wins the cruise.
*/
程序9.10: 用双向链表排序

#include <iostream.h>
#pragma hdrstop

#include "dnode.h"

template <class T>
void InsertLower(DNode<T> *dheader, DNode<T>* &currPtr, T item)
{
    DNode<T> *newNode= new DNode<T>(item), *p;
    
    // look for the insertion point
    p = currPtr;
    while (p != dheader && item < p->data)
        p = p->NextNodeLeft();

    // insert the item
    p->InsertRight(newNode);

    // reset currPtr to the new node
    currPtr = newNode;
}

template <class T>
void InsertHigher(DNode<T>* dheader, DNode<T>* & currPtr, T item)
{
    DNode<T> *newNode= new DNode<T>(item), *p;
    
    // look for the insertion point
    p = currPtr;
    while (p != dheader && p->data < item)
        p = p->NextNodeRight();

    // insert the item
    p->InsertLeft(newNode);

    // reset currPtr to the new node
    currPtr = newNode;
}

template <class T>
void DLinkSort(T a[], int n)
{
    // set up the doubly linked list to hold array items
    DNode<T> dheader, *currPtr;
    int i;
    
    // insert the first element in dlist 
    DNode<T>  *newNode = new DNode<T>(a[0]);
    dheader.InsertRight(newNode);
    currPtr = newNode;

    // insert the remaining elements in dlist 
    for (i=1;i < n;i++)
        if (a[i] < currPtr->data)
            InsertLower(&dheader,currPtr,a[i]);
        else
            InsertHigher(&dheader,currPtr,a[i]);

    // scan the list and copy the data values back to the array
    currPtr = dheader.NextNodeRight();
    i = 0;
    while(currPtr != &dheader)
    {
        a[i++] = currPtr->data;
        currPtr = currPtr->NextNodeRight();
    }
    
    // delete all nodes in the list
    while(dheader.NextNodeRight() != &dheader)
    {
        currPtr = (dheader.NextNodeRight())->DeleteNode();
        delete currPtr;
    }
}

// scan the array and print its elements
void PrintArray(int a[], int n)
{
    for(int i=0;i < n;i++)
        cout << a[i] << "  ";
}

void main(void)
{
    // initialized array with 10 integer values
    int A[10] = {82,65,74,95,60,28,5,3,33,55};
    
    DLinkSort(A,10);                     // sort the array
    cout << "Sorted array:     ";
    PrintArray(A,10);                   // print the array      
    cout << endl;
}

/*
<Run of Program 9.10>

Sorted array:     3  5  28  33  55  60  65  74  82  95
*/




1