数据结构PPT(第四章).ppt

1. 普通算法--------穷举的模式匹配过程 * 串的概念 串的存储表示 串的模式匹配算法 是由零个或多个字符组成的有限序列，一般记为 s=“a1a2…an”(n?0) 其中，s是串名，用单引号（也可以是用双引号括起来的） 括起来的字符序列是串的值。ai可以是字母、数字或其他字符；串中字符的个数n成为串的长度。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 位置：字符在序列中的序号。子串在主串中的位置则以子 串的第一个字符在主串中的位置来表示。 相等：两个串的长度相等，并且对应位置的字符都相等。 注意区分空串与空格串的区别！ 4.1 串的定义 串的逻辑结构和线性表的区别: 对于串可以定义以下运算： 1. 串的数据对象约束为字符集。 2. 线性表的基本操作大多以“单个元素”为操作对象， 而串的基本操作通常以“串的整体”作为操作对象。 1. 置串为一个空串； 2. 判断一个串是否为空串 3. 求一个串的长度； 4. 将两个串拼接在一起构成一个新串； 5. 如果串S2是S1的子串，则可求串S2在串S1中第一次出现的位置。 6. 在一个串中，求从串的第i个字符开始连续j个字符所构成的子串； 1. 定长顺序表示 #define MAXNUM 1000 /* 串允许的最大字符个数 */ struct SeqString /* 顺序串的类型 */ { char c[MAXNUM]; int n;//串的长度 }SeqString, *PSeqString; 4.2串的存储表示 PSeqString createNullStr_seq( void ) { PSeqString pstr; pstr=(PSeqString)malloc(sizeof(SeqString)); if (pstr==NULL) printf(“Out of space!!\n”);/*申请空间失败*/ else pstr-n = 0;/*长度置0*/ return pstr; } 算法4.1创建空顺序串 提取子串的算法示例 pos+len -1 ? Len-1 i n f i n i t y pos = 2, len = 3 f i n i n f i n i t y pos = 5, len = 4 i t y 超出 pos+len -1 ? Len-1 PSeqString subStr_seq(PSeqString s,int pos,int len) /* 求从s所指的顺序串i个字符(下标是i)开始 连续j个字符所构成的子串 */ { PSeqString s1; int k,m; s1 = createNullStr_seq( ); /* 创建一空串 */ if (s1==NULL) return NULL; if ( pos0 pos=s-n len0 ) { /*若从pos开始取不了len个字符,则能取几个就取几个*/ if (pos+len-1 s-n-1 ) len = s-n -pos; for (k=0;klen;k++) s1-c[k]=s-c[pos+k]; s1-c[len]=‘\0’;/*为什么要这条语句？？*/ s1-n =len; } else s1-c[0]=\0; return(s1); } 算法4.2求顺序表示的串的子串 typedef struct { char *ch; int length; }HString; 2. 变长顺序表示 //生成一个其值等于串常量chars的串T void StrAssign(HString *str, char *chars); void StrCopy(HString *dest, HString src); //串的复制 BOOL IsStrEmpty(HString str); int StrCompare(HString str1, HString str2); int StrLength(HString str); Status StrCat(HString *dest, HString str1, HString str2); //用dest返回由str1和str2构成的新串 …………… Status SubString(HString *sub, HString str, int pos, int len) {/* 0 =