Discussion 3

9/10/02 Tue

1. Memory allocation in C
2. Introduction to structure
3. Pointer and structure
4. Typedef
5. Self referencing structure

Memory allocation in C

In C, memory can be allocated in three diffrent ways:

Static storage, stack and heap

Static storage is allocated for a global variable and the storage exists during entire program run. Stack storage is allocated when the program enters a block and deallocated when it exits from the block. Both the size of static and stack storage is determined at compile time and storage allocation and deallocation are done by the compiler.

Heap storage is allocated at run time for whatever size specified up to the limit. While heap storage has its advantage that a programmer can specify the size of memory as necessary at run time, the allocated heap storage should be explicitly deallocated by the programmer. If the storage is left without being deallocated, it can't be accessed from the system and reduce the total available memory in a system.

#define ARRAY_SIZE 10
double array1[ARRAY_SIZE];

double average(int a[], int n)
{
    double result = 0.0;
    for (i = 0; i < n; i++) {
        result += array1[i];
    }
    return (result / n);
}

int main(void)
{
    double array2[10];
    double *array3;
    fill_array(array1);
    fill_array(array2);
    array3 = (double *) malloc(sizeof(double) * ARRAY_SIZE);
    fill_array(array3);
    printf("Average of array 1, 2 and 3 are: %lf, %lf, %lf\n",
            average(array1), average(array2), average(array3));
    free(array3);

    return 0;
}

Allocation memory dynamically:

ptr = (type *) malloc (sizeof(type) * ARRAY_LENGTH);

The memory can be deallocated:

free (ptr);

Short quiz

1. Write a code to allocate the space for the string and copy the given string to the newly allocated space.

char* strdup(char *str)
{
	char *result;

	_____________________

	strcpy(result, str);
	return result;
}

Introduction to structure

Structure is a collection of one or more variables grouped in a single name. Each variable in a structure called a member. Unlike Java, which evolved from C, the structure in C has only members not the methods. 

Structures can be declared as follows: 

struct point {
	int x;
	int y;
};

Given the declaration of point above, a variable pt of struct  point type can be defined as follows:

struct point pt;

Operations on structures.

To access a member in a structure, we use "." (dot) operator. For example,

pt.x = 0;
pt.y = 10;

Short quiz

2. Write a code to find calculate the distance between two points (pt1 and pt2).

double sqrt(double x);

struct point {
	double x;
	double y;
};

double dist(struct point pt1, struct point pt2)
{
	return sqrt(____________________);
}

Pointer and structure

As in the basic type, we can think of a pointer of a structure.

struct point *p1;

is the declaration for a pointer whose type is pointer to struct point.

When we take the address of a structure we take the address of (&) operator.

struct point pt1;
struct point *p1 = &pt1;

When we dereference a structure, we use the dereference operator (*). 

struct point pt1, pt2;
struct point *p1 = &pt1;

(*p1).x = 0;
(*p1).y = 1;
pt2 = *p1;

Since the accessing a member of dereferenced variable is frequently used, there is a short hand notation.

Short quiz

3. Modify the code in short quiz 2 so that dist takes the the pointers to struct point instead.

double dist(struct point *p1, struct point *p2)
{
	return sqrt(_________________________________);
}

Typedef

Typedef is alasing a type so that the type can be used more conveniently. Typically, a structure is used with typedef to make its type name shorter.

struct point {
	double x;
	double y;
};
typedef struct point point;

typedef struct point {
	double x;
	double y;
} point;

struct point * can be shorted to ppoint using the following declaration:

typedef struct point * ppoint;

Self referencing structure

A structure (struct t1) cannot have a variable of its own type (struct t1) because we don't know how much space needs to be allocated for the structure. Whereas a pointer to the structure (struct t1 *) can be a member of the structure. This is because pointer always takes the same size (4 bytes) in 32-bit machine, thus it's possible to determine the size of structure variable. When a structure has a member of pointer to the structure, then it is called self referencing structure. Self referencing structure is used when a data structure is composed of the same type and it is travered using pointer like linked-list and tree.

Example: Linked list

struct lnode {
	char *word;
	struct lnode *next;
};

typedef struct lnode lnode;
typedef struct lnode * plnode;

plnode addhead(plnode head, char *str)
{
	plnode *temp;

	if (head == NULL) {
		temp = (plnode)malloc(sizeof(lnode));
		temp->word = strdup(str);
		temp->next = NULL;
		return temp;
	}
	else {
		temp = (plnode)malloc(sizeof(lnode));
		temp->word = strdup(str);
		temp->next = head;
		return temp;
	}
}

void print_list(plnode head)
{
	plnode *temp;

	for (temp = head; temp != NULL; temp = temp->next) {
		printf("%s\n", temp->word);
	}
}

void delete_list(plnode head)
{
	plnode *old, *temp = head;

	while (temp != NULL) {
		old = temp;
		temp = temp->next;
		free (old->word);
	}
}

int main(void)
{
	char *test_string[] = {
		"This", "is", "a", "test." };
	int n = sizeof(test_string) / sizeof(test_string[0]);
	plnode *head;

	for (i = 0; i < n; i++) {
		head = addhead(head, test_string[i]);
	}
	print_list(head);
	delete_list(head);

	return 0;
}

Short quiz

4. Complete the function to add a node at the tail of the list rather than at the head.

plnode addtail(plnode head, char *str)
{
	plnode *p, *temp;

	if (head == NULL) {
		temp = (plnode)malloc(sizeof(lnode));
		temp->word = strdup(str);
		temp->next = NULL;
		return temp;
	}
	else {
		for (p = head; p->next != NULL; p = p->next)
			;
		
		temp = (plnode)malloc(sizeof(lnode));
		temp->word = strdup(str);

		___________________

		___________________

		return head;
	}
}

Back to Top

Revised: 09/09/02 .