Java Reference
In-Depth Information
Swap
s[0]
and
s[s.length() - 1];
Swap
s[1]
and
s[s.length() - 2];
Swap
s[2]
and
s[s.length() - 3];
…
The invariant must state what has and what has not been swapped into its
final position thus far. Based on the above sequence of statements, we see that
there is a prefix and a suffix of
s
that contain their final values, while the middle
remains to be reversed. We use two variables
k
and
n
to define the boundaries of
these three segments of
t
and write the invariant as:
inv:
s[0..k-1]
and
s[n+1..]
contain their final values, and
s[k..n]
remains to be reversed
How does it start?
By setting
k
to
0
and
n
to
b.length() - 1
, so that the prefix
and suffix that contain their final values are empty.
When does it stop?
The loop can stop when the middle segment contains at
most one character, because then the middle segment is its own reverse. On the
other hand, when the middle segment contains more than one element, that is,
when
k<n
, more elements need to be reversed.
How does it make progress?
By incrementing
k
or decrementing n (or both).
How does it fix the invariant?
The elements
s[k]
and
s[n]
need to be
swapped. Then
k
can be incremented and
n
decremented.
This completes the development of the program segment —see Fig. 7.5.
Remarks
Using
k!=n
as the loop condition is incorrect because it is not guaranteed
//
Set
t
to the reverse of
t
StringBuffer s=
new
StringBuffer(t);
int
k= 0;
int
n= s.length() - 1;
// {
invariant:
s[0..k-1]
and
s[n+1..]
contain their final values, and
// s[k..n]
remains to be reversed
}
while
(k < n) {
char
c= s.getChar(k);
s.setChar(k, s.getChar(n));
s.setChar(n, c);
k= k + 1;
n= n - 1;
}
t= s.toString();
Figure 7.5:
Reversing a
String
Search WWH ::
Custom Search