Hello
this lecture of Data Structure and Algorithm
we continue the study of the 4th chapter Character String
Today we introduce the storage structure of string
and the implementation of basic operations.
In the case without much change of string length
there are a few classical solutions.
First we should consider
the length of string
because the string is a pretty dynamic
data structure
Its length is big for a while and small for a while.
How do we save this value?
In Pascal,
s0 is used to record its value.
But the drawback is that
we only have a byte to
save the length value.
So the entire length of string
can be no longer than 256.
Maybe I can save
this length value
in another variable.
But such method
can not support the dynamic implementation
of string well.
In C and C++
a special end symbol is used.
\0 means the end of a string.
In fact, the value of \0
is 0
and is equal to the NULL commonly used.
With such a constant,
string class can expediently
support the representation of string.
This is an array of string.
The string array str
and the length "size"
both are private members
that can not access directly.
we can visit such two values
through some function definitions.
In C and C++.
such basic operations are used
as get the length of string
and the copy of string.
and the join and comparison of strings.
Let us see the function of get string length.
Because we have such \0.
as the symbol of end.
It equals to
the end "next" field
of list
points to NULL
When we estimate the length
of the string
We first set the subscript i
as 0
Then we find one by one from 0.
If it is the ith that it equals to \0.
Then it ends.
the count number is
our string length.
For string copy,
we, in fact, can not use = directly
to copy it.
Because for the two strings,
they both have independently storage space.
We must copy every character
of s
to the target string d.
If you directly let d=s,
the result is that the storage address of
s is copyed to d.
The storage space that d keeps
disappears.
The process of copy
in fact, also starts from 0.
until the original string s
reach \0
we let, one by one,
d[i]=s[i]
Then the subscript i ++
At last,
We will manually let the value
at d[i] be \0.
This makes the string
a normal one.
The comparison of string
is very important in many operations.
The comparison operation
is according to the lexicographical order
We set the subscript variable i of the array
as 0.
Then we from s1 and s2
the corresponding position of i
compare one by one.
When they both don't finish,
we see whether the current position s1[i]
is bigger than s2[i]
If so, I return 1.
If s1[i] is smaller,
-1 is returned.
If they are equal,
we continue to compare the char value
at the next position.
Except for this cycle,
we have some other cases.
First is s1[i]
equals to \0.
That is, it finishes.
But s2[i] has not.
In this case, s1 is smaller than s2.
-1 is returned.
If s2 finishes,
but s1 not,
in this case,
s1 is bigger than s2
+1 is returned.
Otherwise, s1[i] and s2[i]
are both \0
They value of characters before are all equal.
and the end symbol
are also at the same position.
So they are completely equal.
Then 0 is returned.
The operation of comparing strings
has another simpler edition.
In this edition, \0 is regarded
as a special symbol.
and participate in the operation directly.
First we set the subscript variable i
to start from 0.
If s1[i] and s2[i]
are euqal at this position.
Then we continue the operation in this cycle.
Let us judge
whether the current s1[i] and s2[i]
are both equal to \0.
If so, they
happen to be equal
at the same position.
and end at the same position.
So they are equal.
If not equal,
let s1[i]-s2[i]
divided by the absolute value of the difference value.
If s1[i] is bigger,
+1 is returned.
If s1[i] is smaller,
-1 is returned.
Can they be equal here?
No!
Because the cycle sentence ahead
guarantee they won't jump out of the cycle
when they are equal.
Or in a special case,
they are equal
and equal to \0
then they jump out of the function and return 0.
So
we guarantee the denominator
is not equal to 0
The basic operation of string class
first of all, is constructor.
If I pass in string s
as its initial value.
We first get the length
of s, size
then I apply a storage space
of size+1
the +1 is for \0
We must guarantee
The storage space I apply is valid.
If in a special case,
we can not get storage space.
We should deal with this exception
and the programme exits.
After valid storage space is got
we call the copy function of string above.
copy the initial value s
to the new storage space
str
The destructor of string
mainly free the space
I have applyed.
Let us introduce the assignment operation
this =
is an overload of the operator
and make the corresponding operation
for us to write
very convenient
First we judge
whether the length
of the current string
is equal to
the target string
If not,
I free
the storage space of current string.
and apply another space
with the size of the length of target string s +1
and guarentee this space
is valid.
Then I set the length of current string
the same as s
Then I invoke the strcpy function
and set the value of the target string
as the value
of the original string.
Then we return this instance
that is return *this such a pointer.
After this
we can support
a continuous assignment operation
that is a continuous equal sign.
can be supported.
Leave you to have a think.
First, it is an operation
to get substring from String
that is, the implementation of Substr method.
The arguments passed in
is the start subscript of Substr
index
is equal to 6 here
Then I will continuously copy some chars,
here is 5.
Please implement
this function.
Pay attention to the handle of boundary
Then let us see these two questions.
For s1 and s2
the two string.
If the
+ here
is an overload
of String cate
and make s1+s2==s2+s1
Which requests should be satisfied.
For a string,
how do I do an operation
that reverse its value.
And I can not apply new storage space.
and make it
upon original space
For example of abcde,
I change it into edcba.
thank you.