使用C語言實現資料結構 - 概述

什麼是資料結構？

資料結構是一種以特定方式組織資料，以便能夠高效使用資料的方法。以下術語是資料結構的基礎術語。

• 介面 - 每個資料結構都有一個介面。介面表示資料結構支援的操作集合。介面僅提供支援的操作列表、它們可以接受的引數型別以及這些操作的返回型別。

• 實現 - 實現提供了資料結構的內部表示。實現還提供了資料結構操作中使用的演算法的定義。

資料結構的特徵

• 正確性 - 資料結構的實現應該正確地實現其介面。

• 時間複雜度 - 資料結構操作的執行時間或執行時間必須儘可能短。

• 空間複雜度 - 資料結構操作的記憶體使用量應儘可能少。

資料結構的必要性

隨著應用程式變得越來越複雜和資料豐富，如今應用程式面臨著三個常見問題。

• 資料搜尋 - 考慮一家商店擁有 100 萬 (10⁶) 件商品的庫存。如果應用程式要搜尋某個商品，則每次都必須在 100 萬 (10⁶) 件商品中搜索該商品，從而降低搜尋速度。隨著資料量的增長，搜尋速度會變得越來越慢。

• 處理器速度 - 儘管處理器速度非常高，但如果資料增長到數十億條記錄，則處理器速度仍然有限。

• 多個請求 - 由於數千名使用者可以同時在 Web 伺服器上搜索資料，即使是最快的伺服器在搜尋資料時也會出現故障。

為了解決上述問題，資料結構可以提供幫助。資料可以以特定方式組織到資料結構中，這樣可能不需要搜尋所有專案，並且可以幾乎立即搜尋所需的資料。

執行時間情況

有三種情況通常用於以相對方式比較各種資料結構的執行時間。

• 最壞情況 - 這是特定資料結構操作可能花費的最長時間。如果某個操作的最壞情況時間為 ƒ(n)，則此操作花費的時間不會超過 ƒ(n)，其中 ƒ(n) 表示 n 的函式。

• 平均情況 - 這種情況描述了資料結構操作的平均執行時間。如果某個操作執行時間為 ƒ(n)，則 m 個操作將花費 mƒ(n) 的時間。

• 最好情況 - 這種情況描述了資料結構操作的最小可能執行時間。如果某個操作執行時間為 ƒ(n)，則實際操作可能花費的時間是一個隨機數，其最大值為 ƒ(n)。