21xrx.com
2024-11-22 09:38:32 Friday
登录
文章检索 我的文章 写文章
C++实现链表数据结构
2023-07-04 14:16:46 深夜i     --     --
C++ 链表 数据结构 实现 指针

链表是一种重要的数据结构,可以用于解决各种问题,并且在广泛的应用领域中发挥着重要作用。C++是一种广泛使用的编程语言,具有良好的对象导向特性和高效的性能,因此可以用C++来实现链表数据结构。

在C++中实现链表数据结构需要以下步骤:

1. 定义链表节点结构体

链表节点包括两个部分,一个是节点值,另一个是指向下一个节点的指针。我们可以用结构体来定义节点。


struct ListNode {

  int val;

  ListNode* next;

};

2. 定义链表类

链表类中需要定义一些基本操作,比如插入节点、删除节点、查找节点等等。以下是链表类的定义:


class LinkedList {

public:

  // 构造函数和析构函数

  LinkedList();

  ~LinkedList();

  // 插入节点

  void insert(int val);

  // 删除节点

  void remove(int val);

  // 查找节点

  bool search(int val) const;

  // 获取链表长度

  int length() const;

  // 打印链表

  void print() const;

 

private:

  // 头节点指针

  ListNode* head = nullptr;

};

3. 实现链表类的操作

插入节点的操作可以通过以下代码实现:


void LinkedList::insert(int val) {

  ListNode* newNode = new ListNode();

  newNode->val = val;

  newNode->next = head;

  head = newNode;

}

删除节点的操作可以用以下代码实现:


void LinkedList::remove(int val) {

  ListNode* curr = head;

  ListNode* prev = nullptr;

  while (curr != nullptr && curr->val != val)

    prev = curr;

    curr = curr->next;

  

  if (curr != nullptr) {

    if (prev == nullptr)

      head = curr->next;

     else

      prev->next = curr->next;  

    

    delete curr;

  }

}

查找节点的操作可以用以下代码实现:


bool LinkedList::search(int val) const {

  ListNode* curr = head;

  while (curr != nullptr && curr->val != val)

    curr = curr->next;

  

  return curr != nullptr;

}

获取链表长度的操作可以用以下代码实现:


int LinkedList::length() const {

  int len = 0;

  ListNode* curr = head;

  while (curr != nullptr) {

    len++;

    curr = curr->next;

  }

  return len;

}

打印链表的操作可以用以下代码实现:


void LinkedList::print() const {

  ListNode* curr = head;

  while (curr != nullptr)

    cout << curr->val << " ";

    curr = curr->next;

  

  cout << endl;

}

4. 测试链表类的功能

最后,我们可以编写一个测试程序来测试链表类的各项功能。以下是一个简单的测试程序:


int main() {

  LinkedList list;

  list.insert(10);

  list.insert(15);

  list.insert(20);

  list.print(); // 输出 20 15 10

  list.remove(15);

  list.print(); // 输出 20 10

  cout << list.search(20) << endl; // 输出 1

  cout << list.search(15) << endl; // 输出 0

  cout << list.length() << endl; // 输出 2

  return 0;

}

以上就是使用C++实现链表数据结构的步骤和示例代码。使用链表数据结构可以更加高效地实现各种复杂的算法和数据处理操作,对于学习和实践算法设计和编程技能都是非常重要的。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复