字符串与模式匹配算法.pptVIP

串模式匹配问题设有两个串t和p:t=t0t1…tn-1，p=p0p1…pm-1其中1m=n(通常mn)模式匹配的目的是在t中找出和p相同的子串。此时，t称为“目标”，而p称为“模式”。模式匹配的结果有两种：匹配成功：t中存在等于p的子串，返回子串在t中的位置匹配失败：返回一个特定的标志（如-1）。*第30页，共42页，星期日，2025年，2月5日HuJunfengPekingUniversity字符串与模式匹配算法第1页，共42页，星期日，2025年，2月5日用数组来实现链表结构structNode{DataTypenum;intnext};structSlinklist{Nodelist[MAXNUM];intelementNum;}1290-1634-112*第2页，共42页，星期日，2025年，2月5日*第3页，共42页，星期日，2025年，2月5日作业讲评：*第4页，共42页，星期日，2025年，2月5日*第5页，共42页，星期日，2025年，2月5日*第6页，共42页，星期日，2025年，2月5日*第7页，共42页，星期日，2025年，2月5日*第8页，共42页，星期日，2025年，2月5日*第9页，共42页，星期日，2025年，2月5日*第10页，共42页，星期日，2025年，2月5日*第11页，共42页，星期日，2025年，2月5日链表应用举例——Josephus问题

求解Josephus问题的一般步骤为：

（1）首先利用线性表的一些运算如创建空线性表、插入元素等构造Josephus表；

（2）从Josephus表中的第s个结点开始寻找、输出和删除表中的第m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第m个结点，重复此过程，直到Josephus表中的所有元素都删除。

*第12页，共42页，星期日，2025年，2月5日顺序表应用举例——Josephus问题voidjosephus_seq(PSeqListpalist,ints,intm){ints1,i,w;s1=s-1;for(i=palist-n;i0;i--)/*找出列的元素*/{s1=(s1+m-1)%i;/*下一个出列的元素*/ w=palist-element[s1]; /*求下标为s1的元素的值*/printf(“Outelement%d\n”,w); /*元素出列*/ delete_seq(palist,s1); /*删除出列的元素*/ }}*第13页，共42页，星期日，2025年，2月5日算法复杂度分析（顺序结构）步骤：1:建立顺序表2:出列时间复杂度分析：出列元素的删除（移动实现）为基本运算（每次最多i-1个元素移动，需要n-1次）(n-1)+(n-2)+……+1=n(n-1)/2=O(n2)*第14页，共42页，星期日，2025年，2月5日算法复杂度分析（链表结构）步骤：(1)建立循环链表；(2)找循环单链表中的第s个结点放在指针变量p中(3)从p所指结点开始计数寻找第m个结点，输出该结点的元素值；(4)删除该结点，并将该结点的下一个结点放在指针变量p中，转去执行(2)，直到所有结点被删除为止；时间复杂度分析：三部分时间（创建链表：O(n)+求第s个结点：O(s)+求n个第m个应出列的元素：O(m*n))*第15页，共42页，星期日，2025年，2月5日链表的用用：一元多项式和运算一元多项式：Pn(x)=p0+p1x+p2x2+…+pnxn线性表表示：P=(p0,p1,p2,…,pn)顺序表表示：只存系数（第i个元素存xi的系数）特殊问题：p(x)=1+2x10000+4x40000链表表示：每个结点结构系数指数0-110210000440000