数据结构——第9章数据结构 anyview作业系统答案 9.25实现下列函数： int Searc

文件名称: 数据结构——第9章数据结构 anyview作业系统答案

所属分类: C/C++

开发工具:

文件大小: 60kb

下载次数: 0

上传时间: 2011-05-04

提供者: lansef*******

下载 (60kb)

不能下载？报告错误

详细说明： 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 -1 typedef 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(); ...展开收缩

(系统自动生成,下载前可以参看下载内容)