建立完全醢序的一些方法及其在動態醢序檔設計上的應用

Abstract

本論文研究兩個主題：設計完全醢序函數及設計動態醢序函數。 本文提出兩種方法來設計完全醢序函數：”鍵序處理法”及””回找法”。兩者皆以 醢序指示表的觀念來定義完全醢序數。鍵序處理法與”函數序處理法”之區別在於當 建立醢序指示表時，選擇單值鍵之順序不同。由於鍵序處理法之特性，此法能夠處理 動態之鍵集合。 在一代表鍵集合及醢序函數之對映表中，若完全醢序函數存在，鍵序處理法及函數序 處理法都可能遺漏。而回找法則一定可找到。實驗值顯示，任意給一對映表，以回找 法找到完全醢序函數的機率大於鍵序處理法及數序處理法甚多。例如，當鍵集合中元 素個數n ＝２５，密度值 ＝０．８，醢序函數之個數s ＝７時，回找法找到完全醢 序函數之實驗值為９７％，而鍵序處理法及函數序處理法分別只有１２％２３％。 在設計動態醢序函數方面，本文亦提出兩種方法：可擴展鍵序處理法及可延長醢序表 法。兩種方法在存體之使用率上都很穩定。其中，第一種方法也是以醢序指示表來定 義完全醢序函數，但其醢序指示表之長度隨處理中之鍵集合大小調整。第二種方法是 利用修正的醢序指示表，即加一分配樹將欲處理之鍵先分配到醢序指示表不同的區段 上。如此則儲刈存體不必整個重組即可增加或縮小資料檔。當醢序函數個數s ＝７， 每一區段長r ＝１０，n 變化於１到１０００時，此法之儲存體使用率約保持於７０ ％。