吉林师范大学计算机学院《数据结构》课件：4.ppt

数据结构（C语言版）  第4章　串 4.1串的概念 1、名词术语 ★串（String)(或字符串），是由零个或多个字符组成的有限序列。 ★空串（Null string),零个字符的串，它的长度为零。 ★子串，串中任意个连续的字符组成的子序列称为该串的子串。 ★主串，包含子串的串。 ★串的长度，串中字符的数目n。 ★空格串 (blank string,请注意此处不是空串），由一个或多个空格组成的串. 2、串的抽象数据类型定义 AST String{????数据对象：D={ai|ai∈CharacterSet,i=1,2,...,n, n≥0}????数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,...,n}????基本操作：????????StrAssign(T,chars)????初始条件：chars是字符串常量。????操作结果：生成一个其值等于chars的串T。…… } ADT String 见 P71 4.2串的存储结构 ★定长顺序存储串的思想： ??◆用一个字符数组存储一个串，c 语言中以‘\0作为串的结束标志。??#define MAXSTRLEN 255 ??????//可由用户定义??typedef unsigned char SString[MAXSTRLEN+1]; ★动态分配顺序存储串的思想： ◆串的存储空间由malloc()函数来分配。?◆类型定义： ????typedef struct{??????????char *ch;??????????int length;????}Hstring; ◆类型定义： #define SIZE 80 //可由用户定义大小????typedef struct Node {??????????char ch[SIZE];??????????struct Node *next;????}LString; 4.3串的基本操作算法 Status StrAssign(HString T,char *chars){??????//生成一个其值等于串常量chars的串T??????if(T.ch) free(T.ch); //释放T原有的空间??????for(i=0,c=chars;*c;++i,++c); //求chars的长度i??????if(!i){T.ch=NULL; T.length=0;}??????else{????????if(!(T.ch=(char*)malloc(i*sezeof(char))))??????????exit(OVERFLOW);????????T.ch[0..i-1]=chars[0..i-1];????????T.length=i;??????}??????return OK;}//StrAssign int StrLength(HString S){??????//返回S的元素个数，称为串长。??????return S.length;}//StrLength int StrCompare(HString S,HString T){??????//若ST,则返回值0;若S=T，则返回值=0；若ST，则返回值0??????for(i=0;iS.length iT.length;++i)??????????if(S.ch[i]!=T.ch[i] return S.ch[i]-T.ch[i];??????return S.length-T.length;)//StrCompare Status ClearString(HString S){??????//将S清为空串。??????if(S.ch) {free(S.ch); S.ch=NULL;}??????S.length=0;??????return OK;}//ClearString Status Concat(HString T,HString S1,HString S2){??????//用T返回由S1和S2联接而成的新串。??????if(T.ch) free(T.ch); //释放旧空间??????if(!(T.ch=(char*)malloc((S1.length+S2.length)*sezeof(char))))??????????exit(OVERFLOW);??????T.ch[0..s1.length-1]=S1.ch[0..S1.length-1];??????T.length=S1.length+S2.length;T.ch[S1.length..T.l