(1) Help you to learn/review advanced C programming (pointer manipulation and dynamic memory management)
(2) Help you with Assignment 2
(3) Help you learn more about ADTs in C -- especially about the "iterator" concept used often with collection ADTs
Hanson, Chapter 7
Continue studying the series of List ADTs from last precept
See example: fnpointer.c
Common use: implement a callback
The implementation: list.c (continued)
Trace List_map
Note: If items were themselves in heap, would need to free them -- typically using List_map
Assessment
+ Simple, symmetric
- Would be good to have a more flexible traversal mechanism
E.g. Ability to stop traversal when sought item is found
E.g. Ability to apply a different function to each item, depending on the qualities of each item
- Would be good to have a way to insert and delete internal nodes
After all, that's the big advantage of a linked list over an array
Note: Very different from Hanson's List ADT
See list.h, list.c, testlist.c
Describe what it does
List_get function
Allows indexed access to any item of a List object
Starts at beginning of list, and traverses forward appropriate number of times until it finds the specified item
List_insertNext, List_insertPrev, List_remove functions allow similar indexed access/update
Look at code
list.h: the List interface
[Describe getItem function declaration]
list.c: the List implementation
[Describe List_get function definition]
testlist.c: the List user
Informally trace typical use of List_get function -- in a loop
Assessment
+ Simple
- Very inefficient if List object contains many items
See list.h, list.c, testlist.c
Describe what it does
Each List object keeps track of a selected item
List ADT provides functions to:
Select the first/last item
Select the next/previous item
Get the selected item
Insert before/after the selected item
Remove, and select the next/previous item
Look at code
list.h: the List interface
Describe "select..." function declarations
testlist.c: the List user
Informally trace typical use of select... functions -- in a loop
list.c: the List implementation
Note: new field in List implementation: psSelectedNode
Describe "select..." function definitions
Assessment
+ More efficient than indexed access
- Can have only one iteration in progress at any given time
Problem: nested loops
(Problem: multithreaded programs)
See list.h, list.c, testlist.c
Describe what it does
Uses "iterator"
Iterator ADT: a separate ADT, associated with a collection (List) ADT
An Iterator object allows traversal of its collection (List) object
Can have multiple Iterator objects for any given collection (List) object
Look at code
list.h: the List interface and the ListIter interface
Describe ListIter function declarations
testlist.c: the List user
Informally trace typical use of ListIter functions -- in a loop
list.c: the List implementation and the ListIter implementation
Note: List structure no longer contains psSelectedNode field
Note: ListIter structure
Describe ListIter function definitions
Assessment
+ Can have multiple iterations in progress simultaneously
Copyright © 2002 by Robert M. Dondero, Jr.