20210317

数据结构

时间复杂度

计算一个算法时间复杂度具体步骤：

1. 确定算法中的基本操作以及问题的规模
2. 根据基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为T(n)=Of(n)中增长最快的项/此项的系数。

eg1:

void fun(int n)
{
    int i = 1,j = 1000;
    while(i < n)
    {
        ++j;
        i += 2;
    }
}

1. 基本操作： ++j; i += 2;
2. 确定规模：i初值为1，每次自增2，那么假设m次后结束循环（这时i的值已经大于n），则i最后的值为1+2m，则有1+2m+k=n，k是因为在循环结束时i的值稍大于n。那么可以算出 m=(n-1-k)/2，即f(n)=(n-1-k)/2，发现增长最快的是n/2，所以时间复杂度为T(n)=O(n)。

eg2:

void fun(int n)
{
    int i,j,x = 0;
    for(i = 0;i < n;++i)
        for(j = i+1;j < n;++j)
            ++x;
}

1. 基本操作：++x
2. 确定规模：

线性表

定义

线性表是具有相同特性数据元素的一个有限数列。该序列中所含元素的个数叫做线性表的长度。用n(n≥0)，n可以等于0的原因是此时表示线性表是一个空表。

1. 有限
2. 相同特性
3. 有序性

线性表的逻辑特性

• 只有一个表头元素
• 只有一个表尾元素
• 表头元素没有前驱
• 表尾元素没有后继
• 除表头和表尾元素之外，其他元素只有一个直接前驱，也只有一个直接后驱。

线性表的存储结构

分为顺序存储结构 （即顺序表） 和链式存储结构（即链表）。

1. 顺序表性质：① 随机访问（查找快，直接定位）②要求占用连续的存储空间 ③ 存储密度高，只存储数据元素 ④ 插入、删除操作需要移动多个元素

2. 链表性质：① 链表不支持随机访问 ②链表中结点的存储空间利用率较顺序表稍低一些 ③ 链表支持存储空间的动态分配 ④链表支持存储空间的动态分配

刘晓艳语法C1

英语句子的基本结构

1. 主谓 主语 + 谓语

The elephant died.
We laugh.

2. 主谓宾
3. 主谓表

主谓宾和主谓表的却别就是谓语动词不同。
主谓表的谓语一定是实义动词；

但是有些动词不仅是系动词还可以是实义动词，要知道在句子中是什么类型，就要根据句子的意思，比如

I grew up in this small town. 我就在这座小城镇中长大（实义动词）
The sweater grew dirty. 这件毛衣变脏了。（系动词）

4. 主谓双宾 主语+谓语+间接宾语+直接宾语。 直接宾语为主要宾语，在句子里面不可或缺，一般由“物”充当。 间接宾语为第二宾语，去掉影响不大，一般由“人”充当。

He teaches us English.
He gave me five sugars.
He bought me a birthday gift.

6. 主谓宾宾补 宾语补足语的主要作用是补充宾语的特点、身份或让宾语完成某个动作。

You should keep the room clean and tidy. 形容词
We made him our monitor. 名词
His father told him not to play in the street. 动词不定式

主谓双宾和主谓宾补最简单的区分方法就是在两个宾语之间，或者宾语和宾补之间加个系动词。如果读起来语义通顺，就是宾补（说明有关系）；反之，则是双宾（说明没关系）。

句子的成分

• 谓语就是具有时态和语态的实义动词（词组）或者系动词。
• 句子主要想表达哪个动作，就留哪个动作做谓语。
• 英文句子中显然不能没有主语，祈使句只是省略了主语。
• transitive verv 及物动词vt；intransitive 不及物动词 vi。

must have done 一定做过某事
needn't have done 本没必要做某事，但是做了
could have done 本能够做某事，但没有做
should have done 本应该做某事

背单词

• correspond 【v.符合；通信；相类似；相对应】
• dazzle 【v.使目眩；使眼花；使惊叹 n.耀眼；眩惑；灿烂】
• alleviate 【v.减轻；缓解；缓和】
• desolate 【adj.荒凉的；孤寂凄凉的 v.使荒无人烟】
• divine 【adj.神的；神性的 v.占卜】
• spade 【n.铁锹；纸牌中的黑桃】
• symmetry 【n.对称】