C++单链表的基本操作实现 |21xrx.com

C++单链表的基本操作实现

2023-07-14 04:51:55 深夜i -- --

C++ 单链表基本操作实现

C++单链表是一种常用的数据结构，其基本操作包括插入、删除、查找等，本文将介绍这些基本操作的实现方法。

1. 创建单链表

单链表是由若干个结点组成的，每个结点包含一个数据域和一个指针域，指向下一个结点。我们可以定义一个结构体来表示一个结点，如下所示：

struct ListNode {

int val;

ListNode* next;

};

其中，val表示结点的值，next指向下一个结点。如果当前结点是最后一个结点，则next指向空指针。

要创建一个单链表，首先需要创建头结点，它不存储实际的数据，只是用来指向第一个实际的结点。创建头结点的代码为：

ListNode* head = new ListNode;

接下来，可以创建任意数量的结点，将它们按照顺序插入到单链表中。使用指针变量（如p）来指向当前正在操作的结点，当需要插入新结点时，可以用new运算符来创建新结点，并将当前结点的next指向新结点，新结点的next指向下一个结点。

2. 遍历单链表

遍历单链表是指逐一访问单链表中的每个结点，并对其进行处理。一般来说，遍历单链表的方法有两种，分别是用while循环和用递归实现。

用while循环遍历单链表的代码为：

ListNode* p = head->next;

while (p != NULL)

// 处理p指向的结点

p = p->next;

其中，p指向第一个实际的结点，while循环会一直进行，直到p指向空指针，即已经访问完了单链表中的所有结点。

用递归遍历单链表的代码为：

void traverse(ListNode* p) {

if (p == NULL) return;

// 处理p指向的结点

traverse(p->next);

}

其中，traverse函数会递归地调用自己，并且在每次调用时传入p指向的下一个结点，直到p指向空指针，递归结束。

3. 插入结点

在单链表中插入结点是指在任意位置（包括头部、尾部和中间）插入新结点。具体实现方法如下：

在头部插入结点：

ListNode* newNode = new ListNode;

newNode->next = head->next;

head->next = newNode;

其中，newNode是新创建的结点，next指向原来的第一个结点（如果有的话），head->next指向新结点。

在尾部插入结点：

ListNode* newNode = new ListNode;

newNode->next = NULL;

ListNode* p = head;

while (p->next != NULL) p = p->next;

p->next = newNode;

其中，newNode是新创建的结点，next指向空指针，p指向最后一个结点，while循环会一直进行，直到p指向最后一个结点，将最后一个结点的next指向新结点。

在中间插入结点：

ListNode* newNode = new ListNode;

newNode->next = p->next;

p->next = newNode;

其中，newNode是新创建的结点，next指向原来的下一个结点，p指向要插入的位置的前一个结点，将p的next指向新的结点，新的结点的next指向原来的下一个结点。

4. 删除结点

在单链表中删除结点是指将任意位置（包括头部、尾部和中间）的结点从单链表中移除。具体实现方法如下：

从头部删除结点：

ListNode* p = head->next;

head->next = p->next;

delete p;

其中，p指向要删除的结点，head->next指向第一个实际的结点，将head->next指向要删除的结点的下一个结点，然后释放p指向的结点的空间。

从尾部删除结点：

ListNode* p = head;

while (p->next->next != NULL) p = p->next;

delete p->next;

p->next = NULL;

其中，p指向要删除的结点的前一个结点，while循环会一直进行，直到p指向倒数第二个结点，将p的next指向空指针，然后释放p->next指向的结点的空间。

从中间删除结点：

ListNode* p = head;

while (p->next != NULL && p->next->val != val) p = p->next;

if (p->next == NULL) return;

ListNode* q = p->next;

p->next = q->next;

delete q;

其中，p指向要删除的结点的前一个结点，while循环会一直进行，直到p指向要删除的结点的前一个结点或者p已经指向了空指针（即要删除的结点不在单链表中），将p的next指向要删除的结点的下一个结点，然后释放q指向的结点的空间。

以上就是C++单链表的基本操作实现方法，熟练掌握这些操作可以帮助我们更好地理解和使用该数据结构。

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

下一篇: 节点JS与Python的比较

评论区

()

相似文章