采用顺序结构存储串 编写一个实现通配符匹配的函数pattern_index（) 其中通配符取“？” 它可以和任
通配符,函数,顺序
已帮助 人
采用顺序结构存储串，编写一个实现通配符匹配的函数pattern_index()，其中通配符取“？”，它可以和任一字符匹配成功，例如，pattern_index("there","？re")返回的结果是2。
请帮忙给出正确答案和分析，谢谢！
-
正确答案：×
(1)数据结构采用字符串的顺序表示定义。(2)思路本题的思想与朴素的模式匹配法有些相似,不同之处：需要解决“?”可与任何字符匹配的问题。这个问题的解决方法很简单,具体见算法中黑体部分。(3)算法intpattern_index(PSeqStringt,PSeqStringp){／*返回匹配成功的第一个字串的第一个字符下标值,若没有匹配则返回-1*／intti,pi；for(ti=0；ti<=t->n-p->n；ti++){pi=0；while((p->c[pi]=="?"‖t->c[ti+pi]==p->c[pi])&&pin)pi++；if(pi==p->n)returnti；}return-1：}(4)代价分析设t含有的字符个数为n,p含有的字符个数为m,则最好情况下的时间代价是p的第一个字符与t的所有字符均不相同,则比较次数为O(n)；最坏情况下的比较次数是每次比较p都要到最后一个字符失败,则总的比较次数为m×(n-m+1),当n足够大时(n$amp;>amp;$gt;m),时间代价约为O(m×n)。