试题四
一个关于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;
}