CST8234 C Programming Week 10 PDF

CST8234 C Programming Spring 2023 Week 10 © 2023 - Copyright George Kriger and other authors as indicated. Agenda o struct – more details o Self-referential Structures simple Linked List o Quiz #3 2 struct – more details o permitted operations...

CST8234 C Programming Spring 2023 Week 10 © 2023 - Copyright George Kriger and other authors as indicated. Agenda o struct – more details o Self-referential Structures simple Linked List o Quiz #3 2 struct – more details o permitted operations initializing a struct variable as part of definition accessing its members with. or -> assignment both variables must be same struct type for pointers, only addresses are copied taking the address of a struct variable sizeof operator on a struct variable or type 3 struct – more details o operations not permitted: can not use relational operators to compare 2 variables of same struct type can compare members of struct (if primitive types) struct type can not contain struct variable of same type can nest different types, but order of declarations matters can nest pointer to struct of same type a struct type that contains a pointer to same struct type is called a self-referential structure 4 Intro to Linked Lists int a, *pa; … a a a a … a pa=a; pa o consider an array we can access an array via its index which can be viewed as the offset from the first element since it’s also contiguous, we can use a pointer and increment it to access each element the location of the next element is implicit it can be derived from the current location o a linked list uses non-contiguous memory So the location of the “next” element must be explicit typically via a pointer to the “next” element. Intro to Linked Lists – continued data link o linked list is made up of “nodes” each contains 1 or more data elements (the “payload”) and a “link” (a pointer containing the explicit location of the “next” node o the nodes are joined via their “links” the final link is given the NULL value the first link is often given it own pointer, since it is accessed often during list operations  Linked Lists – pointer implementation struct Node { int data; struct Node* next; }; o linked list nodes are typically C structures and link is a pointer to a struct of same type o to find the “next” node we use the link e.g. temp_ptr->next to move from the current node to the “next” node, we use the link and update the pointer e.g. temp_ptr=temp_ptr->next; o the last node has a NULL link while(temp_ptr != NULL) { … traversing a temp_ptr=temp_ptr->next; linked list }  Linked Lists – an example simple LL o to add to the front of the list start with a NULL list Front create a node fill in the data make link of new node point to temp_ptr the first node temp_ptr make new node the first node Front o Note: last data entered is now the first node ! temp_ptr Front  Simple LL – continued o to add to the end of the list allocate a new node and fill in the data, set its link to NULL N traverse the list to find the last node Front set link of last node to point to new node p N  Simple LL – continued o to delete the last node set 2 pointers to beginning of the list Front Cur Prev  Simple LL – continued o to delete the last node move pointers to the next node, but one always “lags” the other Front Cur Prev Simple LL – continued keep moving until Cur is at the last node Front Prev Cur set link of the Prev pointer to NULL Front Prev Cur see example Linked Lists - continued o other operations find node containing data with specific value insert & delete in the middle of list find node and then delete or insert after o code must handle special cases empty list list with only one node operations on node at beginning or end 13 Next week o look at variations on simple linked list o e.g. "dummy node" is an additional node placed at the front of the LL doesn't store any data (i.e. no "payload") never deleted. o programming challenge code a simple LL with a dummy node why use a dummy node? 14 Credits: o George Kriger 15