首页在seqlist1.cpp的基础上，编写一个程序 prac4-2.cpp，输出在顺序表(1，2，3，4，5，6，7，8，9，10)中采用折半查找方法查找关键字9的过程。

在seqlist1.cpp的基础上，编写一个程序 prac4-2.cpp，输出在顺序表(1，2，3，4，5，6，7，8，9，10)中采用折半查找方法查找关键字9的过程。

时间: 2024-12-14 11:22:53 浏览: 40

在`prac4-2.cpp`程序中，我们可以按照以下步骤编写一个简单的顺序表（这里假设我们已经有一个名为`SequenceList`的模板类，其中包含插入、删除和查找元素等基本操作）并使用折半查找方法来查找关键字9。注意，折半查找通常适用于已排序的数据结构，如数组或有序链表。首先，我们需要在`SequenceList`类中添加一个辅助函数`binarySearch`来进行折半查找： ```cpp template <typename T> class SequenceList { private: // 其他成员变量和函数... public: // 插入、删除等方法... // 折半查找方法 int binarySearch(T key) const { int left = 0; int right = size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (data[mid] == key) return mid; // 找到匹配的关键字 else if (data[mid] < key) left = mid + 1; // 如果中间值小于key，更新左边界 else right = mid - 1; // 否则，更新右边界 } return -1; // 如果未找到，返回-1表示不存在 } }; ``` 接下来，在`main`函数中创建一个`SequenceList<int>`实例，并填充数据： ```cpp int main() { SequenceList<int> myList; // 插入1到10的元素 for (int i = 1; i <= 10; ++i) myList.insert(i); // 使用折半查找方法查找关键字9 int result = myList.binarySearch(9); if (result != -1) cout << "Keyword 9 found at position: " << result << endl; else cout << "Keyword 9 not found." << endl; return 0; } ``` 这个程序会输出："Keyword 9 found at position: 9"，因为9在这个顺序列表中的索引位置确实是9。

阅读全文