CSc 352: Lecture-13

Unions(continue Prev. Lecture), List Processing

Note: All the programs mentioned in this lecture are in:

/home/cs352/SUMMER02/lecture13progs/

- UNIONS
	- Another derived type like a structure.
	
	- defines a set of alternative values that may be stored in a 
	shared portion of memory.

	Ex:
	union number{
		int i;
		double d;
		};
	number is the union tag name. The members are i and d.
	The derived type is then "union number". Again only the
	type is created but no storage allocated. For declaring 
	a variable of this type:

	union number num1, num2;

	This declaration allocates storage for num1 and num2. For
	each variable compiler allocates storage that accomodates
	the largest of the members, in this case double.  

	Accessing the member is the same as structures. 

	See union.c


- LIST PROCESSING
	- Self Referential Structures
		Ex: 
		struct list_elem{
			int num;
			struct list *next;
		};
		struct list_elem  a;

		We first define a structure type. One member is an int, 
		the other is called a link. Each structure can be linked 
		to a succeeding structure through "next". It contans either
		NULL, or the address of the next structure.

		Ex:
		struct list_elem a, b, c;
		a.num=1;
		b.num=2;
		c.num=3;
		a.next=&b;
		b.next=&c;
		c.next=NULL;

		creates a list with three elements.

		Now we can access the members of the list elems:
		a.num     		/*the num member of a*/
		a.next->num		/*the num member of b*/
		a.next->next->num	/*the num member of c*/
	
	- Linear Linked Lists
		- a head pointer(addresses the first elem. of the list)
		  each elem. of the list has a link to the next elem.
		  last elem's link is NULL.
		   	
		- We can dynamically grow the list:
		  void * malloc(size_t size);
		  returns the base address of the space that is allocated
		  (size bytes) or NULL(if call is unsuccessful)
			
		Ex:
		typedef struct list_elem element;
		element *head;
		head=malloc(sizeof(element));
		head->num=100;
		head->next=NULL;
		
		In order to add more elements:
		head->next=malloc(sizeof(element));
		head->next->num=1000;
		head->next->next=NULL;
		...

	- List Operations
		- creating a list
		- counting the elems
		- look up
		- inserting, deleting an elem
		- concatenating two lists

		see listopers.c 

		NOTE: Recursion is used in many of the list operations.
		The generic form of recursion is as:
		
		void recursivefun(elem *head)
		{
		  if (head==NULL)
			do the base_case
		  else
			do the general_case
			recursivefun(head->next)
		}