13_Midterm_Review
## Midterm Review Overview
- **Due Date:** Tonight, no late submissions allowed.
- **Assignments:** Project 4
---
## Goals of the Review
1. Explore the midterm structure.
2. Examine midterm examples.
3. Provide tips for preparation.
---
## Midterm Details
- **Date & Time:** March 12th, 1:00 PM - 2:15 PM
- **Format:** Written test in the classroom.
- **Restrictions:** No hats or sunglasses allowed.
---
## Midterm Structure
- **Topics and Points**
- **Abstract Data Types & Data Structures:** 6 points
- **Analysis:** 12 points
- **Implementation:** 12 points
- **Programming:** 30 points
- **Total:** 60 points
---
## Abstract Data Types & Data Structures
- **Key Questions to Address:**
- Main purpose of Abstract Data Types (ADTs).
- Differences between an ADT and a Data Structure.
- C++ tools for implementing data structures and their support for ADTs.
- Two approaches to storage in Data Structure implementations and their differences.
---
## Analysis Section
- **Compare and Contrast Requirements:**
- Function from a data structure using each storage approach (similarities/differences).
- Function from two data structures using the same storage approach (similarities/differences).
- Note: Code examples will not be provided.
---
## Example Analysis
- **Task:** Compare and contrast the `Bag` and `toVector` functions for each storage approach.
---
## Analysis of `toVector`
```cpp
// Array Implementation
template
vector ArrayBag::toVector() const {
vector bagContents;
for (int i = 0; i < itemCount; i++) {
bagContents.push_back(items[i]);
}
return bagContents;
}
// Linked Implementation
template
vector LinkedBag::toVector() const {
vector bagContents;
Node* curPtr = headPtr;
for (int i = 0; i < itemCount && curPtr != nullptr; i++) {
bagContents.push_back(curPtr->getItem());
curPtr = curPtr->getNext();
}
return bagContents;
}
```
- **Comparison:**
- The array implementation uses index iteration from `0` to `itemCount - 1`.
- The linked implementation uses `getNext()` to traverse nodes in the chain.
---
## Function Comparison Example
- **Task:** Compare and contrast `ArrayBag::add()` and `ArrayList::insert()` functions.
---
## Functions Analysis
```cpp
// ArrayBag add
template
bool ArrayBag::add(const ItemType& newEntry) {
bool hasRoom = itemCount < maxItems;
if(hasRoom) {
items[itemCount] = newEntry;
itemCount++;
}
return hasRoom;
}
// ArrayList insert
template
bool ArrayList::insert(int newPos, const ItemType& newEntry) {
bool canInsert = itemCount < maxItems && newPos >= 1 && newPos