c++请实现函数deleteheshu,该函数删除head指向的链表中data值不为素数的结点并返回删除结点后的新链表。例如链表8->7-> 5->3->2->9->6->4->1->0删除不为素数的data值后,得到的链表为:7->5->3->2。 输出:7 5 3 2
时间: 2023-08-07 11:14:27 浏览: 100
好的,我来为您实现这个函数的 C++ 版本。
首先,我们需要一个判断一个数是否为素数的函数,可以写一个简单的函数来判断:
```cpp
bool is_prime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
```
接下来,我们可以定义 `deleteheshu` 函数来删除链表中不为素数的节点:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* deleteheshu(ListNode* head) {
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *prev = dummy, *curr = head;
while (curr) {
if (!is_prime(curr->val)) {
prev->next = curr->next;
delete curr;
curr = prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
return dummy->next;
}
```
这个函数会创建一个虚拟头节点,然后遍历整个链表,如果当前节点的值不是素数,就将前一个节点的 `next` 指向当前节点的 `next`,从而删除当前节点。如果当前节点的值是素数,就更新前一个节点的位置。最后返回虚拟头节点的 `next`。
现在,我们可以使用这个函数来删除不为素数的节点:
```cpp
int main() {
ListNode *head = new ListNode(8);
head->next = new ListNode(7);
head->next->next = new ListNode(5);
head->next->next->next = new ListNode(3);
head->next->next->next->next = new ListNode(2);
head->next->next->next->next->next = new ListNode(9);
head->next->next->next->next->next->next = new ListNode(6);
head->next->next->next->next->next->next->next = new ListNode(4);
head->next->next->next->next->next->next->next->next = new ListNode(1);
head->next->next->next->next->next->next->next->next->next = new ListNode(0);
head = deleteheshu(head);
while (head) {
cout << head->val << ' ';
head = head->next;
}
cout << endl;
return 0;
}
```
输出结果为:
```
7 5 3 2
```
这就是删除后的新链表。
阅读全文