C++链表类合并操作 |21xrx.com

C++链表类合并操作

2023-06-26 15:53:24 深夜i -- --

C++ 链表类合并操作

C++是一门非常流行的编程语言，被广泛应用于软件开发领域。C++的链表类是常用的数据结构之一，可以通过链表类实现链表结构的数据存储和访问。在实际编程中，有时需要对多个链表进行合并操作，本文将介绍如何使用C++链表类实现链表合并操作。

首先，我们需要先实现一个链表类。链表类通常包括节点类和链表类两个部分。节点类定义了链表中的节点，通常包括一个数据成员和一个指针成员，分别表示当前节点的值和下一个节点的地址。链表类则包括了链表的头节点和相关的操作函数，如链表插入、删除和查找等。

下面是一个简单的链表类的实现，包括节点类和链表类：


// 节点类的定义
template<typename T>
class Node {
  public:
    T data;
    Node* next;
    Node(T data): data(data), next(nullptr) {}
};
// 链表类的定义
template<typename T>
class LinkedList {
  public:
    Node<T>* head;
    void insert(T data);
    void remove(T data);
    Node<T>* find(T data);
};
// 链表插入操作
template<typename T>
void LinkedList<T>::insert(T data) {
  Node<T>* node = new Node<T>(data);
  if (!head)
    head = node;
   else {
    Node<T>* curr = head;
    while (curr->next)
      curr = curr->next;
    
    curr->next = node;
  }
}
// 链表删除操作
template<typename T>
void LinkedList<T>::remove(T data) {
  Node<T>* curr = head;
  Node<T>* prev = nullptr;
  while (curr && curr->data != data)
    prev = curr;
    curr = curr->next;
  
  if (curr) {
    if (prev)
      prev->next = curr->next;
     else
      head = head->next;
    
    delete curr;
  }
}
// 链表查找操作
template<typename T>
Node<T>* LinkedList<T>::find(T data) {
  Node<T>* curr = head;
  while (curr && curr->data != data)
    curr = curr->next;
  
  return curr;
}

有了链表类的基础，我们就可以实现链表的合并操作了。链表合并操作通常包括两种情况：合并两个有序链表和合并多个无序链表。

首先，我们来看两个有序链表的合并操作。假设我们有两个有序链表A和B，我们需要将它们合并成一个有序链表C。我们可以使用一个指针从头节点开始遍历两个链表，每次将较小的那个节点加入到新的链表C中，直到其中一个链表为空。然后，将另一个链表中剩余的节点全部加入到链表C中即可。

下面是一个简单的实现：


template<typename T>
LinkedList<T> merge(LinkedList<T>& l1, LinkedList<T>& l2) {
  LinkedList<T> l3;
  Node<T>* curr1 = l1.head;
  Node<T>* curr2 = l2.head;
  while (curr1 && curr2) {
    if (curr1->data < curr2->data) {
      l3.insert(curr1->data);
      curr1 = curr1->next;
    } else {
      l3.insert(curr2->data);
      curr2 = curr2->next;
    }
  }
  while (curr1) {
    l3.insert(curr1->data);
    curr1 = curr1->next;
  }
  while (curr2) {
    l3.insert(curr2->data);
    curr2 = curr2->next;
  }
  return l3;
}

接下来，我们来看合并多个无序链表的情况。假设我们有n个无序链表L1、L2、...、Ln，我们需要将它们合并成一个无序链表。我们可以使用一个哈希表来保存每个节点的值和所在的链表编号，然后按照节点的值将它们排序后依次加入到新的链表中即可。

下面是一个简单的实现：


template<typename T>
LinkedList<T> merge(vector<LinkedList<T>>& lists) {
  LinkedList<T> result;
  unordered_map<T, set<int>> hash;
  // 将所有节点的值和所在的链表编号加入到哈希表中
  for (int i = 0; i < lists.size(); i++) {
    Node<T>* curr = lists[i].head;
    while (curr) {
      hash[curr->data].insert(i);
      curr = curr->next;
    }
  }
  // 将哈希表中的节点按照值进行排序
  vector<T> values;
  for (auto& p : hash) {
    values.push_back(p.first);
  }
  sort(values.begin(), values.end());
  // 将排序后的节点加入到新的链表中
  for (T& val : values) {
    set<int>& s = hash[val];
    for (int i : s) {
      result.insert(val);
    }
  }
  return result;
}

到此为止，我们就介绍了如何使用C++链表类实现链表合并操作。链表合并操作是一种常用的算法问题，对于加深对数据结构和算法的理解非常有帮助。

上一篇: idea打包java可执行jar包

下一篇: C++中的抽象类概念及定义

评论区

()

相似文章