11.2 Operations on Structures
Note if dont show image you download pdf book and solved this problem
The operations permitted on structures are a subset of the operations permitted on basic types (such as int, double, etc). Structures may be copied or assigned, but it is not possible to directly compare two structures.
struct Point p1 = { 0, 0 };
struct Point p2;
p2 = p1; /* Valid. structs may be assigned. */
if (p1 == p2) /* Invalid. structs may not be compared. */
printf("Points are equal\n");
if (p1.x == p2.x && p1.y == p2.y) /* Valid. May compare basic types. */
printf("Points are equal\n");
A structure may be passed to a function and may be returned by a function.
struct Point point_difference(struct Point p1, struct Point p2)
/* Return the delta (dx, dy) of p2 with respect to p1. */
{
p2.x -= p1.x;
p2.y -= p1.y;
return p2;
}
As with any other variable, structures are passed by value. Thus, in the above example, p1 and p2 are copies of the passed arguments, and the changes to p2 within the function do not a ect the value of the associated variable in the calling function.
struct Point a = {5,10}, b = {20,30}, c;
c = point_difference(a, b); /* c = {15,20}, b is unchanged. */
Passing structures by value can be ine cient if the structure is large, and it is generally more e cient to pass a pointer to a struct rather than making a copy. Defining structure pointers and obtaining the address of a struct variable is the same as for basic types.
struct Point pt = { 50, 50 };
struct Point *pp;
pp = &pt;
(*pp).x = 100; /* pt.x is now 100. */
Note, the parentheses about (*pp).x are necessary to enforce the correct order-of-evaluation, so that the pointer-to-struct is dereferenced before attempting to access member x. To avoid this rather complicated dereferencing syntax, an alternative notation is provided to access structure members via a pointer. The -> operator permits the expression (*pp).x to be rewritten more simply as pp->x.
As a further example, given the variable definitions
struct Rectangle rect, *pr = ▭
the following statements are equivalent.
rect.topleft.x = 50;
(*pr).topleft.x = 50;
pr->topleft.x = 50;
11.3 Arrays of Structures
As for basic types, it is possible to create an array of structures.
struct Point pa[10];
The elements of the array may be initialised by a brace-enclosed initialiser list and, when doing so, the size of the array need not be specified. The example below defines an array of four elements.
struct Point pa[] = {
{0, 0}, {0, 240}, {320, 240}, {320, 0}
};
The size of a structure type in bytes may be computed using the sizeof operator, and the number of elements in the above array can be found using the idiom
int nelems = sizeof(pa) / sizeof(pa[0]);
As for basic types, pointer arithmetic for structure types is managed by the compiler, so that the operations
struct Point *pp = pa;
for (; pp != pa + sizeof(pa) / sizeof(pa[0]); ++pp)
printf("%d %d\n", pp->x, pp->y);
will e ectively print the (x,y) values of each element in the array. The compiler knows the size of the structure type and determines the appropriate address o sets accordingly.
Important. The size of a structure might not equal the sum of its constituent parts. For example, if we assume a char is one byte and an int is four bytes, the following structure type
struct Stype {
char c;
int i;
};
might not have size five bytes. Most real machines require objects to satisfy certain alignment restrictions (e.g., integers must be located at even addresses), and the compiler will pad the structure with unnamed “holes” to ensure each member is properly aligned. Thus, the above example might have size six or eight bytes rather than five bytes. The sizeof operator returns the correct value.
11.4 Self-Referential Structures
A structure definition may not contain an object of its own type,
struct Node {
int item;
struct Node next; /* Invalid. Cannot define an object of an incomplete type. */
}
but it may refer to a pointer of its own type.
struct Node {
int item;
struct Node *next; /* Valid. May define a pointer to an incomplete type. */
}
The ability of a structure to refer to incomplete types (including itself) via a pointer is a vital property for constructing a number of important data-structures. These include linked-lists, binary trees, graphs, hash tables, and many more.1
The following example demonstrates a simple linked-list implementation. Linked-lists come in two main varieties: singly-linked and doubly-linked. The former consists of a series of nodes con-taining a value and a pointer to another node. Each node is defined as follows.
struct List {
int item;
struct List *next;
};
In this example, the value contained by the node is an integer variable, but it could be a variable of any type. The set of nodes are connected such that the next pointer for each node points to the address of the next node in the list as shown in Figure 11.1. The end of the list is marked by a node whose next pointer is NULL.
Figure 11.1: Singly linked-list. Each node in the list contains an item and a pointer to the next node in the list. A pointer to the first node is called the head. The end node points to NULL to signify the end of the list.
1 Several of these data-structures are presented in Chapter 15.
To traverse a singly linked-list, it is necessary to hold a pointer to the first node in the list; this pointer refers to the head of the list. The subsequent nodes may be accessed by iterating through each node in turn. For example, the code segment below shows how to reach the end node.
struct List *node = head;
while (node->next != NULL)
node = node->next;
Linked-lists are useful for their ability to be grown and shrunk easily without issues of memory reallocation and data copying. It is straightforward to add and delete elements, even to splice elements into the middle to the list. The function below demonstrates a list-growing implementation that adds a new node to the end of the list. The first argument may be a pointer to the head of the list, or a pointer to any node midway along the list, and the function will find the end and attach a new node to it. If the function is passed NULL, it creates a new head node and returns a pointer to it.
1 struct List *insert back(struct List *node, int item)
2 /* Add new item to the end of the list. Return pointer to the new List node. */
3 {
4/* Allocate memory for new node. */
5struct List *newnode = (struct List *) malloc(sizeof (struct List));
6if (newnode == NULL)
7 return NULL; /* allocation failed */
8
9newnode−>item = item;
10 newnode−>next = NULL;
11
12 /* If list is not empty, find end of list and attach new node. */
13 if (node) {
14 while (node−>next)
15 node = node−>next;
16 node−>next = newnode;
17 }
18
19 return newnode;
20 }
The following function inserts a node at a specified location in the list. A pointer to the node one before the insertion is passed to the function, and its next pointer is used to splice the new node into the next position in the list, as shown in Figure 11.2.
Figure 11.2: Inserting a new node into the middle of a singly linked-list. Prior to insertion, the next pointer of node A points to node B. A new node, C, is created, and its next pointer is made to point to B and the next pointer of node A is made to point to C.
1 struct List *insert after(struct List *node, int item)
2 /* Add new item to the next position in the list after node. */
3 {
4 /* Allocate memory for new node. */
5 struct List *newnode = (struct List *) malloc(sizeof (struct List));
6if (newnode == NULL)
7 return NULL; /* allocation failed */
8
9/* If list is not empty, splice new node into list. */
10 if (node) {
11 newnode−>next = node−>next;
12 node−>next = newnode;
13 }
14 else newnode−>next = NULL;
15
16 newnode−>item = item;
17 return newnode;
18 }
A doubly linked-list is similar to a singly linked-list except that each node also contains a pointer to the previous node in the list as follows.
struct List {
int item;
struct List *next;
struct List *prev;
};
The enables the list to be constructed as shown in Figure 11.3, and permits traversal up the list as well as down. In particular, doubly linked-lists make the deletion of elements simpler and more e cient than is possible with a singly linked-list.
Figure 11.3: Doubly linked-list. Each node contains a pointer to the next and the previous node in the list. The ends of the list in both directions are marked by NULL pointers.
No comments:
Post a Comment