Linked ListA linked list is a data structure in which each item in the list has a link to another item in the list. The are many varieties of linked lists including trees, queues, stacks, and sequential. Linked lists have a pointer to the first item in the list typically called head because it points to the head of the list. For sequential linked lists, each item in the list has a pointer to the next item in the list which is typically called next because it points to the next item. Below is a conceptual representation of a linked list of lines of text. For each line of text there is the length of the line, the line text, and a pointer to the next line of text. When the next pointer is NULL, that indicates the end of the linked list. If the head pointer were NULL, that would indicate an empty linked list.
----------------
Head Pointer --> - Line of Text -
----------------
- Line Length -
- Line Text - ----------------
- Next Pointer - --> - Line of Text -
---------------- ----------------
- Line Length -
- Line Text - ----------------
- Next Pointer - --> - Line of Text -
---------------- ----------------
- Line Length -
- Line Text -
- Next Pointer - --> NULL
----------------
This program puts to use things learned in all the previous topics to create a set of functions that could be used anytime you needed to create a linked list from a text file. It reads a text file, saves each line in memory, and then displays the lines in the same order in which they were read and prefixes each line with a line number. Learning to create, populate, navigate, and delete a linked list is a very common programming exercise. The mastering of this code and the concepts it embodies will enhance a programmers ability to use the concepts to code solutions to many programming problems.In the following sections the code is explained, first at a high level, then going into more and more detail. The actual code appears at the end of this page. Download this source code in text format (Plain.c) OverviewLooking at main() lines 49 to 51, the program will read a text file and store the text in memory in a linked list via ReadFileIntoMemory(), display the lines stored in the linked list via ShowText(), and free the memory used by the linked list via FreeLineOfTextMemory(). Reading the fileLine 74 opens the file and lines 75-79 check for a sucessful open. Line 130 gets a character from the file. Line 99 closes the file. Storing the linesThe characters are stored via StoreChar(). At the end of each line, StoreLine() creates an entry in the linked list by the allocating memory needed to store the line of text.Showing the textShowText() goes through the linked list sequentially and via PutLine() displays the text.Freeing memoryFreeLineOfTextMemory() goes through the linked and frees the memory allocated to hold each line of text. ReadFileIntoMemory()This function is an expanded version of Files example #2. It receives a character pointer which points to the file name and is used to open the file in line 74. When ReadFileIntoMemory ends, it returns a LineOfText structure pointer, pLineOfTextHead, which is the head of the linked list. Lines 68-69 define two LineOfText structure pointers. pLineOfTextHead is the head of linked list pointer and pLineOfTextCursor is used throughout the code to point to the 'current' LineOfText structure. These are both initialized to NULL. The integer variable Count is used to count the number characters in each line. Line 71 sets it to zero initially and line 92 resets to zero after each line has been stored in the linked list. Line 80 assigns the character pointer returned by AllocateBuffer() to character pointer variable pBuffer. pBuffer then points to a 1024 byte block of storage (a buffer) which is used to store the characters as they are read from the file via the call to StoreChar() in line 84. Lines 81 and 94 call GetChar() which returns a character from the file and sets the Eof (end of file) flag when Eof is detected. The while loop, lines 82-95, causes the file to be processed until Eof. Lines 85-93 handle the 'end of line' processing which is detected by the if statement on line 85 by checking for the newline character '\n'. When end of line is detected, the line is stored in the linked list via a call to StoreLine() on line 87 which returns a LineOfText structure pointer and assigns it to pLineOfTextCursor. Thereby causing pLineOfTextCursor to point to the most recent LineOfText structure. Lines 88-91 detect the first LineOfText structure created and set pLineOfTextHead to point to that structure. Line 96 stores the last line of text in the linked list via a call to StoreLine() because Eof means there is also an end of line condition. Line 97-98 frees the memory allocated to the buffer and sets pBuffer to NULL because the memory block that pBuffer pointed to, does not exist. AllocateBuffer()This function allocates a block of memory to be used as temporary storage for the characters as they are read from the file. Temporary storage like this is often referred to as a buffer. Line 111 allocates a block of memory that will hold 1024 characters via a call to malloc(), casts the result as a character pointer, and assigns the result to pBuffer. If malloc() fails it returns NULL. The program cannot continue without a buffer, so Lines 112-116 check for this condition and ends the program if the malloc() fails. This function is called via line 80. Remember that pBuffer in AllocateBuffer() and pBuffer in ReadFileIntoMemory are two totally different variables. Therefore AllocateBuffer() must return pBuffer and line 80 assigns that return value to the pBuffer in AllocateBuffer(). GetChar()GetChar() receives a file pointer which was obtained via the fopen() call on line 74 and the Eof variable is passed by reference so that GetChar() can change it and the changed value will be available in ReadFileIntoMemory(). pEof is dereferenced in lines 131 and 132 in order to change and check the value of variable Eof. If the '*' were left off, those lines would be changing and checking the address stored in pEof instead of what the address stored in pEof points to, which is of course Eof. GetChar() returns the character read from the file. When end of file is reached, the character returned is a blank. Line 132 checks for eof and when it is not eof, InputInt is cast as a character and assigned to InputChar. This is done because fgetc() returns an integer not a character. The integer returned can be safely cast as a character as long as eof has not been reached. StoreChar()StoreChar() receives InputChar, pBuffer, and Count which is passed by reference via pointer pCount. Line 145 changes the local copy of variable pBuffer so that pBuffer points to the next position in the buffer. The first time this statement is executed, Count will be zero. As Count is incremented via line 147, the position in the buffer pointed to by pBuffer will be incremented as well. Line 146 assigns InputChar to the position in the buffer pointed to by pBuffer.StoreLine()StoreLine() receives pBuffer, Count, and pLineOfTextCursor. pBuffer points to all the stored characters from the line just read, Count is the number characters stored in the buffer, and pLineOfTextCursor points to the current LineOfText structure. Character pointer pLine, integer variable i, and two LineOfText pointers, pLineOfText and pLineOfTextPrev are declared in lines 156-160. Line 163 allocates a block of memory which is the size of 1 LineOfText structure, casts the resulting pointer as type LineOfText, and assigns the pointer to pLineOfText. Line 164 allocates a block of memory which is the size of 'Count' characters, casts the resulting pointer as type character, and assigns the pointer to pLine. Lines 166-167 saves the previous LineOfText pointer in pLineOfTextPrev and saves the pointer to the new LineOfText structure in pLineOfTextCursor. Lines 169-171 set each field in the new LineOfText structure. Length is set to the Count of characters saved in the buffer. pLine is set the pointer resulting from the malloc() on line 164, and pLineOfTextNext is set to NULL because this LineOfText structure is the last one in the linked list. Lines 173-178 copies the characters stored in the buffer to the memory block pointed to by pLine which was allocated via the malloc() in line 164. Line 180-183 link the previous LineOfText structure to the current LineOfText structure, if the previous LineOfText structure exists. If the previous LineOfText structure does not exist, indicated by pLineOfTextPrev being NULL, then this must be the first structure in the linked list. StoreLine() returns the pointer to the current LineOfText structure. ShowText()ShowText() receives the pointer to the head of the linked list as pLineOfTextHead and has a local variables LineNumber and pLineOfTextCursor. pLineOfTextCursor is set to pLineOfTextHead and is used in the while loop, lines 199-205, to 'step' through the linked list. For each LineOfText structure, LineNumber is incremented and printed then PuttLine() is called to display the characters making up that line of text. Lastly, pLineOfTextCursor is set equal to the current LineOfText's next pointer via line 204. ShowText() returns nothing. PutLinePutLine() recieves the length of the line and the pointer to the character making up the line of text and has local variable i. The for loop, lines 216-220, steps through the characters making up the line of text which is pointed to by pChar. The value of Length controls how many times the for loop is executed. Line 218 displays the character and then line 219 increments the character pointer by 1. PutLine() returns nothing. FreeLineOfTextMemory()FreeLineOfTextMemory() receives the LineOfText structure pointer via a pass by reference. This allows FreeLineOfTextMemory() to change pLineOfTextHead and have the change reflected in ReadFileIntoMemory(). Two LineOfText structure pointers, pLineOfTextCursor and pLineOfTextNext, are declared as local variables. pLineOfTextCursor is set to pLineOfTextHead in line 232. Line 232 and line 198 accomplish the same thing. The only difference is the '*' in *pLineOfTextHead. This is a direct result of passing pLineOfTextHead 'by reference' instead of passing it 'by value'. Passing pLineOfTextHead by reference means that we have passed the address of pLineOfTextHead. pLineOfTextHead contains the address of the first LineOfText structure in the linked list. So what we have is a pointer to a pointer. The while loop, lines 233-239, steps through the linked list and frees all memory allocated by malloc() in lines 163-164. If the program does not free all memory it previously allocated, the it is 'leaking memory', which is a very bad thing. For each LineOfText structure in the linked list, line 235 saves the pointer to the next structure before the memory used by the current structure is freed. If the memory used by the current structure were freed first, the next pointer would be gone. The memory for the characters making up the line of text must also be freed before the memory used by the current structure is freed (line 236). Line 237 frees the memory used by the current structure and line 238 advances the cursor to the next LineOfText structure. Line 240 sets pLineOfTextHead to NULL. This line is the only reason that pLineOfTextHead was passed by reference. The program could be modified to set pLineOfTextHead to NULL right after calling FreeLineOfTextMemory() in line 51. But then we would not have an example of how to change the value of a pointer passed to a function. Technically pLineOfTextHead does not need to be set to NULL becuase the program ends right after the call to FreeLineOfTextMemory(). It is, however, good programming practice to set pointers to NULL as soon as you know that the memory to which it pointed has been freed. Given that rule, it could be argued that pLineOfTextHead should be set to NULL right after line 232 because in the very first iteration of the while loop the memory pointed to by pLineOfTextHead is indeed freed. Setting pLineOfTextHead to NULL could even be imbedded in the while loop with an if statement checking to see if pLineOfTextHead is NULL and if it is not, then set it to NULL. The point is, be sure to NULL your pointers when you know they should be NULL and not before. CrashCrash() is crude attempt at providing a means to abort the program without the compiler flagging a divide by zero condition. There are numerous strategies for gracefully ending a program when something unexpected occurs and the program cannot logically continue, but that is not the point of this example program. The Plain.c program listing
1 /***********************************************************
2 * Plain - Nothing fancy, just code that's plain *
3 * File: Plain.c *
4 * Usage: Read a text file, save each line in memory, then *
5 * display the lines in the order they were read. *
6 ************************************************************/
7
8 /***********************************************************
9 * Includes *
10 ************************************************************/
11
12 #include <stdio.h>
13 #include <malloc.h>
14
15 /***********************************************************
16 * Structure declarations *
17 ************************************************************/
18
19 struct LineOfText
20 {
21 int Length;
22 char *pLine;
23 struct LineOfText *pLineOfTextNext;
24 };
25
26 /***********************************************************
27 * Function declarations *
28 ************************************************************/
29
30 char *AllocateBuffer(void);
31 void Crash(void);
32 void FreeLineOfTextMemory(struct LineOfText **pLineOfTextHead);
33 char GetChar(FILE *pInputFile, int *pEof);
34 void PutLine(int Length, char *pChar);
35 void ShowText(struct LineOfText *pLineOfTextHead);
36 void StoreChar(char InputChar, char *pBuffer, int *pCount);
37
38 struct LineOfText *ReadFileIntoMemory(char *pFileName);
39 struct LineOfText *StoreLine(char *pBuffer, int Count, struct LineOfText *pLineOfTextCursor);
40
41 /***********************************************************
42 * main *
43 ************************************************************/
44
45 int main(int argc, char *argv[])
46 {
47 struct LineOfText *pLineOfTextHead;
48
49 pLineOfTextHead = ReadFileIntoMemory("SomeInp.txt");
50 ShowText(pLineOfTextHead);
51 FreeLineOfTextMemory(&pLineOfTextHead);
52 printf("\n");
53 return 0;
54 }
55
56 /***********************************************************
57 * Read the file *
58 ************************************************************/
59
60 struct LineOfText *ReadFileIntoMemory(char *pFileName)
61 {
62 char *pBuffer;
63 FILE *pInputFile;
64 int Count;
65 int Eof;
66 char InputChar;
67
68 struct LineOfText *pLineOfTextHead;
69 struct LineOfText *pLineOfTextCursor;
70
71 Count = 0;
72 pLineOfTextHead = NULL;
73 pLineOfTextCursor = NULL;
74 pInputFile = fopen(pFileName, "r");
75 if (pInputFile == NULL)
76 { /* fopen() did not return a pointer */
77 printf("Open failed\n");
78 Crash();
79 }
80 pBuffer = AllocateBuffer();
81 InputChar = GetChar(pInputFile, &Eof);
82 while (Eof == 0)
83 { /* Read the whole file */
84 StoreChar(InputChar, pBuffer, &Count);
85 if (InputChar == '\n')
86 { /* This is the end of a line */
87 pLineOfTextCursor = StoreLine(pBuffer, Count, pLineOfTextCursor);
88 if (pLineOfTextHead == NULL)
89 { /* This is the first line of text */
90 pLineOfTextHead = pLineOfTextCursor;
91 }
92 Count = 0;
93 }
94 InputChar = GetChar(pInputFile, &Eof);
95 }
96 pLineOfTextCursor = StoreLine(pBuffer, Count, pLineOfTextCursor);
97 free(pBuffer);
98 pBuffer = NULL;
99 fclose(pInputFile);
100 return pLineOfTextHead;
101 }
102
103 /***********************************************************
104 * AllocateBuffer - get memory for buffer *
105 ************************************************************/
106
107 char *AllocateBuffer(void)
108 {
109 char *pBuffer;
110
111 pBuffer = (char *)malloc(sizeof(char) * 1024);
112 if (pBuffer == NULL)
113 { /* If pBuffer is NULL, then the malloc failed */
114 printf("malloc failed/n");
115 Crash();
116 }
117 return pBuffer;
118 }
119
120 /***********************************************************
121 * Get a character and detect end of file *
122 ************************************************************/
123
124 char GetChar(FILE *pInputFile, int *pEof)
125 {
126 char InputChar;
127 int InputInt;
128
129 InputChar = ' ';
130 InputInt = fgetc(pInputFile);
131 *pEof = feof(pInputFile);
132 if (*pEof == 0)
133 { /* If feof() returned a zero, then fgetc() returned a char */
134 InputChar = (char)InputInt;
135 }
136 return InputChar;
137 }
138
139 /***********************************************************
140 * Store the character *
141 ************************************************************/
142
143 void StoreChar(char InputChar, char *pBuffer, int *pCount)
144 {
145 pBuffer = pBuffer + *pCount;
146 *pBuffer = InputChar;
147 *pCount = *pCount + 1;
148 }
149
150 /***********************************************************
151 * Store a line of text *
152 ************************************************************/
153
154 struct LineOfText *StoreLine(char *pBuffer, int Count, struct LineOfText *pLineOfTextCursor)
155 {
156 char *pLine;
157 int i;
158
159 struct LineOfText *pLineOfText;
160 struct LineOfText *pLineOfTextPrev;
161
162 /* Allocate memory for a struct and a line of text */
163 pLineOfText = (struct LineOfText *)malloc(sizeof(struct LineOfText) * 1);
164 pLine = ( char *)malloc(sizeof( char ) * Count);
165 /* Save the pointer to previous structure and point to current structure */
166 pLineOfTextPrev = pLineOfTextCursor;
167 pLineOfTextCursor = pLineOfText;
168 /* Set each field in the current structure */
169 pLineOfTextCursor->Length = Count;
170 pLineOfTextCursor->pLine = pLine;
171 pLineOfTextCursor->pLineOfTextNext = NULL;
172 /* Copy buffer to line */
173 for (i = 0; i < Count; i++)
174 {
175 *pLine = *pBuffer;
176 pLine++;
177 pBuffer++;
178 }
179 /* Link previous structure to current structure */
180 if (pLineOfTextPrev != NULL)
181 { /* If prev is null, then this is the first, and there is no prev */
182 pLineOfTextPrev->pLineOfTextNext = pLineOfTextCursor;
183 }
184 return pLineOfTextCursor;
185 }
186
187 /***********************************************************
188 * Show text *
189 ************************************************************/
190
191 void ShowText(struct LineOfText *pLineOfTextHead)
192 {
193 int LineNumber;
194
195 struct LineOfText *pLineOfTextCursor;
196
197 LineNumber = 0;
198 pLineOfTextCursor = pLineOfTextHead;
199 while (pLineOfTextCursor != NULL)
200 { /* Step through each structure and call PutLine */
201 LineNumber++;
202 printf("%3d ", LineNumber);
203 PutLine(pLineOfTextCursor->Length, pLineOfTextCursor->pLine);
204 pLineOfTextCursor = pLineOfTextCursor->pLineOfTextNext;
205 }
206 }
207
208 /***********************************************************
209 * Put a line of text *
210 ************************************************************/
211
212 void PutLine(int Length, char *pChar)
213 {
214 int i;
215
216 for (i = 0; i < Length; i++)
217 { /* Step through the characters,putting each one */
218 putchar(*pChar);
219 pChar++;
220 }
221 }
222
223 /***********************************************************
224 * Free memory allocated to structures and lines *
225 ************************************************************/
226
227 void FreeLineOfTextMemory(struct LineOfText **pLineOfTextHead)
228 {
229 struct LineOfText *pLineOfTextCursor;
230 struct LineOfText *pLineOfTextNext;
231
232 pLineOfTextCursor = *pLineOfTextHead;
233 while (pLineOfTextCursor != NULL)
234 { /* Step through the structures, freeing pLine first, then the structure */
235 pLineOfTextNext = pLineOfTextCursor->pLineOfTextNext;
236 free(pLineOfTextCursor->pLine);
237 free(pLineOfTextCursor);
238 pLineOfTextCursor = pLineOfTextNext;
239 }
240 *pLineOfTextHead = NULL;
241 }
242
243 /***********************************************************
244 * Crash the program *
245 ************************************************************/
246
247 void Crash(void)
248 {
249 int x;
250 int y;
251
252 printf("The program has crashed!\n");
253 x = 0;
254 y = 1;
255 y = y/x;
256 }
Top
|
|