Bo2SS

課程內容#

引言#

• 【基礎數據結構】課程綜述
  • 
  • 重點掌握紅色！
• 三個等式
  • 程式 = 演算法 + 數據結構
  • 程式設計 = 演算法 + 數據結構 + 程式設計範式
  • 數據結構 = 結構定義 + 結構操作
• 透過演算法與數據結構，使計算機合理利用資源，讓計算資源更有價值

順序表#

【功能更高級的數組】

結構定義#

• 空間連續，可以存儲任意類型的相同元素
  • 順序表裡也可以存順序表
• size：順序表的空間大小
• length：已存儲的元素個數
• data_type：存儲的元素類型

結構操作#

• 插入
  • 
  • 👇👇👇
  • 
  • 不能空著插，必須連續
  • 插入位置後的所有元素向後移動一位
    • 從後開始移動，每個元素向後移動一位
  • 必須要改變的屬性：length + 1
    • size 有可能需要改變，擴容請看下面
• 刪除
  • 
  • 👇👇👇
  • 
  • 不是真的刪除，而是告訴系統這個地址的存儲區可以被佔用、被覆蓋
  • 將後面所有的元素整體向前移動一位
    • 相當於要刪除的位置的值被覆寫
    • 最後一個值怎麼覆寫？
      • 直接將 length - 1
      • 其實都可以自定義設計
  • 必須要改變的屬性：length - 1
• ⭐添加擴容操作
  • 動態內存分配函數
    • malloc：只是開辟空間，值不確定。舉例：開房沒有保潔阿姨
    • calloc：開辟空間，並且初始化。舉例：開房後有保潔阿姨打掃清理
    • realloc：重新開辟空間。舉例：升級房型

​ void* realloc (void* ptr, size_t size); // 返回新開辟空間的首地址

3 種情況【realloc】

1. 先試探能不能在原地址後面直接加空間，空間首地址不變；如果不行，
2. 換個地址找找，申請空間，然後把原空間數據拷貝到新空間，並 free 掉原空間；如果不行，（自己可以設計減少擴容）
3. 就返回空地址，不清空當前地址

鏈表#

結構定義#

• 

• 程式內部 + 內存內部

  • 【程式內部】只暴露頭指針
    • 頭指針、小抓手、雞媽媽：記錄第一個結點的地址
    • 聯想老鷹捉小雞
  • 【內存內部】是連接的結點
    • 結點：數據域 + 指針域
    • 指針域
      • 最後一個結點的指針域為 NULL
      • 單向鏈表的指針域又名 “後繼”；雙向鏈表有 “前驅” 和 “後繼”

• 與順序表都屬於順序存儲結構

  • 鏈表思維邏輯上連續，但物理上不一定連續

結構操作#

• 插入
  • 
  • ①走到待插入位置的前一個位置的結點 p
  • ②先將新的結點 x 的指針域指向待插入位置的結點 p.next
  • ③將 p 的指針域指向新的結點 x
  • 順序不能變！否則可能引發內存泄漏（你想用已經用不了，但系統卻以為你在用）
• 刪除
  • 走到待刪除結點位置的前一個位置
• 翻轉
  • 方法一
    • 用一個新鏈表存，使用頭插法
    • 不斷在 index = 0 的位置插入結點
    • 不足：浪費空間，麻煩
  • 方法二
    • 原地翻轉，用兩個變量倒，也是頭插法
    • 前提：每次操作不要造成內存泄漏
    • NULL 地址還是在最後面，不會翻轉
• 代碼演示見後

單向循環鏈表#

• head 永遠記錄的是尾結點的地址～

1. 對於需在 index = 0 插入結點的情況
   • 
   • 🆒當 head 記錄的是尾結點時，直接在 head 指向的尾結點後插入即可
   • ❌如果 head 記錄的還是首結點的地址，不好使，因為
     • 要找 index = 0 的結點的前一個結點，可能需要遍歷完整個鏈表找到尾結點
     • 而不像單向鏈表那樣，可以直接在 head 後、index = 0 結點前插入
2. 對於在尾部插入結點的情況
   • 
   • 需要修改 head 指向新的尾結點【8】！

代碼演示#

順序表#

• 初始化、銷毀
  • 使用 malloc 開辟空間初始化該結構
  • 從結構裡到外 free，再將指針置空
• 擴容操作
  • realloc 返回地址先賦給中間變量，避免返回 NULL 的情況，導致原數據迷失
  • realloc 成功後原地址空間自動被 free
  • 可設計折半減小的擴容空間，直到確實一點空間都不剩返回失敗標誌 0
  • 細節很多，詳見註釋
• 插入、刪除
  • 注意不能操作的情況
  • 插入滿員時，進行擴容操作
• 打印：人性化
• main 函數測試：使用 rand ()、神奇的取模操作 (得到數據、模擬各種樣例、決定操作數)，記得 clear 空間

鏈表#

部分結果

• 

• 虛擬頭結點，方便插入和刪除第一個結點

  • 使用普通變量定義 head，❓考慮的是
    • 虛擬頭結點比較固定，不需要隨時 free
    • 普通變量比指針變量更穩定，沒必要 malloc

思考點#

• ⭐初始化數據結構 [比如鏈表、鏈表結點] 時，為什麼要動態開辟內存 [用 malloc 等]，而不是定義普通變量？
  • 首先，排除盲區：不是因為指針只能接受 malloc 返回的地址，指針也能指向普通變量
  • 關鍵：【malloc 申請的內存在堆空間，普通變量定義在棧空間 (在函數裡面定義的)】
  • 棧空間：大小只有 8MB；出了函數 [作用域] 變量就被自動釋放了
  • 堆空間：可分配大內存；變量生命週期長，一般需手動釋放
• ❓虛擬頭結點定義為普通變量和指針變量的區別
  • 個人理解，用指針變量，是為了接收 malloc 返回的地址
  • 而虛擬頭結點，在這只是個指示作用，不需要大空間，所以不需要 malloc，用普通變量即可

Tips#

• 學習程式設計不局限於語言

• 課後練習題

• 

課程速記#