cdat

一本全面剖析C++数据结构算法的书籍

is given in ?P{lstackclass}.
.KF
.hl
.nf
.ft CW
template<class type>
class LinkedStack : protected Chain<type> {
public:
   int IsEmpty() {return Chain<type>::IsEmpty();}
   int IsFull();
   int Top(type& x) {return Find(1, x);}
   int operator +(type& x) {return Insert(0, x);}
   int operator -(type& x) {return Delete(1, x);}
};

template<class type>
int LinkedStack<type>::IsFull()
{
ChainNode<type> *i;
i = new ChainNode<type>;
if (i) {delete i; return 0;};
return 1;
}
.ft R
.fi
.hl
\fB?P{lstackclass}:\fR Class definition for a linked stack
.KE
.pp
The implementation of @IsFull@ is inelegant as the only way to know
whether or not we can add an element to a stack is to see if enough
space exists to create a node of type @Node@.  This is done by
invoking \fBnew\fR and then deleting the created node as we do not
intend to use it.
As in the case of the class @Stack@ (?P{stackclass}), we can improve the
run time performance by customizing the code.  The customized code
is given in ?P{clstack}.
.KF
.hl
.nf
.ft CW
template<class type>
class LinkedStack : protected Chain<type>
{
public:
   int IsEmpty() {return first == 0;}
   int IsFull();
   int Top(type& x);
   int operator +(type x);
   int operator -(type& x);
};

template<class type>
int LinkedStack<type>::IsFull()
{
ChainNode<type> *i;
i = new ChainNode<type>;
if (i) {delete i; return 0;}
return 1;
}

template<class type>
int LinkedStack<type>::Top(type& x)
{//set x to top element
if (IsEmpty()) return 0; //Top fails
x = first->data;
return 1; //Top succeeds
}
.ft R
.fi
.hl
\fB?P{clstack}:\fR Customized linked stack
(continued on next page)
.KE
.KF
.hl
.nf
.ft CW
template<class type>
int LinkedStack<type>::operator+(type& x)
{//add x to stack
ChainNode<type> *i;
i = new ChainNode<type>;
if (i) {i->data = x; i->link = first;
        first = i; return 1;}
return 0; // add fails 
}

template<class type>
int LinkedStack<type>::operator-(type& x)
{//delete top element and return in x
if (IsEmpty()) return 0; //delete fails
x = first->data;
ChainNode<type> *i = first;
first = first->link;
delete i;
return 1;
}
.ft R
.fi
.hl
\fB?P{clstack}:\fR Customized linked stack
(continued from previous page)
.KE
.pp
The code of ?P{lstackclass} took 21% more time to execute
a \fBfor\fR loop of 100,000 add and delete
operations than did the customized code of ?P{clstack}.
.EX
.EH
.MB
.RS
.ip (a)
Obtain the code for the C++ class @LinkedStack@ without making use of the
class @Chain@.
.ip (b)
Write a program to measure the run time of an alternating sequence of
@n@ stack add and delete operations.  Measure the times needed
by Programs ?p{lstackclass}, ?p{clstack}, and your code of part (a).
.RE
.EH
Extend the class @LinkedStack@ to include the following stack operations:
.RS
.ip (a)
Determine the size (i.e., number of elements) of the stack.
.ip (b)
Input a stack.
.ip (c)
Print a stack.
.RE
.EH
Extend the class @LinkedStack@ to include the following operations:
.RS
.ip (a)
Split a stack into two.  The first contains the bottom half elements and the second the remaining elements.
.ip (b)
Combine two stacks into one by placing all elements of the second stack
on top of those in the first.  The relative order of elements from the
second stack is unchanged.
.RE
.LP
.oh "Applications"
.NH 2
APPLICATIONS
.NH 3
Parenthesis Matching
.LP
.sp
In this problem, we are to match the left and right parentheses in a
character string.  For example, the string (a*(b+c)+d) has left parentheses
at positions one and four and right parentheses at positions eight and eleven.
The left parenthesis at position one matches the right at position eleven
while the left parenthesis at four matches the right parenthesis at eight.
In the string (a+b))(, the right parenthesis at six has no matching
left parenthesis and the left parenthesis at seven has no matching
right parenthesis.  Our objective is to write a C++ program that inputs
a string and outputs the pairs of matched parentheses as well as those
parentheses for which there is no match.
.pp
We observe that if we scan the input string left-to-right then each right
parenthesis is matched to the most recently seen unmatched left parenthesis.
This motivates us to save the position of
left parentheses on a stack as they are encountered
in a left-to-right scan.  When a right parenthesis is encountered,
it is matched to the left parenthesis (if any) at the top of the stack.
The matched left parenthesis is deleted from the stack.  The complete C++
program is given in ?P{paren}.  A sample input / output dialogue is given
in ?F{paren}.  The time complexity of ?P{paren} is \(*H(@n@), where
@n@ is the length of the input string.
.KF
.hl
.nf
.ft CW
#include <iostream.h>
#include <string.h>
#include <stdio.h>
#include "stack.h"
const int MaxLength = 100; //max expression length
void PrintMatchedPairs(char *expr);
void main(void)
{
char expr[MaxLength];
cout << "Type an expression of length at most "
     << MaxLength << endl;
cin.getline(expr, MaxLength);
cout << "The pairs of matching parentheses in the expression" << endl;
puts(expr);
cout << "are" << endl;
PrintMatchedPairs(expr);
}

void PrintMatchedPairs(char *expr)
{
Stack<int> s(MaxLength);
int j, length = strlen(expr);
for (int i = 1; i <= length; i++) {
   if (expr[i - 1] == '(') s + i;
   else if (expr[i - 1] == ')')
	{if (s - j) cout << j << ' ' << i << endl;
      else cout << "No match for right parenthesis at "
                << i << endl;}
   }
while (!s.IsEmpty()) {
   s - j;
   cout << "No match for left parenthesis at " << j 
        << endl;}
}
.fi
.hl
\fB?P{paren}:\fR Program to output matched parentheses
.KE
.KF
.hl
.nf
Type an expression of length at most 100
(d+(a+b)*c*(d+e)-f))(()
The pairs of matching parentheses in the expression
(d+(a+b)*c*(d+e)-f))(()
are
4 8
12 16
1 19
No match for right parenthesis at 20
22 23
No match for left parenthesis at 21
.fi
.hl
\fB?F{paren}:\fR Sample run of parenthesis matching program
.KE
.NH 3 
Towers of Hanoi
.LP
.sp
The \*(LQTowers of Hanoi\*(ZQ problem
is fashioned after the ancient Tower of Brahma
ritual.  According to legend, at the time the world was created there
was a diamond tower (tower 1) with sixty four golden disks.  The disks were
of decreasing size and were stacked on the tower in decreasing
order of size bottom to top.
Besides this tower there are two other diamond towers (towers 2 and 3).
Since the time of creation,
Brahman priests have been attempting to move the disks from
tower 1 to tower 2 using tower 3 for intermediate storage.
As the disks are very heavy, they can be moved only one at a time.
In addition, at no time can a disk be on top of a smaller disk.
According to legend, the world will come to an end when the
priests have completed their task.
.KF
.hl
.PS
x = 1.3i; d=.9; e=.5
A:[B:line right x
   Y:B.c
   line from Y to Y+(0,2)
   line from Y-(d*x/2,0) to Y-(d*x/2,-.2)
   line from Y+(d*x/2,0) to Y+(d*x/2,.2)
   B:line from Y-(d*x/2,-.2) to Y+(d*x/2,.2)
   Y:B.c
   line from Y-(d*d*x/2,0) to Y-(d*d*x/2,-.2)
   line from Y+(d*d*x/2,0) to Y+(d*d*x/2,.2)
   B:line from Y-(d*d*x/2,-.2) to Y+(d*d*x/2,.2)
   Y:B.c
   line from Y-(d*d*d*x/2,0) to Y-(d*d*d*x/2,-.2)
   line from Y+(d*d*d*x/2,0) to Y+(d*d*d*x/2,.2)
   B:line from Y-(d*d*d*x/2,-.2) to Y+(d*d*d*x/2,.2)
   Y:B.c+(0,1)
   line from Y-(e*x/2,0) to Y-(e*x/2,-.2)
   line from Y+(e*x/2,0) to Y+(e*x/2,.2)
   line from Y-(e*x/2,0) to Y+(e*x/2,0)
   B:line from Y-(e*x/2,-.2) to Y+(e*x/2,.2)]
"Tower 1" at last [].s-(0,.2)
B:[B:line right x
   Y:B.c
   line from Y to Y+(0,2)] with .nw at A.ne+(.3,0)
"Tower 2" at last [].s-(0,.2)
C:[B:line right x
   Y:B.c
   line from Y to Y+(0,2)] with .nw at B.ne+(.3,0)
"Tower 3" at last [].s-(0,.2)
.PE
.hl
\fB?F{14.2}:\fR  Towers of Hanoi
.KE
.pp
In the \fITowers of Hanoi\fR problem\fR, we are given @n@ disks and three
towers.  The disks are initially stacked on tower 1 in decreasing
order of size bottom-to-top.  They are to be moved to tower 2, one disk
at-a-time such that no disk is ever on top of a smaller one.
You may wish to attempt a solution to this problem for
@n@ = 2, 3, and 4 before reading further.
.pp
A very elegant solution results from the use of recursion.
To get the largest disk to the bottom
of tower 2, we move the remaining @n^-^1@ disks to tower 3 and then move
the largest
to tower 2.  Now, we are left with the task of moving the 
@n^-^1@ disks from tower 3 to
tower 2.  To do this we have available the towers 1 and 2.  The fact that
tower 2 has a disk on it can be ignored as this disk is larger
that the disks being moved from tower 3 and so any disk can
be placed on top of it.
Recursive C++ code for this solution is provided in ?P{hanoi}.
The initial invocation is @TowersOfHanoi(n,1,2,3)@.
The correctness of ?P{hanoi} is easily established.
.KF
.nf
.hl
.ft CW
void TowersOfHanoi(int n, int x, int y, int z)
{//Move the top n disks from tower x to tower y
//Use tower z for intermediate storage
if (n > 0) {
   TowersOfHanoi(n-1, x, z, y);
   cout << "Move top disk from tower " << x 
        << " to top of tower " << y << endl;
   TowersOfHanoi(n-1, z, y, x);}
}
.ft R
.hl
\fB?P{hanoi}:\fR Recursive function for Towers of Hanoi
.fi
.KE
.pp
Let @t(n)@ be the time taken by ?P{hanoi}.  We see that
@t(n)@ is proportional to the number of lines of output
generated.  This is equal to the number of disk moves performed.
Examining ?P{hanoi}, we obtain the following recurrence
for the number of moves, @moves(n)@:
.sp
@moves(n)~=~ left { ~~lpile {0 above {2moves(n-1)~+~1}} ~~~lpile {n=0 above n>0}@
.sp
This recurrence may be solved using the substitution method of
Chapter 1.  The result is @moves(n)@ = @2 sup n ~-~1@.  One can show that
this is, in fact, the least number of moves in which the disks can be moved.