串与线性表的区别： ◆串的逻辑结构和线性表极为相似，区别仅在于串 的数据对象约束为字符集。 ◆ 然而，串的基本操作和线性表有很大差别。在线 性表的基本操作中，大多以“单个元素”作为操 作对象，如：在线性表中查找某个元素、求取某 个元素、在某个位置上插入一个元素和删除一个 元素等； ◆ 而在串的基本操作中，通常以“串的整体”作为 操作对象，如：在串中查找某个子串、求取一个 子串、在串的某个位置上插入一个子串以及删除 一个子串等
串与线性表的区别： ◆ 串的逻辑结构和线性表极为相似，区别仅在于串 的数据对象约束为字符集。 ◆ 然而，串的基本操作和线性表有很大差别。在线 性表的基本操作中，大多以“单个元素”作为操 作对象，如：在线性表中查找某个元素、求取某 个元素、在某个位置上插入一个元素和删除一个 元素等； ◆ 而在串的基本操作中，通常以“串的整体”作为 操作对象，如：在串中查找某个子串、求取一个 子串、在串的某个位置上插入一个子串以及删除 一个子串等
4.1.2 串的抽象数据类型定义 ADT String{ 数据对象：D={ala:∈CharacterSet,i=l,2,,n,n≥0} 数据关系：R={<a-l,a>a,a1∈D,=2,3,n} 基本操作： StrAssign(&T,chars) 初始条件：chars是串常量。 操作结果：赋于串T的值为chars。 StrCopy(&T,S) 初始条件：串S存在。 操作结果：由串S复制得串T。 DestroyString(&S) 初始条件：串S存在。 操作结果：串S被销毁
4.1.2 串的抽象数据类型定义 ADT String{ 数据对象：D = { ai |ai∈CharacterSet, i=1,2,…,n, n ≥0 } 数据关系：R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n } 基本操作： StrAssign (&T, chars) 初始条件：chars 是串常量。 操作结果：赋于串T的值为chars。 StrCopy (&T, S) 初始条件：串S 存在。 操作结果：由串S 复制得串T。 DestroyString (&S) 初始条件：串S 存在。 操作结果：串S 被销毁
StrEmpty (S) 初始条件：串S存在。 操作结果：若S为空串，则返回TRUE,否则返回FALSE。 StrCompare(S,T) 初始条件：串S和T存在。 操作结果：若S>T, 则返回值>0；若S=T,则返回值=0；若S<T, 则返回值<0。 StrLength(S) 初始条件：串S存在。 操作结果：返回串S序列中的字符个数，即串的长度。 ClearString(&S) 初始条件：串S存在。 操作结果：将S清为空串。 Concat(&T,S1,S2) 初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。 Replace(&S,T,V) 初始条件：串S,T和V存在，T是非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串
StrEmpty (S) 初始条件：串S 存在。 操作结果：若S 为空串，则返回TRUE，否则返回FALSE。 StrCompare (S, T) 初始条件：串S 和 T 存在。 操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T， 则返回值<0。 StrLength (S) 初始条件：串S 存在。 操作结果：返回串S 序列中的字符个数，即串的长度。 ClearString (&S) 初始条件：串 S 存在。 操作结果：将 S 清为空串。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 Replace (&S, T, V) 初始条件：串S，T 和 V 存在，T 是非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串
SubString(&Sub,S,pos,len) 初始条件：串S存在，l≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。 Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S).。 操作结果：若主串$中存在和串T值相同的子串，则返回它 在主串S中第pos个字符之后第一次出现的位置； 否则函数值为0。 StrInsert(&S,pos,T) 初始条件：串S和T存在，1≤pos≤StrLength(S)+1。 操作结果：在串S的第pos个字符之前插入串T。 StrDelete(&S,pos,len) 初始条件：串S存在，1≤pos≤StrLength(Slen+1。 操作结果：从串S中删除第pos个字符起长度为len的子串。 }ADT String
SubString (&Sub, S, pos, len) 初始条件：串S存在，1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果：用 Sub 返回串S的第 pos 个字符起长度为len的子串。 Index (S, T, pos) 初始条件：串S和T存在，T 是非空串， 1≤pos≤StrLength(S)。 操作结果：若主串S中存在和串T值相同的子串，则返回它 在主串S中第pos个字符之后第一次出现的位置； 否则函数值为0。 StrInsert (&S, pos, T) 初始条件：串S 和 T 存在，1≤pos≤StrLength(S)＋1。 操作结果：在串S 的第 pos 个字符之前插入串T。 StrDelete (&S, pos, len) 初始条件：串S 存在，1≤pos≤StrLength(S)-len+1。 操作结果：从串S 中删除第pos 个字符起长度为len 的子串。 } ADT String
定位函数（算法4.1) ● 基本思想：从主串S中取“第i个字符起、长度和串T相等的子串” 和串T比较，若相等，则求得函数值为i,否则i值增1直至找到相等 的子串或者不存在和T相等的子串为止。 int Index (String S,String T,int pos){ /T为非空串。若主串$中第pos个字符之后存在与T相等的子串， /则返回第一个这样的子串在$中的位置，否则返回0。 if (pos >0){ n StrLength(S);m=StrLength(T);i pos; while（i<∈n-mt1)[ SubString(sub,S,i,m);/取从第i个起长度为m的子串 if (StrCompare(sub,T)!=0)+i; else return i; /找到和T相等的子串 }/while /if return 0; //$中不存在满足条件的子串 }/Index
定位函数（算法4.1） ⚫ 基本思想：从主串S中取“第i个字符起、长度和串T相等的子串” 和串T比较，若相等，则求得函数值为i，否则i值增1直至找到相等 的子串或者不存在和T相等的子串为止。 int Index (String S, String T, int pos){ // T为非空串。若主串S中第 pos 个字符之后存在与T相等的子串， // 则返回第一个这样的子串在S中的位置，否则返回0。 if (pos > 0){ n = StrLength(S); m = StrLength(T); i = pos; while ( i <= n-m+1){ SubString (sub,S,i,m); // 取从第i个起长度为m的子串 if (StrCompare(sub,T) != 0) ++i ; else return i ; // 找到和 T 相等的子串 } // while } // if return 0; // S 中不存在满足条件的子串 } // Index