数据结构实验9.1：静态查找表的基本操作

---

一，实验目的

1. 熟练掌握各种静态查找表方法（顺序查找、折半查找、索引顺序表等）：通过实际编程实现不同查找算法，深入理解其原理和执行过程，能够根据数据特点和应用场景合理选择合适的查找方法，提高查找效率。
2. 熟练掌握二叉排序树的构造方法、插入算法、删除算法和查找算法：全面了解二叉排序树的数据结构特性，精准把握其节点的插入、删除逻辑，以及高效的查找策略，为解决涉及有序数据存储和检索的问题提供有力工具。
3. 掌握散列表的有关技术及各种基本运算的算法：透彻理解散列函数的设计、散列表的存储结构以及冲突处理方法，熟练实现散列表的插入、查找、删除等基本运算，以应对大规模数据快速查找的需求。

二，实验内容

设有关键字序列（34，78，45，56，53，23，39，46），编程实现关键字序列的下列静态查找表查找操作：

(1) 建立有序顺序表

使用有序直接插入法，将给定的关键字序列逐个插入到顺序表中，确保顺序表中的元素始终保持有序状态。具体实现时，从第二个元素开始，将每个元素与已排序部分的元素进行比较，找到合适的位置插入，从而构建出有序顺序表。

(2) 有序顺序表顺序查找算法的实现

从有序顺序表的末尾开始，将待查找的关键字与表中元素逐个比较。为提高查找效率，设置监视哨（将待查找关键字存放在 L.elem[0].key 位置），从表尾向前比较，当找到相等元素时，返回其在表中的位置；若遍历完整个表都未找到，则返回0，表示查找失败。

(3) 有序顺序表折半查找算法的实现

利用有序顺序表的特性，通过不断缩小查找范围来提高查找效率。初始时，设置查找范围的下限 low 为1，上限 high 为顺序表的长度。每次计算中间位置 mid = (low + high) / 2，将中间位置的元素与待查找关键字比较。若相等，则查找成功，返回中间位置；若关键字小于中间元素，则将查找范围缩小到前半区（更新 high = mid - 1）；若关键字大于中间元素，则将查找范围缩小到后半区（更新 low = mid + 1）。当 low > high 时，说明查找失败，返回0。

三，实验要求

（1）设计查找表的数据结构

定义合适的结构体来表示顺序表，包含用于存储元素的数组（如 elem 数组）、表示当前表长度的变量（如 length）以及当前分配的存储容量变量（如 listsize）等。例如：

typedef struct {KeyType *elem;      // 存储空间基址int length;         // 当前长度int listsize;       // 当前分配的存储容量
} SqList;

（2）为保证查找表的有序性，可用有序直接插入法创建查找表

在插入元素时，从第二个元素开始，将当前元素与已排序部分的元素依次比较。若当前元素小于比较元素，则将比较元素后移一位，继续向前比较；直到找到不大于当前元素的位置，将当前元素插入该位置。通过这种方式，确保顺序表在插入元素过程中始终保持有序。

（3）进行算法分析与设计

• 时间复杂度分析：顺序查找算法在最坏情况下需要遍历整个顺序表，时间复杂度为 $O(n)$；折半查找算法每次将查找范围缩小一半，时间复杂度为 $O({\log }_{2}n)$。
• 空间复杂度分析：两种算法主要依赖于顺序表本身的存储空间，额外使用的辅助空间较少，空间复杂度均为 $O(1)$。同时，分析算法在不同数据规模和分布下的性能表现，如顺序查找在数据量较小或数据基本有序时可能具有一定优势，而折半查找在大规模有序数据查找中效率更高。

（4）在参考程序中的下划线处填上适当的语句，完善参考程序

仔细分析参考程序中各函数的逻辑和功能需求，根据算法原理和上下文语义，在空缺处填写正确的语句。例如，在顺序查找算法中，可能需要补充对特殊情况的处理（如空表情况）；在折半查找算法中，确保中间位置计算和查找范围更新的语句准确无误。

（5）上机调试、测试参考程序，保存并打印测试结果，对测试结果进行分析

使用不同规模和特点的测试数据对程序进行测试，包括正常数据、边界数据（如查找第一个元素、最后一个元素、不存在的元素等情况）。记录程序的运行结果和执行时间等信息，分析程序在不同测试用例下的正确性和性能表现。对比顺序查找和折半查找在相同数据规模下的查找效率，总结算法的优缺点和适用场景。

四，算法分析

（1）有序顺序表顺序查找算法设计

int Sq_search(Sqlist L, KeyType key) {// 在有序表中查找关键字key，查找成功时，返回关键字元素在表// 中的位置，否则返回0 int i = L.length;  L.elem[0].key = key;   //监视哨：下标为0的位置存放待查找的元素while (i > 0 && L.elem[i].key!= key)  i--;if (i > 0) {return i;} else {return 0;}
}

分析：此算法通过设置监视哨，从表尾开始向前比较，减少了每次循环都要判断是否越界的操作，提高了查找效率。在循环中，只要当前元素不等于待查找关键字且未遍历到表头（i > 0），就继续向前比较。循环结束后，若 i > 0，说明找到了关键字，返回其位置；否则，返回0表示查找失败。其时间复杂度在最坏情况下为 $O(n)$，其中 $n$ 为顺序表的长度，因为可能需要遍历整个表。空间复杂度为 $O(1)$，仅使用了少量辅助变量。

（2）折半查找算法设计

int B_search(SqList L, KeyType key) {// 在有序表中查找关键字key，若查找成功，则返回关键字元素在// 表中的位置，否则返回0 int low = 1;  int high = L.length;while (low <= high) {   int mid = (low + high) / 2;if (L.elem[mid].key == key) return mid;         //查找成功else if (key < L.elem[mid].key) high = mid - 1;  //下一次到前半区查找  else low = mid + 1;        //下一次到后半区查找 } //end of while return 0;   //查找失败
}  //end of B_search 

分析：该算法利用有序顺序表的特性，不断将查找范围缩小一半。每次通过计算中间位置 mid，比较中间元素与待查找关键字。若相等则查找成功；若关键字小于中间元素，更新查找范围上限 high 为 mid - 1，将查找范围缩小到前半区；若关键字大于中间元素，更新查找范围下限 low 为 mid + 1，将查找范围缩小到后半区。当 low > high 时，说明查找失败。其时间复杂度为 $O({\log }_{2}n)$，因为每次查找都将范围缩小一半，相比顺序查找在大规模数据下效率更高。空间复杂度同样为 $O(1)$，仅使用了几个辅助变量来记录查找范围的上下限和中间位置。

五，示例代码

9-1.cpp源代码

#define MAXNUM 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>typedef int Status;
typedef int KeyType;typedef struct {KeyType  key;int      other;
} ElemType;typedef struct {ElemType* elem;      // 存储空间基址int length;         // 当前长度int listsize;       // 当前分配的存储容量
} SqList;Status Creat_List(SqList& L) {// 用有序插入法建立有n个元素的有序顺序表L，L.elem[0]作为监视哨不存储元素KeyType xk;int i, j;printf("请输入元素个数：");scanf("%d", &L.length);if (L.length < 0) return ERROR;L.elem = (ElemType*)malloc(MAXNUM * sizeof(ElemType));if (!L.elem) return OVERFLOW;L.listsize = MAXNUM;for (i = 1; i <= L.length; i++) {printf("请输入第%d个关键字==>", i);scanf("%d", &xk);for (j = i - 1; L.elem[j].key > xk && j > 0; j--)L.elem[j + 1].key = L.elem[j].key;L.elem[j + 1].key = xk;}return OK;
}int Sq_search(SqList L, KeyType xkey) {// 在有序顺序表中查找关键字xkey，查找成功时，返回关键字元素在表// 中的位置，否则返回0int i;i = L.length;L.elem[0].key = xkey;  //监视哨：下标为0的位置存放待查找的元素while (L.elem[i].key > xkey) i--;  // 从后往前找，直到找到不大于待查关键字的位置if (L.elem[i].key == xkey)  // 判断找到的元素是否就是要查找的关键字return i;elsereturn 0;
}int B_search(SqList L, KeyType xkey) {// 在有序表中查找元素e，若查找成功，则返回元素在表中的位置，否则返回0int low, high, mid;low = 1;high = L.length;printf("折半查找路径为：");while (low <= high) {  // 当查找范围有效时继续查找mid = (low + high) / 2;printf("%4d", L.elem[mid].key);  //输出查找路径if (L.elem[mid].key == xkey) return mid;  //查找成功else if (xkey < L.elem[mid].key) high = mid - 1;  //下一次到前半区查找else low = mid + 1;       //下一次到后半区查找} //end of whilereturn 0;  //查找失败
}  //end of B_searchvoid OutputList(SqList L) {// 输出有序表中所有关键字int i;for (i = 1; i <= L.length; i++)printf("%4d", L.elem[i].key);printf("\n");
}int main()  // 主函数
{SqList L;KeyType xkey;int i;printf("(1) 创建有序顺序表……\n");if (!Creat_List(L)) {printf("输入错误或内存空间不足，创建有序顺序表失败！");return 0;}printf("当前有序顺序表关键字序列为：\n");OutputList(L);printf("（2）有序顺序表的顺序查找……\n");while (1) {printf("请输入待查找的关键字（-1结束）－＞");scanf("%d", &xkey);if (xkey == -1) break;i = Sq_search(L, xkey);if (i)printf("查找成功！关键字位序为：%d\n", i);elseprintf("查找失败！\n");}printf("（3）有序顺序表的折半查找……\n");while (1) {printf("请输入待查找的关键字（-1结束）－＞");scanf("%d", &xkey);if (xkey == -1) break;i = B_search(L, xkey);printf("\n");if (i)printf("查找成功！关键字位序为：%d\n", i);elseprintf("查找失败！\n");}return 0;
}

六，操作步骤

1，双击Visual Studio程序快捷图标，启动程序。

2，之前创建过项目的话，直接打开即可，这里选择【创建新项目】。

3，单击选择【空项目】——单击【下一步】按钮。

4，编辑好项目的名称和存放路径，然后单击【创建】按钮。

5，创建C++程序文件，右击【源文件】——选择【添加】——【新建项】。

6，输入项目名称9-1.cpp，单击【添加】按钮。

7，编写代码，单击运行按钮，运行程序。

七，运行结果

1，实验要求的测试结果。

2，编写代码测试测试的结果。