要求:定义单链表类模板,并初始化实现一个空int型链表; 实现单链表的插入操作; 实现单链表的按值查找操作; 实现单链表的删除操作; ·基于单链表,实现两个int 型集合的交集操作。
时间: 2024-12-23 16:23:50 浏览: 12
在C++中,我们可以定义一个模板类`ListNode<int>`表示单链表节点,包含一个整数值和指向下一个节点的指针。首先,我们需要创建一个空链表的结构:
```cpp
template <typename T>
class ListNode {
public:
T value;
ListNode* next;
ListNode() : value(0), next(nullptr) {}
};
// 创建一个空链表
template <typename T>
ListNode<T>* createEmptyList() {
return new ListNode<T>();
}
```
接下来,我们分别实现链表的插入、查找、删除以及交集操作:
1. 插入操作(例如在链表尾部插入):
```cpp
void insertNode(ListNode<T>** head, const T& value) {
ListNode<T>* newNode = new ListNode<T>(value);
if (*head == nullptr) {
*head = newNode;
} else {
ListNode<T>* current = *head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
```
2. 查找操作:
```cpp
bool search(const ListNode<T>* head, const T& target) {
ListNode<T>* current = head;
while (current != nullptr) {
if (current->value == target) {
return true;
}
current = current->next;
}
return false;
}
```
3. 删除操作(移除第一个匹配项):
```cpp
void removeValue(ListNode<T>** head, const T& value) {
if (*head == nullptr) {
return;
}
if ((*head)->value == value) {
ListNode<T>* temp = *head;
*head = (*head)->next;
delete temp;
return;
}
ListNode<T>* current = *head;
while (current->next != nullptr && current->next->value != value) {
current = current->next;
}
if (current->next != nullptr) {
ListNode<T>* toDelete = current->next;
current->next = current->next->next;
delete toDelete;
}
}
```
4. 计算两个整数链表的交集(假设两个链表已经排序):
```cpp
template <typename T>
ListNode<T>* intersection(ListNode<T>* list1, ListNode<T>* list2) {
ListNode<T> *ptr1 = list1, *ptr2 = list2;
int len1 = 0, len2 = 0;
while (ptr1 != nullptr) {
ptr1++;
len1++;
}
while (ptr2 != nullptr) {
ptr2++;
len2++;
}
ptr1 = list1, ptr2 = list2;
for (int i = 0; i < std::min(len1, len2); ++i) {
if (ptr1->value == ptr2->value) {
// 如果找到相同的元素,将其添加到结果链表
ListNode<T>* intersectionNode = new ListNode<T>(ptr1->value);
intersectionNode->next = nullptr;
if (*intersectionIntersection == nullptr) {
*intersectionIntersection = intersectionNode;
} else {
intersectionIntersection->next = intersectionNode;
}
ptr1++;
ptr2++;
} else if (ptr1->value < ptr2->value) {
ptr1++;
} else {
ptr2++;
}
}
return *intersectionIntersection;
}
```
在这个例子中,`intersectionIntersection`是一个全局变量,用于存储最终的交集链表头结点。
阅读全文