Page 333 - Introduction to Microcontrollers Architecture, Programming, and Interfacing of The Motorola 68HC12

310 Chapter 10 Elementary Data Structures

10.5 Summary

This chapter has presented the data structures that are most commonly used in
microcomputers. Although many programmers have written millions of lines of code
without knowing about them, they help you to create order in a maze of possible ways
to store data, they allow you to copy, or almost copy, the code needed to access the
structures, and they allow you to save memory by using a better structure.
To show how your knowledge of data structures can save memory in a small
computer, consider the storage and access of a mathematical array of ten rows by ten
columns of 1-byte numbers, where 96 of the numbers are zero (this is called a sparse
array). A natural way to store this data is in an array, but that array would take 100
memory locations, and most would contain zeros. It is more efficient to store the four
numbers of the sparse array in a table that stores the nonzero elements of the array, where
the first column of the table is the row number, the second is the column number, and
the third is the data in that row and column. This could be done in only twelve bytes.
Knowledge of data structures can enable you to make a program work in a limited
amount of memory, which may not be possible otherwise.
This chapter only scratches the surface of this fertile area of study. If you study
computer science, you will probably take a whole course on data structures, as well as
meeting this material in other courses on database systems and compiler design. It is
your best single course to take from the computer science area of study. Many textbooks
are available for these courses, and you can use practically any of them to expand your
comprehension of data structures. We suggest one of the earliest books, Fundamental
Algorithms. Vol. 1, The Art of Computer Programming, 2nd ed. (D. Knuth, Addison-
Wesley Publishing Co., Inc., Reading, Mass., 1973), for your reading.
From reading this chapter, you should be able to handle any form of the simple
data structures that are likely to be met in microcomputer programming, and you should
be able to handle the various types of sequential structures. You should also be able to
recognize the linked list structures. But most important, you should be prepared to put
some order in the way your programs handle data.

Do You Know These Terms?

See the end of chapter 1 for instructions.

data structure base deque buffer
vector histogram push tree
element list pop root
component array pull successor
index row major queue linked list
precision column major shift register structure
length table first-in crotch
origin string first-out link