Unit 2: Assignments - Assignment 7 CIS 210 fall 2011 PART A You are to build a f
ID: 3635109 • Letter: U
Question
Unit 2: Assignments - Assignment 7CIS 210 fall 2011
PART A
You are to build a function that creates a doubly liked list as discussed in class. Be sure to keep a list of available locations. A main program will input a number from the keyboard and call the function. After each insertion or deletion another function will write the sorted list forward and then backward. You will need a search routine to locate an element to be deleted. Test the program with the following sequence:
enter 5
enter 7
enter 9
enter 11
delete 9
enter 2
delete 5
delete 11
You will receive double points if you use a vector to implement your linked list.
Partial credit will be given.
PART B
Programming project 7, page 527 of the Savitch text.
Explanation / Answer
1. #include 2. 3. template 4. class double_linked 5. { 6. struct node 7. { 8. T data; 9. node* prev; 10. node* next; 11. node(T t, node* p, node* n) : data(t), prev(p), next(n) {} 12. }; 13. node* head; 14. node* tail; 15. public: 16. double_linked() : head( NULL ), tail ( NULL ) {} 17. template 18. double_linked( T (&arr) [N]) : head( NULL ), tail ( NULL ) 19. { 20. for( int i(0); i != N; ++i) 21. push_back(arr[i]); 22. } 23. 24. bool empty() const { return ( !head || !tail ); } 25. operator bool() const { return !empty(); } 26. void push_back(T); 27. void push_front(T); 28. T pop_back(); 29. T pop_front(); 30. 31. ~double_linked() 32. { 33. while(head) 34. { 35. node* temp(head); 36. head=head->next; 37. delete temp; 38. } 39. } 40. }; 41. 42. template 43. void double_linked::push_back(T data) 44. { 45. tail = new node(data, tail, NULL); 46. if( tail->prev ) 47. tail->prev->next = tail; 48. 49. if( empty() ) 50. head = tail; 51. } 52. 53. template 54. void double_linked::push_front(T data) 55. { 56. head = new node(data, NULL, head); 57. if( head->next ) 58. head->next->prev = head; 59. 60. if( empty() ) 61. tail = head; 62. } 63. 64. template 65. T double_linked::pop_back() 66. { 67. if( empty() ) 68. throw("double_linked : list empty"); 69. node* temp(tail); 70. T data( tail->data ); 71. tail = tail->prev ; 72. 73. if( tail ) 74. tail->next = NULL; 75. else 76. head = NULL ; 77. 78. delete temp; 79. return data; 80. } 81. 82. template 83. T double_linked::pop_front() 84. { 85. if( empty() ) 86. throw("double_linked : list empty"); 87. node* temp(head); 88. T data( head->data ); 89. head = head->next ; 90. 91. if( head ) 92. head->prev = NULL; 93. else 94. tail = NULL; 95. 96. delete temp; 97. return data; 98. } 99. 100. 101. int main() 102. { 103. int arr[] = { 4, 6, 8, 32, 19 } ; 104. double_linked dlist ( arr ); 105. dlist.push_back( 11 ); 106. dlist.push_front( 100 ); 107. while( dlist ) 108. std::coutRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.