CST8234 C Programming PDF

CST8234 – C Programming Self-Referencing Structures & Introduction to Linked List  Self-Referencing Structs The previous lecture discussed struct vs program namespaces, and how the format of struct naming allows it to be referenced with a struct...

CST8234 – C Programming Self-Referencing Structures & Introduction to Linked List  Self-Referencing Structs The previous lecture discussed struct vs program namespaces, and how the format of struct naming allows it to be referenced with a struct typedef struct House {  adds ‘House’ to struct namespace char *strStreet; struct House *pNeighbour;  uses struct namespace } House;  adds ‘House’ to program namespace House housesOnStreet[NUM_HOUSES]; 2  Initializing We can now initialize our list of houses, so that each house points to its next door neighbour for ( i = 0; i < NUM_HOUSES-1; i++ ) housesOnStreet[i].pNeighbour = &housesOnStreet[i+1]; housesOnStreet[NUM_HOUSES-1].pNeighbour = null;  last is null The last house on the street has no neighbour, so we assign its neighbour to be NULL 3  How it Looks in Memory Here’s a possible layout for our housesOnStreet Address Value house.strStreet 0x01001000 “2 Elm Street”.pNeighbour 0x01001004 0x01001008 house.strStreet 0x01001008 “4 Elm Street”.pNeighbour 0x0100100c 0x01001010 house.strStreet 0x01001010 “6 Elm Street”.pNeighbour 0x01001014 0x01001018 house.strStreet 0x01001018 “8 Elm Street”.pNeighbour 0x0100101c NULL 4  Sample Application Let’s say we want to print out the street addresses of all the houses We can do this by indexing into the array int i = 0; for ( i = 0; i < NUM_HOUSES-1; i++ ) printf( “address = %s\n”, housesOnStreet[i].strStreet); typedef struct House { char *strStreet; struct House *pNeighbour; } House; House housesOnStreet[NUM_HOUSES]; 5  Sample Application Let’s say we want to print out the street addresses of all the houses We can do by incrementing a pointer House pHouse = &housesOnStreet; while ( ) printf( “address = %s\n”, (pHouse++)->strStreet); typedef struct House { char *strStreet; struct House *pNeighbour; } House; House housesOnStreet[NUM_HOUSES]; 6  Sample Application Let’s say we want to print out the street addresses of all the houses Or… we can make use of our new “pNeighbour” member House pHouse = &housesOnStreet; while ( pHouse != null ){ printf( “address = %s\n”, pHouse->strStreet); pHouse = pHouse->pNeighbour; } typedef struct House { char *strStreet; struct House *pNeighbour; } House; House housesOnStreet[NUM_HOUSES]; 7  Why Not Just Use Arrays? Using array indexing (e.g., housesOnStreet[i]) or pointer incrementing (e.g., pHouse++) are both very simple! Except… Have to know the start of array, in order to use an index Sometimes you just have a pointer to a house, without knowing where it sits within the array Have to know when to end the iteration when using a pointer Remember, C arrays have no built-in knowledge of their own length! All the house objects have to be in a contiguous block of memory (i.e., an array) What happens if we are dynamically creating our ‘House’ structs as we need them, so they are scattered all over the heap? 8  How it Looks in Memory Here’s a possible layout for our housesOnStreet Address Value.strStreet 0x01001000 “4 Elm Street”.pNeighbour 0x01001004 0x01001008.strStreet 0x01001008 “6 Elm Street”.pNeighbour 0x0100100c 0x0ca81000 : pFirstHouse.strStreet 0x03301000 “2 Elm Street”.pNeighbour 0x03301004 0x01001000 :.strStreet 0x0ca81000 “8 Elm Street”.pNeighbour 0x0ca81004 NULL 9  Deletion If we ever need to destroy our neighbour, we can simply skip over it House pDoomedHouse = pHouse->pNeighbour; pHouse->pNeighbour = pDoomedHouse->pNeighbour; pDoomedHouse->pNeighbour = NULL;  no longer in the list We have now shrunk the size of the list by one… with very little effort In contrast, to splice an item out of the middle of an array House pDoomedHouse = pHouses[iDoomed]; while ( iDoomed < n-1 ) pHouses[iDoomed] = pHouses[++iDoomed]; pHouses = realloc( pHouses, (--n) * sizeof( House * ) ); Again, we have to do a lot of copying to shift items up AND we have to realloc (which does even more copying) AND we have to make sure we update the number of items 10  Splitting a list Frequently, you may want to divide a list into two halves… Easy with a list… House *pEndFirstList= getHouseByIndex( getHouseCount()/2 ); House *pSecondList = EndFirstList->pNeighbour; pEndFirstList->pNeighbour = NULL; With arrays, this requires Alloc’ing space for the second list Copying over all the items Reallocing the first list Updating the new size of the first list Recording the size of the second list 11  Turning into a Circular Buffer You can simply set the neighbour of the last house to be the first house pLastHouse->pNeighbour = pFirstHouse; Now you can merrily iterate forever, over the fixed number of houses, without having a specific beginning or end pHouse = pHouse->pNeighbour With an array, you could accomplish the same thing with iHouse = (++iHouse)%n; But you still need to know the start of the array, and know the size 12  Linked Lists Everything discussed so far is essentially describing a “linked list”, and we usually talk about “Nodes” What is a linked list? A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list. 13