21xrx.com
2024-06-02 22:35:18 Sunday
登录
文章检索 我的文章 写文章
C++手写链表：从零开始实现链表数据结构
2023-07-13 06:10:48 深夜i     --     --
C++ 手写 链表 数据结构 实现

在软件开发过程中，数据结构是一个至关重要的概念，链表（Linked List）是一种常用的数据结构之一。在C++中，通过手写链表的实现，可以深入理解链表的原理和实现方式，提高程序开发的效率和质量。

链表是一种由节点（Node）组成的数据结构，每个节点都有一个指向下一个节点的指针，最后一个节点的指针为空。通过这种方式，链表可以实现动态存储数据，具有插入、删除节点的灵活性。链表有单向、双向和循环等多种类型，本篇文章将重点介绍如何实现单向链表。

链表的头指针（Head Pointer）指向链表的第一个节点，如果链表为空则指针为空。我们需要定义一个节点结构体Node，包含数据域和指针域，如下所示：



struct Node {


  int data;  // 数据域


  Node* next; // 指针域


};

其中，data可以是任何类型的数据，next是指向下一个节点的指针，将其初始化为空指针NULL。

接下来，我们可以通过创建Node对象来组织节点，并将它们连接起来。可以通过以下步骤实现：

1. 定义一个头指针pHead，将其初始化为空指针NULL。

2. 创建第一个节点，并将其next指向NULL。

3. 将pHead指向第一个节点。

4. 创建后面的节点，将其next指向前一个节点。

具体实现代码如下：



Node* pHead = NULL; // 头指针


// 创建第一个节点


Node* p = new Node;


p->data = 1;


p->next = NULL;


// 将头指针指向第一个节点


pHead = p;


// 创建后面的节点


for (int i = 2; i <= 5; i++) {


  Node* q = new Node;


  q->data = i;


  q->next = NULL;


  p->next = q;


  p = q;


}

创建链表后，我们可以遍历链表，输出链表中所有节点的值。可以通过以下步骤实现：

1. 定义一个指针p，将其指向头指针pHead。

2. 使用while循环遍历链表，输出每个节点的data。

3. 不断将p向后移动到下一个节点。

具体实现代码如下：



Node* p = pHead; // 指向头指针


// 遍历链表并输出每个节点的data


while (p != NULL)


  cout << p->data << " ";


  p = p->next;

最后，链表的删除操作也是十分重要的。删除节点需要先找到该节点的前一个节点，将其next指向该节点的下一个节点，再将该节点删除。如果该节点是首节点，需要特殊处理。具体实现代码如下：



// 删除链表中第k个节点


void DeleteNode(Node* pHead, int k) {


  if (pHead == NULL) // 链表为空


    return;


  if (k == 1) { // 删除首节点


    Node* p = pHead;


    pHead = pHead->next;


    delete p;


    return;


  }


  Node* p = pHead;


  for (int i = 1; i < k - 1 && p != NULL; i++)


    p = p->next; // 找到第k-1个节点


  


  if (p == NULL || p->next == NULL)  // 节点不存在或者k超出了链表长度


    return;


  


  Node* q = p->next;


  p->next = q->next; // 删除第k个节点


  delete q;


}

通过这样的手写链表实现，可以加深对链表的理解，为日后更加高效的程序开发打下坚实的基础。

  
  

评论区

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