数据结构实验报告 救！

Question

实验目的：
1•掌握几种典型的查找方法(顺序查找、折半查找、二又排序树查找、哈希查找),对各种算法的特点、使用范围和效率有进一步的了解；
2、能用C语言实现这些查找算法设计一个程序，用于演示顺序查找、折半查找和二叉排序树查找等几种典型的查找方法，要求采用菜单的形式进行选择。
实验内容：
查找表结构定义如下
typedef struct '
int key; 1/主关键宇
• 1数据元素其他项的信息可不定义；
} ElemType;
typedef struct {
ElemType *R; 1/表基址
int
length; 1/表长
}SSTable;
基于如上存储结构，设计一个程序,用于演示顺序
查找、折半查找和二叉排序树查找等几种典型的查找
方法，要求采用菜单的形式进行选择
1．理解并程序实现顺序查找算法；
2.理解并程序实现折半查找算法；
3.理解并程序实现二叉排序树的创建，并将其创建的二叉排序树进行中序遍历进行验证；
4. 在第3题的基础上，实现如下功能：根据给定某个
关键字值，用递归算法在已经创建好的二叉排序树查
找该关键字值是否存在，如果存在，返回指向该结点的指针，否则返回空指针
求解！

Answer 1

// 查找表结构
typedef struct {
  int key; // 主关键字
  // 其他数据元素的信息可不定义
} ElemType;

typedef struct {
  ElemType *R; // 表基址
  int length; // 表长
} SSTable;

// 顺序查找算法
int Sequential_Search(SSTable T, int key) {
  T.R[0].key = key; // 哨兵
  for (int i = T.length; T.R[i].key != key; --i)
    ;
  return i;
}
// 折半查找算法
int Binary_Search(SSTable T, int key) {
  int low = 1, high = T.length;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (key < T.R[mid].key)
      high = mid - 1;
    else if (key > T.R[mid].key)
      low = mid + 1;
    else
      return mid;
  }
  return 0;
}
// 二叉排序树的结点结构
typedef struct BSTNode {
  int key; // 关键字
  struct BSTNode *lchild, *rchild; // 左右孩子指针
} BSTNode, *BSTree;

// 创建二叉排序树
BSTree Create_BST(int data[], int n) {
  BSTree T = NULL;
  for (int i = 0; i < n; i++) {
    BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
    s->key = data[i];
    s->lchild = s->rchild = NULL;
    if (!T)
      T = s;
    else {
      BSTNode *p = T, *q;
      while (p) {
        q = p;
        if (s->key < p->key)
          p = p->lchild;
        else
          p = p->rchild;
      }
      if (s->key < q->key)
        q->lchild = s;
      else
        q->rchild = s;
    }
  }
  return T;
}

// 中序遍历二叉排序树
void InOrder_Traverse(BSTree T) {
  if (T) {
    InOrder_Traverse(T->lchild);
    printf("%d ", T->key);
    InOrder_Traverse(T->rchild);
  }
}
// 在二叉排序树上查找给定的关键字值是否存在
BSTNode* BST_Search(BSTree T, int key) {
  if (!T || T->key == key)
    return T;
  else if (key < T->key)
    return BST_Search(T->lchild, key);
  else
    return BST_Search(T->rchild, key);
}