C++ 对输入的正整数序列建立有序单链表。在建立单链表的过程中,链表中的数据元素按升序排列。当输入的数据元素在单链表中已经存在时,不进行插入操作。 请使用面向对象形式定义结点类和链表类
时间: 2024-09-14 08:08:12 浏览: 49
在C++中,创建一个有序单链表通常需要定义两个类:一个是节点类(Node),用来表示链表中的每个元素;另一个是链表类(OrderedList),用来管理整个链表的结构和操作。以下是一个简单的示例实现:
```cpp
#include <iostream>
// 定义节点类
class Node {
public:
int data; // 节点存储的数据
Node* next; // 指向下一个节点的指针
// 节点类的构造函数
Node(int d) : data(d), next(nullptr) {}
};
// 定义有序单链表类
class OrderedList {
private:
Node* head; // 指向链表头部的指针
public:
// 有序单链表类的构造函数
OrderedList() : head(nullptr) {}
// 析构函数,释放链表内存
~OrderedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
// 向链表中插入新的数据元素
void insert(int value) {
Node* newNode = new Node(value);
// 如果链表为空,或者新节点应该插入到头部
if (head == nullptr || head->data >= newNode->data) {
newNode->next = head;
head = newNode;
} else {
// 找到合适的插入位置
Node* current = head;
while (current->next != nullptr && current->next->data < newNode->data) {
current = current->next;
}
// 插入新节点
newNode->next = current->next;
current->next = newNode;
}
}
// 打印链表中的所有元素
void print() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
OrderedList list;
int value;
// 从标准输入读取正整数序列,并建立有序单链表
while (std::cin >> value) {
list.insert(value);
}
// 打印建立好的有序单链表
list.print();
return 0;
}
```
这个程序首先定义了一个节点类`Node`,其中包含数据域`data`和指向下一个节点的指针`next`。然后定义了一个有序单链表类`OrderedList`,它包含一个指向链表头部的指针`head`。`OrderedList`类提供了插入新元素的方法`insert`,该方法会将新元素按升序插入到链表中,如果要插入的元素已经在链表中,则不执行插入操作。此外,`OrderedList`类还提供了一个析构函数来释放链表占用的内存,以及一个`print`方法来打印链表中的所有元素。
阅读全文