C++programming

* 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 are only permitted to modify sections labelled as "fill in here". Please leave the other sections (e.g., the main

* function and all function protocols) intact.

#include

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;

}

}