C++ Program to Implement Vlist

«
»
This C++ Program demonstrates operations on Vlist.

Here is source code of the C++ Program to demonstrate operations on Vlist. 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 Vlist
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. using namespace std;
  8. /*
  9.  * Sublist Declaration
  10.  */
  11. struct sublist
  12. {
  13.     struct sublist* next;
  14.     int *buf;
  15. };
  16. /*
  17.  * Vlist Node Declaration
  18.  */
  19. typedef struct vlist_t 
  20. {
  21.     sublist* head;
  22.     int last_size, ofs;
  23. }*vlist;
  24. /*
  25.  * Vlist Class Declaration
  26.  */
  27. class v_list
  28. {
  29.     public:
  30.         sublist *sublist_new(int);
  31.         vlist v_new();
  32.         void v_del(vlist);
  33.         int v_size(vlist);
  34.         int* v_addr(vlist, int);
  35.         int v_elem(vlist, int);
  36.         int* v_unshift(vlist, int);
  37.         int v_shift(vlist);
  38.         v_list()
  39.         {}
  40. };
  41.  
  42. /*
  43.  * Main:Conatins Menu
  44.  */
  45. int main()
  46. {
  47.     int i, x, choice;
  48.     v_list vl;
  49.     vlist v = vl.v_new();
  50.     while (1)
  51.     {
  52.         cout<<"\n------------------"<<endl;
  53.         cout<<"Operations on Vlist "<<endl;
  54.         cout<<"\n------------------"<<endl;
  55.         cout<<"1.Insert Element to the front of Vlist"<<endl;
  56.         cout<<"2.Compute length of Vlist"<<endl;
  57.         cout<<"3.Find k-th Element"<<endl;
  58.         cout<<"4.Remove Element from Vlist"<<endl; 
  59.         cout<<"5.Display Vlist Elements"<<endl;
  60.         cout<<"6.Quit"<<endl;
  61.         cout<<"Enter your Choice: ";
  62.         cin>>choice;
  63.         cout<<endl;
  64.         switch(choice)
  65.         {
  66.         case 1:
  67.             cout<<"Enter element to be inserted: ";
  68.             cin>>x;
  69.             vl.v_unshift(v, x);
  70.             break;
  71.         case 2:
  72.             cout<<"Size of Vlist: "; 
  73.             cout<<vl.v_size(v)<<endl;
  74.             break;
  75.         case 3:
  76.             cout<<"Enter position of element to locate: ";
  77.             cin>>x;
  78.             if (x > vl.v_size(v))
  79.                 cout<<"Position out of range"<<endl;
  80.             else
  81.                 cout<<"Element at position "<<x<<": "<<vl.v_elem(v, x - 1)<<endl;
  82.             break;
  83.         case 4:
  84. 	    cout<<"Element Removed: "<<vl.v_shift(v)<<endl;   
  85. 	    break;
  86.         case 5:
  87. 	    cout<<"Displaying Elements of Vlist"<<endl;
  88. 	    for (i = 0;i < vl.v_size(v);i++)
  89. 	        cout<<vl.v_elem(v, i)<<" ";
  90. 	    cout<<endl;
  91. 	    break;  
  92.         case 6:
  93.             exit(1);
  94.             break;
  95.         default:
  96.             cout<<"Wrong Choice"<<endl;
  97.         }
  98.     }
  99.     vl.v_del(v);
  100.     return 0;
  101. }
  102.  
  103. /*
  104.  * Creating new sublist
  105.  */
  106. sublist *v_list::sublist_new(int s)
  107. {
  108.     sublist* sub = (sublist *)malloc(sizeof(sublist) + sizeof(int) * s);
  109.     sub->buf = (int*)(sub + 1);
  110.     sub->next = 0;
  111.     return sub;
  112. }
  113. /*
  114.  * Creating Vlist from Sublist
  115.  */
  116. vlist v_list::v_new()
  117. {
  118.     vlist v = new(vlist_t);
  119.     v->head = sublist_new(1);
  120.     v->last_size = 1;
  121.     v->ofs = 0;
  122.     return v;
  123. }
  124.  
  125. /*
  126.  * Deleting Vlist
  127.  */
  128. void v_list::v_del(vlist v)
  129. {
  130.     sublist *s;
  131.     while (v->head) 
  132.     {
  133.         s = v->head->next;
  134.         free(v->head);
  135.         v->head = s;
  136.     }
  137.     free(v);
  138. }
  139.  
  140. /*
  141.  * Compute Length of Vlist
  142.  */
  143. int v_list::v_size(vlist v)
  144. {
  145.     return v->last_size * 2 - v->ofs - 2;
  146. }
  147.  
  148. int *v_list::v_addr(vlist v, int idx)
  149. {
  150.     sublist *s = v->head;
  151.     int top, i;
  152.     top = v->last_size; 
  153.     i = idx + v->ofs;
  154. 	if (i + 2 >= (top << 1)) 
  155.     {
  156.         cout<<"!: idx "<<idx<<" out of range"<<endl;
  157.         abort();
  158.     }
  159.     while (s && i >= top) 
  160.     {
  161.         s = s->next;
  162.         i ^= top;
  163.         top >>= 1;
  164.     }
  165.     return s->buf + i;
  166. }
  167.  
  168. /*
  169.  * Locate Element at any position in the Vlist 
  170.  */
  171. int v_list::v_elem(vlist v, int idx)
  172. {
  173.     return *v_addr(v, idx);
  174. }
  175.  
  176. /*
  177.  * Add Element in the Vlist 
  178.  */
  179. int *v_list::v_unshift(vlist v, int x)
  180. {
  181.     sublist* s;
  182.     int *p;
  183.     if (!v->ofs) 
  184.     {
  185.         if (!(s = sublist_new(v->last_size << 1))) 
  186.         {
  187.             cout<<"allocation failure"<<endl;
  188.             return 0;
  189.         }
  190.         v->ofs = (v->last_size <<= 1);  
  191.         s->next = v->head;
  192.         v->head = s;
  193.     }
  194.     *(p = v->head->buf + --v->ofs) = x;
  195.     return p;
  196. }
  197.  
  198. /*
  199.  * Remove Element from the Vlist 
  200.  */
  201. int v_list::v_shift(vlist v)
  202. {
  203.     sublist* s;
  204.     int x;
  205.     if (v->last_size == 1 && v->ofs == 1) 
  206.     {
  207.         cout<<"empty list"<<endl;
  208.         abort();
  209.     }
  210.     x = v->head->buf[v->ofs++];
  211.     if (v->ofs == v->last_size) 
  212.     {
  213.         v->ofs = 0;
  214.         if (v->last_size > 1) 
  215.         {
  216.             s = v->head;
  217.             v->head = s->next;
  218.             v->last_size >>= 1;
  219.             free(s);
  220.         }
  221.     }
  222.     return x;
  223. }

advertisement
$ g++ vlist.cpp
$ a.out
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 0
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 5
 
Displaying Elements of Vlist
 
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 1
 
Enter element to be inserted: 100
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 1
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 1
 
Enter element to be inserted: 200
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 1
 
Enter element to be inserted: 300
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 3
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 5
 
Displaying Elements of Vlist
300 200 100 
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 3
 
Enter position of element to locate: 2
Element at position 2: 200
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 4
 
Element Removed: 300
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 2
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 5
 
Displaying Elements of Vlist
200 100 
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 1
 
Enter element to be inserted: 400
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 3
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 1
 
Enter element to be inserted: 500
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 1
 
Enter element to be inserted: 600
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 5
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 5
 
Displaying Elements of Vlist
600 500 400 200 100 
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 5
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 3
 
Enter position of element to locate: 1
Element at position 1: 600
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 4
 
Element Removed: 600
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 5
 
Displaying Elements of Vlist
500 400 200 100 
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 2
 
Size of Vlist: 4
 
------------------
Operations on Vlist 
 
------------------
1.Insert Element to the front of Vlist
2.Compute length of Vlist
3.Find k-th Element
4.Remove Element from Vlist
5.Display Vlist Elements
6.Quit
Enter your Choice: 6
 
 
------------------
(program exited with code: 1)
Press return to continue

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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 & technical discussions at Telegram SanfoundryClasses.