Doraemonzzz

week6&week7这两周主要讲了函数以及数组，这里提几个点。首先看下数组 数组是一种容器，特点是： 其中所有的元素具有相同的数据类型； 一旦创建，不能改变大小 *数组中的元素在内存中是连续依次排列的 函数部分提一个细节如果声明一个没有参数的函数，应该声明为void f(void)而不要声明为void f()因为这样是表示函数的参数未知，并不表示没有参数。

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 这周是图的第二部分内容，介绍的是最短路径问题，下面回顾下。 Part1:回顾1.最短路径问题首先看下最短路径问题的描述。这类问题也可以分为两类，分别是单源和多源。首先来看下单源的问题，这里也可以分为两种，分别为无权和有权的情形。无权图的情形其实就是数距离原点的步数，这样的话就可以使用上一讲使用的BFS算法。有权图的情形使用了贪心算法，从源点开始，每一步找到已访问节点至未访问节点的最短路径，将这条路径及顶点包括在已访问的节点中具体如下。最后来看一下多源最短路算法，其实就是个三重循环。 Part2:作业 作业1 07-图4 哈利·波特的考试（25 分）哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠 ...

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 这周开始了图的内容，内容不是很多，下面回顾一下。 Part1:回顾1.图(Graph)首先来看一下图的定义。再来看下图的抽象数据类型定义。看了上述介绍之后，自然有个很基础的问题，如何在程序中表示一个图，一般有以下两种方法。1.邻接矩阵法。显然，无项图的邻接矩阵为对称矩阵，浪费了很多空间，所以此时可以使用一维数组来表示，如下所示。那么邻接矩阵的优缺点分别是什么呢？ 2.邻接表表示法。邻接表表示法的意思是记录每个点以及和它直接相连的点，具体的意思是首先记录根节点，根节点指向与其链接的节点，每个节点分为两个部分，值和指针，指针指向与根节点相连的其他节点，所以共占$N+2E$空间(每条边占用两个空间)。 再来看下邻接表的优缺点。 最后来比较一下邻接矩阵法和邻接表法占用的空间,设$N$个点和$E$条边。那么邻接矩阵法占用的空间为$N^2$,邻接表法占用的空间为$N+2E$。注意对于图来说不计重边，如果是无向图，那么$E\le C_N^2$。因为任意两点之间最多一条边 ...

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 这周是树的最后一部分内容，主要讲了堆以及哈夫曼树，下面回顾下。 Part1:回顾1.堆(heap)首先看一下优先队列的含义。如果我们使用完全二叉树存储优先队列，那么就称为堆。简单来说，堆就是任意父节点小于等于或大于等于子节点的完全二叉树。再来看下堆的抽象数据类型描述，这里只列了最大堆，最小堆同理。这部分的代码实现都会在作业中体现，故这里从略。最后来看下最大堆的建立这个问题。这里讲一下第二种方法,处于倒数第2层的元素最多交换1次，倒数第3层可能要交换1次至倒数第2层，之后可能再交换一次，所以1共最多要交换2次，同理倒数第k层的元素最多交换k-1次，下面计算倒数第k层的元素个数。假设一共有$n$个元素，完全二叉树共$k$层，那么$2^{k-1}\le n< 2^k-1$,最后一层最多有$2^{k-1}$个元素，所以最后一层的元素个数小于$\frac{n}{2}$,倒数第二层的元素个数小于$\frac{n}{4}$,交换次数最多为$1$,同理倒数第$i$层 ...

week3这一周主要讲了分支，还是比较基础的内容，来看两点。 switch switch适合多分支的情形，但是注意switch后的参数必须为整数以及只有碰到break才会跳出switch。#include <stdio.h> int main() { printf("请输入月份："); int month; scanf("%d", &month); switch ( month ) { case 1: printf("January\n"); break; case 2: printf("February\n"); break; case 3: printf("March\n"); break; case 4: printf("April\n"); break; case 5: printf("May\n"); break; case 6: printf("June\n"); break; case 7: printf("July\n"); break; case 8: printf("August\n" ...

这次作业比较简单，但还是记录一下。 problem1: 这题只要算出矩形左上角的坐标即可。import acm.graphics.*; import acm.program.*; import java.awt.*; public class DrawCenteredRect extends GraphicsProgram { /** Size of the centered rect */ private static final int WIDTH = 350; private static final int HEIGHT = 270; public void run() { GRect rect= new GRect(WIDTH,HEIGHT); rect.setFilled(true); rect.setColor(Color.BLUE); add(rect,(getWidth()-WIDTH)/2.0,(getHeight()-HEIGHT)/2.0) ...

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 这周的的内容依旧是树，感觉有点难，现在回顾下。 Part1:回顾1.二叉搜索树(BST)首先来看一下二叉搜索树的定义。看完了定义，再来看下二叉搜索树支持的操作,这部分操作和上一周课程中树的操作类似，但是由于二叉搜索树的性质，又略有不同。先来看下Find操作，Find操作是在二叉搜索树寻找给定的元素，返回它所在节点的位置，如果元素不存在，则返回空。FinMin,FinMax比较容易，因为根据二叉搜索树的特点，最大元素一定在最右分支的端节点上，最小元素一定在最左分支的端节点上。再来看一下Insert操作,插入操作的关键点是找到插入的位置，最方便的自然是插在叶节点之后，所以这里可以采取类似Find的操作。 从根节点开始，如果树为空，则插入点为根节点。 若树非空，则拿插入值和根节点比较，如果插入值小于节点值，在左子树继续进行插入操作。 如果插入值大于节点值，在右子树继续进行插入操作。 重复此操作直至节点为叶节点。 来看一张图可以方便理解。最后来看一下删除操作， ...

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 第三周的内容是讲树，现在来回顾下。 Part1:回顾1.树的定义光看定义还挺抽象，但是看下示意图还是比较好理解的，注意这里互不相交这个特点很关键，可以据此来判断一个结构是否为树，例如一下三个例子均不是树。再来看一些常用术语，这里只列几个最常用的。 节点的度：节点的子树个数 树的度：树的所有节点中最大的度数 叶节点：度为0的节点 根节点：没有父节点的节点 父节点：有子树的节点是其子树的根节点的父节点 子节点：若A是B的父节点，那么B是A的子节点 兄弟节点：具有同一父节点的各个节点彼此是兄弟节点 现在有了抽象数据结构，那么在计算机中如何表示呢？课程中老师给了一种通用方法，适用于任何树，称为儿子兄弟表示法，即每个节点由三个元素构成，分别为节点的值，指向兄弟节点的指针，指向子节点的指针。树的集合称为森林，可以看出森林也可以使用儿子兄弟表示法表出，只要将每个根节点指向下一颗数即可。 2.二叉树现在来看一种特殊的树，二叉树。二叉树的特点为每个节点有0到2个子节点， ...

一直想学这门课，网易公开课的版本确实不错，但是代码看不清，非常难受，所以自己搬运了youtube上2016年的课程，非常清晰，字幕是youtube自动翻译的，可能有些不准，但内容和网易公开课版本基本一致，这里给下链接。视频地址：https://pan.baidu.com/s/12oEpv022SiKlJGwZiQNO0g密码：62nu参考书籍：https://pan.baidu.com/s/1PYRjvvq6fkV_NdTR7FOa2g密码：h092 课程主页：https://www.baidu.com/link?url=Ti8c7qJ4ibyIfgMgucbK5qTnnzGf3xWVsRdzORr1_fF-vGRVoHQ7Q7RlITXwHgPE&wd=&eqid=a77bcc030001438d000000045aba5907最新版的课程其实和网易公开课上的资料基本一致,选择哪个都可以，个人感觉把这些部分都完成应该会有不错的效果。 再来简述一下这门课程，这门是编程的入门课，0基础都可以学，介绍java的，老师讲课很有意思，难度不大，感觉这门课的精华是作业，所以在这里 ...

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 之前忙于研究生复试，所以停滞了一周的课程。这次回顾下第二周的课程，这周主要讲了三个部分，线性表，堆栈，队列。 Part1:回顾1.线性表这里引用老师的介绍。线性表比较常用，比如python中的list的就是线性表，由于python自带，所以这里没有自己实现一遍。 2.堆栈(Stack)堆栈是一种特殊的线性表，只在栈顶插入删除数据，插入操作称为入栈(Push)，删除操作称为出栈(Pop)。栈的最大特点为后入先出Last In First Out(LIFO)。栈在生活中也是比较常见的，例如碗，我们一般会将新的碗放在最上面，用碗的时候也会拿最上面的碗，还有一个例子是夏天冰箱里的饮料，我们一般会拿最外层的，放饮料的时候也会放在最外层。下面是老师的介绍。 第一周的部分使用c语言实现的，但是我指针后面部分都不大会，正在恶补，故这里使用python实现。# -*- coding: utf-8 -*- """ Created on Sat Mar 24 11:11:38 ...

Week1这一周相对基础，只列两点 解释与编译的区别解释：一条一条运行编译：翻译完成之后运行这里老师说解释执行未必比编译执行慢，因为现在计算机的运算速度已经非常快了。 现在一般说哪个语言比较适合做什么不是说这个语言本身，而是这个语言有很强大的库函数。比如python的pandas,numpy库非常适合做科学计算，所以人们常说python适合做数据分析。 Week2这周的知识列三个要点 读取double类型数据的时候使用scanf(“%lf”,&a) 运算优先级 前缀后缀运算

课程地址：https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。 这周开始了浙大陈越老师的数据结构课程，听了一周，感觉讲的很清晰，现在总结一下。 Part1:回顾1. 什么是数据结构简单来说，就是数据对象在计算机中的组织方式，分为逻辑机构和物理存储结构，而数据对象必定和一些操作相关，这些操作就是算法。这里老师还提到抽象数据类型的概念，就是定义一个数据对象集和其操作集，而不管其具体的实现。举个例子，大家都知道矩阵，也知道它的运算，那么矩阵可以看成一个抽象数据类型，在计算机中具体由python还是C来定义这些细节就不是抽象数据类型关心的了。抽象的好处在与处理问题的时候只需要关注问题本身，而不用关注底层的实现。 2. 什么是算法算法的其实就是解决问题的方法，设计算法的时候要考虑时间复杂度和空间复杂度。时间复杂度一般就是考虑最坏情况以及渐进表示，因为最坏情况方便计算，而且算法只需要考虑当数据量大的情形，所以只需要考虑渐进表示。 3. 应用实例这部分也是这周的作业，虽然不算很难，但是本菜鸡还是折腾了很久。本周的例子是最大子列，PT ...