第四章 串和广义表Data Structure --String.ppt

第四章串和广义表§ String ? Concepts ? String ’ s ADT ? Implementation ? String/Pattern matching Concepts n String: a sequence which consists of zero or more letters. s= ‘a 1a 2…a n’ (n ≥ 0) n Jargons : u S, string name u‘a 1a 2…a n’, value u n, string length ua i, letter or character u n=0, Null String ), noted as Ф ua i = ‘’, blank string concepts u Substring u Substring ’ s position Example : s = ‘ I am a chinese ’; substring :s 1 = ‘ am ’, s 2 = ‘ chinese ’; position : 3 8 String ’ s ADT ADT String { objects : D={ a i|a i∈ CharacterSet ,i=1,2, …,n n ≥ 0} relation :R 1 ={< a i -1,a i >|a i -1,a i∈ D,i=1, 2, …, n} operations : StrEmpty ( S); pare ( S, T); index(T, S); String ’ s ADT StrLength ( S); ClearString ( &S ); Concat ( &T, S1, S2 ); SubString ( &Sub, S, pos , len ); Index( S, T, pos ); Replace( &S, T, V); StrInsert ( &S, pos , T); StrDelete ( &S, pos , len ); DestroyString (&S); } representation n Sequential representation n Linked representation Sequential representation # define MAXSTRING 255 typedef unsigned char SString [ MAXSTRLEN +1 ]; //element 0 stores the length of the string SString s; S[0] = 0; S[254] S[2] S[255] S[1] S[0] … Concat ( ) Status Concat ( SString T, SString S 1, SString S 2 ) { if( S 1 [0] + S 2 [0] <= MAXSTRLEN ) { T[ 1, … , S 1 [0] ] = S 1 [1, … S 1 [0]]; T[ S 1 [0] + 1 , … , S 1 [0] + S 2 [0] ] = S 2 [1, …, S 2 [0] ]; T[0] = S 1 [0] + S 2 [0]; return TRUE; } else if( S 1 [0] < MAXSTRLEN ) { T[ 1, … , S 1 [0] ] = S 1 [1, … S1[0]]; T[ S 1 [0]+1, … , MAXSTRLEN ] = S 2 [1, … , MAXSTRLEN –S 1 [0] ]; T[0] = MAXSTRLEN; return FALSE; } else { T[ 1, … , S 1 [0] ] = S 1 [1, … S 1 [0]]; T[0] = MAXSTRLEN; return FALSE; } }// Concat