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.

advertisement
  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

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn