设计一个单项链表类模版,要求各个节点数据域中的数据从大到小排列,成员函数能够进行节点的插入,删除和查找
时间: 2024-03-06 19:52:02 浏览: 58
好的,下面是一个实现单向链表的模版类,要求节点数据域从大到小排列,同时提供插入、删除和查找节点的成员函数:
```cpp
template<typename T>
class SortedLinkedList {
public:
// 节点结构体
struct Node {
T data;
Node* next;
Node(T d) : data(d), next(nullptr) {}
};
SortedLinkedList() : head(nullptr) {}
~SortedLinkedList() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
// 插入节点,保持数据域从大到小排列
void insert(const T& data) {
Node* new_node = new Node(data);
if (!head || data > head->data) {
new_node->next = head;
head = new_node;
return;
}
Node* curr_node = head;
while (curr_node->next && data < curr_node->next->data) {
curr_node = curr_node->next;
}
new_node->next = curr_node->next;
curr_node->next = new_node;
}
// 删除节点
void remove(const T& data) {
Node dummy(0);
dummy.next = head;
Node* prev_node = &dummy;
Node* curr_node = head;
while (curr_node) {
if (curr_node->data == data) {
prev_node->next = curr_node->next;
delete curr_node;
head = dummy.next;
return;
}
prev_node = curr_node;
curr_node = curr_node->next;
}
}
// 查找节点,返回节点指针
Node* find(const T& data) {
Node* curr_node = head;
while (curr_node) {
if (curr_node->data == data) {
return curr_node;
}
curr_node = curr_node->next;
}
return nullptr;
}
// 打印链表中的所有元素
void print() const {
Node* curr_node = head;
while (curr_node) {
std::cout << curr_node->data << " ";
curr_node = curr_node->next;
}
std::cout << std::endl;
}
private:
Node* head;
};
```
这个模版类中,使用链表来存储节点数据,同时保持数据域从大到小排列。insert() 方法用于插入节点,删除节点的 remove() 方法会在链表中查找相应的节点并删除它,查找节点的 find() 方法会返回指向该节点的指针,print() 方法用于打印链表中的所有元素。示例代码如下:
```cpp
int main() {
SortedLinkedList<int> list;
list.insert(3);
list.insert(1);
list.insert(5);
list.insert(2);
list.print();
SortedLinkedList<int>::Node* node = list.find(5);
if (node) {
std::cout << "Found node with value 5" << std::endl;
} else {
std::cout << "Node with value 5 not found" << std::endl;
}
list.remove(3);
list.print();
return 0;
}
```
阅读全文