Chapter 4 : C Data Structures

[ Team LiB ]

Chapter 4: C Data Structures Read explicit data structure operations in terms of the underlying abstract data class. (p. 96) Vectors are typically realized in C by using the built-in array type without attempting to abstract the properties of the vector from the underlying implementation. (p. 96) An array of N elements is completely processed by the sequence for (i = 0; i < N ; i++); all other variations should raise your defenses. (p. 96) The expression sizeof(x) always yields the correct number of bytes for processing an array x (not a pointer) with memset or memcpy. (p. 97) Ranges are typically represented by using the first element of the range and the first beyond it. (p. 100) The number of elements in an asymmetric range equals the difference between the upper and the lower bounds. (p. 100) When the upper bound of an asymmetric range equals the lower bound, the range is empty. (p. 100) The lower bound in an asymmetric range represents the first occupied element, the upper bound, the first free one. (p. 100) Arrays of structures often represent tables consisting of records and fields. (p. 101) Pointerstostructuresoftenrepresentacursorforaccessingtheunderlyingrecords and fields. (p. 101) Dynamically allocated matrices are stored as pointers to array columns or as pointers to element pointers; both types are accessed as two-dimensional arrays. (p. 103) Dynamically allocated matrices stored as flat arrays address their elements using custom access functions. (p. 104) An abstract data type provides a measure of confidence regarding the way the underlying implementation elements will be used (or abused). (p. 106) Arrays are used for organizing lookup tables keyed by sequential integers starting from 0. (p. 111) Arrays are often used to efficiently encode control structures, thus simplifying a program's logic. (p. 111) Arrays are used to associate data with code by storing in each position a data element and a pointer to the element's processing function. (p. 112) Arrays can control a program's operation by storing data or code used by abstract or virtual machines implemented within that program. (p. 113) Read the expression sizeof(x)/sizeof(x[0]) as the number of elements of the array x.(p. 113) A structure with an element titled next pointing to itself typically defines a node of a singly linked list. (p. 118) A permanent (for example, global, static, or heap allocated) pointer to a list node often represents the list head. (p. 118) A structure containing next and prev pointers to itself is probably a node of a doubly linked list. (p. 121) Follow complicated data structure pointer operations by drawing elements as boxes and pointers as arrows. (p. 122) Recursive data structures are often processed by using recursive algorithms. (p. 126) Nontrivial data structure manipulation algorithms are typically parameterized using a function or template argument. (p. 126) Graph nodes are stored sequentially in arrays, linked in lists, or linked through the graph edges. (p. 131) The edges of a graph are typically represented either implicitly through pointers or explicitly as separate structures. (p. 134) Graph edges are often stored as dynamically allocated arrays or linked lists, both anchored at a graph's nodes. (p. 137) In a nondirectional graph the data representation should treat both nodes as equal, and processing code should similarly not discriminate edges based on their direction. (p. 139) On nonconnected graphs, traversal code should be coded so as to bridge isolated subgraphs. (p. 139) When dealing with graphs that contain cycles, traversal code should be coded so as to avoid looping when following a graph cycle. (p. 139) Inside complicated graph structures may hide other, separate structures. (p. 140)

[ Team LiB ]