C++ Program To Implement Self Organising List

«
»
This C++ Program demonstrates the concept of self organising list.

Here is source code of the C++ Program to demonstrate self organising list. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Self Organising List 
  3.  */
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<cstring>
  8. using namespace std;
  9. /*
  10.  * Node Declaration
  11.  */
  12. struct node
  13. {
  14.     char info;
  15.     int counter;
  16.     struct node *next;
  17. }*start;
  18.  
  19. /*
  20.  * Class Declaration
  21.  */
  22. class self_list
  23. {
  24.     public:
  25.         node* create_node(char);
  26.         void insert_last(char);
  27.         void insert_begin(char);
  28.         void delete_pos(int);
  29.         void display();
  30.         void sort();
  31.         void move_to_front();
  32.         int search(char);
  33.         void transpose();
  34.         void count();
  35.         self_list() 
  36.         {
  37.             start = NULL;
  38.         }			
  39. };
  40.  
  41. /*
  42.  * Main :contains menu 
  43.  */
  44. int main()
  45. {
  46.     int choice, position;
  47.     char element;
  48.     self_list sl;
  49.     start = NULL;
  50.     while (1)
  51.     {
  52.         cout<<endl<<"---------------------------------"<<endl;
  53.         cout<<endl<<"Operations on Self Organising list"<<endl;
  54.         cout<<endl<<"---------------------------------"<<endl;
  55.         cout<<"1.Insert Node at first"<<endl;
  56.         cout<<"2.Insert Node at last"<<endl;
  57.         cout<<"3.Delete a Particular Node"<<endl;
  58.         cout<<"4.Display List"<<endl;
  59.         cout<<"5.Move To Front Organising List"<<endl;
  60.         cout<<"6.Transpose Organising List"<<endl;
  61.         cout<<"7.Count Organising List"<<endl;
  62.         cout<<"8.Exit "<<endl;
  63.         cout<<"Enter your choice : ";
  64.         cin>>choice;
  65.         switch(choice)
  66.         {
  67.         case 1:
  68.             cout<<"Inserting Element at first"<<endl;
  69.             cout<<"Enter the character to be inserted: ";
  70.             cin>>element;
  71.             sl.insert_begin(element);
  72.             cout<<endl;
  73.             break;
  74.         case 2:
  75.             cout<<"Inserting Element at last"<<endl;
  76.             cout<<"Enter the character to be inserted: ";
  77.             cin>>element;
  78.             sl.insert_last(element);
  79.             cout<<endl;
  80.             break;  
  81.         case 3:
  82.             cout<<"Deleteing element at a given position"<<endl;
  83.             cout<<"Enter the position of element to be deleted: ";
  84.             cin>>position;
  85.             sl.delete_pos(position);
  86.             cout<<endl;
  87.             break;
  88.         case 4:
  89.             cout<<"Display elements of link list"<<endl;
  90.             sl.display();
  91.             cout<<endl;
  92.             break;
  93.         case 5:
  94.             cout<<"Move To Front Organising List"<<endl;
  95.             sl.move_to_front();
  96.             cout<<endl;
  97.             break;
  98.         case 6:
  99.             cout<<"Transpose Organising List"<<endl;
  100.             sl.transpose();
  101.             cout<<endl;
  102.             break;   
  103.         case 7:
  104.             cout<<"Count Organising List"<<endl;
  105.             sl.count();
  106.             cout<<endl;
  107.             break;    
  108.         case 8:
  109.             cout<<"Exiting..."<<endl;
  110.             exit(1);
  111.             break;  
  112.         default:
  113.             cout<<"Wrong choice"<<endl;
  114.         }
  115.     }
  116.     return 0;
  117. }
  118.  
  119. /*
  120.  * Creating Node
  121.  */
  122. node *self_list::create_node(char value)
  123. {
  124.     struct node *temp;
  125.     temp = new(struct node); 
  126.     if (temp == NULL)
  127.     {
  128.         cout<<"Memory not allocated "<<endl;
  129.         return 0;
  130.     }
  131.     else
  132.     {
  133.         temp->info = value;
  134.         temp->next = NULL;
  135.         temp->counter = 0;     
  136.         return temp;
  137.     }
  138. }
  139.  
  140. /*
  141.  * Inserting Node at last
  142.  */
  143. void self_list::insert_last(char value)
  144. {
  145.     struct node *temp, *s;
  146.     temp = create_node(value);
  147.     if (start == NULL)
  148.     {
  149.         start = temp;
  150.         return; 
  151.     }
  152.     s = start;
  153.     while (s->next != NULL)
  154.     {         
  155.         s = s->next;  
  156.     }
  157.     temp->next = NULL;
  158.     s->next = temp;
  159.     cout<<"Element Inserted"<<endl;
  160. }
  161. /*
  162.  * Inserting Node at beginning
  163.  */
  164. void self_list::insert_begin(char value)
  165. {
  166.     struct node *temp, *p;
  167.     temp = create_node(value);
  168.     if (start == NULL)
  169.     {
  170.         start = temp;
  171.         start->next = NULL;          
  172.     } 
  173.     else
  174.     {
  175.         p = start;
  176.         start = temp;
  177.         start->next = p;
  178.     }
  179. }
  180.  
  181. /*
  182.  * Delete element at a given position
  183.  */
  184. void self_list::delete_pos(int pos)
  185. {
  186.     int i, key = 0;;
  187.     if (start == NULL)
  188.     {
  189.         return;
  190.     }
  191.     struct node *s, *ptr;
  192.     s = start;
  193.     if (pos == 1)
  194.     {
  195.         start = s->next;
  196.     }
  197.     else
  198.     {
  199.         while (s != NULL)
  200.         {
  201.             s = s->next;
  202.             key++;    
  203.         }
  204.         if (pos > 0 && pos <= key)
  205.         {
  206.             s = start;
  207.             for (i = 1;i < pos;i++)
  208.             {
  209.                 ptr = s;
  210.                 s = s->next;
  211.             }
  212.             ptr->next = s->next;
  213.         }
  214.         free(s);
  215.     }
  216. }
  217.  
  218. /*
  219.  * Searching an element
  220.  */
  221. int self_list::search(char value)
  222. {
  223.     int pos = 0;
  224.     bool flag = false;
  225.     if (start == NULL)
  226.     {
  227.         return 0;
  228.     }
  229.     struct node *s;
  230.     s = start;
  231.     while (s != NULL)
  232.     {
  233.         pos++;
  234.         if (s->info == value)
  235.         {
  236.             flag = true;
  237.             return pos;
  238.         }
  239.         s = s->next;
  240.     }
  241.     if (!flag)
  242.         return 0;
  243. }
  244. /*
  245.  * Sorting Link List
  246.  */
  247. void self_list::sort()
  248. {
  249.     struct node *ptr, *s;
  250.     int value, temp;
  251.     if (start == NULL)
  252.     {
  253.         return;
  254.     }
  255.     ptr = start;
  256.     while (ptr != NULL)
  257.     {
  258.         for (s = ptr->next;s != NULL;s = s->next )
  259.         {
  260.             if (ptr->counter < s->counter)
  261.             {
  262.                 value = ptr->info;
  263.                 temp = ptr->counter;
  264.                 ptr->info = s->info;
  265.                 ptr->counter = s->counter;
  266.                 s->info = value;
  267.                 s->counter = temp;
  268.             }
  269.         }
  270.         ptr = ptr->next;
  271.     }
  272. }
  273.  
  274. /*
  275.  * Display Elements
  276.  */
  277. void self_list::display()
  278. {
  279.     struct node *temp;
  280.     if (start == NULL)
  281.     {
  282.         cout<<"The List is Empty, nothing to display"<<endl;
  283.         return;
  284.     }
  285.     temp = start;
  286.     while (temp != NULL)
  287.     {
  288.         cout<<temp->info<<"->";
  289.         temp = temp->next;
  290.     }
  291.     cout<<"NULL"<<endl;
  292. }
  293.  
  294. /*
  295.  * Move To Front Self Organizind List
  296.  */
  297. void self_list::move_to_front()
  298. {
  299.     if (start == NULL)
  300.     {
  301.         cout<<"The List is Empty, first create the list"<<endl;
  302.         return;
  303.     } 
  304.     char stream[100001];
  305.     cout<<"Enter the string of elements searched"<<endl;
  306.     cin>>stream;
  307.     int len, pos;
  308.     len = strlen(stream);
  309.     for (int i = 0;i < len;i++)
  310.     {
  311.         if (search(stream[i]) != 0)
  312.         {
  313.             if (search(stream[i]) != 1)		  
  314.             {
  315.                 pos = search(stream[i]);
  316.                 delete_pos(pos);
  317.                 insert_begin(stream[i]);
  318.             }
  319.             cout<<stream[i]<<": "; 
  320.             display();
  321.         }
  322.     }          	 
  323. }
  324.  
  325. /*
  326.  * Transpose Self Organizind List
  327.  */
  328. void self_list::transpose()
  329. {
  330.     if (start == NULL)
  331.     {
  332.         cout<<"The List is Empty, first create the list"<<endl;
  333.         return;
  334.     } 
  335.     char stream[100001];
  336.     cout<<"Enter the string of elements searched"<<endl;
  337.     cin>>stream;
  338.     int len, pos, temp;
  339.     len = strlen(stream);  
  340.     struct node *s;
  341.     for (int i = 0;i < len;i++)
  342.     {
  343.         s = start;	
  344.         if (search(stream[i]) != 0)
  345.         {
  346.             if(search(stream[i]) != 1)		  
  347.             {
  348.                 pos = search(stream[i]);
  349.                 for (int j = 1;j < pos - 1;j++)
  350.                 {
  351.                     s = s->next;
  352.                 }
  353.                 temp = s->info;
  354.                 s->info = s->next->info;
  355.                 s->next->info = temp;
  356.             }
  357.             cout<<stream[i]<<": ";
  358.             display();
  359.         }
  360.     }          	 
  361. }
  362. /*
  363.  * Count Self Organizind List
  364.  */
  365. void self_list::count()
  366. {
  367.     if (start == NULL)
  368.     {
  369.         cout<<"The List is Empty, first create the list"<<endl;
  370.         return;
  371.     } 
  372.     char stream[100001];
  373.     cout<<"Enter the string of elements searched"<<endl;
  374.     cin>>stream;
  375.     int len,pos;
  376.     len = strlen(stream);
  377.     struct node *s;
  378.     for (int i = 0;i < len;i++)
  379.     {
  380.         s = start;	
  381.         if (search(stream[i]) != 0)
  382.         {
  383.             pos = search(stream[i]);
  384.             for (int j = 0;j < pos - 1;j++)
  385.             {
  386.                 s = s->next;
  387.             }
  388.             (s->counter)++;
  389.             sort();
  390.             cout<<stream[i]<<": ";
  391.             display();
  392.         }
  393.     }          	 
  394. }

advertisement
$ g++ selforganising_+list.cpp
$ a.out
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 1
Inserting Element at first
Enter the character to be inserted: A
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 4
Display elements of link list
A->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 2
Inserting Element at last
Enter the character to be inserted: B
Element Inserted
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 2
Inserting Element at last
Enter the character to be inserted: C
Element Inserted
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 4
Display elements of link list
A->B->C->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 2
Inserting Element at last
Enter the character to be inserted: D
Element Inserted
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 1
Inserting Element at first
Enter the character to be inserted: E
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 4
Display elements of link list
E->A->B->C->D->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 2
Inserting Element at last
Enter the character to be inserted: F
Element Inserted
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 4
Display elements of link list
E->A->B->C->D->F->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 3
Deleteing element at a given position
Enter the position of element to be deleted: 6
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 4
Display elements of link list
E->A->B->C->D->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 5
Move To Front Organising List
Enter the string of elements searched
DEICABLMIONECBAYCE
D: D->E->A->B->C->NULL
E: E->D->A->B->C->NULL
C: C->E->D->A->B->NULL
A: A->C->E->D->B->NULL
B: B->A->C->E->D->NULL
E: E->B->A->C->D->NULL
C: C->E->B->A->D->NULL
B: B->C->E->A->D->NULL
A: A->B->C->E->D->NULL
C: C->A->B->E->D->NULL
E: E->C->A->B->D->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 6
Transpose Organising List
Enter the string of elements searched
DEICABLMIONECBAYCE
D: E->C->A->D->B->NULL
E: E->C->A->D->B->NULL
C: C->E->A->D->B->NULL
A: C->A->E->D->B->NULL
B: C->A->E->B->D->NULL
E: C->E->A->B->D->NULL
C: C->E->A->B->D->NULL
B: C->E->B->A->D->NULL
A: C->E->A->B->D->NULL
C: C->E->A->B->D->NULL
E: E->C->A->B->D->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 4
Display elements of link list
E->C->A->B->D->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 7
Count Organising List
Enter the string of elements searched
DEICABLMIONECBAYCE
D: D->C->A->B->E->NULL
E: D->E->A->B->C->NULL
C: D->E->C->B->A->NULL
A: D->E->C->A->B->NULL
B: D->E->C->A->B->NULL
E: E->D->C->A->B->NULL
C: E->C->D->A->B->NULL
B: E->C->B->A->D->NULL
A: E->C->B->A->D->NULL
C: C->E->B->A->D->NULL
E: C->E->B->A->D->NULL
 
 
---------------------------------
 
Operations on Self Organising list
 
---------------------------------
1.Insert Node at first
2.Insert Node at last
3.Delete a Particular Node
4.Display List
5.Move To Front Organising List
6.Transpose Organising List
7.Count Organising List
8.Exit 
Enter your choice : 8
Exiting...
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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