顾长贵-第5章-串.ppt

数据结构课程的内容;第5章 串 ;5.1 串;字符串可否可以和栈或者队列结合？;5.1 串;5.1 串;5.1 串;5.1 串;5.1 串;5.1 串;串的存储表示和实现;串的顺序存储;5.2 串的顺序表示与实现 ;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现; /*第2种情况*/ else if(T-lengthMaxLen) { for(i=T-length;iMaxLen;i++) /*将串S部分连接在T的末尾*/ T-str[i]=S.str[i-T-length]; T-length=MaxLen; /*修改串T的长度*/ flag=0; /*修改标志，表示S部分被连接在T中*/ } return flag; } ;5.2 串的顺序表示与实现;5.2 串的顺序表示与实现;堆分配存储;5.3 串的堆分配表示与实现;5.3 串的堆分配表示与实现 ;5.3 串的堆分配表示与实现;5.3 串的堆分???表示与实现;5.3 串的堆分配表示与实现;5.3 串的堆分配表示与实现;串的块链式存储;5.4 串的块链式存储表示与实现 ;5.4 串的块链式存储表示与实现;5.4.1 串的块链存储表示;5.4 串的块链式存储表示与实现;5.4 串的块链式存储表示与实现;5.5 串的模式匹配算法;5.5.1 Brute-Force模式匹配算法; 这样，串匹配问题可简化为找出某给定模式T在给定目标串S中首次出现的有效位移。 算法实现 int IndexString(StringType s , StringType t , int pos ) /* 采用顺序存储方式存储主串s和模式t， */ /* 若模式t在主串s中从第pos位置开始有匹配的子串，*/ /* 返回位置，否则返回-1 */ { char *p , *q ; int i , j ; i=pos-1 ； j=0 ; p=s.str+pos-1 ; q=t.str ; /* 初始匹配位置设置 */ /* 顺序存放时第pos位置的下标值为pos-1 */;while (is.length)(jt.length){ if (*p==*q) { p++ ; q++ ; i++ ; j++ ; } else { i=i-j+1 ; j=0 ; q=t.str ; p=s.str+i ; } /* 重新设置匹配位置 */ } if (j==t.length) return(k-t.length) ; / * 匹配，返回位置 */ else return(-1) ; /* 不匹配，返回-1 */ } 见书例子p79; 该算法简单，易于理解。在一些场合的应用里，如文字处理中的文本编辑，其效率较高。 该算法的时间复杂度为O(n*m) ，其中n 、m分别是主串和模式串的长度。通常情况下，实际运行过程中，该算法的执行时间近似于O(n+m) 。 理解该算法的关键点 当第一次sk≠tj时：主串要退回到k-j+1的位置，而模式串也要退回到第一个字符（即j=0的位置）。 比较出现sk≠tj时：则应该有 sk-1=tj-1，…，sk-j+1=t1， sk-j=t0 。;5.6 小结 ;串的联结操作 作业 Status Hstring *StrConcat(HString *T, HString *s1, HString *s2) /* 用T返回由s1和s2联结而成的串 */ { int k, j , t_len ; if (T.ch) free(T); /* 释放旧空间 */ t_len=s1-length+s2-length ; if ((p=(char *)__?__(sizeof((char)*t_len))==NULL) { printf(系统空间不够，申请空间失败 ！\n) ; return ERROR ; } for (j=0 ; js1-length; j++) ______?_____; /* 将串s复制到串T中 */ k=s1-length; for ( j=k ; ___?____;j++) T-ch[j+k