如何编写函数以测试链接列表是否已排序 [英] How do I code a function to test if a linked list is sorted

问题描述

我查看了其他帖子，但没有找到很好的解决方案来进行查询.我不想对链接列表进行实际排序，我想看看它是否已排序.我在C ++中有一个链表问题.我被要求对给定链接列表定义的函数进行编码，以查看其是否已排序.

I looked at other posts and didnt find a great solution for my inquiry. I don't want to actually sort the linked list I want to see if its sorted or not. I have a linked list question in c++. I am asked to code a function given a linked list definition to see if its sorted.

实现函数 isSorted——如果链表中的值按升序排序，则返回 true.(链接列表由整数组成).

Implement the function isSorted – it returns true if the values in the linked list are sorted in increasing order. (The linked list is composed of integers).

具有以下结构:

struct ListNode
   {
      double value;           // The value in this node
      struct ListNode *next;  // To point to the next node
   }; 

样本数据:从isSorted返回
1-> 3-> 7是
4-> 2-> 7错误
()True//空列表.
3真实
1-> 5-> 7-> 2错误

Sample data: Return from isSorted
1 -> 3 -> 7 True
4 -> 2 -> 7 False
() True // Empty List.
3 True
1-> 5 -> 7 -> 2 False

我有这样的东西.

bool NumberList::isSorted() const
{
   ListNode *nodePtr;  // To move through the list
   nodePtr = head;

   while (nodePtr)
   {
      if(nodePtr->value <= nodePtr->value+1)
         nodePtr = nodePtr->next;
      else 
         return false;

       return true;
   }
}

我不确定我是否做对了，我需要帮助.谢谢.

I'm not sure if i'm doing this right, I need help. Thank you.

推荐答案

如果列表以升序排序，则对于您使用的比较函数，每个节点的值都大于或等于前一个值.IE.值永远不会减少.只需遍历节点并进行检查即可.

If the list is sorted in ascending order, then for the comparison function you're using each node has greater or equal value to the previous one. I.e. the values are never decreasing. Just iterate through the nodes and check that.

注意:您所显示的状况，

Note: the condition you have shown,

nodePtr->value <= nodePtr->value+1

不检查任何合理的东西:它检查一个值是否小于或等于该值加1.

does not check anything reasonable: it checks whether a value is less than or equal to that value plus 1.

一个更合理的条件的想法是将 nodePtr-> value 与上一个节点的值进行比较.为了轻松做到这一点，您需要在先前的迭代中存储先前节点的值(或指向先前节点的指针).在某些变量中.

One idea for a more reasonable condition is to compare nodePtr->value to the previous node's value. To do that easily, you need to have stored the previous node's value (or a pointer to the previous node) in the previous iteration. In some variable.

这篇关于如何编写函数以测试链接列表是否已排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！