Slides

S1: Data Structures to Organize Collections: An Introduction

Transition: C++ class -- > data-structures
- Analogy: C++ class = Integrated circuits (packaging )
- data-structures = Components (counter, micro-processor, ...)
Goals
- (1) Understand the idea of Data-Structures
  - Motivation, Definition, Specification
- (2) Collection Hierarchy
  - Linear ad Nonlinear data structures
- (2) Learn A Specific Data-Structure (SeqList)
  - Motivation, Uses, functional specification, Properties
  - Implementation in C++, Manipulation Example
- Leave performance issues (Ch#4.3) for 3322
- Textbook Reading
- 4.1, 4.2 Collections - linear and nonlinear
- 1.4 SeqList ADT
- 4.5 SeqList ADT: C++ Implementation
Recommended Ex. 4.1, 4.2, 4.12, 4.13, 4.14, 4.15

S2: Why Study Data-Structures?

Program = Data Structures + Algorithms
- Frequent Step = TAKE this and DO that
- DO - uses algorithms - change program states (data)
- TAKE - uses data-structures - organize data for fast search
Example - Creation of Huffman Codes - 3 steps
- 1. Create a collection of weighted trees : one tree/ character
- 2. Take two trees with lowest weights, and Merge them into one
- 3. Repeat step 2 till only one weighted tree is left
- 4. Traverse final tree to extract codes
  Q?: Identify TAKE and DO in Huffman Code Ex.
- TAKE vs. DO (Human Experience vs. Programming)
- Book reading = TAKE(Catch-22), DO (read Catch-22)
  - Which is more work - TAKE or DO?
  - Effect of scale - home vs. library?
- Ex. DBMS: TAKE = long search, DO = little work
  Q?: Which is more work in Huffman Code Ex.

S3: Data-Structures : Motivation, Definition

Why data-structures? Why not spread all the data on a desk-top?
- Efficiency and Convenience of access, use, and maintenance
Def.: Methods of organizing large collection of data
- To support operations
- To reflect relationship among data
- Ex. Data Organization from Real-Life:
- David letterman's top ten
- Post Office - customers take a number
- Restaurant - dishes are stacked for Buffet
- University - Administrators organized as hierarchy
- Dictionary, Library - Index on name organizes
- Road Map - Graph
- Bus Schedule
- Pyramid made of stone-blocks
- Hospital Emergency Room - patients

S4: Specifying Data-Structures

Q? What is a Queue?
- a check-out line at grocery store
- People waiting for elevators on different floors
- "Take a number" for at Target customer center
Specification should
- be implementation independent!
- determine what is a "queue" and what is not a "queue"
Specification Components
- Functional: What can be done with an instance?
  - e.g. Operations, the data structure supports
  - and their Properties (e.g. First Come First Served)
- Performance : How much will it cost?
  - e.g. Worst-case time, Avg.-case memory for operations
- CS 3321 FOCUS:
- Performance Specs - Left for 3322
- Functional Specs of Data Structures
  - using Abstract data types and C++ classes
  - specify data elements and operations
  - For operations - name, number/types of arguments, results, properties

S5: Functional Specification: (What not How)

Functional Spec.: Q? What functional behavior a data structure
- must exhibit to be called a Queue?
- Helps in understanding general properties
- Helps in data abstraction, information hiding
Implementation ("How" the goals can be achieved? )
- Multiple implementations are possible!
  - Ex. array-based and linked-list based
  - May differ in performance
  - However each should be "correct", i.e. satisfy functional specs
- Example: "What" is a Queue data structure?
- Following operations must be supported :
  - is_empty() - returns true if queue is empty
  - insert/enqueue(...) - insert a new element at the tail-end
  - retrieve/front() - returns the front element of queue
  - remove() - removes the front element
- Implementations:
- a check-out line at grocery store
- "Take a number" for at Target customer center

S6: Classifying Data-Structures for Collections

Analogy to Chemistry (Periodic Chart of Elements)
- Classification Diagram of Data-Structures
- Properties can be deduced
Classification criteria: Collections in Smalltalk
- Q? Can items be ordered/sorted? Is there a first item? a last item?
  - Yes: Linear collection
  - No: Non-Linear collection
- Ex. Categorize real-life examples into above two classes.
- Classifying Linear Collections
- Q? Should all items be directly accessible?
  - Yes: Direct Access OR Indexed collection
  - No: Sequential Access collection
- Classifying Non-Linear Collections
- Q? Can items be partially ordered into a hierarchy?
  - Yes: Hierarchical collection
  - No: Group collection
- Summary in Fig. 4.1 (pp 142) or cover page

S7: Sequential-List Collections (Section 4.1)

List Collection
- Data: homogeneous collection of objects
- Operations: insert, delete, size, ...
- Property: at most first and last items are directly accessible.
  - List is traversed to access individual items
- Stack Collection
- Data: homogeneous collection w/ access to top item only
- Operations: push, pop, top, empty, ...
- Property: last in first out (LIFO)
Queue Collection
- Data: homogeneous collection w/ access to front and rear of list
- Operations: add-to-rear, remove-from-front, ...
- Property: first in first out (FIFO)
Priority Queue Collection
- Data: homogeneous collection of < item, priority >
- Op.: add(item, priority), remove-highest-priority(item), ...

S8: Sequential Access Collections

Ex. Classify the following into one of {non-linear collections,
- list, stack, queue, and priority queue}
- David letterman's top ten
- Post Office - customers take a number
- Casino - Deck of card used by a dealer
- A typical electrical circuit
- a check-out line at grocery store
- Bus Schedule
- Set of colors in a painting
- Hospital Emergency Room - collection of patients
- People waiting for elevators on different floors

S9: Sequential-Lists ADT

Abstract Specification in Ch# 1.4 (pp 16-17)
- Data: size (number of items), a list of data items
- Operations: insert, delete, empty, ...
C++ Specification in Ch# 4.5 (pp 168)
class SeqList {
private: int size;
DataType listitem[MaxListSize]; // array implementation
public: SeqList(void); // constructor
int ListSize(void) const;
int ListEmpty(void) const;
int Find (DataType& item) const;
DataType GetData(int position) const;
// modifiers
void Insert(const DataType& item);
void Delete(const DataType& item);
DataType DeleteFront(void);
void ClearList(void);
}
Linked list based implmntn. in Ch#9.6 (pp 432-6)

S10: Exercises to Understand List

Ex. Find output from cout statements.
void PrintList(const SeqList& L) {
int i, length = L.listSize();
for (i=0; i < length; i++) cout << L.GetData(i) << " ";
cout << endl;
}

SeqList L; int i;
for (i=0; i < =5; i++) L.insert( 5*i ); PrintList(L); // *A*
L.insert(30); L.Delete(25); PrintList(L); // *B*
if (L.Find(5)) cout "Have 5 in list L" << endl; // *C*
while (!L.Empty()) cout << L.DeleteFront() << endl; // *D*
Write a function to find minimum integer in a list of integers.
You can only use public operations.
This function is not a member or friend-of the class queue.

S11: Implementation of Find( DataType& item )

See code and diagram from pp 172
Input: Key (DataType& item)
Output: True if "item" in list, False otherwise
- Parameter output: "item" = member if found.
Precondition:
- listitem[0] ... listitem[size - 1] are full
- listitem[size] ... listitem[MaxListSize] are empty
Postcondition: No change in SeqList
Process: Match "item" with each member of list
- Assume == operator defined on DataType to match keys
  int SeqList::Find(DataType& item) const {
  int i = 0; if (ListEmpty()) return 0;
  while (i < size) && !(item == listitem[i]) i++;
  if (i < size) { item = listitem[i]; return 1; }
  else return 0; // false
  }

S12: Implementation of Insert(const DataType& item)

See code and diagram from pp 170
Input: Data-item to be inserted
Output: none.
Precondition:
- listitem[0] ... listitem[size - 1] are full
- listitem[size] ... listitem[MaxListSize] are empty
Postcondition:
- SeqList has one more item, i.e. newsize = oldsize + 1
- listitem[0] ... listitem[newsize - 1] are full
- listitem[newsize] ... listitem[MaxListSize] are empty
Process: Put item in first empty spot in array, increment size

void SeqList::Insert(DataType& item) {
if (size+1 > MaxListSize) { /* error message */ }
else { listitem[size] = item; size++ ; }
}
Q? Why not return error flag as value of function?

S13: Implementation of Delete()

See code and diagram from pp 171
Input: Key (DataType& item)
Output: None.
Precondition:
- listitem[0] ... listitem[size - 1] are full
- listitem[size] ... listitem[MaxListSize] are empty
Postcondition:
- List has one less item, newsize = oldsize - 1
- listitem[0] ... listitem[oldsize - 2] are full
- listitem[oldsize - 1] ... listitem[MaxListSize] are empty
Process:
- 1. Search for the data-item, say it is listitem[index]
- 2. Then remove it from list
- 3. Remove holes (shift if needed to satisfy postcondition)
  - (index < size) = > put listitem[index+1] into listitem[index], ...

S14: Exercise on Different Implementations of "int Delete( ... )"

Ex. Find the correct code for Step 3 (shifting) of Delete()
- Ignore return statements to be consistent with the book.
  int i ; // code segment 1
  if (index < 0 || index > = size) return 0;
  else {
  for (i = index-1; i > =0; i--) {listitem[i+1] = listitem[i];}
  size--; return 1;
  }
  
  int i; // code segment 2
  if (index < 0 || index > = size) return 0;
  else {
  for (i = index+1; i < size; i++) {listitem[i-1] = listitem[i];}
  size--; return 1;
  }
  
  int i; // code segment 3
  if (index < 0 || index > = size) return 0;
  else {
  for (i = size-1; i != index; i--) {listitem[i-1] = listitem[i];}
  size--; return 1;
  }
  
  int i; // code segment 4
  if (index < 0 || index > = size) return 0;
  else { listitem[index] = listitem[size - 1]; size--; return 1; }