实现一个函数模板SelectSort,以带头结点的单链表为存储结构实现简单选择排序。算法实现代码应填写在alg6.h相应函数中。在每趟排序完成后,应调用alg6.h中提供的ShowRunK函数显示该趟排序的结果。 算法测试时,第一行输入待排序元素个数,第二行输入待排序的各个元素。调用MyBubbleSort输出各趟排序结果。根据要求,在以下函数中实现以带头结点的单链表为存储结构实现简单选择排序template <class ElemType> void SelectSort(LinkList<ElemType> &la) { }
时间: 2023-06-27 15:04:28 浏览: 52
void SelectSort(LinkList<ElemType>& L){
LNode<ElemType>* p, * q, * min;
p = L.getHead();
while (p->next != NULL) {
min = p;
q = p->next;
while (q != NULL) {
if (q->data < min->data)
min = q;
q = q->next;
}
if (min != p) {
std::swap(p->data, min->data);
ShowRunK(L, min);
}
p = p->next;
}
}
相关问题
实现一个函数模板MyBubbleSort,对教材上的冒泡排序算法进行改进,当某一趟排序没有发生交换时则不用执行下一趟。算法实现代码应填写在alg5.h的相应函数中。在每趟排序完成后,应调用alg5.h中提供的ShowRunK函数显示该趟排序的结果。 算法测试时,第一行输入待排序元素个数,第二行输入待排序的各个元素。调用MyBubbleSort输出各趟排序结果。根据要求,在以下函数中实现在数组elem中用冒泡排序进行排序。template <class ElemType> void MyBubbleSort(ElemType elem[], int n) { }
好的,我知道了,这是关于实现改进的冒泡排序算法的问题。这里是 MyBubbleSort 函数的代码实现:
```c++
template <class ElemType>
void MyBubbleSort(ElemType elem[], int n) {
bool flag = true; // 标志位,用于判断某一趟排序是否有交换
for (int i = 0; i < n - 1 && flag; ++i) {
flag = false; // 每趟排序开始前都要将标志位设置为 false
for (int j = n - 1; j > i; --j) { // 每一趟将最大元素交换到最后
if (elem[j] < elem[j - 1]) {
std::swap(elem[j], elem[j - 1]);
flag = true; // 若进行过交换,则将标志位设置为 true
}
}
ShowRunK(elem, i + 1, n); // 每趟排序结束后调用 ShowRunK 函数显示该趟排序结果
}
}
```
这里使用了一个 `flag` 标志位,用于判断当前趟排序是否有数字交换。若没有,则说明已经排好序,不用再进行后续的排序操作。在每趟排序结束后,调用 `ShowRunK` 函数显示该趟排序结果。
题目1. 输出二叉排序树中所有的关键字值不小于key的元素值 实验要求: (1)实现一个函数模板InOrderHelp大到小输出以r为根的二叉排序树中所有的关键字值不小于key的元素值。输出时,各关键字之间隔一个空格; (2)利用编程模板中提供的主函数,测试算法正确性。 实现提示: 本题提供的编程模板包含bin_tree_node.h、binary_sort_tree.h、main.cpp、alg1.h共4个文件,其中bin_tree_node.h包含了二叉树结点类模板,binary_tree.h包含二叉排序树类模板类模板,main.cpp为测试所使用的主函数。算法实现代码应填写在alg1.h的InOrderHelp函数中,不可以在其它任何位置添加、删除或更改代码。 算法测试时,第一行输入二叉排序树结点个数,第二行依次输入插入二叉排序树的元素,构造出的二叉排序树t以及给定的关键字key作为参数传给alg1.h中的InOrder函数,InOrder函数调用InOrderHelp从大到小输出二叉排序树中所有的关键字值不小于key的元素值。
回答:好的,我明白您的问题了。您想要实现一个函数模板InOrderHelp,用于从二叉排序树中查询所有关键字值不小于key的元素,然后将这些元素从大到小输出。您还提供了一些实验要求和提示。我会保密您的要求,不会重复您的话并开始为您回答问题。
答案:
好的,这是一个有关于二叉排序树的问题。我们可以利用中序遍历的方法进行解题,具体实现如下:
```c++
template<class ElemType>
void InOrderHelp(const binary_sort_tree<ElemType>& t, const ElemType& key) {
bool found = false;
typename binary_sort_tree<ElemType>::iterator itr = t.lower_bound(key);
for (; itr != t.end() && !t.is_greater(*itr, key); ++itr) {
cout << *itr << " ";
found = true;
}
if (!found) {
cout << "不存在符合条件的元素" << endl;
}
}
```
这里我们通过调用lower_bound函数来寻找第一个关键字不小于key的元素,然后从这个元素开始利用迭代器(iterator)遍历整个树,输出符合条件的元素,直到遍历完整棵树。需要注意的是,如果树中没有符合条件的元素,我们需要输出“不存在符合条件的元素”。
需要注意的是,这个函数是一个函数模板,因此ElemType可以是任意类型。为了方便起见,我们可以把这个函数写在alg1.h文件中,然后在main.cpp中调用测试。具体代码可以参考实验要求和提示。
希望我的回答能够满足您的需求。