文章目录

General Question
Programming in C
- Struct 结构体
- typedef 与 #define
- Linked List 链表
Week 01 Introduction
Week 02 Analysis of Algorithms
Week 03 Dynamic Data Structures
Week 04 Graph Data Structures
- Lab 04 总结
Week 05 Graph Algorithms
- Lab 05 总结
Mid-term
- 21T2 期中真题回顾
Week 07

General Question

怎么交作业？

方法①：用Cyberduck在本地与CSE Vlab之间传输文件

1. 下载Cyberduck

2. 如何设置Cyberduck

方法②：使用scp指令

在CSE与Mac之间传输文件

从服务器传输文件至本地
scp [email protected]:服务器文件路径本地目标路径 从本地将文件传至服务器 scp 本地文件路径 [email protected]:服务器路径 从本地文件夹传至服务器 scp -r 文件夹/目录 [email protected]:服务器路径
按下回车后输入你的密码

关于scp指令还可以参考这个视频（需翻墙）：如何使用scp命令在本地环境与服务器之间传输文件、文件夹？

更多关于远程连接CSE的问题请移步UNSW CSE Home Computing
Mac环境下简化ssh连接Vlab口令实现免密登录(UNSW)
有意思的vim小游戏，帮你熟悉vim操作：VIM大冒险

Programming in C

在for循环中迭代n个元素，控制语句被执行n次，条件判断语句会被执行(n+1)次，所以一句迭代n个元素的for循环包含n+(n+1)次操作。
file.c : .c 文件即储存代码的源文件。 file.h :h代表head，每个c文件都跟着一个h文件，h文件的作用是放着c文件中函数的声明，结构体的定义，宏的定义等。 file.o :o代表output，o文件是目标文件。每个c文件的源码经过编译都会形成一个目标文件（二进制文件），多个目标文件链接后才能形成可执行文件。
一元运算符 * 是间接寻址或间接引用运算符。当它作用与指针时，将访问指针所指向的对象。 int *p; 这样声明是为了便于记忆。该声明语句表名表达式 *p 的结果是int类型，或者说int表示的是 *p 这个表达式的类型。C 语言设计的本意并不是把 int* 作为类型声明。它的设计本意是解一个方程，从表达式 *p 的类型是 int 反向推出未使用 *
操作的p是个int指针（指向int型变量的地址）。

虽然
int* p; 这种写法对于编译器来说和 int *p 没有区别（编译器忽视空格），但相比推荐的 int *p; 写法，它容易让人在定义语句中，误认为类型修饰符( * 或 &
)作用于本次定义的全部变量。

因为
int* 放在一起好像是这条语句中所有变量的共同类型一样。其实恰恰相反，基本数据类型是 int 而非 int* ， * 只是修饰了p而已，对于该语句中的其他变量， * 并不产生任何作用:
```
int* p1, p2;  // p1是指向int的指针，p2是int
int *p3, *p4;  // p3和p4都是指向int的指针
           
```
解决这个问题的好办法是：每个变量的声明独立成行，每行只定义一个变量，既方便注释，也避免上述的混淆

Struct 结构体

结构体是C编程中另一种用户自定义的可用的数据类型（int和char等这类是已经定义好的基本数据类型），它允许您在一个结构体中存储不同类型的数据项。
为了定义结构，您必须使用 struct 语句。struct 语句定义了一个包含多个成员的新的数据类型，struct 语句的格式如下：
```
struct tag { 
    member-list
    member-list 
    member-list  
    ...
} variable-list;
           
```
tag 是结构体标签。 member-list 是标准的变量定义，比如 int i; 或者 float f，或者其他有效的变量定义。结构体的成员可以包含其他结构体，也可以包含指向自己结构体类型的指针，而通常这种指针的应用是为了实现一些更高级的数据结构如链表和树等。我们使用成员访问运算符 . 来访问结构的成员，如 Books.title variable-list
结构变量，定义在结构的末尾，最后一个分号之前，您可以指定一个或多个结构变量。

一般情况下，
tag member-list variable-list 这 3 部分至少要出现 2 个。
数组用来储存相同类型数据项的变量，您可以定义一个结构体数组——一个储存了多个相同结构体的数组。
结构体内存大小对齐原则（这个部分有问题，待修改，请勿参考）
- 结构体变量的首地址能够被其最宽基本数据类型（结构体是符合数据类型，不是基本类型）成员的大小所整除。
- 结构体每个成员相对于结构体首地址的偏移量(offset)都是成员大小的整数倍，如有需要编译器会在成员之间加上填充字节(internal adding)。即结构体成员的末地址减去结构体首地址(第一个结构体成员的首地址)得到的偏移量都要是对应成员大小的整数倍。
- 结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要编译器会在成员末尾加上填充字节（padding)。
- eg:求下面结构体实际占用空间大小
```
struct eg {
char [13];
int age;
} example;
           
```
  char 1Byte，int 4Byte。最大数据类型是int 4Byte，1*13+4=17Byte,padding补齐至4Byte的整数倍，实际占20Byte
```
typedef struct {
char name[13];
} A ;

typedef struct {
A set[2];
char b;
} B ;

// A 是 13 Byte, B 是 27 Byte
           
```
  补丁是按顺序打的
```
// 下面这个结构体大小为12
typedef struct C {
	char a;  // 补3至4
	int b;  //不补
	char c;  // 补3至4
}C;
	// 下面这个结构体大小为8
	typedef struct D {
	char a;
	char b;  
	// 两个连续的char占2Byte需要补2至4
	int c;  //不补
}D;
           
```

参考资料

C结构体 - 菜鸟教程

typedef 与 #define

#define

是C指令，用于为各种数据类型定义别名，与

typedef

类似，但是它们有以下几点不同：

typedef 仅限于为类型定义符号名称， #define 不仅可以为类型定义别名，也能为数值定义别名，比如您可以定义 1 为 ONE。
typedef 是由编译器执行解释的， #define 语句是由预编译器进行处理的。

#define

可以使用其他类型说明符对宏类型名进行扩展，但对

typedef

所定义的类型名却不能这样做。例如：

#define INTERGE int;
unsigned INTERGE n;  //没问题

typedef int INTERGE;
unsigned INTERGE n;  //错误，不能在 INTERGE 前面添加 unsigned

在连续定义几个变量的时候，

typedef

能够保证定义的所有变量均为同一类型，而

#define

则无法保证。例如：

#define PTR_INT int *
PTR_INT p1, p2;  //p1、p2 类型不相同，宏展开后变为int *p1, p2

typedef int * PTR_INT
PTR_INT p1, p2;  //p1、p2 类型相同，它们都是指向int类型的指针。

typedef 还通常用于为数组或其他复杂的声明定义一个新的简单的别名，例如：表示用A代替 int a[6] 。即 A a; 等同于 int a[6];

参考资料

C typedef

Linked List 链表

头指针是链表中指向第一个结点的存储位置的指针，整个链表的存取就必须从头指针开始进行。头指针具有标识作用，故常用头指针冠以链表的名字。无论链表是否为空，头指针均不为空，头指针是链表的必要元素。之后的每一个结点，其实就是上一个的后继指针指向的位置。

头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。

头指针和头结点不同，链表中可以没有头结点，但不能没有头指针。

首元结点是指第一个元素的结点，也就是头结点后边的第一个结点。

在线性表的链式存储结构中：

若链表有头结点，则头指针就是指向链表头结点的指针；

若链表没有头结点，头指针是指链表指向第一个结点的指针。

Week 01 Introduction

Week 02 Analysis of Algorithms

Week 03 Dynamic Data Structures

指针是一种用于存储一个变量的内存地址的特殊变量，指针也像其他变量类型一样需要内存空间，所需内存空间与计算机架构有关：在16位计算机中需要2个储存单元，在32位计算机中需要4个储存单元，在64位计算机中需要8个储存单元。
所有指针都受约束于指向某种特定类型的对象。
如果指针p指向一个整形变量x，那么 *p 可以出现在任何 x 能出现的地方。
一些关于指针的例子

int *p; int *q; // this is how pointers are declared
int a[5];
int x = 10, y;

 p = &x;      // p now points to x
*p = 20;      // whatever p points to is now equal to 20
 y = *p;      // y is now equal to whatever p points to
 p = &a[2];   // p points to an element of array a[]
 q = p;       // q and p now point to the same thing

一个指针p储着一个值x的地址，C语言知道p所指向的x所属类型的大小即 sizeof(x) ，也可以通过 p++ 计算出下一个对象的地址 p + sizeof(x) 。指针的剪发运算同理
如果你要通过命令行给main()传入参数，需要不同类型的参数： argc argument counts，其值等于命令行参数个数+1。如果参数为0，那么argc == 1 argv[] argument virables，用于储存程序的名称+所有的参数，其中argv[0]总是程序的名称
命令行如何向fuction传入参数：

COMP9024笔记General QuestionProgramming in CWeek 01 IntroductionWeek 02 Analysis of AlgorithmsWeek 03 Dynamic Data StructuresWeek 04 Graph Data StructuresWeek 05 Graph AlgorithmsMid-termWeek 07

COMP9024笔记General QuestionProgramming in CWeek 01 IntroductionWeek 02 Analysis of AlgorithmsWeek 03 Dynamic Data StructuresWeek 04 Graph Data StructuresWeek 05 Graph AlgorithmsMid-termWeek 07

64位架构下常见数据类型的大小：

类型	大小
char	1 byte
short	2 byte
int	4 byte
float	4 byte
double	8 byte
pointer	8 byte

不同操作系统位数下不同类型所占的大小差别如下：

COMP9024笔记General QuestionProgramming in CWeek 01 IntroductionWeek 02 Analysis of AlgorithmsWeek 03 Dynamic Data StructuresWeek 04 Graph Data StructuresWeek 05 Graph AlgorithmsMid-termWeek 07

malloc()的用法

TicketT *tickets;
tickets = malloc(1000 * sizeof(TicketT));
assert(tickets != NULL);

C语言函数的声明以及函数原型

Week 04 Graph Data Structures

图的特性（假设一个图含有V个顶点和E条边）：

含有V个顶点的图最多有V(V-1)/2条边
如果E更接近V^2，这个图是稠密的（dense）

如果E更接近V，这个图是稀疏的（sparse）

图是稠密的或是稀疏的，可能影响到我们选择表达这个图的数据结构和处理这个图的算法
vertex = node = 顶点, edge = arc = link = 边
刚接触欧拉和汉密尔顿的时候总是分不清哪个和边有关哪个和点有关，这里分享一个谐音助记：
- 用一个O型环可以去拉图的边-欧拉是和边有关的概念
- 汗和米都是一点一点的的-汉密尔顿是和点有关的概念
判断连通图是否存在欧拉通路、欧拉回路的方法

连通图	欧拉通路	欧拉回路
有向图	有一个顶点出度比入度大1，另一个顶点入度比出度大1，其余顶点都是出度=入度	所有的顶点出度=入度
无向图	只有两个顶点是奇数度，其余顶点都是偶数度（奇数度的点为起止点）	所有顶点的度都为偶数

欧拉回路基本概念+判断+求解

Lab 04 总结

遍历链表中的结点，往往通过while循环实现。注意有while循环，就一定要有改变while控制条件的迭代语句，建议当while循环产生时就把迭代语句写上，避免遗漏

双链表插入newNode时受影响的指针数：

如果list为空，插入newNode作为第一个结点，合计2个指针受影响：

// 如果list为空，合计2个指针受影响：
list->head = newNode;
list->tail = newNode;

在不为空的双链表中插入新的头结点，合计3个指针受影响：

// 在不为空的双链表中插入新的头结点，合计3个指针受影响：
newNode->next = list->head;  // 让newNode的next指向原list的头结点
list->head->prev = newNode;  // 让原list头结点的prev指向newNode
list->head = newNode;  // 新list的头指针指向newNode

在list中间某处curNode前插入newNode，合计4个指针受影响：

// 在list中间curNode前插入newNode，合计4个指针受影响：
newNode->next
newNode->prev
cur->prev = newNode;
cur->prev->prev->next = newNode;

在不为空的双链表中插入新的尾结点，合计3个指针受影响：

// 在不为空的双链表中插入新的尾结点，合计3个指针受影响：
newNode->prev = list->tail;  // 让 newNode的prev 指向 原list的尾结点
list->tail->next = newNode;  // 让 原list尾结点的next 指向 newNode
list->tail = newNode;  // 让 list的tail 指向 新的尾结点即newNode

为字符串分配动态内存空间

// 给char型指针data分配能容纳字符串value的空间，并在该空间存储字符串value代表的值
char *data;
data = malloc(sizeof(char) * (strlen(value) + 1);  // +1是为了多一位给'\0'
assert(data != NULL);  // could be dropped
strcpy(findingNode->data, value);
// add '\0' at the end of value
data[strlen(value)] = '\0';

快慢指针解题技巧

Week 05 Graph Algorithms

Lab 05 总结

size_t是一个基本的无符号整数的C/C++类型，它是 sizeof
操作符返回的结果类型，该类型的大小可选择。因此，它可以存储在理论上是可能的任何类型的数组的最大大小。换句话说，一个指针可以被安全地放进为size_t类型（一个例外是类的函数指针，但是这是一个特殊的情况下）。

size_t类型通常用于循环、数组索引、大小的存储和地址运算。虽然size_t可以存储一个指针，它的目的是更好地使用另一个unsigned整数类型uintptr_t。在某些情况下，使用size_t类型是更为有效，比习惯性使用无符号类型的程序会更安全。(这段话是百度百科里的，感觉语序不通顺没读懂…）

size_t是在基于无符号整数memsize类型的C/C++的标准库中定义的。C语言中，此类型位于头文件stddef.h中，而在C++中，则位于cstddef.h中。
把size_t类型的变量赋值给int类型变量的时候系统有警告，反过来把int类型变量赋给size_t类型时无警告。

这是因为size_t是unsigned int类型，而int是signed int类型，C/C++ 规定signed int可以赋给unsigned int而unsigned int不能随便赋给signed int。

数据存入存储空间中是以补码的形式存的，当a=b的时，实际上是把b的补码存入了a的存储空间(&a)中。带符号的数储存时要在第一位专门保存符号，不带符号的数赋给带符号的会导致第一位溢出（数据截断）。而带符号的数赋给不带符号的数则不会导致溢出。

// TODO: 如果故意把-1赋值给一个size_t类型的变量，然后打印这个变量，值显然就是不对的，但却没有警告，这是为什么呢？

Mid-term

不同表达方式下不同操作的算法复杂度

Graph	Insert	Delet	Search	Creat
Array of edges	O(1)	O(E)	O(E)	O(1)
Adjacency matrix	O(1)	O(1)	O(1)	O(V²)
Adjacency list	O(1)	O(V)	O(V)	O(V)

注：O(1)∈O(n)∈O(n²)

Adjacency Matrix Represention can represent graphs, digraphs and weighted graphs. For digraphs, the Adjacency Matrix is a non-symmetric boolean matrix

True.

Adjacency Matrix Represention can represent graphs, digraphs and weighted graphs. For digraphs, the Adjacency Matrix is a symmetric boolean matrix

False.
DFS用stack实现，允许有重复的点，
BFS用queue实现，不许有重复的点，可以用于找最短路径
DFS和BFS都可以用于探测环
删除Array of edges中的一条边，算法复杂度是O(E);

删除Array of edges中的所有边，算法复杂度是O(1)，即free列表

21T2 期中真题回顾

Linear Search vs Binary Search

Important Differences
- Input data needs to be SORTED in Binary Search and NOT SORTED in Linear Search
- Linear search does the sequential access whereas Binary search access data randomly.
- Time complexity of linear search -O(n) , Binary search has time complexity O(log n).
- Linear search performs equality comparisons and Binary search performs ordering comparisons
  
  数组查找: 线性查找与二分查找

COMP9024笔记General QuestionProgramming in CWeek 01 IntroductionWeek 02 Analysis of AlgorithmsWeek 03 Dynamic Data StructuresWeek 04 Graph Data StructuresWeek 05 Graph AlgorithmsMid-termWeek 07

文章目录

General Question

Programming in C

Struct 结构体

typedef 与 #define

Linked List 链表

Week 01 Introduction

Week 02 Analysis of Algorithms

Week 03 Dynamic Data Structures

Week 04 Graph Data Structures

Lab 04 总结

Week 05 Graph Algorithms

Lab 05 总结

Mid-term

21T2 期中真题回顾

Week 07

继续阅读

【趋高机器视觉】机器视觉技术原理解析及解决方案

[转]ISUP信令的IAM消息详细内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

C语言：初学者必定看懂的注释！！！猴子吃桃问题。猴子第一天摘下若干个桃子，每天都吃了前一天剩下的一半零一个，到第10天早上想再吃的时候，就剩下一个桃子. 求第一天共摘多少个桃子。

[转]九大排序算法——C语言实现及详解

笔试面试题目：滑动窗口(二)

while 循环、do- while 循环和 for 循环之间的那点事C语言自学之三种循环比较

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

结构体：typedef与struct的区别

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希