c - 使用已排序的链表进行顺序搜索

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;
}

我无法解释这个伪代码。任何人都可以向我解释这个程序是如何工作和流动的吗？给出这个在链表和升序列表中搜索值的伪代码，这个程序会返回什么？

一个。列表中小于目标的最大值
b.列表中小于或等于target的最大值
C。列表中大于或等于目标的最小值
d.目标
e.列表中大于目标的最小值

假设 List 是 [1, 2, 4, 5, 9, 20, 20, 24, 44, 69, 70, 71, 74, 77, 92] 和目标 15，进行了多少次比较？ (这里的比较就是比较target的值)

编辑:@Stephen 如果我粗鲁地问我的问题，我很抱歉。

嗯，由于我习惯用 Visual Basic 编程，所以我将程序第 4 行中的“cur->key”理解为“cur 大于或等于 key”，但由于“+=”表示“前者” value加上后面的值等于后面的值'，我可以把'->'解释成'+='，这部分是我面临的问题之一。

我面临的第二个问题是 Record_node 中指针的使用(如果它是指针)。我什至不确定我是否知道我不知道的事情!我将此程序理解为某种递归算法。

Answer 1

Well, since I am used to programming in Visual Basic, I understand 'cur->key' in line 4 of the program as 'cur is larger than or same as key', but since '+=' means 'former value plus the latter value equals the latter value', I can interpret '->' in the same manner as '+=' This part is one of the problems I am facing.

这就是问题所在，我很高兴你澄清了:)

此代码是用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

顺便说一句，真正的大于或等于运算符是 >=。

顺便说一句，它不是递归的。递归将是一个调用自身的函数(您可以递归地实现它)。这个函数是迭代的(它使用循环)。递归算法的一个例子是:

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

希望对您有所帮助!