Write a program to perform sequential search on a linked list.

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>
#include <stdlib.h>

typedef struct node *LINK;
struct node {
    int item;
    LINK next;
};

void list_add(LINK *head, int item);
void list_prn(LINK head);
int sequential_search(int key, LINK head);
void list_delete(LINK head);

int main(int argc, char ** argv) {
int i;
    LINK head;
    head = NULL; /* empty list */
    // Generate 10 random numbers and add to a linked list
    for (i = 1; i <= 10; i++) {
        list_add(&head, rand() % 1000);
    }
    // Display content of list
    list_prn(head);

    // Search for an item on the list
    if(sequential_search(200, head))
        printf("%d was found on the list\n", 200);
    else
        printf("%d not found\n", 200);
    // Delete list
    list_delete(head);
    printf("\nList deleted\n");

    return 0;
}

// Add items to the front or beginning of the list
void list_add(LINK *head, int item) {
    LINK tmp;
    /*allocate space for new node*/
    if ((tmp = malloc(sizeof(*tmp))) == NULL) {
        printf("\nNot enough memory");
        exit(1);
    }
    tmp -> item = item;
    tmp -> next = *head;
    *head = tmp;
}

// Print list beginning with the head
void list_prn(LINK head) {
    LINK tmp = head;
    printf("List items:\n");
    while(tmp != NULL) {
        printf("%d ", tmp->item);
        tmp = tmp->next;
    }
    printf("\n");
}

void list_sort(LINK head) {
    LINK tmp, track_node;
    int min;
    // Find node with smallest value in list
    while (head->next != NULL){
        tmp = head;
        min = tmp->item;
        while(tmp->next != NULL) {
            if(tmp->next->item < min) {
                min = tmp->next->item;
                track_node = tmp->next;
            }
            tmp = tmp -> next;
        }
        // Interchange its data with that at the top of the list
        track_node->item = head->item;
        head->item = min;
        // Assign Node next to the top as new top
        head = head -> next;
        track_node = head;
    }

}

// Perform sequential search on the list for a key
int sequential_search(int key, LINK head){
    int found = 0;
    list_sort(head);  
    LINK tmp = head;

    while (tmp != NULL) {
        if (tmp->item > key) 
            break;
        if (tmp->item == key){
            found = 1;
            break;
        }
        tmp = tmp->next;
    }
    return found;
}

// Loop through each node and free up the space used by the node
void list_delete(LINK head) {
    LINK tmp;
    while (head != NULL) {
       tmp = head -> next;
       free(head);
       head = tmp;
    }
}

When you compile and execute the above program it produces the following result on Linux:

List items:
421 649 492 386 335 793 915 777 886 383 
200 not found

List deleted

Brief Explanation

  • The program starts by setting the head of the list to NULL (empty list).
  • Using the random function rand, 10 numbers are generated and added to the list.
  • The function list_prn, takes the head of the list as parameter and display the content of the list.
  • The function sequential_search, searches for an item on the list. It does this by first sorting the list to make the search meaningful. Since the list is sorted, if the first item on the list is greater than what we are searching for, then the item is not found on the list otherwise keep searching in sequence until we find the item or we reach the end of the list. The function returns a value of 1 if found and 0 otherwise.
  • The function list_delete loops through each node and free up the space used by the node.

 

Add comment


Security code
Refresh