共找到3條詞條名為字典的結果 展開

字典

數據結構中元素的集合

字典(dictionary)是一些元素的集合。每個元素有一個稱作key的域,不同元素的key各不相同。有關字典的操作有:插入具有給定關鍵字值的元素、在字典中尋找具有給定關鍵字值的元素、刪除具有給定關鍵字值的元素。

抽象數據類型


抽象數據類型Dictionary的描述如下所示。若僅按照一個字典元素本身的關鍵字來訪問該元素,則稱為隨機訪問(randomaccess)。而順序訪問(sequentialaccess)是指按照關鍵字的遞增順序逐個訪問字典中的元素。順序訪問需藉助於Begin(用來返回關鍵字最小的元素)和Next(用來返回下一個元素)等操作來實現。
字典
字典
抽象數據類型Dictionary{
實例
具有不同關鍵字的元素集合
操作
Create():創建一個空字典
Search(k,x):搜索關鍵字為k的元素,結果放入x;
如果沒找到,則返回false,否則返回true
Insert(x):向字典中插入元素x
Delete(k,x):刪除關鍵字為k的元素,並將其放入x
}

重複元素


有重複元素的字典(dictionarywithduplicates)與上面定義的字典相似,只是它允許多個
元素有相同的關鍵字。在有重複元素的字典中,在進行搜索和刪除時需要一個規則來消除岐義。也就是說,如果要搜索(或刪除)關鍵字為k的元素,在有些字典應用中,可能需要刪除在某個時間以後插入的所有元素。

應用實例


學生成績

一個班中註冊學習數據結構課程的學生構成了一個字典。當有一個新學生註冊時,就要在字典中插入與該學生相關的元素(記錄)。當有人要放棄這門課程時,則刪除他的記錄。在上課過程中,老師可以查詢字典以得到與某特定學生相關的記錄或修改記錄(例如,加入或修改考試成績)。學生的姓名域可作為關鍵字。

符號表實例

在編譯器中定義用戶描述符的符號表(symboltable)就是一個有重複元素的字典。當定義一個描述符時,要建立一個記錄並插入到符號表中。記錄中包括作為關鍵字的描述符以及其他信息,如描述符類型(int,float等)和(相關的)存儲其值得內存地址。因為同樣的描述符號可以定義多次(在不同的程序塊中),所以符號表中必然存在有多個記錄具有相同的關鍵字,搜索結果應是最新插入的元素。只有在程序塊的結尾才能進行刪除,所有在開始插入的元素最終都要被刪除掉。