lyharthur's Hw3
這次作業是要從期初測驗中貼選出至少三個題目分別做出遞迴與非遞迴版本,並分析測試。
  • 應該要有完整的測試程式,並測試各項邊界狀況 
  • 執行時間分析
  • 記憶體需求分析
  • cache miss 分析
  • 時間複雜度分析
自己對於驗證程式碼正確性的方法並不是很會,故有參考其他同學的main來設計驗證方法。
Question #2  smallest_character 
Iterative Version
char smallest_character(char str[], char c) {
    int i=0;
    while(str[i]!='\0'){
        if(c<str[i])
            return str[i];
        i++;
    }
    return str[0];
}
很直覺的利用迴圈進行一步一步的比較。
可改善搜尋的方法,例如使用Binary Search
 
Recursive Version
char smallest_character_r(char str[], char c, int index)
    if(str[index] == '\0') return str[0];
    if(str[index] > c) return str[index];
    else  return smallest_character_r(str,c,index+1);
} 
兩種版本的時間複雜度都為O(n)
發現了問題在OSX編譯出來的執行檔答案會是對的,但是從Linux編譯出來的第三筆測資會過不了,會return出奇妙的東西。
經過杰翰同學的建議在linux中安裝了clang後(因為OSX下的編譯器是clang),使用clang編譯程式碼。執行後測資會過。有可能是程式碼的判斷式沒寫好導致 str[] 跑到不該去的地方。
最後解決了...是我的測資寫太爛,導致迴圈無法順利結束,所以會輸出str[]後面的那個位置。
 
Question #3  flatten 
Iterative Version
void flatten(struct TreeNode *root){
    if(!root)return ;
    TreeNode* node = root;
    TreeNode* tmp1;
    TreeNode* tmp2;
    while(node) {
        if(node->left){
            tmp1 = node->right;
            tmp2 = node->left;
            while(tmp2->right)
                tmp2=tmp2->right;
            node->right = node->left;
            node->left = NULL;
            tmp2->right = tmp1;