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].key<k) //不能忽略i=a.length这种情况
return ERROR;
return i;
}
/* {
int i;
a.elem[a.length+1].key=k;
for(i=1;a.elem[i].key>k;i++)
if(i>a.length||a.elem[i].key<k)
return ERROR;
return i;
} */
9.26② 试将折半查找算法改写成递归算法。
实现下列函数：
int BinSearch(SSTable s, int low, int high, 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 BinSearch(SSTable s, int low, int high, KeyType k)
/* Index the element which key is k */
/* in StaticSearchTable s. */
/* Return 0 if x is not found. */
{ int mid;
if(low<=high)
{
mid=(low+high)/2;
if(s.elem[mid].key==k) return mid;
if(s.elem[mid].key<k)
return BinSearch(s,mid+1,high,k);
if(s.elem[mid].key>k)
return BinSearch(s,low,high-1,k);
}
return 0;
}
/* { int mid;
if(low<=high)
{
mid=(low+high)/2;
if(s.elem[mid].key<k)
return BinSearch(s,mid+1,high,k);
else
return BinSearch(s,low,high-1,k);
}
return 0;
}
*/
9.31④ 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
实现下列函数：
Status IsBSTree(BiTree t);
/* 判别给定二叉树t是否为二叉排序树。*/
/* 若是，则返回TRUE，否则FALSE */
二叉树的类型BiTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} ElemType;
typedef struct BiTNode {
ElemType data;
BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
KeyType predt=-32767;
Status IsBSTree(BiTree t)
/* 判别给定二叉树t是否为二叉排序树。*/
/* 若是，则返回TRUE，否则FALSE */
{
if( t )//&& ! ( t->lchild || 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.key<t->data.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->data<x) exit();
visit(x);
if(t->lchild)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();
数据结构是计算机科学中至关重要的基础概念，它涉及到如何有效地组织和管理大量数据，以便进行高效的操作。在上述内容中，我们看到三个主要知识点：静态查找表的线性搜索、折半查找的递归实现以及二叉排序树的判断。
1. **静态查找表的线性搜索**（9.25）
在这个问题中，`Search` 函数用于在静态查找表 `SSTable` 中找到键值为 `k` 的元素。检查表是否为空，然后通过循环遍历元素，直到找到键值大于或等于 `k` 的元素，或者遍历完整个表。如果在表末尾都没有找到匹配项，返回错误。这里需要注意，当 `i` 等于表长度时，也需要检查元素是否匹配，以防止错过最后一个元素。
2. **折半查找的递归实现**（9.26）
折半查找通常用于有序数组，其效率远高于线性搜索。给出的 `BinSearch` 函数采用递归方式实现。它首先计算中间索引 `mid`，然后比较中间元素的键值与目标 `k`。如果相等，返回中间索引；如果中间元素的键值小于 `k`，则在右半部分继续查找；如果中间元素的键值大于 `k`，则在左半部分查找。这个递归过程一直持续到找到目标元素或搜索范围为空。
3. **二叉排序树的判断**（9.31）
二叉排序树（BST）是一种特殊的二叉树，满足每个节点的左子树中的所有节点的键值都小于该节点，而右子树中的所有节点的键值都大于该节点。函数 `IsBSTree` 使用递归方法检查给定的二叉树是否满足这个性质。如果树为空或仅包含单个节点，那么它是二叉排序树。否则，它检查当前节点的左右子节点的键值是否满足条件，并递归地检查左右子树。
这些概念在实际编程和数据管理中具有广泛应用。静态查找表的线性搜索适用于小规模数据，而折半查找则在处理有序数据时提供更快的速度。二叉排序树则在插入、删除和查找操作中展现出良好的性能，尤其在保持平衡时。理解并熟练掌握这些数据结构及其操作对于提升算法设计和问题解决能力至关重要。
Jim_Qiu2013-11-03现在有的题目已经更新，里面有一些没有
