[工学]数据结构课件4.ppt

在上述抽象数据类型定义的13种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来 实现， 反之，其他串操作（除串清除 ClearString和串 销毁DestroyString外）可 在这个最小操作子集上实现。 ‘ 例如，可利用串比较、求串长和求子串 等操作实现定位函数Index(S,T,pos)。 算法的基本思想为： StrCompare(SubString(S, i, StrLength(T)),T ) ? 0 S 串 T 串 T 串 i pos n-m+1 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); if (StrCompare(sub,T) != 0) ++i ; else return i ; } // while } // if return 0; // S中不存在与T相等的子串} // Index 又如串的置换函数： S 串 T 串 V 串 V 串 pos pos sub i news 串 sub 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。在线性表的基本操作中,大多以“单个元素”作为操作对象;在串的基本操作中，通常以“串的整体”作为操作对象。 在程序设计语言中，串只是作 为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。 4.2 串的表示和实现 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 #define MAXSTRLEN 255 //用户可在255以内定义最大串长 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0号单元存放串的长度 一、串的定长顺序存储表示 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。 串的实际长度可在这个予定 义长度的范围内随意设定,超过 予定义长度的串值则被舍去,称 之为“截断” 。 特点: Status StrInit(String s){ //for(int i=0;i=MAXSTRING;++i) s[i]=0; s[0]=0; return OK;} Status StrAssign(String s,char *t){ char *p; int i; p=t;i=1; while(*pi=MAXSTRING){s[i]=*p;++i;++p;} s[0]=i-1; return OK;} //如果串t的长度大于MAXSTRING, 则t被截断 Status StrLength(String s) { return s[0]; } Status StrCopy(String s,String t) { int i; for(i=0;i=StrLength(t);++i) s[i]=t[i]; return OK; } Status StrCompare(String s,String t) { int i , n; i=1; n=StrLength(s)StrLength(t)?StrLength(t):StrLength(s); while(s[i]==t[i]i=n) ++i; if (s[i]t[i]) return