第2章：线性表.pptVIP

Void DELETE( STRING S, STRING T ) { STRING t1, t2 ; int m, n ; m = INDEX( S, T ); if ( m==0 ) error ‘串S中不包含子串T’ ; else { n = LEN( T ) ; t1 = SUBSTR( S, 1, m - 1 ) ; t2 = SUBSTR( S, m + n, LEN( S ) ); S = CONCAT( t1, t2); } } 例二：从串 S 中将子串 T 删除DELETE( S, T )。 2.5.2 串的实现 1、串的顺序存储 采用连续的存储空间（数组），自第一个元素开始，依次 存储字符串中的每一个字符。 char str[ 10 ] =“China”； ‘C’ ‘h’ ‘i’ ‘n’ ‘a’ ‘\0’ 0 1 2 3 4 5 6 7 8 9 str 串的顺序存储 操作：NULL，ISNULL，IN，LEN，CONCAT，SUBSTR，INDEX 2、串的链式存储 构造线性链表，element类型为char，自第一个元素开始，依 次存储字符串中的每一个字符。 栈的基本① MAKENULL ( S ) 　操作　 ② TOP ( S ) ③ POP ( S ) ④ PUSH ( x , S ) ⑤ EMPTY ( S ) 例2：利用栈实现行编辑处理。 设定符号“#”为擦讫符，用以删 除“#”前的字符；符号“@”为删 行符，用以删除当前编辑行。 原理： 一般字符进栈； 读字符 擦讫符退栈； 删行符则清栈 算法： Void LINEEDIT( ) { STACK Ｓ； 　char c ; MAKENULL ( S ); c = getchar ( ) ; while ( c != ‘\n’ ) { if ( c == ‘#’ ) POP ( S ); else if ( c == ‘@’ ) MAKENULL ( S ); else PUSH ( c , S ); c = getchar( ); } 逆序输出栈中所有元素； ｝ 2.3.1 栈的实现 1、顺序存储 顺序栈示意图 a1 a2 a3 ··· ai ··· an 0 1 2 3 ··· ··· maxlength-1 top 结构类型： typedef struct { elementtype data[maxlength]; int top ; } STACK ; STACK S ; 栈的容量：maxlength – 1 ; 栈空：S.top = 0 ; 栈满：S.top = maxlength – 1 ; 栈顶元素：S.data[ S.top ] ; 操作： ① Void MAKENULL( STACK S ) { S.top = 0 ; } ; ② Boolean EMPTY( STACK S ) { if ( S.top 1 ) return TRUE else return FALSE ; } ; ③ elementtype TOP( STACK S ) { if EMPTY( S ) return NULL; else return ( S.data[ S.top ] ); }; 操作： ④ elementtype POP( STA