Data Structures and Algorithms 4 - edX

Ming Zhang" Data Structures and Algorithms "

Data Structures and Algorithms4

Instructor: Ming Zhang Textbook Authors: Ming Zhang, Tengjiao Wang and Haiyan Zhao Higher Education Press, 2008.6 (the "Eleventh Five-Year" national planning textbook)



Chapter Four

Strings

Outline

Outline

? The Basic Concept of Strings ? The Storage Structure of Strings ? The Implementation of Strings'

Operations ? Pattern Matching for Strings

? Na?ve Algorithm ? KMP Fast String Matching

2

Ming Zhang "Data Structures and Algorithm"

Chapter Four

Strings

4.1 The Basic Concept of Strings

Examples for Strings

? s1="123"

? s2="ABBABBC"

? s3="BB"

? s4="BB "

? s5="Hello World!"

? s5=""

3

Ming Zhang "Data Structures and Algorithm"

Chapter Four

Strings

4.1 The Basic Concept of Strings

4.1 The Basic Concept of Strings

? Stringsa special kind of Linear Lists whose element is Character

? Finite Sequence with n ( 0 ) charactersn 1noted as S : "c0c1c2...cn-1"

? S is the name of String

? "c0c1c2...cn-1" is the value of String ? ci is the character in String ? N is the length of the stringThe number of

characters in a String. ? Empty Stringits length is 0and don't contain any characters.Note its difference with " Blank String"

4

Ming Zhang "Data Structures and Algorithm"

Chapter Four

Strings

4.1 The Basic Concept of Strings

String - a special kind of Linear Lists

? Data Object

? No special limitation

? Data Object of a String is called as Character Set

? Basic Operation

? The operating object of most Linear Lists is "element unit"

? Strings always use "the whole string" as the operating object

? The storage method of Linear Lists can be applied in Strings

? Choose storage method according to different situations

5

Ming Zhang "Data Structures and Algorithm"

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download