Show the output and answer the questions for the following exercise.
#include<stdio.h> // struct declaration... struct Branch { int value; struct Branch *left; struct Branch *right; }; void main(void) { struct Branch x, y, z, *p = &y; printf("&x = %p, &y = %p, &z = %p, p = %p\n", &x, &y, &z, p); x.value = 100; y.value = 200; z.value = 300; x.left = (struct Branch *) 0; x.right = &z; z.left = NULL; z.right = &y; y.left = &x; y.right = &z; printf("\n&x = %p: x.value = %d, x.left = %p, x.right = %p\n", &x, x.value, x.left, x.right); printf("&y = %p: y.value = %d, y.left = %p, y.right = %p\n", &y, y.value, y.left, y.right); printf("&z = %p: z.value = %d, z.left = %p, z.right = %p\n", &z, z.value, z.left, z.right); } | |
|
How many items each do x, y and z hold? For each item that they hold, how many are pointers? And pointers to what data type? How many items does p hold? It can store addresses to what data type? What is its value? Where are the variables x, y and z stored? Give their addresses. Fill in all the addresses and boxes in the following Figures.
| Based on the struct member variables, each x, y and z hold three items that is value, *left and *right. Two are pointers (*left and *right) of struct Branch data type. p also hold three items and it can store addresses of struct Branch. From the output sample shown below, its value is 0012FF44, same as the address of y. From the output sample shown below &x = 0012FF58, &y = 0012FF44 and &z = 0012FF30. See the following Figure.
|
| |
| |
| |
For the following and the next exercises, add the some code at the end of the code given in exercise 10. Show the output and answer the questions based on the added code.
#include<stdio.h> // struct declaration... struct Branch { int value; struct Branch *left; struct Branch *right; }; void main(void) { struct Branch x, y, z, *p = &y; printf("&x = %p, &y = %p, &z = %p, p = %p\n", &x, &y, &z, p); x.value = 100; y.value = 200; z.value = 300; x.left = (struct Branch *) 0; x.right = &z; z.left = NULL; z.right = &y; y.left = &x; y.right = &z; printf("\n&x = %p: x.value = %d,\nx.left = %p, x.right = %p\n", &x, x.value, x.left, x.right); printf("&y = %p: y.value = %d,\ny.left = %p, y.right = %p\n", &y, y.value, y.left, y.right); printf("&z = %p: z.value = %d,\nz.left = %p, z.right = %p\n\n", &z, z.value, z.left, z.right); printf("&y = %p, y.value = %d \n", &y, y.value); printf("y.left = %p, y.right = %p \n", y.left, y.right); printf("p = %p, (*p).value = %d \n", p, (*p).value); printf("(*p).left = %p, (*p).right = %p\n", (*p).left, (*p).right); } | |
When printing y.value, why was a %d used for the format string? When printing y.left, why was a %p used for the format string? What is the address in p? This is the address of which variable? Can you print p.value? Why do you need an asterisk in front of the p when printing (*p).value? In the three places that this appears, "(*p).", change it to: "p →" (a combination of hyphen and a greater than operator). Use no period or spaces. Is there any difference in the expressions? For instance, try the following code.
printf("p = %p, p→value = %d \n", p, p→value); (*p).left gives the address stored in the left member of which variable? Why does (*p).left give the address stored in the left member of y? The address stored in (*p).left is the address of which variable?
| The %d format string used because value variable is an integer data type. The %p format string used because left variable is a pointer variable of struct Branch data type. Based on the sample output, &p = 0012FF44 and this is the address of y variable. No, p.value cannot be printed because p is a pointer variable. This is because p is a pointer that hold an address instead of the value. By using the asterisk, we mean to print the value. There is no difference. y variable. This is because of the *p = &y. x variable.
|
| |
Now add the following code to the end of your program. Rebuild and show the output for the added code.
p = (*p).left; printf("\np = %p, (*p).value = %d \n", p, (*p).value); printf("(*p).left = %p, (*p).right = %p\n", (*p).left, (*p).right);
Now p has the address of which variable?
| p has the address of x variable.
|
| |
Convert these lines to the notation that uses the arrow (→). Is the result the same?
p = p->left; printf("\np = %p, p->value = %d \n", p, p->value); printf("p->left = %p, p->right = %p\n", p->left, p->right);
| Yes, the result is same. |
| |
Now add the following code at the end of your previous program. Rebuild and show the output for the added code.
p = (*p).right; printf("\np = %p, (*p).value = %d \n", p, (*p).value); printf("(*p).left = %p, (*p).right = %p\n", (*p).left, (*p).right);
Convert these three lines to the arrow notation (->) as done previously and test your code.
p = p->right; printf("\np = %p, p->value = %d\n", p, p->value); printf("p->left = %p, p->right = %p\n", p->left, p->right);
Now the address stored in p is the address of which variable?
| See the following Figure.
The address stored in p is the address of z variable.
|
| |
Now add the following code to the end of your program that you have so far.
p = (*p).right; printf("\np = %p, (*p).value = %d \n", p, (*p).value); printf("(*p).left = %p, (*p).right = %p\n", (*p).left, (*p).right);
Convert these lines to the arrow notation as done previously and test your code. Is there an address or a member name on the left side of the arrow? What about on the right side?
p = p->right; printf("\np = %p, p->value = %d \n", p, p->value); printf("p->left = %p, p->right = %p\n", p->left, p->right);
Now the address that is stored in p is the address of which variable?
| On the left-side is an address and on the right-side is a member name. The address that stored in p is the address of y variable.
|
| |
Can you do any of these assignments? Why or why not?
p = (*p).value; p = &p; y.left = &y; | p = (*p).value; - Cannot. value variable holds an integer instead of an address. p = &p; - Cannot. p already a pointer that holds an address. y.left = &y; - Can. Both side have similar data type, a pointer to an address. |
| |
More Questions And Answers For all questions and their parts, start with the following code definitions. #include<stdio.h> // struct declaration... struct Ball { int Radius; struct Ball *last; struct Ball *next; }; void main(void) { struct Ball x, y, *p5 = &x, *p6 = &y; int i = 0, m[5] = {3, 6, 9, 12, 15}, *p1, *p3, *q[5]; double j, a[5] = {20.0, 30.5, 40.3, 50.3, 60.4}, *p2 = a; // ... // ... // ... }
| |
| |
Show the contents of the variables that have changed after executing each of the following codes.
p1 = &i;
*p1 = 8; p1 = &m[0];
p1 = p1 + 2; *p1 = *p1 + 8; p1 = &i;
p3 = m; *(p3 + 1) = *p3 + *p1; p1 = m + 2;
p3 = p1 + 1; i = *p1 + *p3; for(i = 0; i <= 4; ++i)
q[i] = m + i; for(i = 0; i <= 4; ++i) *(a + i) = *q[i] + a[i]; for(i = 4; i >= 0; --i)
{ q[i] = &m[4 – i]; *p2 = *q[i] + *(a + i); }
| We add some code so that the output and the changed variables can be seen. p1 = &i; printf("p1 = %p, *p1 = %d\n",p1, *p1); *p1 = 8; printf("p1 = %p, *p1 = %d\n",p1, *p1); p1 = &m[0]; printf("p1 = %p\n",p1); p1 = p1 + 2; printf("p1 = %p\n",p1); *p1 = *p1 + 8; printf("*p1 = %d\n",*p1); p1 = &i; printf("p1 = %p\n",p1); p3 = m; printf("p3 = %p\n",p3); *(p3 + 1) = *p3 + *p1; printf("*p1 = %d, p3 = %p, *p3 = %d\n",*p1,p3, *p3); p1 = m + 2; printf("p1 = %p, m = %p\n",p1, m); p3 = p1 + 1; printf("p3 = %p, p1 = %p\n",p3, p1); i = *p1 + *p3; printf("i = %d, *p1 = %d, *p3 = %d\n",i,*p1, *p3); for(i = 0; i <= 4; ++i) { q[i] = m + i; printf("m = %p, i = %d, q[%d] = %p\n", m, i, i, q[i]); } printf("\n"); for(i = 0; i <= 4; ++i) { *(a + i) = *q[i] + a[i]; printf("*q[%d] = %d, a[%d] = %.2f, a = %p, i = %d\n", i, *q[i],i,a[i],a, i); } for(i = 4; i >= 0; --i) { q[i]=&m[4-i]; printf("i = %d, &m = %p, &m[4-%d] = %p\n", i, &m, i, &m[4-i]); *p2 = *q[i] + *(a + i); printf("a = %p, i = %d, *(a+%d) = %.2f, *q[%d] = %d, *p2=%.2f\n", a, i, i, *(a+i), i, *q[i], *p2); } |
| |
Which of the following are valid?
last = next; x = y; p5 = p6; x = 10; x.last = 10; x.Radius = 10; p5.Radius = 10; p5 -> Radius = 10; (*x).Radius = 10; *(x.Radius) = 10; *(x.last) = &y; (*x).last = &y; (*p5).last = &y; *(p5.last) = &y; p5 -> last = &y; *p5 = y; p5 -> last = NULL; p5 -> next = 10;
| last = next; - Invalid, we cannot directly access the member variable. x = y; p5 = p6; x = 10; - Invalid, x is a variable of type struct Ball and should be written such as x.Radius = 10 or on the right-side must be struct Ball type such as x = y x.last = 10; - Invalid, last is a pointer variable. On the right-side must be a struct Ball type instead of an integer. x.Radius = 10; p5.Radius = 10; - Invalid, p5 is a pointer variable of struct Ball type so must be written as (*p5).Radius = 10 or p5->Radius = 10. p5 -> Radius = 10; (*x).Radius = 10; - Invalid, Radius is an integer so must be something like x.Radius = 10 *(x.Radius) = 10; - Invalid, Radius is an integer so must be something like x.Radius = 10 *(x.last) = &y; - Invalid, supposed to be written as x.last = &y; (*x).last = &y; - Invalid, supposed to be written as x.last = &y; (*p5).last = &y; *(p5.last) = &y; - Invalid, supposed to be written as (*p5).last = &y; or p5->last = &y; p5 -> last = &y; *p5 = y; p5 -> last = NULL; p5 -> next = 10; - Invalid, p5 is a pointer variable of struct Ball type and last is a pointer variable so on the right-side it must be an address |
| |
Do A ProgrammingWrite a function called AddTwo(). It will receive three pointers to floats. It will add the numbers pointed to by the first two floats and store their sum in the location pointed to by the third pointer. In main(), define j, k and m. Scan in j and k, send their addresses to AddTwo() and have main() print the address of m and its value that is in it from AddTwo().
| #include <stdio.h> float * AddTwo(float *, float *, float *); void main() { // we need to initialize pointer variables, // giving some dummy values float p =1.2f, q=2.2f, r=3.3f, *j=&p, *k=&q, *m=&r, *n; printf("Enter two floats: \n"); scanf_s("%f%f", j,k,sizeof(float*),sizeof(float*)); n = AddTwo(j,k,m); printf("The sum of %.2f and %.2f is %.2f\nwhich stored at %p.\n", *j, *k, *n, n); } float * AddTwo(float * pointTo_j, float * pointTo_k, float * pointTo_m) { *pointTo_m = *pointTo_j + *pointTo_k; printf("The sum is %.2f\n", *pointTo_m); return pointTo_m; } |
| |
Define an integer array called a[10]. Initialize it to some values. Then assign the address of the slot whose index is 4 to an integer pointer called p. Print the contents of the array and the address of each slot using the namea but no brackets. Now do the same using the name p.
| #include <stdio.h> void main() { int i, a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9 , 10}, *p; p = &a[3]; for(i=0;i<=9;i++) { printf("a[%d] = %d at %p\n", i, a[i], a + i); } printf("\n"); for(i=0;i<=9;i++) { printf("a[%d] = %d at %p\n", i, a[i], p - 3 + i); } } |
| |
More DrillsThe following diagram shows four variables and the addresses where they are stored. After the execution of these statements, show the values of the locations that are assigned.
int i = 43, j; int *p1, *p2; p1 = &i; p2 = p1; p2 = p2 + 1; | p1 gets the address of i, p2 gets p1 and p2 then gets incremented by one storage unit. p1 and p2 are pointers to integers. |
| |
The asterisk (*) is the indirection operator. *p1 refers to the location in memory that has its address in p1. Or, in other words, the location whose address is given in p1. What will the following code print? Notice that p1 uses a %p and *p1 uses a %d. Differentiate between the memory address and the actual value stored at the address.
printf("p1 = %p, *p1 = %d\n", p1, *p1); | p1 simply prints the address in it. However *p1 prints the value stored at a location pointed by p1. *p1 prints 43 because the address in p1, namely FF00, has 43 stored in it. |
| |
Show the new contents of the locations in the diagram after the following code is executed.
*p2 = *p1; j = j + 1;
| The contents that p1 points to are stored in the location that p2 points to. Then 1 is added to j. |
| |
After the following code execution, show the contents of the locations that will be changed.
*p2 = *(p1 + 1) - 2; *p1 = *p1 - 2;
| 1 is added to p1, which is the address of FF02. From the contents of the location pointed to by FF02, 2 is subtracted, making j equal to 42. p1 remains the same. Then the contents pointed to by p1, which is actually i, has a 2 subtracted from it. now the current value of i is 41. |
| |
Continue from the previous drill, for the following code, show the values for x and y in the diagram. From main(),ShakeIt() is called. Show its effects in memory. Lastly, what is printed?
ShakeIt(p1, p2); printf("*p1 = %d, *p2 = %d\n", *p1, *p2); void ShakeIt(int *x, int *y) { *x = 0; *y = 0; }
| The values for x and y are FF00 and FF02 respectively. *x is actually i and *y is actually j. These are set to zero in ShakeIt(). The two zeroes, the values of i and j are printed. |
| |
For the following code, show the printout. You may try to complete the code by adding the main() etc.
char x[10] = "Inside", y[10] = "and out"; ShakeIt(x, y); printf("%s %s\n", x, y); void ShakeIt(char *a, char *b) { *(a + 1) = 'M'; *b = 'u'; }
| #include <stdio.h> void ShakeIt(char *, char *); void main() { char x[10] = "Inside", y[10] = "and out"; ShakeIt(x, y); printf("%s %s\n", x, y); } void ShakeIt(char *a, char *b) { *(a + 1) = 'M'; *b = 'u'; } Array names are actually array addresses. hence, the pointer a actually has its address at the beginning of x[ ] . This is also the case with y[ ]. When ShakeIt() changes the contents of the location pointed to by a and b, that changes the array x[ ] and y[ ]. |
| |
Are there any errors in the following code? If not, show the printout.
void ShakeIt(char *, char *); void main(void) { char x[10] = "Inside", y[10] = "and out"; ShakeIt(&x[0], &y[0]); printf("%s %s\n", x, y); } void ShakeIt(char a[ ], char b[ ]) { a[1] ='M'; b[0] ='u'; }
| No errors exist. Address can be passed to an array and the pointers can be used as arrays. The output is the same. |
| |
For the following questions, take a[ ] to be an array and specify which are true.
a == &a[0] a + 1 == &a[1] *a == a[0] *(a + 1) == a[1]
| a == &a[0] - True a + 1 == &a[1] - True *a == a[0] - True *(a + 1) == a[1] - True
All are true. a is the address of &a[0]. *a accesses what is stored in a[0], as does a[0]. |
| |
Here we have an array of pointers. Show the values of the memory locations in the provided diagram.
char x[ ] = "Lawdy", y[ ] = "Mamma", *t[3]; t[0] = x; t[1] = y;
| |
| |
For the following scanf_s()/scanf(), "Hey" is read in. Show the contents of the memory locations after the execution of the given code.
t[2] = t[1]; strcpy_s(t[2], 10, t[0]); scanf_s("%s", t[0], 10);
| |
| |
In the following structure, Rev andFwd are pointers to typestruct Node. Draw a diagram of each of the four variables. Which have three members and which have only one?
struct Node { int Qty; struct Node *Rev; struct Node *Fwd; }; struct Node x, y, *Head, *Tail;
| x and y have three members but Head and Tail have one only (an address). |
| |
Which of the following statements are valid? (True or false).
Head = &x; x = &Head; Head = Tail; Head = &Tail; x = &y; x.Rev = 30; x.Rev = &Head; x.Rev = &y; x.Rev = &x; x.Qty = 30; x.Qty = &y; x = y;
| Head = &x; - Valid x = &Head;- Not Valid Head = Tail; - Valid Head = &Tail; - Not Valid x = &y;- Not Valid x.Rev = 30; - Not Valid x.Rev = &Head; - Not Valid x.Rev = &y; - Valid x.Rev = &x; - Valid x.Qty = 30; - Valid x.Qty = &y; - Not Valid x = y;- Valid Head can store only an address of a struct Node, so (a) and (c) are valid and (d) is not valid. x.Rev also can store only an address of a struct Node, so (h) and (i) are valid but (f) and (g) are not valid. In (l), we assign one entire structure to another with similar data type (struct Node) and it is valid. |
| |
In the diagram for solution 11 (shown below), fill in the values that the following code will assign.
Head = &x; x.Fwd = &y; // a NULL means that the address doesn't point to any object // or pointing to address 0. y.Fwd = NULL; x.Qty = 500; y.Qty = 800; | The address of x, which is A100, is stored in Head. The address of y, which is A200, is stored in x, Fwd and so on. |
| |
Write the statements to set up the following pointers: HaveTail point to y, have the Rev member ofy point to x, and have the Rev member ofx point to nothing.
| Tail = &y; y.Rev = &x; x.Rev = NULL; |
| |
One way to access the Qty member ofx is to state "x.Qty". Another way of doing that now is to state "(*Head).Qty".*Head will bring us to the location of A100 or x. And (*Head).Qty will bring us to theQty member. A more common way of coding this is to state: "Head -> Qty". Give three ways to access the Fwd member of x.
| x.Fwd (*Head).Fwd Head->Fwd. Could also be written as y.Rev->Fwd
|
| |
Try writing the loop that starts with a pointerp, which is initialized toHead and then traverses the chain by following the Fwd pointers until it becomes NULL. Have the loop simply write out the values ofp and the Qty members of each node as it traverses the chain. To advance the pointerp to the next link,p would have to be set equal to(*p).Fwd. Here is how your printout may look.
A100 500 A200 800
| for(p = Head; p!=NULL; p = p->Fwd) printf("%p %d\n", p, p->Qty); |
| |
Now try reversing the traversal, starting p with Tail and following theRev pointers.
| for(p = Tail; p != NULL; p = p->Rev) printf("%p %d\n", p, p->Qty); |
| |
Usingmalloc(), we have created a new node that has no name, like x and y, but it has an address and it is stored in p. Let us pretend that the address stored in p is B100. How would you write the code so that this new node is placed betweenx and y. That is, x andy should point to the new node. Firstly, show the values in the diagram shown below that need to be changed.
| |
|
There should be four addresses assigned or changed in the previous diagram. Give the four statements that will do that. Does the order of these statements matter? Do not use the pointers Head or Tail.
| p->Rev = x.Fwd; p-> Fwd = y.Rev; x.Fwd = p; y.Rev = p;
The first of the last two statements can be switched. However, the first two statements should come first. The Fwd andRev members should be used first before new pointers are copied in them. |
| |
Now, do the same as above except do not use x or y. Instead, useHead and Tail. Let us also place a quantity, Qty of 600 in the new node.
| p->Rev = Head->Fwd; p->Fwd = Tail->Rev; Head->Fwd = p; Tail->Rev = p; p->Qty = 600; |
| |
We will add a new node whose address is in pNew. Its quantity is 700 and we are to add it in the list. To start, first write the for loop that will start p at Head and make it follow theFwd pointers until it finds a NULL. That is, p should followA100, B100 and A200 where the NULL is found. Also fill in the diagram.
| p = Head; for( ; p != NULL; p = p->Fwd) |
| |
Now add an if statement to this loop that will break out of it when the quantity pointed to byp is greater than the quantity pointed to by pNew. In this example, the loop will break out when p becomesA200. That is, whenp is A200 the 800 pointed to byp is greater than the700 pointed to bypNew.
| p = Head; for( ; p != NULL; p = p->Fwd) if(p->Qty > pNew->Qty) break; |
| |
Since we know the Rev pointer from p, assign the address of the previous node from p into a pointer called pLast. That is, pLast should now be set to B100 after the loop. Then using pLast and p, change and assign the needed pointers so that the new node is linked between B100 and A200 in both directions. Also fill in the diagram for the changed and new address or/and data.
| p = Head; for( ; p != NULL; p = p->Fwd) if(p->Qty > pNew->Qty) break; pLast = p->Rev; pNew->Fwd = p; pNew->Rev = pLast; p->Rev = pNew; pLast->Fwd = pNew; |
| |
Now assume that our node didn’t have the Rev pointers. Rewrite the code so that the pointerpLast follows one node behind p inside the loop. When we need to link up the pointers, we will know where the previous node is. Your new code should make no reference toRev pointers because now they are not needed.
| p = Head; for( ; p != NULL; p = p->Fwd) if(p->Qty > pNew->Qty) break; else pLast = p; pNew->Fwd = p; pLast->Fwd = pNew; |
| |
What changes are needed in the provided code of the drill 24 solution to accommodate each of the following special conditions?
p = Head; for( ; p != NULL; p = p->Fwd) if(p->Qty > pNew->Qty) break; else pLast = p; pNew -> Fwd = p; pLast -> Fwd = pNew; ... The new quantity is greater than the quantity in the last node of the list. The new quantity is greater than the quantity in the first node of the list. The linked list is empty; that is, to begin with,Head is NULL.
| No changes are needed for part (a). Answers for (b) and (c) are as follows: p = Head; for( ; p != NULL; p = p->Fwd) if(p->Qty > pNew->Qty) break; else pLast = p; pNew -> Fwd = p; if(p == Head) Head = pNew; else pLast->Fwd = pNew; |
| |
In C++ what standard library that will be used for linked list and other related data manipulation of the C++ constructs?
| Standard Template Library (STL). |
| |
Which of the following are advantages of a double linked list and which are advantageous of a single linked list?
Take less memory space. Easier to use if you are dumped in the middle of the linked list and need to go back one node. Easier to traverse in both directions. Less pointer maintenance.
| Single. Double. Double. Single.
|