《数据结构英文课件：Chap4 String》由会员分享，可在线阅读，更多相关《数据结构英文课件：Chap4 String（12页珍藏版）》请在金锄头文库上搜索。
1、Chap4 StringOverviewStringImplementation of StringBasic operationsStrings pattern matching algorithmStringString 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 number
2、 in the whole string;We call the special string of size 0 is an empty string, marked by .StringWe 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 string;When tw
3、o strings have equal size and the same character in the corresponding position, we deem the two strings are equal.Implementation of StringArray Implementation 1 #define MAXSIZE 256 typedef struct char SMAXSIZE; int curlen; SeqString;Implementation of StringArray Implementation 2 The string is ended
4、up by a specific character 0. Implementation of StringLinked 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 OperationsStrLength(s):
5、 returns the length of the stringStrAssign(s1, s2): copy s2 to s1StrConcat(s1, s2): connect s2 in the end of s1SubStr(s, i, len): get a substring of size len from the position i of sCmpStr(s1, s2): compare two strings s1, s2StrIndex(s, t): find the position of string t in the string s Basic Operatio
6、nsStrInsert(s, i, t): insert t into s on the position i of tStrDelete(s, i, len): delete a substring of size len from the position of string sStrRep(s, t, r): replace any string t appeared in the string s by string r Pattern MatchingStrings pattern matching is a very important string operation;The p
7、rocedure of finding substring t in the given string s is called pattern matching;When found, the routine returns the first matching position. If not found, returns 0. Example 4.1Simple pattern matching algorithmint StrIndex_BFint StrIndex_BF(char *s, char *t)(char *s, char *t) int i=1,j=1; int i=1,j=1; while (i=s0 & j=t0 ) while (i=s0 & jt0) if (jt0) return (i-t0); return (i-t0); else else return 0; return 0;
