Homework Assignment #8

1. 假設一個三維整數陣列 A 的大小自第一維到第三維各為 m, n, 和 p, 且這些變數的值需到程式執行時才能決定,所以陣列 A 是一個動態陣列。畫出陣列 A 的位址圖示,並寫出陣列 A 記憶體空間分配的程式片段。

2. 下列圖示是一個單向連結表的圖,假設 ptr0, ptr1ptr2 是指向三個相鄰節點的指標:

a. 寫一個程式片段以定義單向連結表結點的資料型態。

b. 用圖示畫出改變節點指標的步驟,以交換 ptr1ptr2 所指的兩個紅色節點順序。(提示: 本題不可直接交換節點的值。共三個步驟,步驟 1 如下圖所示。)

c. 寫一個程式片段以交換 ptr1ptr2 所指的兩個紅色節點順序。

3. 下列圖示是一個雙連結表的圖,假設 ptr1ptr2 是兩個節點 (不一定相鄰) 的指標:

a. 寫一個程式片段以定義雙向連結表節點的資料型態。

b. 用圖示畫出改變節點指標的步驟,以交換 ptr1ptr2 所指的兩個紅色節點順序。(提示: 本題不可直接交換節點的值。需使用一個 temp 節點指標;共十個步驟,步驟 1, 2, 3 如下圖所示。)

c. 寫一個程式片段以交換 ptr1ptr2 所指的兩個紅色節點順序。

4. 假設你將設計及實作以下 string.h 的副程式,即是你的實作不能呼叫 strig.h 的副程式,除非是本題已完成的副程式。各副程式的意義請參考 The C Library Reference Guide 的定義。使用迴圈 (loop) 或遞迴副程式 (recursive function) 寫出下列副程式的 C 語言程式碼 (program code):

size_t strlen(const char *str);

int strcmp(const char *str1, const char *str2);

char *strcpy(char *str1, const char *str2);

char *strcat(char *str1, const char *str2);

char *strpbrk(const char *str1, const char *str2);

size_t strspn(const char *str1, const char *str2);

char *strstr(const char *str1, const char *str2);