## Discussion 3

9/10/02 Tue

### Memory allocation in C

#### 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

#### 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;`

#### 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;`

#### 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;```

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

p1->x = 0;
p1->y = 1;

### 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;```

#### is equivalent to

```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.

```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);
return temp;
}
}

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

{
```	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]);
```	for (i = 0; i < n; i++) {
}
```	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;
}
}
```