V1EERIE
个人学习笔记
实验十三:静态查找表上查找的操作实验

access_time
brush 695个字
whatshot 514 ℃
百度收录:无法查询

一、实验目的

  1. 能够用高级语言编写顺序查找和二分查找操作的算法在计算机中的实现。
  2. 能够正确分析静态查找表上操作特性。
  3. 能够根据二分查找的思想对二分查找操作的性进行正确的分析。

二、实验内容

  1. 建立顺序查找表,并在此查找表上实现顺序查找操作。(验证性实验)
  2. 对上述顺序查找表选择一种简单的排序方法对此进行排序。(验证性实验)
  3. 在上述有序顺序查找表上实现二分查找操作。(验证性实验)
  4. 建立索引查找表,并在此查找表上实现索引查找操作。(设计性内容)

三、实验要求

编程实现如下功能:
(1)根据输入的查找表的表长n和n个关键字值,建立顺序查找表;
(2)用顺序查找方法在上述顺序查找表中查找与已经给定关键值相等的记录;
(3)选择一种排序方法对(1)中建立的顺序查找表进行排序;
(4)在(3)中的有序查找表中用二分查找方法查找与已经给定关键值相等的记录 ;
(5)编写main函数,设计菜单使用户能通过菜单的选择多次通过调用上述功能函数来实现所选择的查找操作,并且在每次操作后都输出其操作结果:若查找成功,则输出“查找成功”并输出这条记录在表中的位置,否则输出“查找失败”。
(6)编程实现如下功能:
① 根据输入索引查找表中的块号和各块中的记录关键字的值创建索引查找表。
②利用索引查找确定给定关键字值的记录在索引查找表中的块号和在块中的位置。

四、源程序代码

【1-5】
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct ElemType
{
  KeyType key;
  InfoType otherinfo;
  bool operator<(ElemType &b)
  {
    if (key != b.key)
      return key < b.key;
    return false;
  }
} ElemType;
typedef struct
{
  ElemType *elem;
  int length;
} SSTable;
int length;
void InitSSTable(SSTable &T, int length)
{
  if (T.elem != NULL)
     free(T.elem);
  T.elem = new ElemType[length + 1];
  cout << "请输入各个记录的关键字值:" << endl;
  for (size_t i = 1; i < length + 1; i++)
     cin >> T.elem[i].key;
}
int SequentialSearch(SSTable &T, KeyType e)
{
  for (size_t i = 1; i < length + 1; i++)
     if (T.elem[i].key == e)
       return i;
  return -1;
}
bool compareE(ElemType &a, ElemType &b)
{
  return a.key < b.key;
}
int BinarySearch(SSTable &T, KeyType e)
{
  sort(T.elem + 1, T.elem + (length + 1), compareE);
  cout << "排序后的顺序表:" << endl;
  for (size_t i = 1; i < length + 1; i++)
     cout << T.elem[i].key << ' ';
  cout << endl;
  for (size_t i = 1, j = length + 1, mid; i <= j;)
  {
     mid = (i + j) / 2;
     if (T.elem[mid].key > e)
       j = mid - 1;
     else if (T.elem[mid].key < e)
       i = mid + 1;
     else
       return mid;
  }
  return -1;
}
int main(int argc, char const *argv[])
{
  int n = 0, t;
  KeyType e;
  SSTable T;
  while (n != 3)
  {
     cout << "\t1---顺序查找" << endl
        << "\t2---二分查找" << endl
        << "\t3---退出" << endl
        << "请选择<1-3>:";
     cin >> n;
     if (n == 3)
       return 0;
     else if (n != 1 && n != 2)
     {
       cout << "输入错误" << endl;
       continue;
     }
     cout << "请输入顺序表的长度:";
     cin >> length;
     InitSSTable(T, length);
     cout << "请输入要查找的关键字:";
     cin >> e;
     if (n == 1)
     {
       if ((t = SequentialSearch(T, e)) == -1)
         cout << "查找失败。" << endl;
       else
       {
         cout << "查找成功,这个记录所在表中的位置是:" << t << endl
            << endl;
       }
     }
     else
     {
       if ((t = BinarySearch(T, e)) == -1)
         cout << "查找失败。" << endl;
       else
       {
         cout << "查找成功,这个记录所在排序后表中的位置是:" << t << endl
            << endl;
       }
     }
  }
  return 0;
}

【6】

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int KeyType;
typedef struct BNode
{
  KeyType key;
  struct BNode *next = NULL;
} BNode;
typedef struct SNode
{
  KeyType Maxkey;
  BNode *head;
} SNode;
typedef struct
{
  SNode *r;
  int length;
} STable;
void InsertBNode(SNode &S, KeyType key)
{
  if (S.head == NULL)
  {
     BNode *q = new BNode;
     S.head = q;
     S.head->key = key;
     return;
  }
  BNode *p = S.head;
  while (p->next != NULL)
  {
     p = p->next;
  }
  BNode *q = new BNode;
  p->next = q;
  q->key = key;
  q->next = NULL;
}
void InitSTable(STable &T)
{
  int length, i;
  cout << "输入表中块的个数:" << endl;
  cin >> length;
  KeyType t;
  T.length = length;
  if (T.r != NULL)
     free(T.r);
  T.r = new SNode[T.length + 1];
  for (i = 0; i < T.length + 1; i++)
     T.r[i].head = NULL;
  for (i = 1; i < T.length + 1; i++)
  {
     cout << "输入块 " << i << " 最大关键字的值:";
     cin >> T.r[i].Maxkey;
     cout << "输入各关键字的值(输入-1表示结束)" << endl;
     do
     {
       cin >> t;
       if (t == -1)
         break;
       InsertBNode(T.r[i], t);
     } while (1);
  }
  return;
}
int searchSNode(STable &T, KeyType key)
{
  int index_ = 0, end_ = T.length + 1, mid;
  while (index_ <= end_)
  {
     mid = (index_ + end_) / 2;
     if (T.r[mid].Maxkey < key)
       index_ = mid + 1;
     else if (T.r[mid].Maxkey > key)
       end_ = mid - 1;
     else
       return mid;
  }
  return index_;
}
BNode *SearchBNode(SNode &S, KeyType key, int &count)
{
  BNode *p = S.head;
  count = 0;
  while (p)
  {
     if (p->key == key)
       return p;
     else
     {
       p = p->next;
       ++count;
     }
  }
  return NULL;
}
void searchSTable(STable &T, KeyType key)
{
  BNode *t;
  int count;
  int n = searchSNode(T, key);
  if ((t = SearchBNode(T.r[n], key, count)) == NULL)
     cout << "查找失败" << endl;
  else
  {
     cout << "查找成功。块号: " << n << " ,存储地址:" << t << "处于块中的第 " << count + 1 << " 位置" << endl;
  }
}
int main(int argc, char const *argv[])
{
  STable T;
  KeyType key;
  InitSTable(T);
  cout << "输入要查找的关键字:";
  cin >> key;
  searchSTable(T, key);
  return 0;
}

五、运行结果

【1】
oX8bT0.png
【2】
oXGcjJ.png

六、 实验总结与体会

  1. 能够熟练掌握静态查找表和索引查找表
  2. 了解并使用索引进行查找
  3. 熟悉各种方式的搜索

#如无特别声明,该文章均为 V1EERIE 原创,转载请遵循 署名-非商业性使用 4.0 国际(CC BY-NC 4.0) 协议,即转载请注明文章来源。
#最后编辑时间为: 2021 年 12 月 25 日


create 添加新评论


account_circle
email
language
textsms





关于 DreamCat

主题名称:DreamCat | 版本:X2.6.220211

主题开发:HanFengA7 | TeddyNight | Dev-Leo | CornWorld | WhiteBearcn | DFFZMXJ

Designed by HanFengA7 Power by Typecho

Copyright © 2015-2022 by LychApe All rights reserved!

加我的QQ
加我的微博
加我的支付宝
加我的微信