CISC 2200 Lecture Notes - Lecture 2: Linear Search

0 views2 pages
user avatar
Published on 4 Jul 2020
School
Fordham University
Department
Computer and Information Sciences
Course
CISC 2200
Professor
Unsorted List: Implementation
Different ways of storing items in memory affect the performance of list operators
Array Based: Elements are store sequentially in a contiguous chunk of memory
Link List_based: Elements are stored in separate nodes, connected by pointers
Using an array-based implementation for now.
Link List benefit is that there is no limit on size, you can just keep adding nodes.
Implementation: Observers
GetItem requires a linear search through the list
Use bool &found reference parameter to indicate success to the user
Return a copy of the found item.
Implementation: Transformer
PutItem: Insert item at the end of the list, increment list
DeleteItem: Linear search to find item, but how to remove it?
If the item is at the end of the list, just reduce the length of the list by one
But what about if it’s at the beginning?
Implementation: Iterators
The field currentPos indicates the current position of iteration in the LIST
Example
GetNextItem
ItemType UnsortedType::GetNextItem()
{
// Pre: ResetList was called to initialized iteration
currentPos++;
Return info[currentPos];
}
WE WILL BE USING POINTERS A LOT!!!
C++ Review Pointers
Pointer is a type of data type that store memory addresses
C++ has a pointer for each data type
There are even pointers for pointers
Declaration
type* pointer_name;
//or
Type *pointer_name;
Example
Int **p; //pointer to pointer
Address Operator&
Example
Int a = 100;
Cout << a; //100
Cout <<&a; //1024(the hex decimal of the address)
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in