使用c++完成线性表的应用算法 创建结点数:5 依次输入结点值:1 2 3 4 5 拆分后的结果: 奇数链表:1 3 5 偶数链表:2 4 将两链表合并: 合并结果为:5 4 3 2 1 的源代码
时间: 2024-10-28 15:08:38 浏览: 16
为了创建一个C++程序实现线性表的拆分和合并操作,首先我们需要定义链表节点结构,并创建两个单独的链表(奇数链表和偶数链表)。然后我们可以编写一个主函数,接收用户输入并按照题目要求拆分链表。最后,我们将这两个链表合并成一个新的链表。以下是基本的源代码框架:
```cpp
#include <iostream>
using namespace std;
// 链表节点定义
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// 帮助函数,用于拆分链表
void splitList(Node*& head, Node*& oddHead, Node*& evenHead) {
if (!head || !head->next)
return;
oddHead = new Node(head->data);
evenHead = new Node(head->data + 1); // 假设偶数节点比奇数节点大1
Node* current = head->next;
bool isOdd = true;
while (current) {
if (isOdd) {
oddHead->next = current;
oddHead = current;
} else {
evenHead->next = current;
evenHead = current;
}
current = current->next;
isOdd = !isOdd; // 切换奇偶
}
}
// 合并链表函数
Node* mergeLists(Node* oddHead, Node* evenHead) {
if (!oddHead && !evenHead) return nullptr;
if (!oddHead) return evenHead;
if (!evenHead) return oddHead;
oddHead->next = evenHead;
Node* result = oddHead;
oddHead = oddHead->next;
while (oddHead && evenHead) {
oddHead->next = evenHead->next;
result = oddHead;
oddHead = oddHead->next;
if (oddHead) evenHead = oddHead->next;
else break;
}
return result;
}
int main() {
int nodes[5] = {1, 2, 3, 4, 5};
Node* listHead = nullptr;
for (int i = 0; i < 5; ++i) {
Node* newNode = new Node(nodes[i]);
if (!listHead) {
listHead = newNode;
} else {
listHead->next = newNode;
}
}
Node* oddHead, *evenHead;
splitList(listHead, oddHead, evenHead);
cout << "奇数链表: ";
printList(oddHead);
cout << "\n偶数链表: ";
printList(evenHead);
Node* mergedList = mergeLists(oddHead, evenHead);
cout << "\n合并结果: ";
printList(mergedList);
delete listHead;
return 0;
}
// 辅助函数,打印链表
void printList(Node* node) {
while (node) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
```
注意:这个示例假设奇数节点的值是偶数节点值加1,实际应用中可能会有不同的条件。同时,`printList` 函数并未给出,你可以自定义该函数来遍历并输出链表。
阅读全文