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.

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