Programming Studio #12ECE 190Programming Studio #12• Topics this week:• Linked Data Structures• Lists, Stacks, Queues, Doubly-linked lists, and trees• Double pointers• MP5 AI Distance MappingWhat is a list?• A sequence of data structures (nodes) connected via pointersStudent A Student B Student CStudent DStudent FSample singly-linked list (SLL)A {name = "Joe"next = &B}B {name = "Bob"next = NULL}int main() {student * A = (student*) malloc( sizeof( student ) );A->name = "Joe";student * B = (student*) malloc( sizeof( student ) );B->name = "Bob";B->next = NULL;A->next = B;return 0;}typedef struct student_struct student;struct student_struct{char * name;student * next;} ;What about a doubly-linked list?• Each struct in your list can point both forwardsand backwardsStudent CJaneStudent BBobStudent AJoeSample doubly-linked list (DLL)typedef struct student_struct student;struct student_struct {char * name;student * next;student * prev;};< OR >typedef struct student{char * name;struct student * next;struct student * prev;} student;int main() {student * A = (student*) malloc( sizeof( student ) );A->name = "Joe";student * B = (student*) malloc( sizeof( student ) );B->name = "Bob";student * C = (student*) malloc( sizeof( student ) );C->name = "Jane";A->prev = NULL;A->next = B;B->prev = A;B->next = C;C->prev = B;C->next = NULL;return 0;}Stacks and Queues• Two very similar data structures• Both structures can be implemented with linked lists• Queues are an example of a FIFO (First-In-First-Out) data structure• Stacks are LIFO (Last-In-First-Out)Stacksint pop() {if (head == NULL) {return -1;}stack_item * temp = head;head = head->next;int ret = temp->data;free(temp);return ret;}int push(int data) {stack_item * new = (stack_item*) malloc(sizeof( stack_item ));if (new == NULL){return -1;}new->data = data;new->next = head;head = new;return 0;}typedef struct stack_node stack_item;struct stack_node {int data;stack_item * next;};stack_item * head = NULL;Stacks (cont)int main() {push(2);return 0;}2Stacks (cont)int main() {push(2);push(9);push(4);return 0;}492Stacks (cont)int main() {push(2);push(9);push(4);int four = pop();printf("Pop again %d\n" , pop());return 0;}What gets printed?92Queuesint dequeue() {if (head == NULL) {return -1;}queue_item * temp = head;head = head->next;if (head == NULL){tail = NULL;}int ret = temp->data;free(temp);return ret;}int enqueue(int data) {queue_item * new = (queue_item*) malloc(sizeof( queue_item ));if (new == NULL){return -1;}if (tail != NULL){tail->next = new;}else{head = new;}tail = new;new->next = NULL;new->data = data;return 0;}typedef struct queue_node queue_item;struct queue_node {int data;queue_item * next;};queue_item * head = NULL;queue_item * tail = NULL;Queues (cont)int main() {enqueue(2);return 0;}2H TQueues (cont)int main() {enqueue(2);enqueue(9);enqueue(4);return 0;}294HTQueues (cont)int main() {enqueue(2);enqueue(9);enqueue(4);int two = dequeue();printf("Dequeue again %d\n" , dequeue());return 0;}What gets printed?94HTDouble pointers• Pointers are tricky enough on their own, but to really make things fun, you can have your pointers point to pointers• When this is useful• Dynamic multi-dimensional array allocation• Modifying head and tail pointers for linked listsDouble pointers (cont)int main()/* Examples for double pointer usage */ {int ** double_ptr;int * single_ptr;int point_to_me = 5;single_ptr = &point_to_me;double_ptr = &single_ptr;point_to_me = 10;return 0;}/* Equivalent statements */*single_ptr = 10;**double_ptr = 10;Double pointers with Stackstack_item * head = NULL;int main()/* Examples for double pointer usage */ {push(5);return 0;}First implementationint push(int data) {stack_item * new = (stack_item*)malloc(sizeof(stack_item));if (new == NULL){return -1;}new->data = data;new->next = head;head = new;return 0;}Double pointers with Stack (cont)int main()/* Examples for double pointer usage */{stack_item * head = NULL;push(5, &head);return 0;}Second implementationint push(int data, stack_item ** head_ptr) {stack_item * new = (stack_item*)malloc(sizeof(stack_item));if (new == NULL){return -1;}new->data = data;new->next = *head_ptr;*head_ptr = new;return 0;}Trees• A tree is a specialized linked list where each node can point to multiple children nodes• The head of a tree is often called the "root" and the nodes below it which have no children are commonly referred to as "leaves"Trees (cont)typedef struct tree_node tree;struct tree_node{int data;tree * left;tree * right;};root5410Trees (cont)• Tree traversal• Preorder• Evaluate data on first visit• Inorder• Evaluate data after visitingthe left child• Postorder• Evaluate data after visitingboth childrenroot5410Preorder:Output = 5, 4, 10, 8, 12Inorder:Output = 4, 5, 8, 10, 12PostorderOutput = 4, 8, ??, ??, ??128Trees (cont)Binary search• The tree to the right is a sorted binary tree• Smaller values to the left, larger to the right• This structure allows us to perform powerful searchesroot5410128int search(int value, tree * node)/** Return 1 if value is in tree, * 0 otherwise*/{if (node == NULL){return 0;}else if (value == node->data){return 1;}else if (value < node->data){return search(value, node->left);}else{return search(value, node->right);}}MP5 AI Distance Mapping• Your enemy snake wants food as bad as you do, for MP5, you will need to implement the algorithm it uses to find that food• The process involves filling a grid map with distance values, your enemy snake will go after the nearest foodMP5 AI Distance Mapping (cont)0 1 2 3 4 517 16 15 X X 618 19 14 X X 721 20 13 12 X 822 23 24 11 10 9After 24 recursive calls (Up, Left, Right, Down order)MP5 AI Distance Mapping (cont)After some reduction about #200 1 2 3 4 517 16 15 X X 618 19 14 X X 721 20 13 12 X 822 21 22 11 10 9MP5 AI Distance Mapping (cont)0 1 2 3 4 51 2 3 X X 62 3 4 X X 73 4 5 6 X 84 5 6 7 8 9Fully travelled and adjusted distance mapClosest food is 6 awayMP5 AI Distance Mapping (cont)• Step 1 – Compare current traveling distance to saved distance, if exists, for this tile• If saved distance is shorter or equal, avoid because you will only travel more or equal to the saved distance to get there• Otherwise, save current distance into tile• Step 2 – Attempt to travel away from the cell• Step 3 - ??? That’s up to youWhat is your base