Homework Soursec Computational Complexity filling in the following three
c++ Computational Complexity
/* filling in the
* following three functions:
*
* 1) void disp(Node* head)
* Given a head pointer to a list, display the list using cout.
* If the list is empty, you should output \"HEAD->NULL\" (without the enclosing \").
* If the list contains one node whose data value is 3, you should output \"HEAD->3->NULL\".
* If the list contains three nodes and the data values are 1, 2, and 3, respectively, then you should output
* \"HEAD->1->2->3->NULL\"
*
* 2) Node* add(Node* head, int data)
* Given the old head pointer to a list, create a new node using the value of data, and add the new node to the front of
* the list. Return the new head pointer.
* Example: If the original list is \"HEAD->1->2->NULL\", then after adding 5, it should become \"HEAD->5->1->2->NULL\". The
* return value should be the address of node 5.
*
* 3) void magic(Node* p1, Node* p2)
* p1 and p2 each points to a node from a same list. p1 may point to a later node than p2. Your task is to calculate how
* many nodes are between p1 and p2. If there are k nodes in between (excluding nodes pointed to by p1 and p2), then the
* result is k (k could be 0). Replace the data fields of all nodes between p1 and p2 by k.
* Example: The original list is \"HEAD->1->7->5->0->3->NULL\". p1 points to node 1 (the node with value 1), p2 points to
* node 0. There are two nodes in between p1 and p2. These two nodes\' data fields need to be replaced by k=2. The
* resulting list should be \"HEAD->1->2->2->0->3->NULL\".
*
* You should modify sections labelled as \"fill in here\". Please leave the other sections (e.g., the main
* function and all function protocols) intact.
*/
#include<iostream>
using namespace std;
struct Node {
int data;
Node* link;
};
void disp(Node* head) {
// fill in here
}
Node* add(Node* head, int data) {
// fill in here
}
void magic(Node* p1, Node* p2) {
// fill in here
}
main() {
Node* head = NULL;
Node *p4, *p7;
for(int i = 0; i < 10; i++) {
head = add(head, i);
if (i==4) p4 = head;
if (i==7) p7 = head;
}
// at this point, we have created the following list: HEAD->9->8->7->6->5->4->3->2->1->0->NULL
// p4 now points to node 4 (the node containing 4); p7 now points to node 7 (the node containing 7)
magic(p4, p7);
disp(head);
// between p4 and p7, there are k=2 nodes, and these two nodes\' values will be replaced by k=2
// the output should be: HEAD->9->8->7->2->2->4->3->2->1->0->NULL
// housekeeping (free all nodes)
Node* tmp;
while (head) {
tmp = head;
head = head->link;
delete tmp;
}
}
Comments
Expert Answer
c++ Computational Complexity
/* Your task is to fill in the
* following three functions:
*
* 1) void disp(Node* head)
* Given a head pointer to a list, display the list using cout.
* If the list is empty, you should output \"HEAD->NULL\" (without the enclosing \").
* If the list contains one node whose data value is 3, you should output \"HEAD->3->NULL\".
* If the list contains three nodes and the data values are 1, 2, and 3, respectively, then you should output
* \"HEAD->1->2->3->NULL\"
*
* 2) Node* add(Node* head, int data)
* Given the old head pointer to a list, create a new node using the value of data, and add the new node to the front of
* the list. Return the new head pointer.
* Example: If the original list is \"HEAD->1->2->NULL\", then after adding 5, it should become \"HEAD->5->1->2->NULL\". The
* return value should be the address of node 5.
*
* 3) void magic(Node* p1, Node* p2)
* p1 and p2 each points to a node from a same list. p1 may point to a later node than p2. Your task is to calculate how
* many nodes are between p1 and p2. If there are k nodes in between (excluding nodes pointed to by p1 and p2), then the
* result is k (k could be 0). Replace the data fields of all nodes between p1 and p2 by k.
* Example: The original list is \"HEAD->1->7->5->0->3->NULL\". p1 points to node 1 (the node with value 1), p2 points to
* node 0. There are two nodes in between p1 and p2. These two nodes\' data fields need to be replaced by k=2. The
* resulting list should be \"HEAD->1->2->2->0->3->NULL\".
*
* You should modify sections labelled as \"fill in here\". Please leave the other sections (e.g., the main
* function and all function protocols) intact.
*/
#include<iostream>
using namespace std;
struct Node {
int data;
Node* link;
};
void disp(Node* head) {
// fill in here
}
Node* add(Node* head, int data) {
// fill in here
}
void magic(Node* p1, Node* p2) {
// fill in here
}
main() {
Node* head = NULL;
Node *p4, *p7;
for(int i = 0; i < 10; i++) {
head = add(head, i);
if (i==4) p4 = head;
if (i==7) p7 = head;
}
// at this point, we have created the following list: HEAD->9->8->7->6->5->4->3->2->1->0->NULL
// p4 now points to node 4 (the node containing 4); p7 now points to node 7 (the node containing 7)
magic(p4, p7);
disp(head);
// between p4 and p7, there are k=2 nodes, and these two nodes\' values will be replaced by k=2
// the output should be: HEAD->9->8->7->2->2->4->3->2->1->0->NULL
// housekeeping (free all nodes)
Node* tmp;
while (head) {
tmp = head;
head = head->link;
delete tmp;
}
}
Solution
#include<iostream>
using namespace std;
struct Node {
int data;
Node* link;
};
void disp(Node* head) {
if(head==NULL)
{
cout<<\"head->NULL\";
return;
}
cout<<\"head->\";
while(head!=NULL)
{
cout<<head->data;
cout<<\"->\";
head=head->link;
}
cout<<\"NULL\";
// fill in here
}
Node* add(Node* head, int data) {
Node* tmp = new Node();
tmp -> data = data;
tmp -> link = head;
return tmp;
// fill in here
}
void magic(Node* p1, Node* p2) {
int k=0,flag=1;
Node* temp1=p1;
Node* temp2=p2;
while(p1!=NULL)
{
if(p1!=p2)
{
p1=p1->link;
k++;
}
else if(p1==p2) break;
}
if(p1== NULL)
{
k=0;flag=1;
p1=temp1;
while(p2!=NULL)
{
if(p1!=p2)
{
p2=p2->link;
k++;
}
else if(p1==p2) break;
}
flag=2;
}
else
p1=temp1;
if(flag==1)
{
while(p1!=p2)
{
p1=p1->link;
p1->data=k;
}
}
else if(flag==2)
{
p2=temp2;
while(p1!=p2)
{
p2=p2->link;
p2->data=k;
}
}
}
main() {
Node* head = NULL;
Node *p4, *p7;
for(int i = 0; i < 10; i++) {
head = add(head, i);
if (i==4) p4 = head;
if (i==7) p7 = head;
}
// at this point, we have created the following list: HEAD->9->8->7->6->5->4->3->2->1->0->NULL
// p4 now points to node 4 (the node containing 4); p7 now points to node 7 (the node containing 7)
magic(p4, p7);
disp(head);
// between p4 and p7, there are k=2 nodes, and these two nodes\' values will be replaced by k=2
// the output should be: HEAD->9->8->7->2->2->4->3->2->1->0->NULL
// housekeeping (free all nodes)
Node* tmp;
while (head) {
tmp = head;
head = head->link;
delete tmp;
}
}
