小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。
编写一个函数来计算给定单链表中的节点数。
例如,对于链表 1->3->1->2->1,函数应该返回 5。
迭代解决方案
1) 初始化计数为 0
2) 初始化一个节点指针,current = head。
3) 在 current 不为 NULL 时执行以下操作
a) current = current -> next
b) count++;
4) 返回计数
复制代码
以下是上述算法的迭代实现,用于查找给定单链表中的节点数。
// 递归 C++ 程序,用于查找链表中节点的长度或计数
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/*给定一个指向头部的引用(指向指针的指针)
一个列表和一个整数,在前面推一个新节点
的名单。*/
void push(Node** head_ref, int new_data)
{
/* 分配节点 */
Node* new_node = new Node();
/* 放入数据 */
new_node->data = new_data;
/* 将旧列表从新节点链接起来 */
new_node->next = (*head_ref);
/*移动头部指向新节点*/
(*head_ref) = new_node;
}
/* 递归计算链表中的节点数 */
int getCount(Node* head)
{
// 基本情况
if (head == NULL) {
return 0;
}
// 计算这个节点加上列表的其余部分
else {
return 1 + getCount(head->next);
}
}
/* 测试计数功能的驱动程序*/
int main()
{
/* 从空列表开始 */
Node* head = NULL;
/* 使用 push() 构造下面的列表 1->2->1->3->1 */
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 1);
/* 检查计数功能 */
cout << "节点数为 " << getCount(head);
return 0;
}
复制代码
输出:
节点数为 5
复制代码
🥇 往期优质文章
教你用Java做出一个五子棋小游戏
使用 python 的单人AI 扫雷游戏
数据结构单链表之链表介绍 | 第一套
数据结构单链表之链表与数组 | 第二套
数据结构单链表之链表插入 | 第三套
数据结构单链表之删除节点 | 第四套
数据结构单链表之删除给定位置的链表节点 | 第五套
数据结构单链表之查看数组与链表的方法 | 第六套-1
数据结构单链表之查看数组与链表的方法 | 第六套-2
📣尾注:
想要获取更多数据结构相关的知识,你可以关注我:海拥,我希望你觉得这篇文章有帮助。
如果你看到这里,感谢你的阅读 🙂
💌 欢迎大家在评论区提出意见和建议!💌
如果你真的从这篇文章中学到了一些新东西,喜欢它,收藏它并与你的小伙伴分享。🤗最后,不要忘了❤或📑支持一下哦。
近期评论