我得到了一个家庭作业，要求我遍历一个带有给定类头的链表，我不应该改变：
template<typename ItemType>
class LinkedList{
public:
...
LinkedList();
LinkedList(const LinkedList<ItemType>&);
int getCurrentSize340RecursiveNoHelper() const;
private:
Node<ItemType>* headPtr{ nullptr }; // Pointer to first node
}
节点类标头为：
template<typename ItemType>
class Node {
public:
...
Node();
Node(const ItemType&);
Node(const ItemType&, Node<ItemType>*);
Node<ItemType>* getNext() const;
private:
ItemType item; // A data item
Node<ItemType>* next{ nullptr }; // Pointer to next node
}
在函数getCurrentSize340RecursiveNoHelper()中，我们应该迭代链表以获得大小。
我知道我可以在静态或全局的帮助下迭代链表，但我的教授说我们应该避免使用它们。有什么可能的方法可以做到这一点吗？
可以通过成员变量而不是参数递归。
int LinkedList::getCurrentSize340RecursiveNoHelper() const {
if (this->headPtr == nullptr){
return 0;
}
Node<ItemType> nextNode = this->headPtr->getNext();
if (nextNode != nullptr){
LinkedList<ItemType> restOfList;
restOfList.add(nextNode); // a bit weird but this is the only way you can set the headPtr of a linked list.
return 1 + restOfList.getCurrentSize340RecursiveNoHelper();
}
return 1;
}
在函数 getCurrentSize340RecursiveNoHelper() 中，我们应该 以迭代链表以获取大小。
我知道我可以在静态或 全球，但我的教授说我们应该避免使用它们。
有什么可能的方法可以做到这一点吗？
最后一个问题首先：是的，这是可能的，甚至很容易。软件非常灵活。
没有函数参数的递归(也不是静态变量，也不是全局变量)。
没有参数的迭代和递归都很容易做到，一旦你了解了如何做。
通过练习，您可以轻松避免静态和全局变量。
另请参阅：https://stackoverflow.com/a/45550373/2785528，它提供了一种简单的机制来"在不使用全局变量的情况下通过系统传递用户输入"。 我们可以将其总结为 2 个步骤，a) 在 main 的早期实例化一个自定义类实例以包含(用于"传输")任何用户输入/值，否则您将这些输入/值放入全局变量中供各种用户获取，然后 b) 通过引用将这些传输对象传递给需要它们的对象的 ctor(以类似于旅行箱的方式)。 容易。
工藤对教授坚持用户定义类型(UDT)。 这是你需要练习的东西。
但是，对于这篇文章，通过简单地忽略您声明没有问题的 UDT，研究操作方法(没有参数的迭代和递归等)会更简单。 这样，我们可以专注于函数形式。
为了进一步简化，我的例子将是函子......一种简短而简单的课程形式。 我推荐函子类既简单又高效。
再简化一点，我将使用 std：：list。有很多关于如何制作、填充和使用这个容器的例子。
一个关键思想(支持无参数函数)是将数据和方法"捆绑"到类中。 封装是你的朋友。
想法 1 -- 最小化 main()。 保持简短。 走出去，直接进入正题。
int main(int, char**)
{
int retVal = 0;
retVal += F820_Iterative_t()();
retVal += F820_Recursive_t()();
return retVal;
}
此处调用了两个函子。 我将迭代示例与递归示例分开。
请注意，这些函子在 main 的早期被调用。 有很多东西在 main 之前被初始化(但请参阅众所周知的初始化惨败)。 这简化并控制了这些初始化何时发生。
第一个函子将实例化、处理，然后销毁，在下一个函子启动之前完成其整个生命周期，即它们被序列化。
数据类型：
// examples use std::list
// user typedefs ---------------vvvvvvvvvvv
typedef list<string> StrList_t;
typedef list<string>::iterator StrListIt_t;
数据属性：
// Functor
class F820_Iterative_t
{
// NOTE: class instance data attributes are not global vars
StrList_t m_strList; // std::list<std::string>
StrListIt_t m_it; // std::list<std::string>::iterator
...
// Functor
class F820_Recursive_t
{
StrList_t m_strList; // std::list<std::string>
StrListIt_t m_it; // std::list<std::string>::iterator
...
示例 1 -- 迭代元素计数
// iterate with no parameters, static vars, or global vars
uint F820_Iterative_t::iterateCount( )
{ // --^-- no params
uint lcount = 0;
do // -------------iterative loop
{
if (m_it == m_strList.end()) // detect end of list
break; // kick out
lcount += 1;
m_it++; // step to next element
} while(true);
return(lcount);
}
示例 2 -- 递归元素计数
// recurse with no parameters, static vars, or global vars
uint F820_Recursion_t::recurseCount( )
{ // --^-- no params
if (m_it == m_strList.end()) // RTC (recursion termination clause)
return 0;
m_it++; // step to next element
return (1 + recurseCount()); // tail recursion
} // --^^^^^^^^^^^^-- recursive invocation
在上述两个元素计数函数中，在调用 F820_xxx：：xxxCount() 之前初始化函子数据属性。
此代码不使用函数参数，也不使用全局变量。 这些函数(m_it 和 m_strList)中使用的变量是类实例的数据属性。 该函数通过隐含的"this"指针直接访问它们。
生活中断。
以上两个 xxxxCount() 都在上面进行比较。 如果需要，请请求更多，此代码将编译并运行。 我打算找时间插入其余的。
当你处理递归问题时，一个技巧是假设递归函数有效，当且仅当你给它一个比你正在处理的问题更简单的问题时。您将获得指向链表头部的指针。处理基本情况后，您现在知道列表至少有一个元素。您可以要求回避函数做的一个更简单的问题是计算列表其余部分的长度，然后在结果中加1。