Hello everyone, thie lecture
we start the study of the 4th chapter of
Data Structure and Algorithm.
Today we first introduce
the related concept of Character String.
Often in input and output, there is
some hints
and some information.
Those are some instances of String.
String is a special linear structure.
It is limited sequence
made up of characters.
We call the String from c0 to cn-1
as s
s its name
c0 to cn-1
is its String value.
Every element ci
is the character inside.
The number of characters of the String
is its length.
The length is also pretty important.
When the length is known,
we can reserve corresponding space
when applying space in memory.
If the length is 0,
it is an empty string.
An empty String is different from
such string
that is represented with double quotation marks
and space in the middle.
Empty string is a valid string without any character.
It is directly an end character.
What is the main difference
between string and normal linear structure
First, for normal linear structure,
the element
does not have special limitation.
Any type is okay.
For string,
the element must be character
For operations,
normal linear list
does not have special limitation.
It is okay to read from middle
or from either side.
There is no limitation about how many to read, too.
But for string,
a substring inside as a whole
is often used.
That is, we operate towards
to succession number of characters.
String is a special expression
of linear list.
When stored,
it is similar as
normal linear structure.
But note that,
because the basic element of string is character.
If you implement with link.
It has large pointer
such a structural cost.
The storage efficiency is low.
Related operations do not
have much improvement.
So
the storage of string
usually use sequential storage.
For string,
let us see
which can be character.
It is, in fact, related to your application.
For code made up in binary system,
the basic character set is 0, 1.
If it is DNA sequence,
such string,
the character set is A C G T
Different application may have
different basic character set.
If we know such character set,
in some algorithm,
we can use the feature
to improve the efficiency.
For character encoding,
we use ASCII most.
It can encode common characters.
In C and C++,
ASCII is used.
But for some complicated language,
such as Chinese, the east language,
if only 8 bits
that is, 1 byte is used.
It must not be enough
Then double bytes are needed.
For double bytes,
there are also different encoding system.
such as GB code formulated in China.
and the international standard UNICODE
along with the populization of internet.
Not only chinese,
but also such complicated language
as Japenese, Korean and Arabic
are included in the UNICODE.
encoding system.
After encoding,
how to judge two strings
even the big or small.
That is decided by
the encoding order of character.
The encoding order is
usually related to lexicographical order.
In some case,
some special requirements may be followed.
For example, in Chinese,
you can encode according to strokes.
For the data structure of string
in different language
there are different opinions.
In some early language system,
string are supposed to
have a complicated structure.
It is not a simple basic structure.
Now,
string is a very important
and basic datastructure.
So we take it
as a simple type.
For string,
we have some constant
and some can be regarded as variable.
In C or C++,
the characters between
double quotation marks
is a string constant.
We can define different variables
and do some flexiable
operations to string.
In string,
there is a very important concept.
That is substring.
If I have a string s1,
that is from a0 to an-1,
and another string s2
from b0 to bm-1
For s1
we take a substring in the middle
from index iv.
ai is corresponding to b0
a's i+j is conrresponding to bj
If the corresponding characters
are the same to each other
all the way from b0 to bm-1
It can just match.
In s1, it is corresponding ai to ai+m-1.
We can say
the s2
is a sub string of s1.
and s1
is the set string of s2.
Empty string is substring of any string.
Besides, any string is substring
of itself.
Another concept is true substring.
the true substring is like this,
if inside a set string
there is a substring
which
neither empty
nor the set string itself.
That is the true substring.
Let us see
some basic operation of string.
Because C++
inherits many contents
of the standard functioin library of C.
For string
such operations
are very fundamental.
If only C is used,
we need include "string.h"
In such operation,
many is towards to substring.
such as copy, concate.
Others are to seek substring.
then to compare between strings.
They are all upon the whole string.
In addition, to locate
a specific character in the string
such operation.
Besides is to get the length of the string.
Note about
the comparison between strings
for two strings s1 and s2,
if s1 is bigger than s2,
the strcmp
returns a value bigger than 0.
If s1 is smaller than s2,
a value smaller than 0 is returned.
Only if the characters in corresponding position
are the same in s1 and s2 with each other,
it returns 0.
The comparison of string
as according to the lexicographical order.
Let's see the location function,
in the string s,
to find the first appearance of character o
we go from the start position,
the 0 position, to right
to find its first appearance.
It is at the index 4.
Then we return 4.
There is a corresponding
reverse search.
that is from right to left.
If we invoke
the reverse search function.
We will get
in the string
the position of index 7.
In C++ standard string class library,
there are many functions.
If we want to use it
we should first include "string.h".
and make a statement that
I will use the namespace of std
For C++ string,
variable-length string is suit.
we use dynamic storage strategy.
Let us see some function definition
of C++ class library.
We can see many operations
is doing towards substring.
such as copy, exchange
copy, insert, concate,
replace, eliminate
of course and finding substring
such a operation
They are all operations
under the meaning of the substring.
Besides,
there is a statistics
about the length of the string
and the space that it can accommodate.
The operations are related.
especially the query operation
is a very important operation.
In a set string,
I specify a subsequence.
And you return the start position
of the sequence in the set string.
This is related to
the pattern match algorithm that we will take about later.
In character string,
locate operation is also an important operation.
We can locate according to its subscript.
Here we overload the subscript operator
[]
For such a string,
I can assign its subscript i,
and s[i]
returns corresponding character
at the ith position in the array
And to assign the start position of the string
From the start position
to right until the end of the string.
to find the first appearance
of char C.
Reverse search is from
a specified position
in the way from the end of the string
to the start
that is, from right to left,
to find the first appearance of C
At last, I'll leave some quizes.
Let us judge
which string behind
is substring of
software
The second quiz is
for the string software.
how many substrings are there?
Thank you.