0

I am doing pset 3 tideman.

For this I first implemented mergesort recursively. Then, to adjust it to the problem, I introduced a new part of the pair data structure, margin, and adjusted my mergesort to look at each pair's .margin.

(i had to look ahead at a video on pointers, because I first tried to implement mergesort and kept getting segmentation faults)

However, I don't quite understand how memory allocation works for your own data structs.

If I have data type, say pair as described above, I can create an array of three pairs. When I use the pointer to the first element, I can use +1 on the pointer to access the next memory slot. But somehow this next memory slot contains all three parts of my type pair (it contains the .winner .loser and .margin), when each of these is of type int and I would have thought required their own slot in memory each? Maybe I am misunderstanding how memory is labelled?

pair arr[3];

pair *my_pointer = &arr[0];

printf("%i", (*(my_pointer + 1)).margin); //the second element of arr is of type pair, and its margin is printed

1

The smallest addressable unit of memory is a byte. Even though a byte consists of multiple bits, you can't address them separately.

When you add a number to a pointer, the actual difference in bytes depends on the type of the pointer. Without that automatism, you couldn't use array syntax, as for the compiler the expressions my_pointer[1] and *(my_pointer + 1) are the same. And also 1[my_pointer], because that's interpreted as *(1 + my_pointer).

Since your pointer is of type pair*, the +1 corresponds to advancing by sizeof(pair) bytes. There's nothing special about structs.

You can see that with some short sample code

#import <stdio.h>

int main(void)
{
    char array[] = {0, 1, 2, 3, 4, 5, 6, 7};
    char* ptr1 = array;
    int*  ptr2 = (int*)array;
    printf("%8p %8p\n%8p %8p\n", ptr1, ptr1+1, ptr2, ptr2+1);
}

Output for example:

0x7ffe3b1f1798 0x7ffe3b1f1799
0x7ffe3b1f1798 0x7ffe3b1f179c

As you see, ptr1+1 is 1 byte, ptr2+1 is 4 bytes behind the first element.

BTW, you are not meant to change the definition of pair. Might be incompatible with the checker.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .