给定头文件List.h,完成以下操作: (1)实现List的成员函数: T& RemoveMin( )//删除链表中值最小的元素,返回最小元素的值
时间: 2024-10-15 09:26:04 浏览: 58
在给定`List.h`头文件中实现`RemoveMin()`成员函数需要考虑链表的数据结构。假设我们有一个简单的单链表,其中每个节点包含一个数据项`T`以及指向下一个节点的指针。首先,我们需要遍历整个列表找到最小的元素,然后更新其前驱节点指向下标为第二个的节点,最后返回并删除最小元素。以下是`List.h`的一部分示例代码:
```cpp
template <typename T>
class List {
public:
// 结构体表示链表节点
struct Node {
T data;
Node* next;
};
// 初始化链表为空
List() : head(nullptr) {}
// 添加元素到链表尾部
void Add(T value);
// 删除最小元素并返回值
T& RemoveMin();
private:
// 链表头指针
Node* head;
// 辅助函数,用于遍历查找最小元素
T findMin(Node* current);
};
// 实现辅助函数 findMin
template <typename T>
T List<T>::findMin(Node* current) {
while (current && (current->data < head->data || !head)) {
head = current;
current = current->next;
}
return current ? current->data : std::numeric_limits<T>::max(); // 返回最大值作为默认
}
// 实现 RemoveMin 函数
template <typename T>
T& List<T>::RemoveMin() {
if (!head) {
throw std::runtime_error("List is empty");
}
T min_val = findMin(head);
if (head == min_val) { // 如果最小元素是头节点
head = head->next;
} else { // 否则,在最小元素之前断开链接
Node* prev = head;
while (prev->next != min_val) {
prev = prev->next;
}
prev->next = prev->next->next;
}
return min_val; // 返回并删除最小元素的值
}
```
阅读全文