文章目錄

• • • 0.抽象數據類型(ADT)的優點？
    • 1.為什么需要鏈表？
    • 2.鏈表的概念？
    • 3.隊列的概念？
    • 4.為什么需要二叉查找樹？

0.抽象數據類型(ADT)的優點？

ADT版本可讀性高，隱藏編程細節，對終端用戶隱藏數據表示的細節。

可復用。用戶接口是根據抽象操作定義的，不是根據某些特定的數據表示和算法來定義。

方便找bug，如果程序運行出現問題，可以把問題定位到具體函數上。如果有更好的方法，只需重寫相應的函數。

可擴展性好，如果需要性能，可添加新函數，不用修改實現程序。

1.為什么需要鏈表？

使用數組時，數據表示不夠靈活。如果只需20個元素，程序不必分配存放500個元素的空間。所以應使用動態內存分配來表示數據，使所需內存量在運行時確定。

使用malloc分配合適的內存空間，此時數據的查找不方便。添加數據時，如果輸入300個數據，需要malloc300次，無法保證調用malloc()都能分配到連續的內存塊，意味著數據不一定被連續存儲。 此時需要存儲300個指針，每個指針指向一個單獨存儲的結構。

使用malloc為新結構分配空間時，也為新指針分配空間。每個新結構中包含指向next結構的指針。創建新結構時，可以把該結構地址存儲在上一個結構中。這樣可以良好的表示和查找數據。

鏈表結構含有指向同類型結構的指針。

2.鏈表的概念？

定義一個結構體，里面包含了幾個變量，還有指向同類型結構的指針。

#define TSIZE 45 struct film{char title[TSIZE];int rating;struct film * next; } struct film * head;

需要一個單獨的指針存儲第一個結構的地址，被稱為頭指針。

如果加入新的數據，首先分配內存空間，然后把新結構的地址存儲在第一個結構的next成員中，并把新結構的next成員設置為NULL，表明該結構是鏈表中最后一個結構。

顯示這個鏈表，根據該項存儲的地址定位下一個項。

釋放鏈表，調用free。

3.隊列的概念？

隊列是具有兩個特殊屬性的鏈表，新項只能添加到鏈表的末尾，只能從鏈表的開頭移除項。先進先出的數據形式。

4.為什么需要二叉查找樹？

訪問元素有兩種，隨機訪問：使用數組下標直接訪問該數組中的任意元素；順序訪問：對于鏈表而言，必須從鏈表首節點開始，逐個節點移動到要訪問的節點。

用數組可以實現二分查找，因為可以使用數組下標確定數組中任意部分的中點。但是鏈表只支持順序訪問，不提供跳至中間節點的方法，所以鏈表中不能使用二分查找。

有一種數據形式的需求，既支持頻繁插入和刪除項，又支持頻繁查找。此時需要二叉查找樹。

總結

以上是生活随笔為你收集整理的链表 队列 基本概念 为什么使用二叉查找树 抽象数据类型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。