Последовательный поиск с отсортированными связанными списками

Question

struct Record_node* Sequential_search(struct Record_node *List, int target) { 
    struct Record_node *cur;
    cur = List->head ;
    if(cur == NULL || cur->key >= target) {
        return NULL;
    }
    while(cur->next != NULL) {
        if(cur->next->key >= target) {
            return cur;
        }
        cur = cur->next;
    }
    return cur;
}

Я не могу интерпретировать этот псевдокод. Кто-нибудь может объяснить мне, как эта программа работает и течет? Учитывая этот псевдокод, который ищет значение в связанном списке и списке в порядке возрастания, что бы эта программа возвратила?

а. Наибольшее значение в списке, которое меньше целевого значения
б. Наибольшее значение в списке, которое меньше или равно целевому значению
с. Наименьшее значение в списке, которое больше или равно целевому значению
д. Target
е. Наименьшее значение в списке больше целевого значения

И скажите, что Список - это [1, 2, 4, 5, 9, 20, 20, 24, 44, 69, 70, 71, 74, 77, 92] и цель 15, сколько проведено сравнений? (здесь сравнение означает сравнение значения цели)

EDIT: @ Стефан, прости, если я грубо задал свой вопрос.

Ну, так как я привык к программированию в Visual Basic, я понимаю «cur-> key» в строке 4 программы как «cur больше или равно ключу», но так как «+ =» означает «прежнее» значение плюс последнее значение равно последнему значению ', я могу интерпретировать' -> 'так же, как' + = '. Эта часть - одна из проблем, с которыми я сталкиваюсь.

Вторая проблема, с которой я сталкиваюсь, - это использование указателей в Record_node (если это указатель). Я даже не уверен, знаю ли я то, чего не знаю! Я понимаю эту программу как некий рекурсивный алгоритм.

Answer 1

Ну, так как я привык к программированию в Visual Basic, я понимаю «cur-> key» в строке 4 программы как «cur больше или равно ключу», но так как «+ =» означает «бывший» значение плюс последнее значение равно последнему значению ', я могу интерпретировать' -> 'так же, как' + = 'Эта часть является одной из проблем, с которыми я сталкиваюсь.

Вот в чем проблема, я рад, что вы разъяснили:)

Этот код записан в c (или c++). Этот язык использует -> для разыменования указателей и указания на элементы структуры. IIRC, VB не имеет указателей, так что вы бы сказали struct.member или cur.next.

while (cur->next != NULL) {   // While current's next node isn't NULL.
}

NULL используется для обозначения конца списка.

Оценка cur->next->key означает «ключ узла после текущего». Это может помочь вам визуализировать это, если вы рисуете связанный список с возрастающими значениями и отслеживаете программу.

В какой-то момент во время выполнения цикла while вы получите следующее:

+-+  +-+  +-+
|2|--|4|--|7|--NULL
+-+  +-+  +-+
 ^    ^    ^
 |    |    |
 head cur  cur->next

Кстати, оператор real больше или равен * >=.

Кстати, это не рекурсивно. Рекурсивом будет функция, которая вызывает себя (вы можете реализовать это рекурсивно). Эта функция итеративна (она использует циклы). Пример рекурсивного алгоритма:

node* Sequential_search(List *list, int target) {
  if (!list) return NULL;
  if (target == list->key) return list;
  return Sequential_search(list->next, target);
}

Надеюсь, это поможет!

Answer 2

Возможно, вам будет полезно просмотреть список операторов C и их приоритет , особенно из VB. Я приветствую вашу храбрость за то, что вы прыгнули в список ссылок сначала .. но вы можете потратить некоторое время на ознакомление с основами указателей, прежде чем начинать реализацию списка.

Это дополнение к великому ответу Стивена , за который я проголосовал.