C++ 程序为从单链表中选择随机节点

2024 年 8 月 29 日 | 阅读 3 分钟

在本文中，您将学习如何在 C++ 中从单链表中选择一个随机节点。如果您想从单链表中选择一个随机节点，可以按照以下步骤操作：

定义节点结构

首先在链表中建立节点结构。每个节点都应包含一个数据字段和一个指向下一个节点的指针。

struct Node {
int data;
Node* next;
// Constructor to initialize the node
Node(int value) : data(value), next(nullptr) {}
};

创建单链表

之后，实现一个类来表示单链表。该类应具有用于插入节点和执行其他所需任务的方法。

class LinkedList {
public:
Node* head;
// Constructor to initialize the linked list
LinkedList() : head(nullptr) {}
// Method to insert a node at the end of the list
void insertNode(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
};

选择随机节点

之后，您必须遍历链表以选择一个随机节点。实现此目的的一种方法是计算节点数，然后在该范围内创建一个随机索引。再次遍历列表，在随机选择的索引处停止。

示例

#include <iostream>
#include <cstdlib>
#include <ctime>
struct Node {
int data;
Node* next;
// Constructor to initialize the node
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
// Constructor to initialize the linked list
LinkedList() : head(nullptr) {}
// Method to insert a node at the end of the list
void insertNode(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Method to select a random node from the list
Node* getRandomNode() {
if (!head) {
return nullptr;  // Return nullptr for an empty list
}
// Count the number of nodes
int count = 0;
Node* temp = head;
while (temp) {
count++;
temp = temp->next;
}
// Generate a random index within the range [0, count-1]
int randomIndex = rand() % count;
// Traverse the list to the randomly selected index
temp = head;
for (int i = 0; i < randomIndex; ++i) {
temp = temp->next;
}
return temp;
}
};
int main() {
srand(time(nullptr));  // Seed for random number generation
LinkedList list;
list.insertNode(1);
list.insertNode(2);
list.insertNode(3);
list.insertNode(4);
list.insertNode(5);
Node* randomNode = list.getRandomNode();
if (randomNode) {
std::cout << "Random Node Value: " << randomNode->data << std::endl;
} else {
std::cout << "The list is empty." << std::endl;
}
return 0;
}

输出

Random Node Value: 4

说明

在调用 getRandomNode() 之前，此程序导入所需的头文件，使用 srand(time(nullptr)) 初始化随机数生成器，并在主函数中向链表添加一些示例节点。

下一主题C++ 中堆和树的比较

C++ 程序为从单链表中选择随机节点

定义节点结构

创建单链表

选择随机节点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 程序为从单链表中选择随机节点

定义节点结构

创建单链表

选择随机节点

相关帖子

在 C++ 中添加两个数字

C++ 锯齿数组

使用类将两个复数相加的 C++ 程序

C++ 程序计算数组中的正数和负数个数

C++ Reinterpret_cast

C++ ratio_less_equal() 函数

C++ 抽象工厂设计模式

C++ String_view

C++ AVL 树

C++ 程序检查矩阵是否正交

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器