文章目錄

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哈希