C++1、随机产生或键盘输入一组元素,建立一个带头结点的单向链表。 2、遍历单向链表。 3、在单向链表中删除所有的偶数元素结点。 4、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表。 5、编写一个主函数,调试上述算法。
时间: 2024-10-11 17:07:34 浏览: 33
单向链表 代码架构
在C++中,可以按照以下步骤来完成这些操作:
1. **创建链表结构**:
首先,需要定义一个链表节点结构,包括一个数据域和指向下一个节点的指针:
```cpp
struct ListNode {
int data;
ListNode* next;
ListNode(int val = 0) : data(val), next(nullptr) {}
};
```
2. **生成或输入元素**:
使用`cin`从用户那里获取输入,或者使用`std::rand()`和`std::srand(time(0))`配合循环随机生成整数,然后将它们添加到链表头部:
```cpp
ListNode* createList() {
int n;
std::cout << "请输入元素个数:";
std::cin >> n;
ListNode* head = nullptr;
for (int i = 0; i < n; ++i) {
int val;
// 输入或生成值并插入链表
std::cin >> val;
head = insertNode(head, val);
}
return head;
}
ListNode* insertNode(ListNode* head, int value) {
ListNode* newNode = new ListNode(value);
newNode->next = head;
return newNode;
}
```
3. **遍历链表**:
可以通过一个循环访问每个节点并打印其值:
```cpp
void traverseList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
```
4. **删除偶数节点**:
```cpp
ListNode* removeEvenNodes(ListNode* head) {
ListNode* dummy = new ListNode(0); // 创建哑节点防止头节点消失导致空指针异常
dummy->next = head;
ListNode* prev = dummy;
ListNode* curr = head;
while (curr != nullptr) {
if (curr->data % 2 == 0) {
prev->next = curr->next;
} else {
prev = curr;
}
curr = curr->next;
}
delete dummy->next; // 删除哑节点
return dummy->next;
}
```
5. **插入保持有序**:
对于非递减有序链表,可以比较新值和当前节点值,找到适当的位置插入:
```cpp
ListNode* insertInOrder(ListNode* head, int value) {
ListNode* tail = head;
while (tail->next && tail->next->data < value) {
tail = tail->next;
}
ListNode* newNode = new ListNode(value);
newNode->next = tail->next;
tail->next = newNode;
return head;
}
```
6. **主函数测试**:
```cpp
int main() {
ListNode* list = createList();
std::cout << "原始链表:";
traverseList(list);
list = removeEvenNodes(list);
std::cout << "移除偶数后的链表:";
traverseList(list);
int newElement;
std::cout << "请输入插入的新元素:";
std::cin >> newElement;
list = insertInOrder(list, newElement);
std::cout << "插入新元素后的链表:";
traverseList(list);
return 0;
}
```
以上就是完成这些操作的基本步骤。运行`main`函数即可看到整个过程。记得处理好内存分配和释放,避免内存泄漏。
阅读全文