軟件設(shè)計師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計師案例分析每日一練試題（2022/11/7）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/11/7

點擊查看：更多軟件設(shè)計師習(xí)題與指導(dǎo)

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2022/11/7）

試題四
閱讀下列函數(shù)說明、圖和C代碼，將應(yīng)填入  (n)  處的字句。
[說明]
散列文件的存儲單位稱為桶(BUCKET)。假如一個桶能存放m個記錄，當(dāng)桶中已有 m個同義詞(散列函數(shù)值相同)的記錄時，存放第m+1個同義詞會發(fā)生“溢出”。此時需要將第m+1個同義詞存放到另一個稱為“溢出桶”的桶中。相對地，稱存放前m個同義詞的桶為“基桶”。溢出桶和基桶大小相同，用指針鏈接。查找指定元素記錄時，首先在基桶中查找。若找到，則成功返回，否則沿指針到溢出桶中進行查找。
例如：設(shè)散列函數(shù)為Hash(Key)=Key mod 7，記錄的關(guān)鍵字序列為15,14,21,87,97,293,35,24,149,19,63,16,103,77,5,153,145,356,51,68,705,453，建立的散列文件內(nèi)容如圖4-1所示。
[圖4-1]

為簡化起見，散列文件的存儲單位以內(nèi)存單元表示。
函數(shù)InsertToHashTable(int NewElemKey)的功能是：將元素NewEIemKey插入散列桶中，若插入成功則返回0，否則返回-1。
采用的散列函數(shù)為Hash(NewElemKey)=NewElemKey % P，其中P為設(shè)定的基桶數(shù)目。
函數(shù)中使用的預(yù)定義符號如下：
#define NULLKEY  -1           /*散列桶的空閑單元標識*/
#define P   7                 /*散列文件中基桶的數(shù)目*/
#define ITEMS  3              /*基桶和溢出桶的容量*/
typedef struct BucketNode{    /*基桶和溢出桶的類型定義*/
int KcyData[ITEMS];
struct BucketNode *Link;
}BUCKET;
BUCKET Bucket[P];             /*基桶空間定義*/
[函數(shù)]
int lnsertToHashTable(int NewElemKey){
/*將元素NewElemKey插入散列桶中，若插入成功則返回0，否則返回-1*/
/*設(shè)插入第一個元素前基桶的所有KeyData[]、Link域已分別初始化為NULLKEY、
NULL*/
int Index;    /*基桶編號*/
int i,k;
BUCKET *s,*front,*t;
(1)  ;
for(i=0; i＜ITEMS;i++)/*在基桶查找空閑單元，若找到則將元素存入*/
if(Bucket[Index].KeyData[i]=NULLKEY){
Bucket[Index].KeyData[i]=NewElemKey;  break;
}
if(  (2)  ) return 0;
/*若基桶已滿，則在溢出桶中查找空閑單元，若找不到則申請新的溢出桶*/
(3)  ;        t=Bucket[Index].Link;
if(t!=NULL)   {/*有溢出桶*/
while (t!=NULL){
for(k=0; k＜ITEMS; k++)
if(t-＞KeyData[k]=NULLKEY){/*在溢出桶鏈表中找到空閑單元*/
t-＞KeyData[k]=NewElemKey;   break;
}/*if*/
front=t;
if(  (4)  )t=t-＞Link;
else break;
}/*while*/
}/*if*/
if(  (5)  ) {/*申請新溢出桶并將元素存入*/
s=(BUCKET*)malloe(sizeof(BUCKET));
if(!s)  return-1;
s-＞Link=NULL;
for(k=0; k＜ITEMS; k++)
s-＞KeyData[k]=NULLKEY;
s-＞KeyData[0]=NewElemKey;
(6)  ;
}/*if*/
return 0;
}/*InsertToHashTable*/