Original Post
Problems and Solutions
The essence of programming is, when given a problem, devise and implement a solution. One's ability to come up with clear, proper and efficient solutions is directly proportional to their knowledge of data structures, code organization, speed/efficiency issues, and of course the programming language itself.
It basically all comes down to having a lot of tools available to you (i.e. knowledge of different programming techniques), and knowing which tools to use for the job. If, for instance, you don't have a decent amount of powerful tools under your belt, you'll be hard-pressed to come up with a viable solution to a given problem. As well, using the wrong tool increases the complexity of the problem or creates unreasonable speed/organizational penalties.
Let's look at a simple example. If I asked you to write a routine that displayed the numbers from 1 to 5 to the standard output, what possible solutions are there? Which is the best? Look here:
Dynamic Data Structures
Arm Yourself
When you think about it, data structures are nothing more than rules that are imposed on how data is organized in a program. The fixed data structures that we discussed are part of the C language itself, and the dynamic data structures all make use of pointers, memory allocation and other fixed structures (notably structs). There are many different ways of structuring data, and this list is not meant to be exhaustive, but it does fairly represent the core data structures at your disposal, so you'd do well to be familiar with each of them.
When you come across a situation that calls for one of these data structures, you can either implement the data structure directly into your code, or take advantage of the collection of data structures that comes with your compiler, which are part of the STL (Standard Template Library), and also provided as MFC classes.
Take a look at 03.03 - Selected C Topics for material on some of these data structures and information on how they can be implemented. If I haven't gotten around to writing up an article on one and you have a question, feel free to ask; many here are already well-versed in using and implementing these (and others).
The important thing to realize is that these data structures are common because they address recurring problems in software development. There's always more than one way to do things when programming, but it's smart to take advantage of the culmination of quality, reusable data structures which have proven themselves.
Finally, you should be aware of the tradeoffs inherent in choosing a data structure. For instance, an array provides sequential data item access, is very fast (if you know the index of the data item you want), but needs to be declared in advance (i.e. at compile time) and has a relatively slow linear search. Linked lists (and others that use them) grow dynamically, but involve some overhead in terms of memory allocation and pointer maintenance, and are also linearly searched. Trees are fast for searches, but insertions are slow and trees may be severly unbalanced, penalizing their search speed.
But hey, what's the best way to get comfortable with the fundamental data stuctures? By using them, of course. I did say that we were going to be writing a game in this section, so let's take our first stab at designing a game with our new weapons ready...
Questions? Comments? Please reply to this topic.
Edited by - Teej on July 4, 2001 5:42:21 PM
int n = 1;
while (n < 6)
{
printf("%d\n", n);
n++;
}
int n = 1;
do
{
printf("%d\n", n);
n++;
} while (n < 6);
for (int n = 1; n < 6; n++)
{
printf("%d\n", n);
}
int n = 1;
display:
printf("%d\n", n);
n++;
if (n < 6) goto display;
Actually, here's the best solution:
printf("1\n2\n3\n4\n5\n");
There are two points I'm trying to make here:
- There's always more than one way to do something
- The ideal solution is a mixture (or tradeoff) between processing speed, readability/intuitiveness and simplicity
struct PERSON
{
char firstName[80];
char lastName[80];
char emailAddress[80];
}
PERSON me;
Here, me is a variable of type PERSON. This variable contains three fields, which are accessable like so:
strcpy(me.firstName, "Tim"); strcpy(me.lastName, "Boston"); strcpy(me.emailAddress, "teej@gdnmail.net");Structures are indespensible as data organizers. We use structures to logically group data items, and since structures themselves define a data type, can be used in turn in arrays and other structures. They are analogous to fields in tables of a database, and are intuitively used in that fashion. It should be noted that arrays and structures, when used together, can be formed to represent any data storage requirement. This isn't to say that they're the ideal solution all of the time, because you have to take speed and memory requirements into account. (1.3) Unions Unions are very similar to structures, with one major exception: members of a union are mutually exclusive. Take a look at this example:
union PERSON
{
char name[80];
int idNumber;
}
Here, PERSON contains two fields, but only one of them can be used. In other words, the compiler sets aside enough memory for the largest single field, and no more. In this example, either a name or an ID number is needed to identify a person, but not both. Here's another possible use for a union:
struct MESSAGE
{
int type;
union
{
int commandCode;
char szData[64];
}
}
Here, we can look at the type variable in order to determine whether the commandCode variable contains a message command, or the szData variable contains some generic data that needs to be stored. Of course, I'm just making this example up, but you should note that it's up to you to decide which union field is valid -- the computer won't keep track of it for you.
(2) Dynamic Data Structures
Dynamic data structures make use of the operating system's memory allocation facilities to provide memory as it's needed. These data structures are designed to use only as much memory as is needed, making them ideal if your needs aren't fixed.
Note that with dynamic data structures, the term 'node' is used to refer to a data item, or more specifically, a data item containing actual data.
These descriptions do not include implementation details -- see 03.03 - Selected C Topics for material related to implementing these data structures.
(2.1) Linear Data Structures
The word linear, in this context, can be taken to mean 'in succession'. These data structures are all based on the fact that data items are stored sequentially, which has its benefits and down-sides, depending on what they're used for.
(2.1.1) Linked Lists
A linked list can be thought of as an array of data items, but the number of items stored in the array can grow or shrink as needed. Each node in a linked list contains not only the data item(s) to be stored, but one or more pointers to other nodes which allows the nodes to be 'chained' together (thus the term 'linked list').
A linked list always has a first node, called the head or root. Successive nodes are attached to each other from the head of the list, and the entire list can be traversed (just like going through the elements of an array) by following node pointers. As a new node is needed, memory is allocated for it, and the node is attached. When a node is no longer needed, it is removed from the list, with the remaining nodes (if any) reattached to each other to fill the gap.
There are other linked list variations, one being the doubly-linked list, which chains nodes together in both directions so that the list can be traversed either way. Other variations use additional pointers to nodes in the linked list, just as bookmarks are used in books.
Just as with its fixed counterpart the array, linked lists are a common staple of software developers, and are used wherever sequential storage is desired and memory requirements aren't fixed or may vary greatly.
(2.1.2) Stacks
If you know anything about assembly programming, you definitely know what a stack is. If you don't, think of a stack of plates in a cafeteria -- you know, where the plates are spring-loaded in a table. Stacks are called LIFO (Last In, First Out) data structures, and are described in terms of 'pushing' and 'popping' data nodes. Using our stack of plates, pushing a data node would be similar to placing a plate onto the stack, and popping a data node implies removing the top plate from the stack. If you push three data nodes (or plates) onto the stack, and then pop one out, you'll get the third (the last) node (or plate) which is on the top -- hence it's called a LIFO data structure.
Guess how local variable memory is organized in C? Yup, stacks. The same is true for function parameters. As a matter of fact, it's good to think of a stack as temporary 'memory' for a program, as that's what it's good at emulating. For instance, if you are processing some piece of data in a program, and that particular data leads you to process something else, you can push this data onto the stack, go off processing somewhere else, and then pop the data off again when you're ready to continue. A good example of this is in scripting languages where there are expressions that need to be evaluated:
13 + (6 * (3 + x))
If your program needs to process an expression like this, it can use a stack to hold intermediate values:
STACK (bottom to top): (empty)
EXPRESSION: 13 + (6 * (3 + x))
When the first bracket is reached in the expression, we need to evaluate expressions in brackets first, so we push 13 onto the stack for later retrieval:
STACK: (bottom to top): 13+
EXPRESSION: 6 * (3 + x)
Here again we need to temporarily put away a value to tackle more brackets:
STACK (bottom to top) 13+, 6*
EXPRESSION: 3 + x
Once we access the variable x (say it's 7), we now have
STACK (bottom to top): 13+, 6*
EXPRESSION: 10
Since 10 is a value (and not an expression), we now work backwards by popping values from the stack:
STACK (bottom to top): 13+
EXPRESSION: 6 * 10
And finally,
STACK (bottom to top): (empty)
EXPRESSION: 13 + 60 = 73
We know we have the final value because our stack is empty.
Granted, stacks are tricky little devils in that it's hard to visualize when they're the answer to a problem, but I assure you that they do have their uses...just think of them in terms of depth (levels), path-following and temporary 'memory', and you'll be able to conjure up a use for one when you're stuck with a seemingly wierd programming problem when the time comes. It's also interesting to note that a stack can be used to implement an algorithm instead of recursion -- the two are interchangeable.
A stack can be implemented in a number of ways, with a linked list variation being the most common. Here, a pointer is maintained for both the front (head) and rear (tail) of the linked list, serving as positions for stack pushes and pops.
(2.1.3) Queues
A queue is also a linear data structure which is used something like a stack (i.e. pushing and popping), but is FIFO (First In, First Out), which means that items are popped from a queue in the same order that they're pushed. A great way to think of queues is to think of people standing in line for something -- 'first come, first served '.
Quite simply, a queue can be used wherever items are stored and processed independently. A good example would be a process running two threads, where one thread receives incoming messages from a socket connection and places them into a message queue for the main thread to process.
As far as implementation is concerned, a queue is a minor variation of a linked list where nodes are 'popped' from the front (head) of the list, and 'pushed' to the rear.
(2.2) Heirarchial Data Structures
Data structures that fall under this category usually take the shape of inverted trees, where one data node is considered the root (at the top), and branches stem from this root containing nodes which in turn branch to other nodes.
These tree stuctures make use of a set of popular terms, with which you should become familiar:
- root : the top-most (head) node.
- parent : any node which branches off to other nodes. Every node has a parent except for the root.
- child : any node stemming from a parent node.
- sibling : nodes that share the same parent node.
- leaf : any node that has no children.
- level : all nodes that are the same number of 'generations' away from the root node.
- depth : the number of levels in a tree structure.
- graphs don't necessarily have a root node
- nodes can be connected to any other nodes
- Fixed Data Structures
- Array
- Structure
- Union
- Linear:
- Linked List
- Stack
- Queue
- Hierarchial:
- Tree
- BST (Binary Search Tree)
- Graph
You really only should concern yourself with our praise, and take heart that you have helped many on a long and ardorous path, one lit by your nuggets of wisdom and marked by your signs of knowledge and ability to convey in a meaningful, yet introductory way. With these, hopefully we all will find our way to the end, wherever that may be.