C++ 对输入的正整数序列建立有序单链表。在建立单链表的过程中,链表中的数据元素按升序排列。当输入的数据元素在单链表中已经存在时,不进行插入操作。 输入 每行一个正整数,当输入-1时结束。
时间: 2024-09-14 20:08:31 浏览: 62
在C++中,为了建立一个有序单链表并在插入时保持升序,你需要定义一个链表节点结构体,并实现插入函数。下面是一个简单的实现示例:
首先定义节点结构体和单链表类:
```cpp
#include <iostream>
struct ListNode {
int value;
ListNode *next;
ListNode(int val) : value(val), next(nullptr) {}
};
class SortedLinkedList {
public:
SortedLinkedList() : head(nullptr) {}
// 插入新元素,并保持链表有序
void insert(int val) {
ListNode *newNode = new ListNode(val);
ListNode *current = head;
ListNode *prev = nullptr;
// 如果链表为空或新元素应该插入到头部
if (current == nullptr || current->value >= val) {
newNode->next = current;
head = newNode;
return;
}
// 查找插入位置
while (current != nullptr && current->value < val) {
prev = current;
current = current->next;
}
// 如果找到相同的元素,则不插入
if (current != nullptr && current->value == val) {
delete newNode; // 释放未使用的节点
return;
}
// 插入新节点
prev->next = newNode;
newNode->next = current;
}
// 打印链表
void print() {
ListNode *current = head;
while (current != nullptr) {
std::cout << current->value << " ";
current = current->next;
}
std::cout << std::endl;
}
// 析构函数释放链表内存
~SortedLinkedList() {
ListNode *current = head;
while (current != nullptr) {
ListNode *next = current->next;
delete current;
current = next;
}
}
private:
ListNode *head; // 链表头部指针
};
```
使用上述类建立链表:
```cpp
int main() {
SortedLinkedList list;
int val;
std::cout << "请输入正整数序列,输入-1结束:" << std::endl;
while (std::cin >> val && val != -1) {
list.insert(val);
}
std::cout << "建立的有序单链表为:" << std::endl;
list.print();
return 0;
}
```
以上程序首先定义了一个节点结构体`ListNode`和一个有序单链表类`SortedLinkedList`。在`SortedLinkedList`类中,`insert`函数用于插入新元素,如果新元素已经在链表中存在,则不会执行插入操作。
输入-1时,程序结束输入,并打印出建立好的有序单链表。
阅读全文