chap3_算法与数据结构—c语言描述(第2版)张乃孝编课件1.ppt

E = (注意区分空串与空格串 区别) T = “ABBABBCA ” t= “ABB ABBCA ” (T和t不等) P= “BBC ” (P是T的子串,在T的位置是5) 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 特别地，空串是任意串的子串。任意串s都是s本身的子串。 除s本身之外，s的其它子串称为s的真子串。 位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 相等：两个串的长度相等，并且对应位置的字符都相等。 2 抽象数据类型 3.2 字符串的实现 顺序表示 链接表示 1 顺序表示 字符串的顺序表示，就是把串中的字符，顺序地存储在一 组地址连续的存储单元中。其类型定义为： struct SeqString { /* 顺序串的类型 */ int MAXNUM; /* 串允许的最大字符个数 */ int n; /* 串的长度，n?MAXNUM */ char *c; }; typedef struct SeqString *PSeqString; 字符串运算1： 创建空顺序串 创建空串的方法与创建空顺序表类似。 PSeqString createNullStr_seq( int m ) 程序 字符串运算2： 求顺序表示的串的子串 PSeqString subStr_seq(PSeqString s,int i,int j) 求从s所指的顺序串中第i(i0)个字符开始连续取j个字符所构成的子串。如： subStr_seq(s, 5,3) 程序实现 2 链接表示 在串的链接表示中，每个结点包含两个字段：字符和指针，分别用于存放字符和指向下一个结点的指针。这样一个串就可 用一个单链表来表示，其类型定义为： struct StrNode; /* 链串的结点 */ typedef struct StrNode *PStrNode; /* 结点指针类型 */ struct StrNode { /* 链串的结点结构 */ char c; PStrNode link; }; typedef struct StrNode *LinkString; /* 链串的类型 */ 字符串运算1：创建带头结点的空链串 创建空串的方法与创建空链表类似 ， 可有如下程序实现： LinkString createNullStr_link( void ) 字符串运算2：求单链表示的串的子串 LinkString subStr_link(LinkString s,int i,int j) 求从s所指的带头结点的链串中第i(i0)个字符 开始连续取j个字符所构成的子串。 这里首先要为链串结构和头结点申请空间，创建一个 空链表，这由算法3.3实现。然后判断所给参数i ，j的值是 否合理，i ，j的取值应为i0，j0。接着从s-head开始找第 i个结点，找到后，就从该结点开始，为子串中的结点申请 空间，并将元素值拷过去。 程序实现 1 朴素的模式匹配 基本思想：用p中的字符依次与t中的字符比较（见图3.3-(a)），如果t0 = p0，t1 = p1，…，tm-1 = pm-1，则匹配成功，返回第一次出现的位置是从第一个字符t0开始。否则必有某个i（0≤i≤m-1），使得ti ≠pi，这时可将p右移一个字符，用p中字符从头p0开始与t中字符t1依次比较（见图3.3-b），如此反复执行，直到下面两种情况之一：或者到达某步时，ti = p0，ti+1 = p1，…，ti+m-1 = pm-1，匹配成功，返回第一次出现的位置是从t中第i+1个字符ti开始，即是找到的（第一个）与模式p相同的子串；或者一直将p移到无法与t继续比较为止，则匹配失败。 程序实现 设目标串以t＝abbaba和p＝aba为例，s的长度为n（n=6），t的长度为m（m=3） 该算法简单，易于理解，但效率不高，一旦比较不等，就将p所指的串右移一个字符，并从p0（算法中用p-c[0]表示）开始比较。在最坏的情况下，每趟比较都在最后出现不等，最多比较n－m＋1趟，总比较次数为m*(n－m＋1)，由于在一般情况下m＜＜n，所以算法运行时