COMP9024学习笔记

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 1k 阅读时长 ≈ 4 分钟

前言

2023T2，麦克教。不愧是著名好老师，上课很生动，口音清晰。算法都会在讲台上用投影仪直接手算一遍伪代码，给你看为什么会输出这个结果。上课体验极好，建议线下全勤。上课用的语言是c，对于我这种初学的人还蛮难的，尤其是分配内存、链表这一块。定义稍稍不谨慎就会报错，和python的便利性没法比，但是也可以帮助你更好的了解数据结构。（毕竟，自律都是罚出来的是不是（

如何开始编c语言

建议新手直接用学校的lab做作业。。附学校链接（我只保证链接在23年T2是能用的）
Windows用户点这里
Mac用户点这里

一般我是这样，首先去下一个VNCviewer（下载链接自己找咯）
安装完后双击打开
输入vlab.cse.unsw.edu.au:5920，点连接
输入zID和zPass，就到一个Linux环境了。这个环境交作业啥的都很方便
里面也有各种各样的软件，有VScode，有Jupiter。。留着自己探索吧

本地环境

我的评价是下载VScode
还要下一个c语言编译器，老师推荐gcc，附下载链接
下载gcc点这里
记得将gcc加入系统环境变量
以Win11为例：
找到此电脑，右键选择属性，高级系统设置，环境变量
在系统变量中找到Path
请注意不是Admin的用户变量
双击Path或者点击编辑，新建，把...\TDM-GCC-64\x86_64-w64-mingw32\bin复制进去
最后把该目录下的mingw32-make.exe重命名为make.exe就可以在本地用老师给的makefile了

期末抱佛脚复习部分

期中之前的知识

Week 1 Elementary data and control structures in C

  1. 浮点数
1
%x.yf   #x为宽，y为精度
  1. 在c中字符串是一个字符的数组，并且结尾是\0
  2. scanf()、atoi()
    atoi()可以将字符串转换为int类型
  3. sum()求和函数
    sum()需要知道数组中元素的个数
1
sum(list[], len(list))
  1. 多元数组
    若 q = [[0, 1], [2, 3]]
    则 print(q[0]); #输出{0, 1}
  2. 自定义数据结构类型
    struct 可以打包不同类型的数据
1
2
3
4
typedef struct {
       char name[30];
       int  zID;
} StudentT;

如果后续想要调用该复合类型

1
2
StudentT.zID
StudentT.name
  1. struct需要的内存
    不满足8字节的类型会填充至8字节
    其余：
    float型占8字节
    int型占4字节
  2. 栈 LIFO（后进先出）
    队列 FIFO（先进先出）
  3. assert.h
    assert可以在不满足条件时，直接弹出程序
  4. static可以定义数据为本地类型

Week 2: Analysis of Algorithms

  1. 时间复杂度O(n)
    对于一个程序，假设它需要运行f(n)次
    如果存在常数c，n0, 对于任给n >= n0
    使得f(n) <= c * g(n)成立
    那么f(n) 属于O(g(n))
    要使用n的最小次方
  2. Binary Search 二分法
    时间复杂度为log2n
    但是由于对数的特性，底数不同差异很小
    可以简写为log n
  3. |Q|
    这并不是绝对值的意思，是栈或队列的大小
  4. Ω, Θ
    Big Omega Ω
    如果存在常数c，n0, 且n0 > 1, 对于任给n >= n0
    使得f(n) >= c * g(n)成立
    Big Theta Θ
    如果存在常数c1，n0, c2, 且n0 > 1, 对于任给n >= n0
    使得c1 * g(n) <= f(n) <= c2 * g(n)成立
  5. 链表 Linked List
    每个格子都要有两个元素
    （1）存储本身的数据
    （2）指针，指向下一个数据的地址
    每个链表的第一格head of list, 是指向该链表的指针
    最后一格的指针，指向NULL。意为链表结束。
    (睡醒施工)
    剩下的应该是不会再写了
  • Week 3: Dynamic data structures
  • Week 4: Graph data structuresk
  • Week 5: Graph algorithms
  • Week 7: Search trees
  • Week 8: Search tree algorithms
  • Week 9: Text processing algorithms, Approximation
  • Week 10: Randomised algorithms

期末用的Cheat Sheet

826f1970
826f1970