[工学]04 串.ppt

相关网站 再 见 块链结构的定义 #define BLOCK_SIZE 4/*每结点存放字符个数4*/ typedef struct Block{ char??ch[BLOCK_SIZE]; struct Block??*next; }Block; typedef struct{ Block?*head; Block *tail; int??len; }BLString; ?三、串的应用举例：简单的行编辑器 可将文本看成为一个大的字符串，文本编辑就相当对字符串的处理。文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。 文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能不同，但基本操作是一样的，都包括串的查找、插入和删除等。 为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字符串，称为文本串，页是文本串的子串，行是页的子串。 这里采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符，同时建立页表和行表存储每一页、每一行的起始位置和长度。 串的应用举例：简单的行编辑器 串的应用举例：简单的行编辑器 当在某行内插入字符时，就要修改行表中该行的长度，若该行的长度超出了分配给它的存储空间，则要重新给它分配存储空间，同时修改它的起始位置和长度。如果要插入或删除一行，就要进行行表的插入和删除，当行的插入和删除涉及页的变化时就要对页表进行修改。 要点小结 典型题例 要求编写一个用带头结点的单链表实现串的模式匹配算法，每个结点存放一个字符（结点大小为1）。 典型题例——问题分析 【问题分析】该算法类同顺序串的简单模式匹配，实现匹配过程需考虑链表的特征（从头比较的技术，指针保留的技术）。 典型题例——算法思想 【算法思想】从主串s的第一个字符和模式串t的第一个字符开始比较，如果相等，就继续比较后续字符，如果不等，则从主串s的下一个字符开始重新和模式串t比较。一直到模式串t中的每一个字符依次和主串s中的对应字符相等，则匹配成功，返回主串的当前起始位置指针。如果主串中没有和模式串相同的子串，则称匹配不成功，返回空指针NULL。 典型题例 typedef struct Link{ char ch; /*保存一个字符*/ struct Link *next; }Link; typedef struct{ Link *head; /*头指针*/ Link *tail; /*尾指针*/ int len; /*串的长度*/ }LKString; 典型题例 /*求子串t在主串s中第一次出现的位置指针*/ Link *StrIndex(LKString *s, LKString *t) { Link *sp, *tp, *start; /*空串是任意串的子串*/ if(t-len == 0) return s-head-next; start = s-head-next;/*记录主串的起始比较位置*/ /*主串从start开始, 子串从第一个结点开始*/ sp = start; tp = t-head-next; 典型题例 while(sp != NULL tp != NULL){ /*若当前sp和tp的字符都相同, 则继续比较*/ if(sp-ch == tp-ch){ sp = sp-next; tp = tp-next; } else{/*返回到串比较起始位置的下一个结点继续比较*/ start = start-next; sp = start; /*更新比较的起始位置*/ tp = t-head-next; /*子串第一个结点*/ } } if( tp == NULL)/*匹配成功, 返回主串当前起始位置指针*/ return start; else/*匹配不成功, 返回空指针*/ return NULL; } Questions - Discussion 作业 判题系统： 资料下载及作业上传： :6727 Further Reading String Matching Exact string matching(http://www-igm.univ-mlv.fr/~lecroq/string/) Approximate string matching String matching with mismatches(/dads/HTML/bruteForceStrSrchwMismatch.html) String matching with errors(/blog/cns!2916695FA7B7532B!44