試題四
一個關于hash的數據結構題,答案不唯一...

#define NULLKey -1 /*散列桶的空閑單元標識*/
#define P 7 /*散列文件中基桶的數目*/
#define ITEMS 3 /*基桶和溢出桶的容量*/
typedef struct BucketNode { /*基桶和溢出桶的類型定義*/
int KeyData[ITEMS];
struct BucketNode *Link;
}BUCKET;
BUCKET Bucket[P]; /*基桶空間定義*/
[函數]
int InsertToHashTable(int NewElemKey){
/*將元素NewElemKey插入散列桶中,若插入成功則返回0,否則返回-1*/
/*設插入第一個元素前基桶的所有KeyData[]、Link域已分別初始化為NULLKEY、NULL*/
int Index; /*基桶編號*/
int i,k;
BUCKET *s,*front,*t;
____(1)____;//(1)Index=NewElemKey%P
for(i=0; i<ITEMS; i++) /*在基桶查找空閑單元，若找到則將元素存入*/
if (Bucket[Index].KeyData[i] == NULLKEY) {
Bucket[Index].KeyData[i] = NewElemKey; break;
}
if (____(2)____)return 0;//(2)i<ITEMS
/*若基桶已滿，則在溢出桶中查找空閑單元，若找不到則申請新的溢出桶*/
_____(3)_____; t = Bucket[Index].Link;//(3)front=&Bucket[Index]，或front=Bucket+Index
if (t != NULL) { /*有溢出桶*/
while (t != NULL) {
for(k = 0;k < ITEMS; k++)
if (t -> KeyData[k] == NULLKEY) { /*在溢出桶鏈表中找到空閑單元*/
t -> KeyData[k] = NewElemKey; break;
}/*if*/
if (____(4)____) t = t-> Link;//(4)k>=ITEMS
else break;
} /*while*/
} /*if*/
if (____(5)____) { /*申請新溢出桶并將元素存入*///(5)t==NULL
s = (BUCKET *)malloc(sizeof(BUCKET));
if (!s) return -1;
s->Link = NULL;
for(k = 0; k < ITEMS; k++)
s->KeyData[k] = NULLKEY;
s->KeyData[0] = NewElemKey;
_____(6)_____;//(6)front->Link=s;
} /*if*/
return 0;
}/*InsertToHashTable*/

試題五
#include <iostream>
const OBS_MAXNUM = 20 //最多與OfficeDoc對象相關聯的DocExplorer對象的個數
____(1)____; //(1)class OfficeDoc

class DocExploer { //關注OfficeDoc公文對象的類
public:
DocExplorer (____(2)____ *doc); //構造函數
//(2)OfficeDoc
_____(3)____ void update(OfficeDoc *doc)=0; //更新自身狀態的函數
//(3)virtual
//其它相關屬性和方法省略
}

class OfficeDoc{ //公文類
private:
DocExploer *myObs[OBS_MAXNUM];
//關注此公文類的DocExplorer類對象指針數組
int index; //與OfficeDoc對象關聯的DocExploer對象的個數
public:
OfficeDoc(){
index=0;
}
void attach(DocExploer *o){
//將一DocExploer對象與OfficeDoc對象相關聯
if (index >= OBS_MAXNUM || o == NULL) return;
for (int loop = 0; loop < index; loop++)
if (myObs[loop] == 0) return;
myObs[index] = o;
index++;
}
void detach(DocExploer *o){
//解除某DocExploer對象與OfficeDoc對象的關聯
if(o==NULL) return;
for(int loop = 0 ;loop < index; loop++){
if(myObs[loop] == o){
if (loop <= index-2) myObs[loop] = myObs[index-1];
myObs[index-1] = NULL;
index--;
break;
}
}
}
private:
void notifyObs(){ //通知所有的DocExplorer對象更改自身狀態
for(int loop = 0; loop <index; loop++) {
myObs[loop]->____(4)____; //DocExplorer對象更新自身狀態 
//(4)update(this)
}
}
//其它公文類的相關屬性和方法
};

DocExplorer::DocExplorer(OfficeDoc *doc){ //DocExploer類對象的構造函數
doc->____(5)____; //將此DocExplorer對象與doc對象相關聯
//(5)attach(this)
}

試題七
用C實現試題五
#include <stdio.h>
#define OBS_MAXNUM 20 /*一個OfficeDoc變量最多能夠關聯的DocExplorer變量的個數*/
typedef void (____(1)____) (struct OfficeDoc * ,struct DocExplorer *);
//(1)*func

struct DocExplorer {
func update; /*DocExplorer結構采用的更新函數*/
/*其它的結構字段省略*/

};

struct OfficeDoc{
___(2)____myObs[OBS_MAXNUM]; //(2)struct DocExplorer*
/*存儲所有與OfficeDoc相關聯的DocExplorer結構指針*/
int index; /*與OfficeDoc結構變量相關聯的DocExplorer結構變量的個數*/
};

void attach(struct OfficeDoc *doc, struct DocExplorer *ob){
/*關聯Obersver結構ob與OfficeDoc結構doc*/
int loop = 0;
if (doc -> index >= OBS_MAXNUM || ob == NULL) return;
for(loop = 0; loop < doc->index; loop++)
if (doc -> myObs[loop] == ob) return;
doc->myObs[doc->index] = ob;
doc->index++;
}

void detach(struct OfficeDoc *doc, struct DocExplorer *ob) {
/*解除doc結構與ob結構間的關系*/
int loop;
if(ob == NULL) return;
for(loop = 0;loop < doc->index; loop++){
if(doc->myObs[loop] == ob){
if (loop <= doc->index - 2)
doc->myObs[loop] = doc->myObs[____(3)____];//(3)doc->index-1
doc->myObs[doc->index-1] = NULL;
doc->index--;
breack; 
}
}
}

void update1(struct OfficeDoc *doc, struct DocExplorer *ob){
/*更新ob結構的值,更新代碼省略*/ 
}

void update2(struct OfficeDoc *doc, struct DocExplorer *ob){
/*更新ob結構的值，更新代碼省略*/
}

void notifyObs(struct OfficeDoc *doc){
/*當doc結構的值發生變化時，通知與之關聯的所有DocExplorer結構變量*/ 
int loop;
for(loop = 0; loop < doc->index; loop++){
(doc->myObs[loop])->update(____(4)____);//(4)doc,doc->myObs[loop]
} 
}

void main() {
struct OfficeDoc doc; /*定義一OfficeDoc變量*/
struct DocExplorer explorer1,explorer2; /*定義兩個DocExplorer變量*/
/*初始化與OfficeDoc變量相關的DocExplorer變量個數為0*/
doc.index = 0;
explorer1.update = update1; /*設置explorer1變量的更新函數*/
explorer2.update = update2; /*設置explorer2變量的更新函數*/
attach(&doc , &explorer1); /*關聯explorer1與doc對象*/
attach(&doc , &explorer1); /*關聯explorer1與doc對象*/
/*其它代碼省略*/
_____(5)____;/*通知與OfficeDoc相關的所有DocExploer變量*/
//(5)notifyObs(&doc)
return;
}