CHAPTER 9
=========

- combining heterogeneous elements in one package.

struct declaration, I
---------------------

struct card {
    int pips;
    char suit;
};

struct card c1, c2;

~~~~~~~~~~~~~~~~~~~~~

struct decleration, II
----------------------

struct card {
    int pips;
    char suit;
} c1, c2;


c1.pips = 3;
c1.suit = 's';

c2 = c1;

~~~~~~~~~~~~~~~~~~~~~

struct decleration, III
-----------------------

typedef struct card card;

card c3, c4, c5;

====================================

yet another struct type definition
----------------------------------

typedef struct{
	float re;
	float im;
} complex;

complex a, b, c[100];

====================================

pointer member, access review
-----------------------------

struct student {
   char   *last_name;
   int    student_id;
   char   grade;
};


struct student tmp, *p = &tmp;

tmp.grade = 'A';
tmp.last_name = "Katz";
tmp.student_id = 9100017;

------------------------------------

expression              equivalent expression    value

tmp.grade               p->grade                A

tmp.last_name           p->last_name             Katz

(*p).student_id         p->student_id            9100017

*p -> last_name + 1     (*(p -> last_name))+1    L

*(p -> last_name + 2)   (p -> last_name)[2]      t

====================================

Operator precedence and associativity, a final look
---------------------------------------------------

	 Operators                           Associativity
-------------------------------------------------------------
() [] . -> ++(postfix) --(postfix)           left to right
-------------------------------------------------------------
+(unary) -(unary) ++(prefix) --(prefix) !    right to left
sizeof(type) &(address) *(dereference) ~
-------------------------------------------------------------
*  /  %                                      left to right
-------------------------------------------------------------
+  -                                         left to right
-------------------------------------------------------------
<< >>                                        left to right
-------------------------------------------------------------
<  <=  >  >=                                 left to right
-------------------------------------------------------------
== !=                                        left to right
-------------------------------------------------------------
&                                            left to right
-------------------------------------------------------------
^                                            left to right
-------------------------------------------------------------
|                                            left to right
-------------------------------------------------------------
&&                                           left to right
-------------------------------------------------------------
||                                           left to right
-------------------------------------------------------------
?:                                           right to left
-------------------------------------------------------------
=  +=  -=  *=  /=  &= >>= etc                right to left
-------------------------------------------------------------
,(comma operator)                            left to right
-------------------------------------------------------------

====================================

struct members in struct
------------------------

- if we specify a pointer, its size is known so no need to define the strcut.

struct dept {
   char   dept_name[25];
   int    dept_no;
};

typedef struct {
   char                 name[25];
   int                  employee_id;
   struct dept          department; /* needs to be defined earlier */
   struct home_address  *a_ptr;    /* can be defined later */
   double               salary;
   ...
} employee_data;

====================================

passing struct to a function, I
-------------------------------

empolyee_data update (empolyee_data e)
{
   .....
   prinf("Input the department number: ");
   scanf("%d", &n);
   e.department.dept_no = n;
   .....
   return e;
}

/* usage */

   employee_data   e;
   e = update(e);

~~~~~~~~~~~~~~~~~~~~

- no strcuture copying is necessary

passing struct to a function, II
--------------------------------

void update (empolyee_data *p)
{
   .....
   prinf("Input the department number: ");
   scanf("%d", &n);
   p->department.dept_no = n;
   .....
}

/* usage */

empolyee_data e;
update(&e);

====================================

struct initialization
---------------------

- similar to arrays. zero for all uninitialized members.

card   c = {13, 'h'};	/* the king of hearts */


complex a[3][3] = {
   {{1.0, -0.1}, {2.0, 0.2}, {3.0, 0.3}},
   {{4.0, -0.4}, {5.0, 0.2}, {6.0, 0.6}},
};  /* a[2][] is assigned zeroes */


struct fruit frt = {"plum", 150};

struct home_address{
  char *street;
  char *city_and_state;
  long zip_code;
  } address = {"87 West Street", "Aspen, Colorado", 80526};

/* initialize all members to 0 */
struct home_address  previous_adress = {0};

====================================


CHAPTER 10
==========

Linked list
===========

- recursive vs. iterative implementation

// list.h

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

typedef   char   DATA;           /* will use char in examples */

struct linked_list {
   DATA                 d;
   struct linked_list   *next;
};

typedef   struct linked_list   ELEMENT;
typedef   ELEMENT              *LINK;

// funution prototype

LINK s_to_l(char *);
LINK string_to_list(char *);
LINK s_to_l(char *);
void print_list(LINK);
int count(LINK);
int count_it(LINK);
void concatenate(LINK,LINK);
void delete_list(LINK);

======================================

// dolist.c


/* List creation using iteration */

#include "list.h"

LINK s_to_l(char s[])
{
   LINK    head = NULL, tail;
   int     i;

   if (s[0] != '\0'){                   /* first element */
      head = (ELEMENT *)malloc(sizeof(ELEMENT));
      head -> d = s[0];
      tail = head;
      for (i=1; s[i] != '\0'; ++i) {    /* add to tail */
          tail -> next = (ELEMENT *)malloc(sizeof(ELEMENT));
          tail = tail -> next;
          tail -> d = s[i];
   }
   tail -> next = NULL;         /* end of list */
  }
  return head;
}


/* list creation using recursion */

LINK string_to_list(char s[])
{
   LINK    head;

   if (s[0] == '\0')                   /* base case */
      return(NULL);
   else {
      head = (ELEMENT *)malloc(sizeof(ELEMENT));
      head->d = s[0];
      head->next = string_to_list(s+1);        
      return head;
   }
}

======================================

// util.c

#include "list.h"

/* print list recursively */

void print_list(LINK head)
{
   if (head == NULL)
      printf("NULL\n");
   else {
      printf("%c --> ", head->d);
      print_list(head->next);
   }
}
 
/* count a list recursively */

int count(LINK head)
{
   if (head == NULL)
      return 0;
   else 
      return(1 + count(head->next));
}
 
 
/* count a list iteratively */

int count_it(LINK head)
{
   int cnt = 0;

   for ( ; head !=NULL; head = head->next)
      ++cnt;

   return cnt;
}

/* concatenate list a and b with a as head */

void concatenate(LINK a, LINK b)
{
   assert(a != NULL);
   if (a->next == NULL)
      a->next = b;
   else
      concatenate(a->next,b);
} 

/* insert */

void insert(LINK p1, LINK p2, LINK q)
{
   assert(p1->next == p2);
   p1->next = q;
   q->next = p2;
}

/* recursive deletion of a list */

void delete_list(LINK head)
{
   if (head != NULL) {
      delete_list(head->next);
      printf("in delete, pointer=%p\n", head);
      free(head);
   }
}

======================================

// main.c

#include "list.h"

main (void)
{
   char *s="crabtree";
   char *t="+ evelyn";
   LINK head, headt;

   char dummy; // for printout delay


   printf("before s_to_l, s=%s\n",s);
   head = s_to_l(s);
   print_list(head);
   printf("number of elements counted by count is %d\n",count(head));

   printf("\npress enter to continue\n"); scanf("%c",&dummy);

   printf("before string_to_list, s=%s\n",s);
   head=string_to_list(s);
   print_list(head);
   printf("number of elements counted by count_it is %d\n",count_it(head));

   printf("\npress enter to continue\n"); scanf("%c",&dummy);

   headt = s_to_l(t);
   concatenate(head, headt);
   printf("after concatenation:\n");
   print_list(head);

   printf("\npress enter to continue\n"); scanf("%c",&dummy);

   delete_list(head);
   printf("after deletion:\n");
   // may print the same sa above
   print_list(head);

   return 0;
}

======================================

Stacks
======

// stack-static.h

/* An implementation of type stack */

#include <stdio.h>

#define MAX_LEN    5000000 // five million 
#define EMPTY      -1
#define FULL	   (MAX_LEN - 1)

typedef struct stack {
   char s[MAX_LEN];
   int  top;
} stack;

void initialize(stack *stk);
void push(char c, stack *stk);
char pop(stack *stk);
char top(const stack *stk);
int empty(const stack *stk);
int full(const stack *stk);

======================================

// stack-static.c

#include "stack-static.h"

//void reset(stack *stk)
void initialize(stack *stk) //changed the name from reset for compatibility
{
   stk -> top = EMPTY;
}

void push(char c, stack *stk)
{
    stk -> top++;
    stk -> s[stk -> top] = c;
}

char pop(stack *stk)
{
  return (stk -> s[stk -> top--]);
}

char top(const stack *stk)
{
  return (stk -> s[stk -> top]);
}

int empty(const stack *stk)
{
	return ((stk -> top == EMPTY));
}

int full(const stack *stk)
{
	return ((stk -> top == FULL));
}

======================================

// stack-dynamic.h

/* A linked list implementation of a stack. */

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

#define   EMPTY      0
#define   FULL       5000000 // five million

typedef   char                 data;

struct elem {                   /* an element on the stack */
   data          d;
   struct elem   *next;
};

typedef   struct elem   elem;

struct stack {
   int    cnt;                  /* a count of the elements */
   elem   *top;                 /* ptr to the top element */
};

typedef   struct stack   stack;

void      initialize(stack *stk);
void      push(data d, stack *stk);
data      pop(stack *stk);
data      top(const stack *stk);
int       empty(const stack *stk);
int       full(const stack *stk);

======================================

// stack-dynamic.c

/* The basic stack routines. */

#include "stack-dynamic.h"

void initialize(stack *stk)
{
   stk -> cnt = 0;
   stk -> top = NULL;
}

void push(data d, stack *stk)
{ 
   elem   *p;

   p = malloc(sizeof(elem));
   p -> d = d;
   p -> next = stk -> top;
   stk -> top = p;
   stk -> cnt++;
}

data pop(stack *stk)
{ 
   data   d;
   elem   *p;

   d = stk -> top -> d;
   p = stk -> top;
   stk -> top = stk -> top -> next;
   stk -> cnt--;
   free(p);
   return d;
}

data top(const stack *stk)
{ 
   return (stk -> top -> d);
}

int empty(const stack *stk)
{ 
   return ((stk -> cnt == EMPTY));
}

int full(const stack *stk)
{ 
   return ((stk -> cnt == FULL));
}

======================================

// main.c

/* Test the stack implementation by reversing a string. */

#include "stack-static.h"
//#include "stack-dynamic.h"

int main(void)
{
   stack   s;
   char    c;

   initialize(&s);   /* initialize the stack */

   //read
   while ((c=getchar()) != EOF)
     if (!full(&s))
       push(c, &s);  /* push a char on the stack */

   //write
   while (!empty(&s))
      putchar(pop(&s));     /* pop a char off the stack */
   putchar('\n');

   return 0;
}