• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Dec 3rd, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. ////////////////////////////////////////////////////////////////////////////////
2. // Faculty of Computing, Universiti Teknologi Malaysia
3. // SCSJ2013- Data Structures and Algorithms
4. // Semester 1, 2018/2019
5. // Assignment 1  - Program 1 Linked List
6. ////////////////////////////////////////////////////////////////////////////////
7.
8. #include<iostream>
9. using namespace std;
10.
11. class Node{
12.     private:
13.         char id;
14.     public:
15.         Node *next;
16.
17.         Node(char anId=0)
18.         { id = anId;
19.           next =NULL;
20.         }
21.
22.         char getId() const
23.         { return id; }
24. };
25.
26.
27. // To print the list of nodes from first to last
28. void print(Node *first,  Node *last)
29. {
30.     Node *node = first;
31.     while (node){
32.         cout << node->getId() << "\t";
33.         node=node->next;
34.     }
35.     cout << endl;
36. }
37.
38.
39. int main()
40. {
41.     Node *first, *last;
42.
43.     first = last = new Node('A');
44.
45.     for (char ch='B'; ch <='G'; ch++){
46.         last->next = new Node(ch);
47.         last = last->next;
48.     }
49.
50.     print(first, last);
51.     cin.get();
52.
53.     Node *node;
54.
55.     // Task 1 : Insert a new node (with the id of 'X') in front of the list
56.     node = new Node('X');
57.     node->next = first;
58.     first = node;
59.
60.
61.
62.     print(first, last);
63.     cin.get();
64.     //-------------------------------------------------
65.
66.
67.     // Task 2 Insert a new node (with the id of 'Y') between node 'C' and node 'D'
68.
69.     //  X--->A--->B--->C--->D--->E--->F--->G--->NULL
70.     Node* current = first;
71.     while (current->next != NULL)     // keep looping through all the linked list; 2nd condition is for making sure you don't go beyond list boundries
72.     {
73.         if(current->getId() == 'C')
74.         {
75.             Node* newnode = new Node('Y');   // creat a new node X
76.             newnode->next = current->next;   // X-->next = C--->next which is D, we connect to preserve the connection, then we break in the next statment
77.             current->next = newnode;         // we now break C--->next from being D to be the newnode we created which is X
78.
79.
80.             /* supposingly here we add break because it's uncesseary to loop anymore. */
81.             break;
82.         }
83.
84.         current = current->next;    // update statment like i++
85.     }
86.
87.
88.
89.     print(first, last);
90.     cin.get();
91.     //-------------------------------------------------
92.
93.
94.     // Task 3 Insert a new node (with the id of 'Z') at the end of the list
95.     current = first;                  // re-intiating current to start at the beggining of the linked list. no need for new pointer.
96.     while (current->next != NULL)     // 2nd condition is for making sure you don't go beyond list boundries
97.     {
98.         current = current->next;      // after we arrive at the end of the linked list, loop will autmatically break;
99.     }                                 // current will be now pointing to the last element in the linked list.
100.
101.     current->next = new Node('Z');    // last element Next ----> our new inserted 'Z';
102.     last = current->next;             // updating the value of last
103.
104.
105.     print(first, last);
106.     cin.get();
107.     //-------------------------------------------------
108.
109.
110.     // Task 4   (Swap first and last elements)
111.
112.     current = first;
113.     while(current->next != last && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
114.     {
115.         current = current->next;
116.     }
117.     // current is now the element before the last.
118.
119.     last->next = first->next;      // last is now connected to the 2nd elemnt in the list
120.     current->next = first;        // element before the last is connected to the new last which is the beggining of the array.
121.     first = last;                 // updating first and last;
122.     last = current->next;         // since current is the element before the last.
123.     last->next = NULL;            // not to forget to make the last pointing to null, otherwise it will be closed(infinite)loop for print
124.
125.
126.     print(first, last);
127.     cin.get();
128.     //-------------------------------------------------
129.
130.
131.     // Task 5 : Swap the positions of the node ‘D’ and ‘E’
132.     // i assume the I already know D and E are going be adjacent !!
133.
134.
135.
136.     current = first;
137.     while(current->next->getId() != 'D' && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
138.     {
139.         current = current->next;
140.     }
141.     // current is now the one before d
142.     Node* temp = current->next->next;      // tmp = the one after D which is E
143.     current->next->next = temp->next;           // D-->next = E-->next;
144.     temp->next = current->next;            // E next is D
145.     current->next = temp;                   // D next is E
146.
147.     print(first, last);
148.     cin.get();
149.     //-------------------------------------------------
150.
151.
152.     // Task 6 : Delete the last node from the list
153.
154.
155.     current=first;
156.     while(current->next != last && current->next != NULL)  // 2nd condition is for making sure you don't go beyond list boundries
157.     {
158.         current = current->next;
159.     }
160.     // current now is poiting on the element befor the last
161.     delete current->next;
162.     current->next = NULL;
163.
164.
165.
166.     print(first, last);
167.     cin.get();
168.     //-------------------------------------------------
169.
170.     // Z       A       B       C       Y       E       D       F       G
171.     // Task 7 : Delete the node ‘C’ from the list
172.     current = first;
173.     Node* temp1;
174.     while(current->next->getId() != 'C' && current->next != NULL) // 2nd condition is for making sure you don't go beyond list boundries
175.     {
176.         current = current->next;
177.     }
178.     // current is now the element just before C
179.
180.     temp1 = current->next;
181.     current->next = current->next->next;  // the one before C point to the thing that C orginally points to
182.     delete temp1;
183.
184.     print(first, last);
185.     cin.get();
186.     //-------------------------------------------------
187.
188.
189.     // Task 8 : Delete the first node from the list
190.
191.
192.     current = first->next;        // make the current to be the 2nd element.
193.     first->next = NULL;          // breaking connection between first node and 2nd node
194.     delete first->next;          // deleting the pointer
195.     first = current;            // putting first at the beggining of the new linked list.
196.
197.
198.
199.     print(first, last);
200.     cin.get();
201.     //-------------------------------------------------
202.
203.
204.
205.
206.     // Find any number from the list (based on input entered by the user)
207.
208.     cout <<"What character position you would like to find?  enter the once character only: ";
209.     char c;           // character input
210.     cin>>c;
211.     current = first;
212.     int currentElementIndex = 1;
213.     while(current->getId() != c && current->next != NULL)  // looping untill you find the character & making sure you don't go beyond list boundries
214.     {
215.         current = current->next;
216.         currentElementIndex++;
217.     }
218.
219.     cout <<"Your Element is the element number \"" << currentElementIndex <<"\" in the list. \n \n";
220.
221.
222.
223.     print(first, last);
224.     cin.get();
225.     //-------------------------------------------------
226. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?