如何在 C 的链表中找到可能有重复项的最小元素

Question

我正在尝试在具有两个数据字段 (data1, data2) 的链表中找到具有最小值 (data1) 的节点。

但可能会出现两个节点共享data1中相同最小值的情况。如果出现这种情况，我需要比较他们的data2，判断哪个较小（data1中的值相同，data2中的值较小），然后return节点。

到目前为止我有这样的东西：

struct Node { 
    int data1;
    int data2;
    struct Node* next; 
};

Node *find_min(Node *head);

C 编程新手。我应该怎么做呢？非常感谢您的帮助！

Answer 1

现在，向你的老师解释一下：

struct node *find_min(struct node *head)
{
struct node *best;

for(best=head; head = head ? head->next : NULL; ) { 
    if (head->data1 > best->data1) continue;
    if (head->data1 == best->data1
     && head->data2 > best->data2) continue;
    best = head;
    }
return best;
}

Answer 2

执行此操作的一个好方法是创建一个小例程来比较两个节点，然后使用它来明确地确定哪个节点具有最小值。像这样：

struct Node {
  int data1;
  int data2;
  struct Node* next;
};

static _Bool node_less(struct Node const* lhs, struct Node const* rhs) {
  if (lhs->data1 < rhs->data1) return 1;

  if (lhs->data1 > rhs->data1) return 0;

  return lhs->data2 < rhs->data2;
}

struct Node* find_min(struct Node* head) {
  struct Node* min_node = head;

  while ((head = head->next))
    if (node_less(head, min_node)) min_node = head;

  return min_node;
}

Answer 3

迭代

Node* find_min(struct Node* node) {
    if (!node)
        return 0;
    struct Node *min_node = node;
    for (struct Node *scan = node; scan; scan = scan->next) {
        if (scan->data1 < min_node->data1 || scan->data1 == min_node->data1 && scan->data2 < min_node->data2) {
            min_node = scan;
        }
    }
    return min_node;
}

递归

Node* find_min(struct Node* node) {
    if (!node)
        return 0;
    if (!node->next)
        return node;
    Node *min_sub_list = find_min(node->next);
    if (min_sub_list->data1 < node->data1 || min_sub_list->data1 == node->data1 && min_sub_list->data2 < node->data2) {
        return min_sub_list;
    }
    return node;
    
}

如何在 C 的链表中找到可能有重复项的最小元素

How to find the smallest element that might have duplicates in a Linked List in C

c

loops

compare

linked-list

min