【正确答案】正确答案：定义散列表结点的数据结构如下： typedef struct{ E1emType elem； int flag， }item； 1)散列表的查找。算法的基本设计思想：先通过散列函数计算元素在散列表中位置，若此位置为空，则查找失败；若此位置为所查找元素，则查找成功：若此位置不为所查找元素，则使用线性探测法依次探测，直到找到元素或者查找失败。算法的代码： int Search(item h[m+1]，ElemType k){ ／／从散列表h[m+1]中查找元素k，若查找成功返回元素下标，否则返回一1 int i=hash(k)； ／／调用散列函数hash()计算地址 if(h(i]．elem==EMPTY) ／／元素为空则查找失败 return 一1， if(h[i]．flag!=DELETED＆＆h[i]．elem==k) ／／与所查找关键字相同并且没有被删除则成功 return i; else { ／／采用线性探测法继续查找 int j=i; for (jnt d=1：d<=m：d++) i=(j+d)％(m+1)； if(h[i]．elem==EMPTY)／／遇到有元素为空，则说明查找失败 return一1； if(h[i]．flag!=DELETED＆＆h[i]-elem==k) return i； } } return一1； ／／查找失败 }IISearch 另一种算法： int Search(item h[m+1]，E1emType k){ int i=hash(k)，j； for(int d=0;d<=m；d++) { j=(i+d)％(m+1); if(h[j]．eIem==EMPTY) return一1； if(h[J]．flag!=DELETED＆＆h[j].elem==k) return i; } } 2)散列表的插入。算法的基本设计思想：先通过散列函数计算元素在散列表中位置，若此位置为空或元素已被删除，则直接插入；若此位置已满，则使用线性探测法依次探测，直到找到为空或元素已被删除的结点进行插入。算法的代码： int Insert(item h[m+1]，ElemType k){ ／／向散列表h[m+1]中插入元素k，若插入成功返回元素下标，否则返回一1 int i=hash(k)； ／／调用散列函数hash()计算地址 if(h[i]．flag==DELETED｜｜h[i]．elem==EMPTY) { ／／元素为空或者已删除，则插入 h[i]．elem==k； h[i]．flag==INUSE； ／／插入成功 return i； } e1Se { ／／否则，采用线性探测法继续寻找可以插入的结点 int j=i; for(int d=1；d<=m；d++) { i=(j+d)％(m+1)； if(h[i]．flag==DELETED ｜｜h[i]．elem==EMPTY) { ／／遇到可插入结点则插入 h[i]．elem==k； h[i]．flag==INUSE; return i; ／／插入成功 } } } return 一1 ; ／／插入失败 }／／Insert 3)散列表的删除。算法的基本设计思想与5题中第4问基本一致。算法的代码： int Delete(int h[m+1]，ElemType k){ ／／从散列表h[m+1]中删除元素k，若删除成功返回1，否则返回0 int i：hash(k)， ／／调用散列函数hash()计算地址 if(h[i]．elem==EMPTY) ／／无此关键字 return 0； if(h[i]．flag!=DELETED＆＆h[i]．elem==k) { h[i]．flag=DELETED； ／／将标志位标记为已删除 return 1; } e1Se { ／／采用线性探测再散列解决冲突 int j=i; for(int d=1;d<=m;d++) { i=(j+d)％(m+1)； if(h[i]．elem==EMPTY) return 0； if(h[i]．flag!=DELETED＆＆h[i]．elem==k) { h[i]．flag=DELETED; return 1； } } } return 0； ／／无此关键字 }