浙大C语言Week6 and week7
week6&week7这两周主要讲了函数以及数组,这里提几个点。首先看下数组
数组是一种容器,特点是:
其中所有的元素具有相同的数据类型;
一旦创建,不能改变大小
*数组中的元素在内存中是连续依次排列的
函数部分提一个细节如果声明一个没有参数的函数,应该声明为void f(void)而不要声明为void f()因为这样是表示函数的参数未知,并不表示没有参数。
浙大数据结构Week7
课程地址:https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周是图的第二部分内容,介绍的是最短路径问题,下面回顾下。
Part1:回顾1.最短路径问题首先看下最短路径问题的描述。这类问题也可以分为两类,分别是单源和多源。首先来看下单源的问题,这里也可以分为两种,分别为无权和有权的情形。无权图的情形其实就是数距离原点的步数,这样的话就可以使用上一讲使用的BFS算法。有权图的情形使用了贪心算法,从源点开始,每一步找到已访问节点至未访问节点的最短路径,将这条路径及顶点包括在已访问的节点中具体如下。最后来看一下多源最短路算法,其实就是个三重循环。
Part2:作业
作业1
07-图4 哈利·波特的考试(25 分)哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠 ...
浙大数据结构Week6
课程地址: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$。因为任意两点之间最多一条边 ...
浙大数据结构Week5
课程地址: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$层 ...
浙大C语言Week3 and Week4 and Week5
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" ...
斯坦福CS106A作业2
这次作业比较简单,但还是记录一下。
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) ...
浙大数据结构Week4
课程地址:https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周的的内容依旧是树,感觉有点难,现在回顾下。
Part1:回顾1.二叉搜索树(BST)首先来看一下二叉搜索树的定义。看完了定义,再来看下二叉搜索树支持的操作,这部分操作和上一周课程中树的操作类似,但是由于二叉搜索树的性质,又略有不同。先来看下Find操作,Find操作是在二叉搜索树寻找给定的元素,返回它所在节点的位置,如果元素不存在,则返回空。FinMin,FinMax比较容易,因为根据二叉搜索树的特点,最大元素一定在最右分支的端节点上,最小元素一定在最左分支的端节点上。再来看一下Insert操作,插入操作的关键点是找到插入的位置,最方便的自然是插在叶节点之后,所以这里可以采取类似Find的操作。
从根节点开始,如果树为空,则插入点为根节点。
若树非空,则拿插入值和根节点比较,如果插入值小于节点值,在左子树继续进行插入操作。
如果插入值大于节点值,在右子树继续进行插入操作。
重复此操作直至节点为叶节点。
来看一张图可以方便理解。最后来看一下删除操作, ...
浙大数据结构Week3
课程地址:https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
第三周的内容是讲树,现在来回顾下。
Part1:回顾1.树的定义光看定义还挺抽象,但是看下示意图还是比较好理解的,注意这里互不相交这个特点很关键,可以据此来判断一个结构是否为树,例如一下三个例子均不是树。再来看一些常用术语,这里只列几个最常用的。
节点的度:节点的子树个数
树的度:树的所有节点中最大的度数
叶节点:度为0的节点
根节点:没有父节点的节点
父节点:有子树的节点是其子树的根节点的父节点
子节点:若A是B的父节点,那么B是A的子节点
兄弟节点:具有同一父节点的各个节点彼此是兄弟节点
现在有了抽象数据结构,那么在计算机中如何表示呢?课程中老师给了一种通用方法,适用于任何树,称为儿子兄弟表示法,即每个节点由三个元素构成,分别为节点的值,指向兄弟节点的指针,指向子节点的指针。树的集合称为森林,可以看出森林也可以使用儿子兄弟表示法表出,只要将每个根节点指向下一颗数即可。
2.二叉树现在来看一种特殊的树,二叉树。二叉树的特点为每个节点有0到2个子节点, ...
斯坦福CS106A作业1
一直想学这门课,网易公开课的版本确实不错,但是代码看不清,非常难受,所以自己搬运了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的,老师讲课很有意思,难度不大,感觉这门课的精华是作业,所以在这里 ...
浙大数据结构Week2
课程地址: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 ...
浙大C语言Week1 and Week2
Week1这一周相对基础,只列两点
解释与编译的区别解释:一条一条运行编译:翻译完成之后运行这里老师说解释执行未必比编译执行慢,因为现在计算机的运算速度已经非常快了。
现在一般说哪个语言比较适合做什么不是说这个语言本身,而是这个语言有很强大的库函数。比如python的pandas,numpy库非常适合做科学计算,所以人们常说python适合做数据分析。
Week2这周的知识列三个要点
读取double类型数据的时候使用scanf(“%lf”,&a)
运算优先级
前缀后缀运算
浙大数据结构Week1
课程地址:https://www.icourse163.org/course/ZJU-93001笔记中图片均来自此mooc中讲义。
这周开始了浙大陈越老师的数据结构课程,听了一周,感觉讲的很清晰,现在总结一下。
Part1:回顾1. 什么是数据结构简单来说,就是数据对象在计算机中的组织方式,分为逻辑机构和物理存储结构,而数据对象必定和一些操作相关,这些操作就是算法。这里老师还提到抽象数据类型的概念,就是定义一个数据对象集和其操作集,而不管其具体的实现。举个例子,大家都知道矩阵,也知道它的运算,那么矩阵可以看成一个抽象数据类型,在计算机中具体由python还是C来定义这些细节就不是抽象数据类型关心的了。抽象的好处在与处理问题的时候只需要关注问题本身,而不用关注底层的实现。
2. 什么是算法算法的其实就是解决问题的方法,设计算法的时候要考虑时间复杂度和空间复杂度。时间复杂度一般就是考虑最坏情况以及渐进表示,因为最坏情况方便计算,而且算法只需要考虑当数据量大的情形,所以只需要考虑渐进表示。
3. 应用实例这部分也是这周的作业,虽然不算很难,但是本菜鸡还是折腾了很久。本周的例子是最大子列,PT ...