6.8 Linked Lists and Structures

6.8 Linked Lists and Structures

Study areas:

• Pointers.   Hanly & Koffman p280, p283, p678. Kernighan Chapter 5 page 93. Harbison page 119. Oualline Chapter 13 & 17.
• Structures.   Hanly & Koffman Chapter 11, page 539. Kernighan Chapter 6 page 127. Oualline page 173 & Chapter 17.
• Linked Lists.   Hanly & Koffman Chapter 14, page 677. Kernighan Chapter 6.5 page 139. Harbison p119-123. Oualline page 283.
• Memory Allocation.   malloc() & free(). Hanly & Koffman Section 14.2, page 682. Kernighan page 167. Harbison Chapter 16 Storage Allocation. Oualline Page 281.

Set up a double linked list with forward and backward pointers with dynamically allocated structures. The structure should have 3 elements. A character, a forward link, and a backwards link.

The program, without comments was, for me 125 lines.

At the start of your program print out:

• Your name
• CIS265 Louis Taber
• Lab: 6.8: Linked Lists and Structures
• A blank line

Then it needs to:

• Read the standard input. If the character is a 'F' dump the list in the forward direction to the standard output. And set the delete flag to forward. (its should be initialized to forward as well.)
• If the character is a 'B' dump the list in the backwards direction. Set the delete flag to backwards.
• If you get an ASCII digit value search down the list in the direction specified by the delete flag and remove that entry. For example, if you "get" a "5", remove the fifth entry from the list. For zero do nothing. If the list is too short do nothing.
• For 'X' and 'Q' or and End-of-File, print the total number of characters read and then exit the program.
• For a new-line print out the number of entries on the linked list.
• For all lower case characters place them into the linked list in character order. If the character is already on the list, put it in anyway.
• You are welcome and encouraged to add other uppercase letters to aid yourself in debugging your program.

For the following input:

abcdzyxw
F4B4FQ

your program should print:

Your name
CIS265  Louis Taber
Lab: 6.8: Linked Lists and Structures

8
abcdwxyz
zyxwcba
abcxyz
15

Hints:

• free each structure deleted.

• struct letter    char lett;
                    struct letter *forward;
                    struct letter *backward; ;
     

Test your program with the following sample data set.

8888B8888F   
qwertyuiopasdfghjklzxcvbnmFB
2222222222222F111111111111F1
qwertyuiopasdfghjklzxcvbnmFB
qwertyuiopasdfghjklzxcvbnmFB
X

It is available by anonymous FTP at
ftp://lt.tucson.az.us/pub/c/link.dat.

Turn in a copy of your program and its output when used with the above test data marked with:

• Your name
• TABER CIS265
• Lab 6.8: Linked Lists and Structures
• The compiler and OS that you used.

6.8 Linked Lists and Structures