遍历链表C++并返回用户输入的最高值

Question

用户输入 int age 的值，并且该函数应该接受来自指向列表头部的指针的参数，并遍历链表节点和 return int age 的最高值。

这是我的功能；我不断得到随机数作为输出：

int findLargest (StudentCard *p) {
    int current = p->age;
    int next;

    StudentCard *temp = p;

    while(temp != NULL){
        if (p->age == NULL) {
            //The value at this node is obviously larger than a non-existent value
            return current;
        } else {
            //Recur to find the highest value from the rest of the LinkedList
            next = findLargest(p->next);
        }
        //Return the highest value between this node and the end of the list
        if (current > next) {
            return current;
        } else {
            return next;
        }
        temp=temp->next;
    }
}

Answer 1

首先，您应该 return -1 在函数的末尾通知未找到任何内容。

然后，您将 p->next 作为 findLargest 函数的参数发送，而没有检查以下代码中的 NULL：

//Recur to find the highest value from the rest of the LinkedList
next = findLargest(p->next);

而且，当您使用递归函数调用时，您根本不需要 while(temp != NULL) 循环。您可以将 while 替换为 if 并删除 temp = temp->next; 语句。递归或迭代足以解决您的问题。

您的 findLargest 函数应如下代码所示：

int findLargest (StudentCard *p) 
{
    if (p != NULL)
    {
        int current = p->age;
        int next = findLargest(p->next);

        if (current > next) {
            return current;
        } 
        else {
            return next;
        }
    }
    return -1;
}

要获取最早的学生节点指针，请使用以下定义：

StudentCard * findLargestNode(StudentCard *p) 
{
    if (p != NULL)
    {
        int curAge = p->age;

        StudentCard *next = findLargestNode(p->next);

        if (next && (next->age > curAge)) {
            return next;
        } 
        else {
            return p;
        }
    }
    return NULL;
}

打印最早的学号，使用如下函数

{
    StudentCard *pOld = findLargestNode(listHead); // `listHead` is HEAD node of your link-list
    if ( pOld )
        cout << pOld->id << endl;
}

Answer 2

您将迭代与递归混合使用，这通常不是一个好主意。

（您的编译器应该警告可能不会 return 从函数中获取值。）

您也可能在此处取消引用空指针：

int current = p->age;

并在这里比较错误的东西：

if (p->age == NULL)

（程序没有崩溃的事实让我怀疑你在某处有一个年龄为零的对象，导致你return那个零而不是递归。）

如果仔细阅读循环，您会注意到它总是 return 是第一次迭代的值，因此 temp 永远不会前进，而 while 可能是替换为 if.

您应该将函数重写为迭代或递归。

迭代解决方案如下所示：

int findLargest (StudentCard *p)
{
    int current = std::numeric_limits<int>::min();
    while (p != NULL){
        if (p->age > current) {
            current = p->age;
        }
        p = p->next;
    }
    return current;
}

递归解决方案如下所示：

int findLargest (StudentCard *p)
{
    if (p == NULL) {
        return std::numeric_limits<int>::min();
    }
    return std::max(p->age, findLargest(p->next));
}

遍历链表C++并返回用户输入的最高值

Looping through linked list C++ and returning the highest value of user input

c++

parameters

function

linked-list

list