字符串与模式匹配算法ppt课件.ppt

《字符串与模式匹配算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、用数组来实现链表结构structNode{DataTypenum;intnext};structSlinklist{Nodelist[MAXNUM];intelementNum;}12作业讲评：345678910链表应用举例——Josephus问题求解Josephus问题的一般步骤为：（1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表；（2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程，直到Josephus表中的所有元素都删除。11顺序表应用举例——Joseph

2、us问题voidjosephus_seq(PSeqListpalist,ints,intm){ints1,i,w;s1=s-1;for(i=palist->n;i>0;i--)/*找出列的元素*/{s1=(s1+m-1)%i;/*下一个出列的元素*/w=palist->element[s1];/*求下标为s1的元素的值*/printf(“Outelement%d”,w);/*元素出列*/delete_seq(palist,s1);/*删除出列的元素*/}}12算法复杂度分析（顺序结构）步骤：1:建立顺序表2:出列时间复杂度分析：出列元素的删除（移动实现）为基本运算（每次最多i-1个元素

3、移动，需要n-1次）(n-1)+(n-2)+……+1=n(n-1)/2=>O(n2)13算法复杂度分析（链表结构）步骤：(1)建立循环链表；(2)找循环单链表中的第s个结点放在指针变量p中(3)从p所指结点开始计数寻找第m个结点，输出该结点的元素值；(4)删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行(2)，直到所有结点被删除为止；时间复杂度分析：三部分时间（创建链表：O(n)+求第s个结点：O(s)+求n个第m个应出列的元素：O(m*n))14链表的用用：一元多项式和运算一元多项式：Pn(x)=p0+p1x+p2x2+…+pnxn线性表表示：P=(p0,p1,p2,…,pn

4、)顺序表表示：只存系数（第i个元素存xi的系数）特殊问题：p(x)=1+2x10000+4x40000链表表示：每个结点结构系数指数0-110210000440000^15一元多项式表示和运算-3数据定义：typedefstruct{floatc;//系数inte;//指数structitem*next}Item;加法:相同指数对应结点的系数项相加，如和为0，删除结点，否则必定为和链表的一个结点。（实质上就是两个单链表的合并问题）3251901101011226316两个一元多项式的乘法可以利用两个一元多项式相加的算法来实现M(x)=A(x)B(x)=A(x)[b1xe1+b2xe2+

5、...+bnxen]=O(n2)复杂度的运算。17字符串与模式匹配：字符串概念与抽象数据类型串模式匹配18C语言中定义的字符串存储结构：字符指针…操作：char*strcpy(char*dst,char*sorc)intstrcmp(char*str1,char*str2);char*strcat(char*dest,constchar*sorc,size);char*strstr(char*str,constchar*strSearch);size_tstrlen(constchar*str);gets(char*);puts(char*);19串匹配函数：cha

6、r*strstr(constchar[],constchar[]);20线性表到字符串ADTStringcreateNullStr(void)创建一个空串。intIsNullStr(Strings)判断串s是否为空串，若为空串，则返回1，否则返回0。intlength(Strings)返回串s的长度。Stringconcat(Strings1,Stings2)返回将串s1和s2拼接在一起构成的一个新串。StringsubStr(Strings,inti,intj)在串s中，求从串的第i个字符开始连续j个字符所构成的子串。intindex(Strings1,Strings2)如果串s2是s1

7、的子串，则可求串s2在串s1中第一次出现的位置。21顺序结构字符串ADT的定义structSeqString{/*顺序串的类型*/intMAXNUM;/*串允许的最大字符个数*/intn;/*串的长度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;22顺序串示例s=“abcdefg”abcdefgs.n=7s.c0123456MAXNUM-123字符串ADT——