1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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>
|
