2015广工数据结构答案(6)

字母的顺序输出哈希表中所有关键字的算法。 哈希表的类型HashTable定义如下： #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1

typedef char StrKeyType[4]; typedef struct {

StrKeyType key; // 关键字项

int tag; // 标记 0:空；1:有效; -1:已删除 void *any; // 其他信息 } RcdType;

typedef struct {

RcdType *rcd; // 存储空间基址 int size; // 哈希表容量

int count; // 表中当前记录个数 } HashTable; **********/

int Hash(char key){ int i;

i=(key-'A'); return i; }

void collision(int &p,int size){ p=(p+1)%size; }

int SearchHash(HashTable H,char key,int &p,int &c){ p=Hash(key);

while(H.rcd[p].tag!=0&&(H.rcd[p].key[0]!=key)||-1==H.rcd[p].tag){ collision(p,H.size);c++; }

if(H.rcd[p].key[0]==key) return 1; else return 0; }

void PrintKeys(HashTable ht, void(*print)(StrKeyType)) /* 依题意用print输出关键字 */ {int p,c=0,t; char key='A'; do{

if(SearchHash(ht,key,p,c)==1) t=p;//print(ht.rcd[p].key);

while(ht.rcd[p].tag!=0&&Hash((ht.rcd[p].key[0])==t)){ if(ht.rcd[p].key[0]==key&&ht.rcd[p].tag!=-1) print(ht.rcd[p].key); collision(p,ht.size); }

key++;

}while(key<='Z'); }

/**********

【题目】假设哈希表长为m，哈希函数为H(x)，用链地址法 处理冲突。试编写输入一组关键字并建造哈希表的算法。 哈希表的类型ChainHashTab定义如下： #define NUM 7 #define NULLKEY -1 #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 typedef char HKeyType; typedef struct HNode { HKeyType data; struct HNode* next; }*HLink;

typedef struct {

HLink *rcd; // 指针存储基址，动态分配数组 int count; // 当前表中含有的记录个数 int size; // 哈希表的当前容量 }ChainHashTab; // 链地址哈希表

int Hash(ChainHashTab H, HKeyType k) { // 哈希函数 return k % H.size; }

Status Collision(ChainHashTab H, HLink &p) { // 求得下一个探查地址p if (p && p->next) { p = p->next; return SUCCESS;

} else return UNSUCCESS; }

**********/

int SearchHash(ChainHashTab H,HKeyType key,HLink &p,int &j){ j=Hash(H,key); p=H.rcd[j];

if(p==NULL) return 0;

while(p->next!=NULL&&p->data!=key){ Collision(H,p); }

if(p->data==key) return 1; else return 0; }

int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) /* 直接调用下列函数 */ /* 哈希函数： */ /* int Hash(ChainHashTab H, HKeyType k); */

/* 冲突处理函数： */ /* int Collision(ChainHashTab H, HLink &p); */ { int i,j; HLink p,t;

for(i=0;i

if(SearchHash(H,es[i],p,j)==0){

t=(HNode*)malloc(sizeof(HNode)); t->data=es[i]; t->next=H.rcd[j]; H.rcd[j]=t; } }

return 1; }

/**********

【题目】试编写如下定义的递归函数的递归算法: g(m,n) = 0 当m=0,n>=0 g(m,n) = g(m-1,2n)+n 当m>0,n>=0 **********/

int G(int m, int n)

/* 如果 m<0 或 n<0 则返回 -1 */ {

if(m<0||n<0) return -1; if(m==0&&n>=0) return 0;

if(m>0&&n>=0) return G(m-1,2*n)+n; }

/**********

【题目】试写出求递归函数F(n)的递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 **********/ int F(int n)

/* 如果 n<0 则返回 -1 */ { if(n<0) return -1; if(n==0) return n+1;

if(n>0) return n*F(n/2); }

/**********

【题目】求解平方根 的迭代函数定义如下：

sqrt(A,p,e) = p 当|p*p-A|=e

其中，p是A的近似平方根，e是结果允许误差。试写出相 应的递归算法。 **********/

float Sqrt(float A, float p, float e) { float t=p*p-A; if(t

if(t>=e) return Sqrt(A,(p+A/p)/2,e); }

/**********

【题目】已知Ackerman函数的定义如下： akm(m,n) = n+1 当m=0 akm(m,n) = akm(m-1,1) 当m!=0,n=0 akm(m,n) = akm(m-1,akm(m,n-1)) 当m!=0,n!=0 请写出递归算法。 **********/

int Akm(int m, int n)

/* 若 m<0 或 n<0 则返回-1 */ { if(m<0||n<0) return -1; if(m==0) return n+1;

if(m!=0&&n==0) return Akm(m-1,1);

if(m!=0&&n!=0) return Akm(m-1,Akm(m,n-1)); }

/**********

【题目】试写出求递归函数F(n)的非递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 **********/ int F(int n)

/* 如果 n<0 则返回 -1 */ { int t=1;

if(n<0) return -1; for(;n>0;n=n/2){ t=n*t; }

return t; }

/**********

【题目】试写出求递归函数F(n)的非递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 **********/ int F(int n)

/* 如果 n<0 则返回 -1 */ { int t=1;

if(n<0) return -1; for(;n>0;n=n/2){ t=n*t; }

return t; }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2015广工数据结构答案(6)在线全文阅读。