diff options
| author | Tobias Klauser <tklauser@distanz.ch> | 2008-01-27 11:37:44 +0100 |
|---|---|---|
| committer | Tobias Klauser <tklauser@xenon.tklauser.home> | 2008-01-27 11:37:44 +0100 |
| commit | 7e0f021a9aec35fd8e6725e87e3313b101d26f5e (patch) | |
| tree | b1cacc4b24393f517aeb4610e9e1021f954307a8 /reference/C/MISC/linklists.html | |
Initial import (2.0.2-6)2.0.2-6
Diffstat (limited to 'reference/C/MISC/linklists.html')
| -rw-r--r-- | reference/C/MISC/linklists.html | 119 |
1 files changed, 119 insertions, 0 deletions
diff --git a/reference/C/MISC/linklists.html b/reference/C/MISC/linklists.html new file mode 100644 index 0000000..f17b58d --- /dev/null +++ b/reference/C/MISC/linklists.html @@ -0,0 +1,119 @@ +<title>Link Lists</title> +<body bgcolor="#ffffcc"> +<hr> +<center> <h1>Link Lists</h1> </center> +<hr> +<p> +<ul> +<li><a href="#long">Long explanation</a> +<li><a href="#short">Short explanation</a> +</ul> + +<a name=long> +Question, how would you write a program to meet the following requirements? + +<ol> +<li>Read an unknown number of records from a file into memory. A typical +record would look like: +<pre> + Ref Title Cost + --- ----- ---- + 1234 Oracle_Guide 22.95 +</pre> +<li>Perform a numeric sort based on the first field. +<li>Delete duplicate records based on the first field. +</ol> + +One method is to define an +<a href="../CONCEPT/arrays.html#chard">array</a> of records as below: + +<pre> + main() + { + char array[50][80]; /* 50 records, 80 bytes long */ + } +</pre> + +The data can then be read into the array and then actions performed +on the data. +This is OK but has some major problems. +<ol> +<li>The arrary will hold all the data in character format. It would be +nice to hold the integer and decimal numbers in a more appropriate form. +<li>If you have more than 50 records the program has to be altered +and recompiled. +</ol> +The first problem could be fixed by defining an +<a href="../SYNTAX/struct.html#array">array of structures</a> BUT both problems +can be solved with linked lists.<p> + +<a name=short> + +<img src=../../GRAPHICS/linklist.gif align=right> +<p> +The concept of a linked list is fairly simple. It is a group of structures +linked together by pointers, here is a picture:<p> +<br clear=right> +<p> +<p> +The "Name Age Pointer" block could be defined as below: +<pre> + struct record {char name[20]; int age; struct record *next_rec;}; +</pre> + +The important bit is "struct record *next_rec" this is the pointer to the next +structure (record). It will either point to the next record which +will require memory reserved +with the <a href="../FUNCTIONS/malloc.html">malloc</a> function or +<a href="../SYNTAX/null.html">NULL</a> if its the last record. +<p> + +<h2>Examples</h2> + +<img src=../../GRAPHICS/computer.gif align=left> +<a href="../EXAMPLES/linklst1.c"> Here is the first example.</a> +This program is more complicated than I would +like, but its the simplest I can come up with. +<br clear=left> +<p> +<img src=../../GRAPHICS/computer.gif align=center> +<a href="../EXAMPLES/linklst2.c"> +This is the same program</a> but without the heavy commenting. +<br clear=left> +<p> +<img src=../../GRAPHICS/computer.gif align=center> +<a href="../EXAMPLES/linklst3.c"> +This is still the same program</a> but it is slightly simplified with the use +of <a href="../SYNTAX/typedef.html">typedef</a>. +<br clear=left> + +<hr> +<p> +<center> +<table border=2 width=80% bgcolor=ivory> +<tr align=center> +<td width=25%> +<a href="../cref.html" target="_top">Top</a> +</td><td width=25%> +<a href="../master_index.html" target="_top">Master Index</a> +</td><td width=25%> +<a href="../SYNTAX/keywords.html" target="_top">C Keywords</a> +</td><td width=25%> +<a href="../FUNCTIONS/funcref.htm" target="_top">Functions</a> +</td> +</tr> +</table> +</center> +<p> + + + +<hr> +<address>Martin Leslie +<script language="JavaScript"> +<!-- // +document.write(document.lastModified); +// --> +</script> +</address> + |