实验1：实现顺序查找的算法
题目描述
- 内容:编写一个程序 cxp9-1.cpp,输出在顺序表(3,6,2.10,18,5.7.49)中采用顺序查找方法查找关键字5的过程，使用顺序表。
- 算法：exp9-1.cpp程序,其中包含函数SeqSearch(RecType R[],intn,KeyTypek),即采用顺序查找方法在顺序表R(含有个元素)中查找关键字为k的元素的位置。实验程序exp9-1.cpp的结构如图9.1所示,图中方框表示函数,方框中指出函数名;箭头方向表示函数间的调用关系;虚线方框表示文件的组成,即指出该虚线方框中的函数存放在哪个文件中
运行代码
seqlist.cpp
#include <stdio.h>
#include <stdlib.h>
#define MAXL 100
// 定义关键字类型为int
typedef int KeyType;
// 假设其他数据项类型为char，可根据实际需求修改
typedef char InfoType;
// 声明查找顺序表元素类型
typedef struct {KeyType key;InfoType data;
} RecType;
// 创建顺序表
void CreateList(RecType R[], KeyType keys[], int n) {for (int i = 0; i < n; i++) {R[i].key = keys[i];}
}
// 输出顺序表
void DispList(RecType R[], int n) {for (int i = 0; i < n; i++) {printf("%d ", R[i].key);}printf("\n");
}excp9-1.cpp
#include"seqlist.cpp"
// 顺序查找算法，从表头往后找，添加输出比较关键字的功能
int SeqSearch(RecType R[], int n, KeyType k) {int i = 0;while (i < n && R[i].key != k) {// 输出正在比较的关键字printf("%d ", R[i].key);i++;}if (i >= n)return 0;else {printf("%d", R[i].key);return i + 1;}
}
int main() {RecType R[MAXL];int n = 10, i;KeyType k = 5;int a[] = { 3, 6, 2, 10, 1, 8, 5, 7, 4, 9 };CreateList(R, a, n);printf("关键字序列:");DispList(R, n);printf("查找%d所比较的关键字:\n\t", k);if ((i = SeqSearch(R, n, k)) != 0)printf("\n元素%d的位置是%d\n", k, i);elseprintf("\n元素%d不在表中\n", k);return 1;
}代码思路
- 实现了一个简单的顺序表操作及顺序查找功能。通过 CreateList 函数利用给定的关键字数组 a 创建顺序表 R，将数组中的元素依次赋值给顺序表元素的关键字成员。接着使用 DispList 函数输出顺序表的关键字序列，能直观展示当前顺序表中存储的数据情况。然后调用 SeqSearch 函数对给定的关键字 k（示例中值为 5）进行顺序查找每比较一个顺序表中的关键字就将其输出，这样可以看到查找时依次遍历比较的元素情况。若找到关键字，则输出该关键字并返回其在顺序表中的位置（序号从 1 开始，通过 i + 1 计算）；若遍历完整个顺序表（i >= n）都没找到，则返回 0 表示未找到。
- 内存管理方面：定义顺序表 R 时使用了固定大小的数组 RecType R[MAXL];，这种方式在顺序表元素个数确定且不超过 MAXL 的情况下可行。但如果要处理元素个数动态变化的数据情况，就需要考虑采用动态内存分配的方式（例如使用 malloc、realloc 等函数）来管理顺序表的内存空间，以避免数组越界或者内存浪费等问题。
- 函数参数传递和返回值处理：在 CreateList 函数中，目前简单地将传入的关键字数组的值赋给顺序表元素的关键字成员，没有对 InfoType 类型的 data 成员做处理。如果实际应用中 data 成员也需要赋值等操作，要注意完善相应的赋值逻辑，确保数据的完整性。对于 SeqSearch 函数的返回值，代码中通过 if ((i = SeqSearch(R, n, k))!= 0) 这样的语句来判断和获取返回值，要注意理解这里先进行函数调用赋值给 i，再判断 i 是否为 0 的逻辑，避免出现混淆，比如误写成 if (SeqSearch(R, n, k)!= 0) 这样没有正确接收返回值的情况。同时返回值的含义（找到元素返回位置序号从 1 开始，没找到返回 0）要清晰，在后续使用返回值进行判断和输出结果时才不会出错。
- 代码的可扩展性和通用性：当前代码对于特定的 KeyType（定义为 int）和 InfoType（定义为 char）类型进行了操作，如果后续需要处理不同类型的数据（比如 KeyType 为 float 或者自定义结构体类型等），代码的通用性就需要改进。可以考虑使用模板（如果是 C++ 环境）或者通过函数指针等方式（在 C 语言环境下）来让代码能够更灵活地适应不同的数据类型，增强代码的可复用性和扩展性。
- 输出格式和可读性：在 printf 语句中设置了相应的格式控制符来输出数据，需要确保格式控制符与实际输出的数据类型匹配，输出的提示信息等尽量做到清晰明了，方便查看和理解程序运行的结果以及查找问题，像当前代码中输出查找关键字比较过程时添加了适当的换行和缩进（如 printf("查找%d所比较的关键字:\n\t", k); 中的 \n\t）来增强输出的可读性，在实验过程中可以根据实际情况进一步优化输出格式。
实验题2:实现折半查找的算法
题目描述
1.内容:编写一个程序 exp9-2.cpp,输出在顺序表(1,2,3,4,5,6,7,8,9,10)中采用折半查找方法查找关键字9的过程。
2.算法：exp9-2.cpp程序,包含函数 BinSear(RecType R[],intn,KeyType k),即采用折半查找方法在顺序表R(含有n个元素)中查找关键字为k的记录的位置。实验程序excp构如图9.3所示,图表示,方框中出函数名;头方向表示雨数间的调用关系;虚线方框表示文件的组成,即该函数放在哪个文件中。
运行代码
#include"seqlist.cpp"
// 折半查找算法
int BinSearch(RecType R[], int n, KeyType k) {int low = 0, high = n - 1, mid, count = 0;while (low <= high) {mid = (low + high) / 2;printf(" 第%d次比较:在[%d,%d]中比较元素 R[%d]:%d\n",++count, low, high, mid, R[mid].key);if (R[mid].key == k) {// 查找成功则返回return mid + 1;}if (R[mid].key > k) {// 继续在[low..mid - 1]中查找high = mid - 1;}else {low = mid + 1;// 继续在[mid + 1..high]中查找}}return 0;
}
int main() {RecType R[MAXL];KeyType k = 9;int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, i, n = 10;CreateList(R, a, n);printf("关键字序列:");DispList(R, n);printf("查找%d的比较过程如下:\n", k);if ((i = BinSearch(R, n, k)) != 0)printf("元素%d的位置是%d\n", k, i);elseprintf("元素%d不在表中\n", k);return 1;
}代码思路
- 顺序表创建与展示：代码中的 CreateList 函数成功地将给定的关键字数组 a 的元素依次赋值给顺序表 R 的关键字成员，使得顺序表得以正确创建。通过 DispList函数能够清晰地输出顺序表的关键字序列，方便直观查看顺序表中的数据内容，为后续的查找操作提供了清晰的数据基础。
- 折半查找执行过程：BinSearch 函数依经典逻辑运行。它靠不断调整由 low 和 high 界定的查找区间，计算中间位置 mid，输出比较次数、查找区间范围及中间元素值等关键信息。目标关键字 k 与 R [mid].key 相等时，能准确返回对应元素在顺序表中的位置（序号从 1 开始，按 mid + 1 计算）；若多次调整比较后仍未找到，则返回 0 表示查找失败。从示例数据运行结果看，对于给定有序顺序表及查找关键字，可准确输出比较过程、判断元素是否在表中并给出位置信息，实现了折半查找功能函数参数传递与返回值处理。
- 在CreateList函数中，仅对顺序表元素的关键字成员赋值，若顺序表结构中的InfoType类型的data成员也需要有相应的赋值逻辑（比如实际应用中每个元素还有其他相关联的数据），则需要完善该函数的实现，完整的数据能正确填充到顺序表中。BinSearch函数的返回值，在main函数中通过if((i = BinSearch(R, n, k))!= 0) 进行判断和获取。要清楚理解这种先进行函数调用并将返回值赋给变量 i，再判断i是否不为0的操作逻辑，避免出现错误的返回值处理方式，比如误写成 if (BinSearch(R, n, k)!= 0)没有正确接收返回值到变量的情况，导致后续根据返回值进行的输出等操作出现错误。
- 整数溢出风险：在 BinSearch 函数中计算中间位置 mid 时，采用的是mid = (low + high) / 2 的方式。当顺序表元素个数非常大时（例如low和high的值接近INT_MAX，即整数类型所能表示的最大值，相加操作可能会导致整数溢出，进而产生错误的中间位置计算结果，影响折半查找的正确性。为避免这种情况，可以采用更为安全的计算方式，如 mid = low + (high - low) / 2，它能在一定程度上降低整数溢出的风险，保证中间位置计算的准确性，尤其是在处理大规模数据时这一点不容忽视。
- 数据有序性要求：折半查找的前提是顺序表中的关键字必须是有序排列的。在代码中，给定的用于创建顺序表的数组 a 是有序的，所以查找功能能正常执行。实际实验中，如果输入的顺序表数据是无序的，那么折半查找算法将无法保证正确的查找结果，出现找不到本应存在的元素或者错误地认为元素存在等情况。务必确保顺序表的关键字是按照升序或降序（取决于具体算法实现的比较逻辑）排列的。
实验题3：实现分块查找的算法
题目描述
1.内容:编写二个程序exp9-3.cpp,输出在顺序表(8,14,6,9,10,22,34,18,19,31,40,38,54,66,78,88,80,85,100,94,88,96,87)中采用分块查找方法查找(每块的长为5，共有5块)关键字46 的过程。
2.算法:得到exp9-3.cPp程序,其中包含函数IdxSearch
(1dxTme7,mtb,RecType R[],intn,KeyTypek),即采用分块查找方法在顺
(含有》个元素)中查找关键字为k的记录的位置。其中R[0..”一1]为含n个元素的据表,共分为6个块,I[0..6-1]为对应的索引表。程序expg-3.cpp的结构如图9.5所示,图中方框表示函数,方框中指出函数名;头方向表示函数间的调用关系;虚线方框表示文件的组成,即指出该虚线方框中的面放在哪个文件中。
运行代码
#include "seqlist.cpp"
#define MAXI 20 // 索引表最大长度
// 定义关键字类型为int
typedef struct {KeyType key;int link;
} IdxType;
// 分块查找函数
int IdxSearch(IdxType I[], int b, RecType R[], int n, KeyType k) {int s = (n + b - 1) / b; // s为每块的元素个数，应为n/b取上界int count1 = 0, count2 = 0;int low = 0, high = b - 1, mid, i;// 在索引表中折半查找while (low <= high) {mid = (low + high) / 2;printf(" 第%d次比较:在[%d,%d]中比较元素 I[%d]:%d\n",count1 + 1, low, high, mid, I[mid].key);if (I[mid].key > k)high = mid - 1;elselow = mid + 1;count1++;}// 找到对应的索引块printf("比较%d次,在第%d块中查找元素 %d\n", count1, low,k);i = I[high + 1].link;printf("(2)在对应块中顺序查找:\n");// 在对应块中顺序查找while (i <= I[high + 1].link + s - 1) {printf(" ");printf("%d ", R[i].key);if (R[i].key == k)break;i++;count2++;}printf("比较%d次,在顺序表中查找元素 %d\n", count2,k);if (i <= I[high + 1].link + s - 1)return i + 1; // 查找成功，返回该元素的逻辑序号return 0; // 查找失败，返回0
}
int main() {RecType R[MAXL];IdxType I[MAXI];int n = 25, i;int a[] = { 8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80,85, 100, 94, 86, 96, 87 };CreateList(R, a, n);// 建立索引表I[0].key = 14;I[0].link = 0;I[1].key = 34;I[1].link = 5;I[2].key = 66;I[2].link = 10;I[3].key = 85;I[3].link = 15;I[4].key = 100;I[4].link = 20;printf("关键字序列:");for (i = 0; i < n; i++) {printf("%4d", R[i].key);if (((i + 1) % 5) == 0)printf(" ");if (((i + 1) % 10) == 0)printf("\n\t ");}printf("\n");KeyType k = 46;printf("查找%d的比较过程如下:\n", k);if ((i = IdxSearch(I, 5, R, 25, k)) != 0)printf("元素%d的位置是%d\n", k, i);elseprintf("元素%d不在表中\n", k);return 1;
}代码思路
- 分块查找执行过程之索引表折半查找：在 IdxSearch 函数里，针对索引表I的折半查找逻辑正确。通过不断更新查找区间（由 low和high界定），每次计算中间位置mid，I[mid].key和目标关键字k的大小关系调整区间，输出每次比较的详细信息（比较次数、当前查找区间、中间元素值等），符合折半查找的常规流程，能有效地在索引表中定位目标关键字所在的大致块范围。
- 对应块顺序查找：在确定了索引块之后，代码进入对应块内进行顺序查找。按照设定的块内元素范围（通过i和s控制）循环遍历块内元素，输出正在查找的元素值，当找到目标关键字k时能够及时终止循环，并且准确统计在块内顺序查找时的比较次数count2。最后根据是否在块内找到元素，返回相应的结果（找到返回元素的逻辑序号，未找到返回 0），整体实现了分块查找的核心功能逻辑。
- 索引表与顺序表关联准确性：代码中索引表I和顺序表R的对应关系至关重要。每个索引表项的link值需精准指向对应块在顺序表中的起始下标，否则在进行分块查找时，会导致定位到错误的块，进而无法正确找到目标元素。例如，若手动修改顺序表的数据或者重新划分块时，必须同步精确更新索引表的各元素 link 值，保证两者的对应关系准确无误。
- 分块参数一致性：定义分块相关的参数（如块数b和每块元素个数 s）要与实际的索引表及顺序表结构相匹配。s的计算方式（(n + b - 1) / b）确保了每块元素个数分配合理，但在修改n（顺序表元素个数）或b时，要确保整个分块逻辑的连贯性以及后续查找算法基于此分块的正确性，避免出现块划分混乱、元素遗漏或重复查找等问题。
- 块内顺序表有序性建议：虽然分块查找算法本身对块内顺序表元素顺序要求相对宽松，提高查找效率角度出发，建议每个块内的顺序表元素按关键字。对应块内进行顺序查找时，遇到有序性相关优化策略（如提前终止查找等情况）就更好地发挥作用，减少不必要的比较次数，提升整体查找性能。
- 数据类型限制：当前代码将 KeyType 定义为 int，意味着只能处理整数类型的关键字数据。若在实验中有处理其他类型数据（如 float、double、自定义结构体类型等）的需求，就需要对代码进行改造，可能涉及修改比较操作逻辑（例如通过函数指针传递自定义的比较函数来适应不同类型的大小比较需求），以提升代码的通用性，使其能应用于更广泛的数据场景
- 功能扩展适应性：如果后续想要对分块查找功能进行扩展，比如增加更多关于索引表的操作、改变分块策略（如动态分块、非等大小分块等）或者优化查找算法性能等，代码的结构和模块化程度要便于进行相应的修改和添加新功能，避免代码过于耦合、难以维护和扩展的问题。
