构造两链表La呢,Lb其中La={2,-8,4,5,11,7},Lb={2,3,5,6}请编写程序实现链表Lc为La和Lb的差,即Lc={-8,4,11,7}
您好,这个需求很简单,如下是我自己写的C++代码,实现将链表La和链表Lb的差集存储在链表Lc中。
#include <iostream>
struct Node {
int data;
Node* next;
};
void insertNode(Node*& head, int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
}
else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
void printList(Node* head) {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
void removeElements(Node*& head, Node* toRemove) {
if (head == nullptr || toRemove == nullptr) {
return;
}
// 如果头节点需要移除
while (head == toRemove) {
Node* temp = head;
head = head->next;
delete temp;
}
// 遍历链表,移除指定节点
Node* current = head;
while (current != nullptr) {
if (current->next == toRemove) {
Node* temp = current->next;
current->next = temp->next;
delete temp;
}
else {
current = current->next;
}
}
}
void subtractLists(Node* La, Node* Lb, Node*& Lc) {
if (La == nullptr) {
Lc = nullptr;
return;
}
// 复制La链表到Lc链表
Node* currentLa = La;
while (currentLa != nullptr) {
insertNode(Lc, currentLa->data);
currentLa = currentLa->next;
}
// 移除Lb链表中与Lc链表重复的元素
Node* currentLb = Lb;
while (currentLb != nullptr) {
removeElements(Lc, currentLb);
currentLb = currentLb->next;
}
}
int main() {
// 创建链表La
Node* La = nullptr;
insertNode(La, 2);
insertNode(La, -8);
insertNode(La, 4);
insertNode(La, 5);
insertNode(La, 11);
insertNode(La, 7);
// 创建链表Lb
Node* Lb = nullptr;
insertNode(Lb, 2);
insertNode(Lb, 3);
insertNode(Lb, 5);
insertNode(Lb, 6);
// 创建链表Lc,并计算差集
Node* Lc = nullptr;
subtractLists(La, Lb, Lc);
// 打印链表Lc
printList(Lc);
// 释放链表内存
Node* current = Lc;
while (current != nullptr) {
Node* temp = current;
current = current->next;
delete temp;
}
getchar();
return 0;
}
你可以使用VS2013以上的编译器运行它,如下是运行效果;