数据结构英文课件：Chap4 String

1、Chap4 StringOverview String Implementation of String Basic operations Strings pattern matching algorithmString String is a character sequence composing zero or several characters; Strings general form is: s=“s1s2s3sn”; si(1in) is a random character called the element of the string, i is sis position

2、 number in the whole string; We call the special string of size 0 is an empty string, marked by .String We call any sub-sequence composing of several consecutive characters a substring; The position of a substring in the whole string is the position of its first characters position in the whole stri

3、ng; When two strings have equal size and the same character in the corresponding position, we deem the two strings are equal.Implementation of String Array Implementation 1 #define MAXSIZE 256 typedef struct char SMAXSIZE; int curlen; SeqString;Implementation of String Array Implementation 2 The str

4、ing is ended up by a specific character 0. Implementation of String Linked List Implementation The string is stored into a single linked list. Though it is feasible, it will bring space waste. So we sometimes store a substring in one node of the linked list, its called block-storage. Basic Operation

5、s StrLength(s): returns the length of the string StrAssign(s1, s2): copy s2 to s1 StrConcat(s1, s2): connect s2 in the end of s1 SubStr(s, i, len): get a substring of size len from the position i of s CmpStr(s1, s2): compare two strings s1, s2 StrIndex(s, t): find the position of string t in the str

6、ing s Basic Operations StrInsert(s, i, t): insert t into s on the position i of t StrDelete(s, i, len): delete a substring of size len from the position of string s StrRep(s, t, r): replace any string t appeared in the string s by string r Pattern Matching Strings pattern matching is a very important string operation; The procedure of finding substring t in the given string s is called pattern matching; When found, the routine retur