[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [CSci202] / 11q
[Text Version] [Syllabus] [Schedule] [Glossary] [Resources] [Grading] [Contact] [Question] [Search ]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Labs: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10]
Sun May 8 17:03:09 PDT 2011

# CS202 session 11 -- linked data structures

## Previous -- Algorithms + Sorting and Searching

[ 10.html ]

## Preparation

Study Chapter 12 and do Review Questions.

Here [ list1.cpp ] is the example at the start of the chapter.

## Introduction to linked lists on Wikipedia

[ Linked_list ]

## Stacks and queues on Wikipedia

[ Stack_(data_structure) ] [ Queue_(data_structure) ]

## Due in

Hand in one even question+answer at the start of class.

Perfect projects can earn a 5 point bonus if handed in at the start of this class.

## Class Work

### Exercise using list iterators

[ tlist.cpp ]

### Demo

[ 13frame.html ]

### Example of simple linked list queue

[ LinkedQueue.cpp ] [ LinkedQueue.h ] [ testLinkedQueue.cpp ]

### You need to think clearly about linked data lists

I had some real problems with the above program because I forgot that when you move or erase an item in the list other iterators that point to the moved or erased node become invalid. They stay attached to the old position in RAM, after the node has moved...

SImilarly inserting an item before the first item does not update iterators... I had a begin iterator that ended up attached to the 4th item, not the 1st!

## Next -- Overloaded operators in Chapter 14

[ 12.html ]

Next project due next class. Quiz on Chapter 10,11,12, algorithms, and P2 in next class.

## Do not study chapter 13 until later

Arrays, vectors, lists, stacks, and queues are all Containers in the Standard Library(STL). It has other Containers as well: sets, maps, priority_queues, and so on. We will study these ate the end of the course using Chapter 13 and the first part of chpter 20. You can use my notes [ stl.html ] if you wish. Some of these are mentioned in laboratories, exercises, but not in quizzes. They are covered in detail in CSE330 Data Structures.

# Glossary

1. accessor::=`A Function that accesses information in an object with out changing the object in any visible way". In C++ this is called a "const function". In the UML it is called a query.
2. Algorithm::=A precise description of a series of steps to attain a goal, [ Algorithm ] (Wikipedia).
3. class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
4. constructor::="A Function in a class that creates new objects in the class".
5. Data_Structure::=A small data base.
6. destructor::=`A Function that is called when an object is destroyed".
7. Function::programming=A selfcontained and named piece of program that knows how to do something.
8. Gnu::="Gnu's Not Unix", a long running open source project that supplies a very popular and free C++ compiler.
9. mutator::="A Function that changes an object".
10. object::="A little bit of knowledge -- some data and some know how". An object is instance of a class.
11. objects::=plural of object.
12. OOP::="Object-Oriented Programming", Current paradigm for programming.
13. Semantics::=Rules determining the meaning of correct statements in a language.
14. SP::="Structured Programming", a previous paradigm for programming.
15. STL::="The standard C++ library of classes and functions" -- also called the "Standard Template Library" because many of the classes and functions will work with any kind of data.
16. Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
17. Q::software="A program I wrote to make software easier to develop",
18. TBA::="To Be Announced", something I should do.
19. TBD::="To Be Done", something you have to do.
20. UML::="Unified Modeling Language".
21. void::C++Keyword="Indicates a function that has no return".