#include <stdio.h> #define MAXSIZE 100 typedef int KeyType; //根据需要设定数据类型 typedef struct { KeyType key; //关键字字段 }ElemType; typedef struct { ElemType r[MAXSIZE]; int length; // 表的长度 } SSTable; int BinSearch(SSTable t,int n,int k) //拆半

查找算法的实现代码如下：

int BinSearch(SSTable t, int n, int k) {
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (t.r[mid].key == k) {
return mid;
} else if (t.r[mid].key > k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}

这段代码实现了在一个静态有序表t中查找关键字为k的元素，如果找到了则返回该元素的位置，否则返回-1。其中，n表示表t的长度，k为待查找的关键字。

相关问题

#include<stdio.h> #include<string.h> #define MAXSIZE 100 typedef struct { int elem[MAXSIZE]; int length; }SeqList; int BinSrch(SeqList l,KeyType k) { int low=1,int high=l.length; while(low<=high) { mid=(low+high)/2; if(k==l.elem[mid]) return mid; else if(l.elem[mid]>k) { high=mid-1; } else { low=mid+1; } } return 0; } int main { }填写该完整代码

这段代码存在一些问题，我先给您做一些修改：

#include <stdio.h>
#include <string.h>
#define MAXSIZE 100

typedef struct {
    int elem[MAXSIZE];
    int length;
} SeqList;

int BinSrch(SeqList l, int k) {
    int low = 1, high = l.length, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (k == l.elem[mid])
            return mid;
        else if (l.elem[mid] > k) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return 0;
}

int main() {
    SeqList l = {{1, 3, 5, 7, 9}, 5};
    int k = 7;
    int pos = BinSrch(l, k);
    if (pos) {
        printf("查找成功，元素 %d 在序列中的位置为 %d\n", k, pos);
    } else {
        printf("查找失败，序列中不存在元素 %d\n", k);
    }
    return 0;
}

这是一个二分查找的代码，您可以根据自己的需要修改序列元素和要查找的元素。在这个代码中，`SeqList` 结构体表示一个线性表，其中 `elem` 数组存储线性表中的元素，`length` 表示线性表中元素的个数。`BinSrch` 函数表示二分查找算法，接收一个线性表和要查找的元素作为参数，返回该元素在线性表中的位置。在 `main` 函数中，我们创建一个线性表 `l`，并初始化其中的元素和元素个数；然后我们调用 `BinSrch` 函数查找元素 `k`，并将查找结果输出。

#define MAXSIZE 100 typedef int KeyType; /*关键字类型*/ typedef struct { KeyType key; /*InfoType otherinfo;*/ }RedType; /*记录类型*/ typedef struct BiTNode { RedType data; struct BiTNode *lchild,*rchild; }BiTNode, *BiTree; /*动态查找表的二叉链表存储表示*/#include <stdio.h> #include <stdlib.h> #include <string.h> #include "search.h" BiTree Search_BST(BiTree T, KeyType key, BiTNode **parent) {/*在二叉排序树T上查找其关键字等于key的记录结点。若找到返回该结点指针，parent指向其双亲；否则返回空指针，parent指向访问路径上最后一个结点。*/ // 请在这里补充代码，完成本关任务 /********** Begin *********/ /********** End **********/ } void Insert_BST(BiTree *T, RedType r)/*若二叉排序树T中没有关键字为r.key的记录，则插入*/ { BiTNode *p,*q,*parent; parent=NULL; p=Search_BST(*T,r.key,&parent); /*查找*/ if(p) printf("BST中有结点r，无需插入\n"); else { p=parent; q=(BiTNode *)malloc(sizeof(BiTNode)); q->data=r; q->lchild=q->rchild=NULL; if(*T==NULL) *T=q; /*若T为空，则q为新的根*/ else if(r.key<p->data.key) p->lchild=q; else p->rchild=q; } } BiTree Create_BST( ) /*二叉排序树的构造*/ {/*输入若干记录的关键字（以-1标志结束），生成一棵BST，采用二叉链表存储，返回其根指针T*/ BiTree T; RedType r; T=NULL; /*建空树*/ scanf("%d",&r.key); while(r.key!=-1) { Insert_BST(&T, r); scanf("%d",&r.key); } return T; } void PreOrder(BiTree bt) /*先序遍历*/ { if(bt) { printf("%d ",bt->data.key); PreOrder(bt->lchild); PreOrder(bt->rchild); } } void InOrder(BiTree bt) /*中序遍历*/ { if(bt) { InOrder(bt->lchild); printf("%d ",bt->data.key); InOrder(bt->rchild); } 补充代码

/*后序遍历*/ void PostOrder(BiTree bt) { if(bt) { PostOrder(bt->lchild); PostOrder(bt->rchild); printf("%d ",bt->data.key); } } /*中序遍历的非递归算法*/ void InOrderTraverse(BiTree T) { BiTree p=T; SqStack S; InitStack(&S); while(p || !StackEmpty(S)) { if(p) { Push(&S, p); p=p->lchild; } else { Pop(&S, &p); printf("%d ",p->data.key); p=p->rchild; } } } /*在二叉排序树T中查找其关键字等于key的记录，若查找成功，删除该结点并返回1；否则返回0。*/ int Delete(BiTree *T,KeyType key) { if(!(*T)) return 0; /*空树*/ else { if(key==(*T)->data.key) /*找到了关键字等于key的结点*/ { DeleteNode(T); return 1; } else if(key<(*T)->data.key) return Delete(&(*T)->lchild,key); else return Delete(&(*T)->rchild,key); } } /*从二叉排序树中删除结点p，并重接它的左或右子树。*/ void DeleteNode(BiTree *p) { BiTree q; if(!(*p)->rchild) /*右子树空则只需重接它的左子树*/ { q=*p; *p=(*p)->lchild; free(q); } else if(!(*p)->lchild)/*左子树空则只需重接它的右子树*/ { q=*p; *p=(*p)->rchild; free(q); } else /*左右子树均不空*/ { q=*p; /*从右子树开始*/ BiTree s=(*p)->rchild; while(s->lchild) /*转左，找到最小值*/ { q=s; s=s->lchild; } (*p)->data=s->data; /*s指向被删结点的直接前驱*/ if(q!=*p) q->lchild=s->rchild; /*重接q的左子树*/ else q->rchild=s->rchild; /*重接q的右子树*/ free(s); } }