Multi dimensional arrays (14)

Administrivia

Practice Web Page - http://www.cs.tau.ac.il/~efif/courses/Programming_Fall_04

Linked list - counting number of items

• Functions that count the number of items in a linked list

  #include <stdio.h> typedef struct item { int value; struct item * next; } Item; int count(Item * head) { int counter = 0; while (head) { counter++; head = head->next; } return counter; } int rcount(Item * head) { if (head == NULL) return 0; return 1 + rcount(head->next); }

• list_count.c

Linked list - melding two linked lists

• A function that melds 2 linked lists

  #include <stdio.h> typedef struct item { int value; struct item * next; } Item; Item * meld(Item * head1,Item * head2) { Item * head1_save = head1; if (head1 == NULL) return head2; if (head2 == NULL) return head1; while (head1->next != NULL) head1 = head1->next; head1->next = head2; return head1_save; }

• ???.c

Multi dimentional arrays

• blah

Multi dimentional arrays - definition

• blah

Multi dimentional arrays - initialization

• blah

  #include <stdio.h> #define ROW 3 #define COLUMN 4 int main() { int array[ROW][COLUMN]= {{1,2,3,4},{5,6,7,8},{9,10,11,12}}; int i, j; for (i = 0; i < ROW; i++) { for (j = 0; j < COLUMN; j++) printf( "%4d", a[i][j]); printf( "\n" ); } }

Multi dimentional arrays - layout in memory

• We treat multi dimensional arrays as an array of multi dimensions
• In memory the layout is an array of a single dimension
  • If the code accesses an allement with square brackets a[x][y], the compiler must know the size of each row (the number of columns).
  • Access a[1][1] - the compiler must know that row 0 contains 3 elements

Multi dimentional arrays - passing as parameters

• A function that accepts a 2-dimensional array and prints it

  #include <stdio.h> void print_array(int a[][COLUMN], int size) { int i, j; for (i = 0; i < size; i++) { for (j = 0; j < COLUMN; j++) printf("%4d", a[i][j]); printf("\n"); } }

• ???.c

Product table

• A function that accepts a 2-dimensional array and fills each element with the product of the row and column indices (shifted by 1)

  #include <stdlib.h> #include <stdio.h>

• ???.c

Multi dimensional strings

• A single dimensional array of strings - each row is a string
• A function that accepts an array of names and a name. It returns true if the name appears in the array, and false otherwise

  #include <stdlib.h> #include <stdio.h>

• ???.c

Review - searching an element in an array

• Binary search

  #include <stdlib.h> #include <stdio.h>

• ???.c