数据结构，第9章：anyview作业系统答案。

简介：
9.25实现下列函数：int Search(SSTable s, KeyType k);/* Index the element which key is k *//* in StaticSearchTable s. *//* Return 0 if x is not found. */ 静态查找表的类型SSTable定义如下：typedef struct { KeyType key; ... ... // 其他数据域} ElemType; typedef struct { ElemType *elem; int length;} SSTable;int Search(SSTable a, KeyType k)/* Index the element which key is k */ /* in StaticSearchTable s. *//* Return 0 if x is not found. */{ int i; if(a.length==0) return ERROR; //先判断a是否为空 a.elem[a.length+1].key=k; for(i=1;a.elem[i].key>k;i++) if(i>=a.length||a.elem[i].keyk;i++) if(i>a.length||a.elem[i].keyk) return BinSearch(s,low,high-1,k); } return 0;} /* { int mid; if(low<=high) { mid=(low+high)/2; if(s.elem[mid].keylchild || t->rchild ) )//空树和叶子不用判断 { if( t->lchild && ( t->data.key < t->lchild->data.key ) )//左孩子不空，左孩子的key比本身的大 return FALSE; else if( t->rchild && ( t->data.key > t->rchild->data.key ) )//右孩子不空，右孩子的key比本身的大 return FALSE; else if( !IsBSTree( t->lchild ) )//判断左子树 return FALSE; else if( !IsBSTree( t->rchild ) )//判断右子树 return FALSE; } return TRUE;} /*{ if(!t) return OK; if(t&&!t->lchild&&!t->rchild) return OK; else { if(t->lchild->data.keydata.key) IsBSTree(t->lchild); if(t->lchild->data.key>=t->data.key) return ERROR; if(t->rchild->data.key>t->data.key) IsBSTree(t->rchild); else return ERROR; return OK; } } */ 9.33③ 编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。要求你的算法的时间复杂度为O(log2n+m)，其中n为排序树中所含结点数，m为输出的关键字个数。 实现下列函数：void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType));/* Output is to use visit(t->data); */ 二叉树的类型BiTree定义如下：typedef struct { KeyType key; ... ... // 其他数据域} ElemType; typedef struct BiTNode { ElemType data; BiTNode *lchild,*rchild;}BiTNode, *BiTree;void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType))/* Output is to use visit(t->data); */ { if(t->rchild) OrderOut(t->rchild,x,visit); if(t->data.key>=x) visit(t->data); if(t->lchild)OrderOut(t->lchild,x,visit); } /*{ if(t->rchild) OrderOut(t->rchild,x); if(t->datalchild)OrderOut(t->lchild,x); } */ 9.44④ 已知某哈希表的装载因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 实现下列函数：void PrintKeys(HashTable ht, void(*print)(StrKeyType));/* 依题意用print输出关键字 */ 哈希表的类型HashTable定义如下：#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1typedef char StrKeyType[4];typedef struct { StrKeyType key; void *any;} HElemType; int hashsize[] = { 7,11,17,23,29,37,47 };typedef struct { HElemType elem[MAXLEN]; int count; int sizeindex;} HashTable;int H(char *s)//求Hash函数{ if( s[0] ) return s[0]-A+1; //求关键字第一个字母的字母序号(小写) else return 0;} void PrintKeys(HashTable ht, void(*print)(StrKeyType))/* 依题意用print输出关键字 */{ int i,j; for( i = 1; i <= 26; i++ ) { for( j = (i-1)%hashsize[ht.sizeindex]; ht.elem[j].key[0]; ) { if( H ( ht.elem[j].key ) == i ) print(ht.elem[j].key); j = (j+1)%hashsize[ht.sizeindex]; } }} /*void PrintKeys(HashTable ht, void(*print)(StrKeyType))/* 依题意用print输出关键字 { int i,j; for(i=1;i<=26;i++) for(j=i;ht.elem[j].key;j=(j+1)%MAXLEN) if(H(ht.elem[j].key)==i) print(ht);} int H(char *s){if(s) return s[0]-96;else return 0;} */9.45③ 假设哈希表长为m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。 实现下列函数：int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) /* 直接调用下列函数 *//* 哈希函数： *//* int Hash(ChainHashTab H, HKeyType k); *//* 冲突处理函数： *//* int Collision(ChainHashTab H, HLink &p); */{ int i = 0,l,flag; HLink p,node; while( es[i] ) { l = Hash( H, es[i] ); node = ( HLink )malloc( sizeof( HNode ) ); node->data = es[i]; node->next = NULL; i++; if( !H.elem[l] ) H.elem[l] = node; else { flag = 0; p = H.elem[l]; if( p->data == node->data ) flag = 1; while( Collision( H, p ) ) if( p->data == node->data ) { flag = 1; break; } if( !flag ) { p = H.elem[l]; node->next = p; H.elem[l] = node; } } } } +userLink+; $(miniAd).show(); } }, onFailure: function(){} }}); } showMiniAd();