Sequential search with sorted linked lists
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;
}
I cannot interpret this pseudocode. Can anyone explain to me how this program works and proceeds? Given this pseudocode, which looks for a value in a linked list and a list that is in ascending order, what would this program return?
and. The largest value in the list that is less than the target b. The largest value in the list that is less than or equal to the target c. The smallest value in the list that is greater than or equal to the target e. Target
f. The smallest value in the list that is greater than the target
And say List is [1, 2, 4, 5, 9, 20, 20, 24, 44, 69, 70, 71, 74, 77, 92] and target 15, how many comparisons are going on? (here comparison means target comparison)
EDIT: @Stephen I am sorry if I was rude in asking my question.
Ok, since I am used to programming in Visual Basic, I understand "cur-> key" in line 4 of the program because "cur is greater than or the same as the key", but since "+ =" means "the previous value plus the last value is equal to the last value ", I can interpret" -> "the same as" + = ". This part is one of the problems I am facing.
The second problem I ran into was using pointers in Record_node (if it is a pointer). I'm not even sure if I know what I don't! I understand this program as a kind of recursive algorithm.
a source to share
Ok, since I am used to programming in Visual Basic, I understand "cur-> key" in line 4 of the program because "cur is greater than or the same as the key", but since "+ =" means "the previous value plus the last value is equal to the last value ", I can interpret" -> "the same as" + = ". This part is one of the problems I am facing.
What's the problem, I'm glad you clarified that :)
This code is written in c
(or c++
). This language uses ->
dereferencing for pointers and points to structure members. IIRC, VB has no pointers, so you could say struct.member
or cur.next
.
while (cur->next != NULL) { // While current next node isn't NULL.
}
NULL
used to mark the end of the list.
Evaluation cur->next->key
means "key node after current". It can help you visualize this if you draw a linked list with ascending values โโand follow the program.
At some point during the while loop, you get this:
+-+ +-+ +-+
|2|--|4|--|7|--NULL
+-+ +-+ +-+
^ ^ ^
| | |
head cur cur->next
BTW, the real operator of greater than or equal to is >=
.
BTW2, it is not recursive. A recursive function will be a function that calls itself (you can implement this recursively). This function is iterative (it uses loops). An example of a recursive algorithm is:
node* Sequential_search(List *list, int target) {
if (!list) return NULL;
if (target == list->key) return list;
return Sequential_search(list->next, target);
}
Hope it helps!
a source to share
You may find it helpful to look at the list of C operators and their precedence , especially from VB. I applaud your courage to go to the list of links first .. but you might want to take some time to base down pointers before starting the list implementation.
This Stephen add-on is a great answer that I voted.
a source to share