資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學不同資料結構在編譯器設計中的作用是什麼？
在編譯過程中，每次遇到識別符號時都會搜尋符號表。如果找到新的名稱或關於現有名稱的新資訊，則會新增資料。因此，在設計符號表結構時，需要一種能夠有效地插入新條目並識別表中現有條目的方案。
資料結構中使用了四種符號表，如下所示：
- 列表- 為符號實現資料結構的最簡單明瞭的方法是線性記錄列表，如圖所示。
它可以使用單個數組或多個等效陣列來儲存名稱及其相關資料。新名稱按遇到的順序插入列表中。可以從陣列的開頭搜尋到指標AVAILABLE標記的位置（表示陣列空閒部分的開頭）來檢索關於某個名稱的資料。
自組織列表- 透過增加少量額外空間，我們可以使用一個技巧來節省大量搜尋符號表的時間。它可以為每個記錄新增一個LINK欄位，我們按照LINK指示的順序搜尋列表。當引用名稱或第一次建立其記錄時，可以透過移動指標將該名稱的記錄移動到列表的前面。
搜尋樹- 符號表組織的更有效方法是為每個記錄插入兩個連結欄位LEFT和RIGHT。我們使用這些欄位將記錄連結到二叉搜尋樹中。
這棵樹具有這樣的特性：透過遵循LEFT(i)連結，然後遵循任何連結序列，從NAME(i)訪問的所有名稱NAME(j)都將按字母順序（符號上，NAME(j) < NAME(i)）在NAME(i)之前。
二叉搜尋樹演算法
- 最初，Ptr將指向樹的根。
- 當Ptr ≠ NULL時
- 如果NAME = NAME(Ptr)
- 則返回true
- 否則如果NAME < NAME(Ptr) 則
- Ptr = LEFT(Ptr)
- 否則 Ptr = RIGHT(Ptr)
- 迴圈結束
雜湊表- 雜湊表包含K個從0到K-1的條目。這些條目是指向符號表的指標，指向符號表的名稱。我們可以使用雜湊函式'h'來判斷“Name”是否在符號表中，使得h(Name)的結果是0到K-1之間的整數。可以透過position = h(Name)來搜尋任何名稱。
更新於：2021年11月8日
3K+瀏覽量
廣告