C Program to Perform Searching using Self-Organizing Lists

This C program performs searching using self-organizing lists.

A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time. The aim of a self-organizing list is to improve efficiency of linear search by moving more frequently accessed items towards the head of the list. A self-organizing list achieves near constant time for element access in the best case. A self-organizing list uses a reorganizing algorithm to adapt to various query distributions at runtime.

Here is the source code of the C program to search using Self-Organizing Lists. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct node
  5. {
  6.     char info;
  7.     struct node *next;
  8. };
  9. struct node *start = NULL;
  10. struct node * create_node(char value)
  11. {
  12.     struct node *temp;
  13.     temp = (struct node *)malloc(sizeof(struct node*));
  14.     if (temp == NULL)
  15.     {
  16.         printf("\nMemory NOT allocated! \n");
  17.         return 0;
  18.     }
  19.     else
  20.     {
  21.         temp->info = value;
  22.         temp->next = NULL;
  23.  
  24.         return temp;
  25.     }
  26. }
  27. void delete_pos(int pos)
  28. {
  29.     int i, key = 0;;
  30.     if (start == NULL)
  31.     {
  32.         return;
  33.     }
  34.     struct node *s, *ptr;
  35.     s = start;
  36.     if (pos == 1)
  37.     {
  38.         start = s->next;
  39.     }
  40.     else
  41.     {
  42.         while (s != NULL)
  43.         {
  44.             s = s->next;
  45.             key++;
  46.         }
  47.         if (pos > 0 && pos <= key)
  48.         {
  49.             s = start;
  50.             for (i = 1;i < pos;i++)
  51.             {
  52.                 ptr = s;
  53.                 s = s->next;
  54.             }
  55.             ptr->next = s->next;
  56.         }
  57.         free(s);
  58.     }
  59. }
  60.  
  61. void insert_last(char value)
  62. {
  63.     struct node  *s;
  64.     struct node *temp = create_node(value);
  65.     if (start == NULL)
  66.     {
  67.         start = temp;
  68.         printf("Start has been initialized\n");
  69.         return;
  70.     }
  71.     s = start;
  72.     while (s->next != NULL)
  73.     {
  74.         s = s->next;
  75.     }
  76.     temp->next = NULL;
  77.     s->next = temp;
  78.     printf("Element inserted\n");
  79. }
  80.  
  81. int search(char value)
  82. {
  83.     int pos = 0;
  84.     int flag = 0;
  85.     if (start == NULL)
  86.     {
  87.         return 0;
  88.     }
  89.     struct node *s;
  90.     s = start;
  91.     while (s != NULL)
  92.     {
  93.         pos++;
  94.         if (s->info == value)
  95.         {
  96.             flag = 1;
  97.             return pos;
  98.         }
  99.         s = s->next;
  100.     }
  101.     if (!flag)
  102.         return 0;
  103. }
  104. void move_to_front(char value)
  105. {
  106.     int pos;
  107.     if (start == NULL)
  108.     {
  109.         printf("List is Empty, first create the list\n");
  110.         return;
  111.     }
  112.     pos = search(value);
  113.     if (pos)
  114.     {
  115.         delete_pos(pos);
  116.         insert_begin(value);
  117.     }
  118.     else
  119.         printf("\nElement not found!! \n");
  120.     display();
  121.  
  122. }
  123. void insert_begin(char value)
  124. {
  125.     struct node *temp, *p;
  126.     temp = create_node(value);
  127.     if (start == NULL)
  128.     {
  129.         start = temp;
  130.         start->next = NULL;
  131.     }
  132.     else
  133.     {
  134.         p = start;
  135.         start = temp;
  136.         start->next = p;
  137.     }
  138. }
  139. void display()
  140. {
  141.     struct node *temp;
  142.     if (start == NULL)
  143.     {
  144.         printf("List is Empty, nothing to display \n");
  145.         return;
  146.     }
  147.     temp = start;
  148.     while (temp != NULL)
  149.     {
  150.         printf("%c->", temp->info);
  151.         temp = temp->next;
  152.     }
  153.     printf("NULL\n");
  154. }
  155. int main()
  156. {
  157.     int position, choice;
  158.     char element;
  159.     do
  160.     {
  161.         printf("Operations on Self Organising list: ");
  162.         printf("\n1. Insert Node: ");
  163.         printf("\n2. Delete a particular node: ");
  164.         printf("\n3. Search a node: ");
  165.         printf("\n4. Display list: ");
  166.         printf("\n5. Exit \n\n");
  167.         scanf("%d", &choice);
  168.         switch (choice)
  169.         {
  170.             case 1:
  171.                 printf("\nEnter an element: ");
  172.                 scanf(" %c", &element);
  173.                 insert_last(element);
  174.                 break;
  175.             case 2:
  176.                 printf("\nEnter position where you want to delete: ");
  177.                 scanf("%d", &position);
  178.                 delete_pos(position);
  179.                 break;
  180.             case 3:
  181.                 printf("\nEnter a character element to search: ");
  182.                 scanf(" %c", &element);
  183.                 move_to_front(element);
  184.                 break;
  185.             case 4:
  186.                 display();
  187.                 break;
  188.             case 5:
  189.                 printf("\nExiting . . . "\n");
  190.                 return 0;
  191.             default:
  192.                 printf("Enter a valid choice: ");
  193.                 scanf("%d", &choice);
  194.         }
  195.     }
  196.     while(choice);
  197.     return 0;
  198.  
  199. }

$ gcc selforglist.c -o selforglist
$ ./selforglist
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: S
 
Start has been initialized
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: A
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: N
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: F
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: O
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: U
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: N
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: D
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: R
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
1
Enter an element: Y
 
Element inserted!
 
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
4
 
S->A->N->F->O->U->N->D->R->Y->NULL
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
3
Enter a character element to search: F->S->A->N->O->U->N->D->R->Y->NULL
Operations on Self Organising list: 
1. Insert Node: 
2. Delete a particular node: 
3. Search a node: 
4. Display list: 
5. Exit 
 
5
 
Exiting . . .

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.