HI! 我是Maple 剛滿20歲沒多久的小朋友 請ㄅ要欺負窩QAQ

今日資料結構上課筆記

7. array v.s string

• Array in c
  • Compare int *lis1 and lis2[5] in c
    • same: list1 and list2 are pointers
    • diffrence:list2 reservers five locations
• structures又稱(Records)

8. 系統生命週期

• 基礎
  • 資料抽象化、演算法描述、效率分析與評估
• 大型程式視為系統
  • 發展到寫成程式的過程稱為系統生命週期 (System Life Cycle)
    • Requirements
      • 規格
    • Analysis
      • 發展多個用來解決問題的方法
      • 方法互相比較
      • Bottom-Up(由下而上)
        • 較古老、無結構化
        • 強調細微處程式編寫
      • Top-Down(由上而下)
        • 以程式最後的目標為開端
        • 將程式分割成可管理的片段
      • 對專案沒有整體計畫
        • 結構鬆散
        • 錯誤程式片段
    • Design
      • 觀察需要什麼
        • 資料物件(Data Object)
        • 運算(Operations)
      • 第一部分
        • 觀察導引出抽象畫資料型態(Abstraction Data Type)
      • 第二部分
        • 演算法的規格
        • 演算法所用設計策略
    • Coding
      • 為資料物件選擇表示法
      • 替處理資料物件的運算設計演算法
    • Verification
      • 驗證程式正確性
        • 使用已被證明其正確性的演算法可減少錯誤
      • 大量測資測試程式
        • 驗證到每一段程式碼
        • 程式的執行時間
      • 除錯
        • 更正一個錯誤可能產生更多錯誤

9. C語言 指標和動態記憶體配置

• &位址運算符號
• 指標為非負整數值
  • 可以對指標進行算術運算
• 不希望浪費記憶體儲存空間
  • 堆疊(Heap)
    • 執行時配置記憶體
  • malloc
    • 記憶體可以取得則回傳指標
      • 指向要求的記憶體起始位置
    • 記憶體不能取得則回傳空指標(NULL)
  • 不需要記憶體
    • free
• Example

#include <stdio.h>

int* pi = NULL;
float* pf = NULL;
pi = (int*)malloc(sizeof(int));
pf = (float*)malloc(sizeof(float));
*pi = 1024;
*pf = 3.14;
printf("An Interger = %d, A Float = %f\n", *pi, *pf);
free(pi);
free(pf);

• 有些系統中 malloc的結果是char*
• 對於ANSI C使用者而言 會發現結果是void*
  • 符號(int*)/(float*)為型別轉換

10. 演算法描述

• 演算法的觀念為電腦科學的基礎
  • 定義:一組有限大小的指令集,照著指令可完成特定的工作
    • 輸入
      • 由外界提供或者不需要輸入
    • 輸出
      • 會產生至少一個輸出
    • 明確性
      • 指令不能含糊不清
    • 有限性
      • 演算法在執行有限步驟後停止
    • 有效率性

Example BinarySearch(二元搜尋法)

#include <stdio.h>

int compare (int x, int y) {
    if (x > y) {
        return 1;
    } else if (x < y) {
        return -1;
    } else {
        return 0;
    }
}

int BinarySearch(int list[], int searchnumber, int left, int right) {
    int length = sizeof(list) / sizeof(int);
    left = 0, right = length - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        switch(compare(list[middle], searchnumber)):
        case 1:
            right = middle - 1;
            break;
        case 2:
            left = middle + 1;
        case 0:
        return middle;
    }
    return -1;
}

11. 印樹

• pre-order
• in-order