C++实现有序链表 |21xrx.com

C++实现有序链表

2023-07-08 10:31:52 深夜i -- --

C++ 实现有序链表

有序链表是一种链表数据结构，它按照一定的顺序来存储元素，比如按照从小到大的顺序或者从大到小的顺序。在实际开发中，我们可以使用C++语言来实现有序链表，以下是具体的实现方法：

1. 定义链表节点的结构体


struct ListNode {
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(nullptr) {}
};

2. 定义有序链表的类


class SortedLinkedList {
public:
  SortedLinkedList()
    head = nullptr;
  
  virtual ~SortedLinkedList() {
    clear();
  }
  void insert(int val) {
    ListNode* node = new ListNode(val);
    if (head == nullptr || node->val < head->val)
      node->next = head;
      head = node;
    
    else {
      ListNode* cur = head;
      while (cur->next != nullptr && node->val > cur->next->val)
        cur = cur->next;
      
      node->next = cur->next;
      cur->next = node;
    }
  }
  void clear() {
    while (head != nullptr) {
      ListNode* node = head;
      head = head->next;
      delete node;
    }
  }
  void print() {
    ListNode* cur = head;
    while (cur != nullptr)
      cout << cur->val << "->";
      cur = cur->next;
    
    cout << "null" << endl;
  }
private:
  ListNode* head;
};

3. 插入元素到有序链表

在插入元素到有序链表时，我们需要保证元素的顺序不被打乱。首先判断链表是否为空或插入的元素比链表头的元素还小，如果是，则将元素插入到链表头；否则，我们需要遍历链表，找到插入位置，并将元素插入到该位置后面。

4. 清空有序链表

清空有序链表时，我们需要遍历整个链表，释放每个节点的内存。

5. 打印有序链表

可以使用print函数将有序链表中的所有元素打印出来。

以上就是使用C++语言实现有序链表的具体方法，它可以帮助我们更好地处理数据，提高代码的效率和可读性。

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

下一篇: 《C++宝典》

评论区

()

相似文章