20210424

回顾

恋词复习

• scrutinize v.详细检查；仔细观察；细读；细阅
• probe n.探索；查究；探针；检测器

田静语法

关于定语从句的分类：限定性定语从句（无逗号隔开）和非限定性定语从句（有逗号隔开）。

• 限定性定语从句，范围不明确。

  • He will call his friend who is working in London.（朋友很多个，不知道是哪个朋友）

• 非限定性定语从句

  • He will call his mother, who is working in London.（妈妈只有一个啊）
  • If it is trying to upset Google, which relies alomost wholly on advertising,it has chosen an indirect method.
  • This trend,which we believe is still in its infancy,effectively began with retailers and travel providers such as airlines an hotels and will no doubt go further.

GS2-C1-660-131~145

依旧做的还是选择题，概念好强，好想吐，加强概念！！！间断点，连续性！！

数据结构-串（三）

KMP模式匹配算法改进

如果主串S="aaaabcde"，子串T="aaaaax"，其next数组值分别为012345，在开始时，当i=5、j=5时，“b”与“a”不相等，如图①，因此j=next[5]=4，如图中的②，此时“b”与第4位置的“a”依然不等，j=next[4]=3，如图中的③，后依次是④⑤，直到j=next[1]=0时，根据算法，此时++i、++j，得到i=6、j=1，如图中的⑥

当中的②③④⑤步骤，其实是多余的判断。由于T串的第二、三、四、五位置的字符都与首位的“a”相等，可以用首位next[1]的值去取代与它相等的字符后续next[j]的值

nextval数组值推导

1．T="ababaaaba"

先算出next数组的值分别为011234223，然后再分别判断。

• 当j=1时，nextval[1]=0；
• j=2时，因第二位字符“b”的next值是1，而第一位就是“a”，它们不相等，所以nextval[2]=next[2]=1，维持原值。
• 当j=3时，因为第三位字符“a”的next值为1，所以与第一位的“a”比较得知它们相等，所以nextval[3]=nextval[1]=0 )
• 当j=4时，第四位的字符“b”next值为2，所以与第二位的“b”相比较得到结果是相等，因此nextval[4]=nextval[2]=1
• 当j=5时，next值为3，第五个字符“a”与第三个字符“a”相等，因此nextval[5]=nextval[3]=0；
• 当j=6时，next值为4，第六个字符“a”与第四个字符“b”不相等，因此nextval[6]=4；
• 当j=7时，next值为2，第七个字符“a”与第二个字符“b”不相等，因此nextval[7]=2；
• 当j=8时，next值为2，第八个字符“b”与第二个字符“b”相等，因此nextval[8]=nextval[2]=1
• 当j=9时，next值为3，第九个字符“a”与第三个字符“a”相等，因此nextval[9]=nextval[3]=0

void getNextval(Str substr, int nextval[], int next[])
{
    int j=1, t=0;
    next[1] = 0;
    nextval[1] = 0;
    while(j<substr.length)
    {
        if (t==0 || substr.ch[j] == substr.ch[t])
        {
            next[j+1] = t+1;
            if(substr.ch[j+1] != substr.ch [next[j+1]])
                nextva1[j+1] = next[j+1];
            else
                nextva1[j+1] = nextval[next[j+1]];
            ++j;![image.png](https://i.typlog.com/tanxy/8380747381_350258.png) 
            ++t;
        }

        else
            t = nextval[t];
    }
}

数据结构-数组

一维数组

dataType a[n];
//其中dataType为数据类型，如int型

二维数组

dataType a[m][n];
//其中dataType为数据类型，如int型
//定义了m行n列的二维数组

二维数组的行优先存储

二维数组的列优先存储

考点

有了这两种存储顺序，对于同一个数组同一个位置上的元素在内存中的地址就有可能不同，这就是出题的点。

比如：

这一部分要掌握在不同存储顺序下对于数组中某一个元素来计算它之前有多少个元素的计算方法。

例题

分析：即int A[6][10]

A[3][5]所在的行之前有3行,每行10个元素;
A[3][5]所在行中位置之前有5个元素;
因此A[3][5]之前的元素个数为: 3x10 + 5=35;
所跨的地址范围为:4x35 =140;
A[0][0]的地址为: 1000 - 140 = 860。