21xrx.com
2024-11-22 07:25:45 Friday
登录
文章检索 我的文章 写文章
C++ 链表例题解析
2023-06-30 07:43:51 深夜i     --     --
C++ 链表 例题 解析 数据结构

链表是计算机科学中一种十分基础的数据结构,也是许多算法和数据结构问题的基础。C++作为一种面向对象的高级编程语言,被广泛地运用于数据结构的实现。本篇文章将解析使用C++实现链表例题的实现过程,并讲解其中的算法思想。

例题描述:

使用C++实现一个链表,要求包含节点的插入、删除、查找操作,并能够完成链表的遍历和打印输出。

实现过程:

首先,我们需要定义链表节点的结构体和链表类的定义。


struct ListNode {

  int val;

  ListNode *next;

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

};

class LinkedList {

private:

  ListNode* head;

public:

  LinkedList() head = nullptr;

  ~LinkedList();

  void insertNode(int val);

  void deleteNode(int val);

  ListNode* findNode(int val) const;

  void traverseAndPrint() const;

};

其中,ListNode是链表节点的结构体,val表示节点的值,next表示指向下一节点的指针。LinkedList是链表类的定义,head表示链表头指针,insertNode函数用于节点插入操作,deleteNode函数用于节点删除操作,findNode函数用于节点查找操作,traverseAndPrint函数用于链表遍历和打印输出。

链表节点的插入操作是比较简单的,具体实现代码如下:


void LinkedList::insertNode(int val) {

  ListNode* newNode = new ListNode(val);

  if (head == nullptr) 则插入的节点为头节点

    head = newNode;

   else {

    ListNode* tmp = head;

    while (tmp->next != nullptr) // 遍历链表找到最后一个节点

      tmp = tmp->next;

    

    tmp->next = newNode; // 将新节点插入到链表末尾

  }

}

节点的删除操作涉及到几种情况,如如果节点不在链表中、节点是头节点、节点是中间节点等等。具体实现代码如下:


void LinkedList::deleteNode(int val) {

  ListNode dummy(-1); // 建立虚拟头节点方便删除头节点

  dummy.next = head;

  ListNode* prev = &dummy;

  ListNode* tmp = head;

  while (tmp) { // 遍历链表寻找目标节点

    if (tmp->val == val) // 找到目标节点

      prev->next = tmp->next; // 链接前后节点

      delete tmp; // 释放内存空间

      return;

    

    prev = tmp;

    tmp = tmp->next;

  }

}

节点查找操作也比较简单,具体实现代码如下:


ListNode* LinkedList::findNode(int val) const {

  ListNode* tmp = head;

  while (tmp) {

    if (tmp->val == val) // 找到目标节点

      return tmp;

    

    tmp = tmp->next;

  }

  return nullptr; // 未找到目标节点

}

链表遍历和打印输出只需要遍历链表,并使用cout输出节点的值即可,具体实现代码如下:


void LinkedList::traverseAndPrint() const {

  ListNode* tmp = head;

  while (tmp)

    cout << tmp->val << " -> ";

    tmp = tmp->next;

  

  cout << "nullptr" << endl;

}

算法思想解析:

链表是由一系列节点组成的链式结构,节点与节点之间通过指针链接起来。链表的基本操作包括插入、删除、查找、遍历等操作。

链表节点的插入操作,可以通过遍历链表然后将新节点插入到链表的末尾来实现。如果链表为空,则新节点为头节点;如果链表不为空,就需要遍历链表直到找到链表的末尾并将新节点插入到末尾。

链表节点的删除操作,需要处理多种情况,如删除的节点不在链表中、删除的节点是头节点、删除的节点是中间节点等。首先需要建立一个虚拟的头节点,这样可以方便处理头节点的删除。然后使用两个指针,分别指向遍历链表的前一个节点和当前节点,遍历链表直到找到目标节点,然后将前一个节点链接到目标节点的下一个节点上。

链表节点的查找操作,可以使用遍历链表的方式,依次访问每个节点并查找值等于目标值的节点。如果找到目标节点,则返回指向该节点的指针;如果没有找到目标节点,则返回空指针。

链表的遍历操作,只需要依次访问链表中的每个节点,并输出节点的值即可。

总结:

链表是一种十分重要的数据结构,本篇文章使用C++语言实现了链表的基本操作,并讲解了插入、删除、查找和遍历的算法思想。在实际的开发中,链表常被用于解决各种问题,如内存管理、算法设计等。熟练地掌握链表的基本操作,可以帮助我们更好地理解和应用数据结构。

  
  

评论区

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