C++链表的实现 |21xrx.com

C++链表的实现

2023-07-02 13:53:43 深夜i -- --

C++ 链表实现

C++链表是一种常用的数据结构，它可以存储数据，并且可以方便地对数据进行增、删、改、查等操作。下面介绍C++链表的实现方法。

首先，我们需要定义链表节点的结构体，包括数据域和指向下一个节点的指针域。


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

接着，我们可以定义链表类，在类中包含头节点和链表长度等信息。


class LinkedList {
public:
  LinkedList();       // 构造函数
  ~LinkedList();      // 析构函数
  void pushBack(int val);  // 在尾部插入元素
  void pushFront(int val); // 在头部插入元素
  void insert(int pos, int val); // 在指定位置插入元素
  void erase(int pos);   // 删除指定位置的元素
  int getLength();     // 获取链表长度
  bool isEmpty();      // 判断链表是否为空
  void print();       // 打印链表
private:
  ListNode* head;      // 头节点
  int length;        // 链表长度
};

在具体实现时，我们需要定义各个函数的具体实现方法。

pushBack函数：在链表尾部插入元素，需要找到链表的最后一个节点，然后将其next指针指向新的节点。


void LinkedList::pushBack(int val) {
  ListNode* node = new ListNode(val);
  ListNode* cur = head;
  while (cur->next != NULL)
    cur = cur->next;
  
  cur->next = node;
  length++;
}

pushFront函数：在链表头部插入元素，需要将新节点的next指针指向原头节点，然后将头节点指向新节点。


void LinkedList::pushFront(int val) {
  ListNode* node = new ListNode(val);
  node->next = head->next;
  head->next = node;
  length++;
}

insert函数：在链表指定位置插入元素，需要将插入位置的前一个节点的next指针指向新节点，然后将新节点的next指针指向插入位置的节点。


void LinkedList::insert(int pos, int val) {
  if (pos < 0 || pos > length)
    return;
  
  ListNode* node = new ListNode(val);
  ListNode* cur = head;
  for (int i = 0; i < pos; i++)
    cur = cur->next;
  
  node->next = cur->next;
  cur->next = node;
  length++;
}

erase函数：删除链表指定位置的元素，需要将插入位置的前一个节点的next指针指向插入位置的后一个节点。


void LinkedList::erase(int pos) {
  if (pos < 0 || pos >= length)
    return;
  
  ListNode* cur = head;
  for (int i = 0; i < pos; i++)
    cur = cur->next;
  
  ListNode* temp = cur->next;
  cur->next = temp->next;
  delete temp;
  length--;
}

getLength函数：获取链表长度。


int LinkedList::getLength()
  return length;

isEmpty函数：判断链表是否为空。


bool LinkedList::isEmpty()
  return length == 0;

print函数：打印链表。


void LinkedList::print() {
  ListNode* cur = head->next;
  while (cur != NULL)
    cout << cur->val << " ";
    cur = cur->next;
  
  cout << endl;
}

在主函数中，我们可以创建一个链表对象，然后调用各个函数进行测试。


int main() {
LinkedList ll;
ll.pushBack(1);
ll.pushFront(2);
ll.pushFront(3);
ll.print();  // 3 2 1
ll.insert(1, 4);
ll.print();  // 3 4 2 1
ll.erase(2);
ll.print();  // 3 4 1
cout << ll.getLength() << endl;  // 3
cout << ll.isEmpty() << endl;  // 0
return 0;
}

以上就是C++链表的基本实现方法，通过链表的操作，我们可以方便地对数据进行增、删、改、查等操作，适用于各种数据处理场景。

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

下一篇: C++ push_back操作函数介绍

评论区

()

相似文章